From: Ruby Quiz <james@...>
Date: 2007-02-01T21:58:04+09:00
Subject: [SUMMARY] Counting Toothpicks (#111)

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[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...