[SUMMARY] Counting Toothpicks (#111)

Discussion in 'Ruby' started by Ruby Quiz, Feb 1, 2007.

  1. Ruby Quiz

    Ruby Quiz Guest

    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 Fischer'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 * $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 }
    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
    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...
    Ruby Quiz, Feb 1, 2007
    #1
    1. Advertising

  2. On Feb 1, 2007, at 7:58 AM, Ruby Quiz 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
    Morton Goldberg, Feb 2, 2007
    #2
    1. Advertising

  3. On Feb 1, 2007, at 9:01 PM, Morton Goldberg wrote:

    > On Feb 1, 2007, at 7:58 AM, Ruby Quiz 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"?


    Yes it should. Thanks for pointing it out.

    James Edward Gray II
    James Edward Gray II, Feb 2, 2007
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Josh Close

    smtplib (111, 'Connection refused')

    Josh Close, Sep 17, 2004, in forum: Python
    Replies:
    8
    Views:
    13,127
    Tim Williams
    Sep 17, 2004
  2. Matt Chwastek
    Replies:
    6
    Views:
    505
    Michael Angelo Ravera
    Nov 20, 2006
  3. chen chen

    111

    chen chen, Mar 22, 2007, in forum: XML
    Replies:
    0
    Views:
    594
    chen chen
    Mar 22, 2007
  4. Soe Yan Min
    Replies:
    2
    Views:
    414
    Roedy Green
    Oct 22, 2007
  5. Ruby Quiz

    [QUIZ] Counting Toothpicks (#111)

    Ruby Quiz, Jan 26, 2007, in forum: Ruby
    Replies:
    47
    Views:
    363
    Marcel Ward
    Jan 31, 2007
Loading...

Share This Page