Forum: Ruby Counting Toothpicks (#111)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
James G. (Guest)
on 2007-02-01 14:58
(Received via mailing list)
I think this was a pretty challenging quiz.  I've played around with
many of the
solutions and noted that some become pretty sluggish with large numbers
and at
least one still seems to get some incorrect answers.  That's not do to
bad
coding mind you, it's just a challenging problem to get right.

The solutions are very interesting browsing material though, despite any
problems.  I saw an RSpec specification, clever math, metaprogramming,
and even
a little golf.  Do take the time to search through them.  It's worth it.

I've chosen to talk a little about Frank F.'s entry below.  It was
significantly smaller than most entries and easy enough to grasp the
inner
workings of.  There were faster solutions though.

Let's get to the code:

  # Number to calculate with toothpicks
  class ToothNumber
    attr_reader :value, :num, :pic
    def initialize value, num=value, pic=("|"*num)
      @value, @num, @pic = value, num, pic
    end

    def + x; operation(:+, 2, "+", x); end

    def * x; operation(:*, 2, "x", x); end

    def <=> x; @num <=> x.num; end

    def to_s; "#{@pic} = #{@value} (#{@num} Toothpicks)"; end

    private
    # create new ToothNumber using an operation
    def operation meth, n_operator_sticks, operator, x
      ToothNumber.new @value.send(meth, x.value),
                      @num + x.num + n_operator_sticks,
                      @pic + operator + x.pic
    end
  end

  # ...

This class is a representation of a toothpick number.  These numbers
support the
standard operators, so you can work with them much like you do Ruby's
native
numbers.  Here's an IRb session showing such operations:

  >> two = ToothNumber.new(2)
  => #<ToothNumber:0x10a3588 @pic="||", @value=2, @num=2>
  >> three = ToothNumber.new(3)
  => #<ToothNumber:0x109c2ec @pic="|||", @value=3, @num=3>
  >> six = two * three
  => #<ToothNumber:0x10935d4 @pic="||x|||", @value=6, @num=7>
  >> eight = six + two
  => #<ToothNumber:0x108e430 @pic="||x|||+||", @value=8, @num=11>
  >> eight.to_s
  => "||x|||+|| = 8 (11 Toothpicks)"

Glancing back at the code, the instance variable @value holds the actual
number
value, @num confusingly holds the toothpick count, and @pic holds the
actual
toothpick pattern in String form.  Note that ToothNumber objects compare
themselves using @num, so lower counts sort first.  Beyond that, the
only
semi-tricky method is operation().  If you break it down though you will
see
that it just forwards the math to Ruby and manually builds the new count
and
String.

To see how these are put to use, we need another chunk of code:

  # ...

  # contains minimal multiplication-only toothpick for each number
  $tooths = Hash.new {|h,n| h[n] = tooth_mul n}
  $tooths_add = Hash.new {|h,n| h[n] = toothpick n}

  # should return the minimal toothpick-number
  # should only use multiplication
  def tooth_mul n
    ways = [ToothNumber.new(n)] +
    (2..(Math.sqrt(n).to_i)).map{|i|
      n % i == 0 ? ($tooths[i] * $tooths[n/i]) : nil
    }.compact
    ways.min
  end

  # returns minimal toothpick-number with multiplication and addition
  def toothpick n
    ways = [$tooths[n]] +
           (1..(n/2)).map{|i| $tooths[n-i] + $tooths_add[i] }
    ways.min
  end

  # ...

Start with the $tooths Hash.  You can see that it delegates Hash
initialization
to tooth_mul(), which is just a factor finder.  It walks from two to the
square
root of the number finding all combinations that multiply to the
original
number.  It then uses min() to pull the result with the lowest toothpick
count.

Now remember, we're only talking about multiplication at this point.
$tooths[10] is going to find the two and five factors and return that as
a
result, since they have a lower count than the ten factor itself.
However,
$tooths[13] is just going to return thirteen, since it is a prime number
and
addition is needed to get a lower count.

That brings us to the other Hash and method, which layer addition on top
of
these factors.  The work here is basically the same:  walk the lower
numbers
building up all the possible sums equal to the passed integer.  Because
this
walk indexes into the $tooths factor Hash though, the results will
actually make
use of multiplication and division.  That's the answer we are after and
again
the low count is pulled with min().

Here's the final bit of code that turns it into a solution:

  # ...

  for i in 1..ARGV[0].to_i
    puts $tooths_add[i]
  end

This just walks a count from one to the passed integer printing
toothpick
counts.  Note that building the bigger numbers isn't generally too much
work
since the factor cache grows as we count up.

My thanks to all who gave this quiz a go and to Gavin for pointing me to
the
problem in the first place.

Tomorrow we will try the other 2006 ACM problem I liked...
Jon Egil S. (Guest)
on 2007-02-01 21:17
(Received via mailing list)
Greetings

I've ran into some performance trouble using define_method.

Benchmarking gives:

With    define_method:  1 second
Without define_method: 21 seconds


Question:

Is this to be expected, or am I doing something totally or partially
wrong?

Hints, comments, links, everything is appreciated.


All the best
Jon Egil S.




The benchmark code is as follows:


----------------------

class Staticperson
  def initialize(personalia)
    @firstname = personalia[:firstname]
    @surname = personalia[:surname]
    @country = personalia[:country]
  end

  attr_reader :firstname, :surname, :country
end


class Dynamicperson
  def initialize(personalia)
    @personalia = personalia
    @personalia .each_key do |k|
      self.class.send(:define_method, k) { @personalia[k] }
    end
  end
end


peter = {:firstname => "Peter",
         :surname => "Pan",
   :country => "Neverland"}



COUNT = 100_000

require 'benchmark'

Benchmark.bmbm do |test|
  test.report("Static: ") do
    COUNT.times do
      s_peter = Staticperson.new(peter)
      s_peter.firstname
      s_peter.surname
      s_peter.country
    end
  end
  test.report("Dynamic: ") do
    COUNT.times do
      d_peter = Dynamicperson.new(peter)
      d_peter.firstname
      d_peter.surname
      d_peter.country
    end
  end
end

----------------------

And the full results goes like this:

Rehearsal ---------------------------------------------
Static:     0.984000   0.047000   1.031000 (  1.047000)
Dynamic:   21.766000   0.094000  21.860000 ( 21.906000)
----------------------------------- total: 22.891000sec

                user     system      total        real
Static:     1.031000   0.000000   1.031000 (  1.031000)
Dynamic:   21.375000   0.109000  21.484000 ( 21.500000)



(Sorry for the naming, I know it's not _static_ per se, but it was a
useful label at the time :-) )
unknown (Guest)
on 2007-02-01 21:44
(Received via mailing list)
On Fri, 2 Feb 2007, Jon Egil S. wrote:

