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…