>
> Question:
>
> Is this to be expected, or am I doing something totally or partially
> wrong?


it's not so much the fact that you are using define_method, which is a
bit
slow, but the fact that one Staticperson you define the methods on once
while
in Dynamicperson you define the methods each and every time even though
the
def simply clobbers the existing one.  if you want to compare apples
with
apples then:

     harp:~ > ruby a.rb
     Rehearsal ---------------------------------------------
     Static:     0.630000   0.000000   0.630000 (  0.622125)
     Dynamic:    1.080000   0.000000   1.080000 (  1.573303)
     ------------------------------------ total: 1.710000sec

     user     system      total        real
     Static:     0.600000   0.000000   0.600000 (  1.086655)
     Dynamic:    1.050000   0.000000   1.050000 (  1.179166)



     harp:~ > cat a.rb
     class Staticperson
       def initialize(personalia)
         @firstname = personalia[:firstname]
         @surname = personalia[:surname]
         @country = personalia[:country]
       end
       attr_reader :firstname, :surname, :country
     end

     class Dynamicperson
       def initialize personalia
         @personalia = personalia
       end
       [:firstname, :surname, :country].each do |k|
         define_method(k){ @personalia[k] }
       end
     end

     peter = {:firstname => "Peter",
              :surname => "Pan",
              :country => "Neverland"}

     COUNT = 100_000

     require 'benchmark'

     Benchmark.bmbm do |test|
      test.report("Static: ") do
        COUNT.times do
          s_peter = Staticperson.new(peter)
          s_peter.firstname
          s_peter.surname
          s_peter.country
        end
      end
      test.report("Dynamic: ") do
        COUNT.times do
          d_peter = Dynamicperson.new(peter)
          d_peter.firstname
          d_peter.surname
          d_peter.country
        end
      end
     end



regards.

-a
Morton G. (Guest)
on 2007-02-02 05:01
(Received via mailing list)
On Feb 1, 2007, at 7:58 AM, Ruby Q. wrote:

> That brings us to the other Hash and method, which layer addition
> on top of
> these factors.  The work here is basically the same:  walk the
> lower numbers
> building up all the possible sums equal to the passed integer.
> Because this
> walk indexes into the $tooths factor Hash though, the results will
> actually make
> use of multiplication and division.  That's the answer we are after
> and again

Shouldn't that "multiplication and division" be "multiplication and
addition"?

> the low count is pulled with min().

Regards, Morton
Jon Egil S. (Guest)
on 2007-02-02 11:32
(Received via mailing list)
> it's not so much the fact that you are using define_method, which is a bit
> slow, but the fact that one Staticperson you define the methods on once while
> in Dynamicperson you define the methods each and every time even though the
> def simply clobbers the existing one.

But of course, thank you.

To keep the dynamicity of Dynamicperson, which is the functionality I'm
trying to achieve, I made the define_method conditional:

class Dynamicperson
  def initialize(personalia)
    @personalia = personalia
    @personalia .each_key do |k|
      self.class.send(:define_method, k) { @personalia[k] } unless
self.respond_to?(k)
    end
  end
end

Still, it would be better to do this only once, on class level rather
than
instance level

class Dynamicperson_class
  def initialize(personalia)
    @personalia = personalia
  end

  def Dynamicperson_class.define_methods(personalia)
    personalia.each_key do |k|
      send(:define_method, k) { @personalia[k] }
    end
  end
end


Followed by _one_ call of

peter = {:firstname => "Peter",
         :surname => "Pan",
         :country => "Neverland"}

Dynamicperson_class.define_methods(peter)


Then benchmarking:

------------------------------------------------------------------------
Static:                                1.772000   0.050000   1.822000 (
1.873000)
Dynamic pr. instance:                 27.260000   1.322000  28.582000 (
28.861000)
Dynamic pr. instance conditionally:    3.284000   0.060000   3.344000 (
3.375000)
Dynamic pr. class:                     2.614000   0.040000   2.654000 (
2.944000)
-------------------------------------------------------------- total:
36.402000sec


Thank's for pointing me in the right direction Ara.

JE
Robert D. (Guest)
on 2007-02-02 11:57
(Received via mailing list)
On 2/2/07, Jon Egil S. <removed_email_address@domain.invalid> wrote:
>
>
> <snip>


If you are doing this for fun, learning research, than  that's just
great if
you need this stuff (and even for fun, learning and research ;) you
might
want to have a look at Facet http://facets.rubyforge.org/doc.html
especially OpenStruct and OpenObject.

Thomas if you are reading this and you are not too busy, why is
OpenStruct
in Core and OpenObject in More? (is the former used much more often?)
Just
curious ;)

Cheers
Robert
James G. (Guest)
on 2007-02-02 15:09
(Received via mailing list)
On Feb 1, 2007, at 9:01 PM, Morton G. wrote:

>> use of multiplication and division.  That's the answer we are
>> after and again
>
> Shouldn't that "multiplication and division" be "multiplication and
> addition"?

Yes it should.  Thanks for pointing it out.

James Edward G. II
Chris C. (Guest)
on 2007-02-02 18:56
(Received via mailing list)
On 2/2/07, Robert D. <removed_email_address@domain.invalid> wrote:
>
> --
> We have not succeeded in answering all of our questions.
> In fact, in some ways, we are more confused than ever.
> But we feel we are confused on a higher level and about more important
> things.
> -Anonymous
>
>

Hi Robert,
It is because OpenStruct is in the ruby standard library, and the
facets OpenStruct is just a set of extensions to it.  OpenObject is a
class made by Facets
Robert D. (Guest)
on 2007-02-02 21:56
(Received via mailing list)
On 2/2/07, Chris C. <removed_email_address@domain.invalid> wrote:
> > you need this stuff (and even for fun, learning and research ;) you
> > Cheers
> > -Anonymous
> >
> >
>
> Hi Robert,
> It is because OpenStruct is in the ruby standard library,


Can you believe that! One never stops learning !!!
Sorry to correct you it is even in the Core. I thought I knew the Core
API
BACK TO CLASS (and that is not Class ;)

and the
> facets OpenStruct is just a set of extensions to it.  OpenObject is a
> class made by Facets


Makes perfect sense, thx for the enlightment ;)

--
> Chris C.
> concentrationstudios.com
> brynmawrcs.com
>
>
Robert
James G. (Guest)
on 2007-02-02 22:06
(Received via mailing list)
On Feb 2, 2007, at 1:56 PM, Robert D. wrote:

> On 2/2/07, Chris C. <removed_email_address@domain.invalid> wrote:
>> It is because OpenStruct is in the ruby standard library,
>
>
> Can you believe that! One never stops learning !!!
> Sorry to correct you it is even in the Core.

I'm not sure if I understood you correctly Robert, but just to be
clear OpenStruct is not a part of Ruby's core.  It is a Ruby standard
library.  I'm talking about Ruby here, not Facets.

James Edward G. II
Robert D. (Guest)
on 2007-02-03 10:35
(Received via mailing list)
On 2/2/07, James Edward G. II <removed_email_address@domain.invalid> wrote:
> I'm not sure if I understood you correctly Robert, but just to be
> clear OpenStruct is not a part of Ruby's core.  It is a Ruby standard
> library.  I'm talking about Ruby here, not Facets.
>
> James Edward G. II


Thank you James for confusing me, it is by pure chance that I choose my
new
signature :)

But  I realize that I do not know how to distinguish between Core
and STL.
So far I just looked it up - cheated -
http://www.ruby-doc.org/core/classes/OpenStruct.html
but I recall remotely that having been wrong already.

I did not think that all I have to 'require' is not in the Core. (e.g.
Enumerable was Core for me)

enumerable.rb and ostruct.rb sit in lib/ of course so that boils down to
the
'require' vs. 'not require'
criterion I guess.


Cheers
Robert
James G. (Guest)
on 2007-02-03 21:02
(Received via mailing list)
On Feb 3, 2007, at 2:34 AM, Robert D. wrote:

> But  I realize that I do not know how to distinguish between Core
> and STL.

If you can use it without a require, it's core Ruby.  Array,
Enumerable, and Hash are examples.

If it comes with Ruby (no extra install), but you must require it to
use it, it's a standard library.  OpenStruct, Logger, and WEBrick are
examples.

Hope that helps.

James Edward G. II
unknown (Guest)
on 2007-02-03 21:11
(Received via mailing list)
Hi --

On Sun, 4 Feb 2007, James Edward G. II wrote:

> On Feb 3, 2007, at 2:34 AM, Robert D. wrote:
>
>> But  I realize that I do not know how to distinguish between Core
>> and STL.
>
> If you can use it without a require, it's core Ruby.  Array, Enumerable, and
> Hash are examples.
>
> If it comes with Ruby (no extra install), but you must require it to use it,
> it's a standard library.  OpenStruct, Logger, and WEBrick are examples.

And "extra install" does not include extra installs made necessary by
the dismemberment of Ruby into multiple packages by third parties :-)


David
Robert D. (Guest)
on 2007-02-04 01:42
(Received via mailing list)
On 2/3/07, James Edward G. II <removed_email_address@domain.invalid> wrote:
> use it, it's a standard library.  OpenStruct, Logger, and WEBrick are
> examples.
>
> Hope that helps.


Sure that is the definition I will  adopt from now, I got confused
mostly by
Enumerable which is in the core *and* some of its extensions in the STL.

Thx for clarifying this.


James Edward G. II
>
>
>
>
Robert
This topic is locked and can not be replied to.