On 26/01/07, Ruby Quiz <james / grayproductions.net> wrote:
> This weeks quiz is to write a program that takes a single command-line argument
> which will be a positive integer.  Your code should build a toothpick expression
> to calculate the number using as few toothpicks as possible.  For example:
>
>         $ruby toothpick.rb 9
>         |||x||| = 9 (8 toothpicks)
>
> Don't forget to count those operators!

Here is my solution.  It is an iterative solution using two caches:
one for "multipicable" toothpick strings (i.e. those that do not
contain any addition signs) and another for "summable" toothpick
strings.

I take the approach that you can multiply as many previous
multiplicable strings together and then add a summable string, knowing
that the result will be valid.

I did start off by preferring shorter toothpick strings (as well as
less toothpicks) but after seeing the talk here decided that
minimising the number of operators (either + or x) is preferable
(again, for equal number of toothpicks).  It turns out this should
favour multiplication over addition anyway.

Arghh, now my favourite coffee shop will have closed for the evening ;)

Thanks James & Gavin and to other participants for the helpful example
expressions.

Marcel

# Marcel Ward   <wardies ^a-t^ gmaildotcom>
# Sunday, 28 January 2007
# Solution for Ruby Quiz number 111 - Counting Toothpicks
#
class Toothpicks
  def initialize
    # Lookups are value indexed arrays that maps to triplets
    # of elements representing:
    # 1. The shortest toothpick string form of the value
    # 2. The number of toothpicks used
    # 3. The number of operators used, i.e. multiply or add
    @lookup_multiplicable = []
    @lookup_summable = []
    @max_cached_value = 0
  end

  def cache_next()
    target = @max_cached_value + 1
    # Find the best multiplicable tootpick expression by trying to
    # multiply together two existing numbers from the multiplicable
    # cache (we only need to search from 2..sqrt(target))
    best_multiplicable = [one() * target, target, 0]
    tpick_op, price_op = multiply()
    x = 2
    while x**2 <= target
      y,remainder = target.divmod(x)
      if remainder == 0
        tpick_x, price_x, ops_x = @lookup_multiplicable[x]
        tpick_y, price_y, ops_y = @lookup_multiplicable[y]
        price = price_x + price_op + price_y
        if (price < best_multiplicable[1]) ||
            (price == best_multiplicable[1] &&
              ops_x + ops_y + 1 < best_multiplicable[2])
          best_multiplicable = [tpick_x + tpick_op + tpick_y, price,
            ops_x + ops_y + 1]
        end
      end
      x += 1
    end

    best_summable = best_multiplicable.dup
    # Now try summing up two existing, cached values to see if this
    # results in a shorter toothpick sum than the multiplicable one.
    tpick_op, price_op = sum()
    x = 1
    y = target - x
    while x <= y
      tpick_x, price_x, ops_x = @lookup_summable[x]
      tpick_y, price_y, ops_y = @lookup_summable[y]
      price = price_x + price_op + price_y
      if (price < best_summable[1]) ||
          (price == best_summable[1] &&
            ops_x + ops_y + 1 < best_summable[2])
        best_summable =[tpick_y + tpick_op + tpick_x, price,
          ops_x + ops_y + 1]
      end
      x += 1
      y -= 1
    end
    @max_cached_value += 1
    @lookup_multiplicable[target] = best_multiplicable
    @lookup_summable[target] = best_summable
  end

  def one()
    "|"
  end

  def multiply()
    ["x", 2]
  end

  def sum()
    ["+", 2]
  end

  def smallest_summable(value)
    # Cache any missing values
    @max_cached_value.upto(value - 1) {cache_next()}
    @lookup_summable[value].dup
  end
end

def show_toothpicks(start, finish=start)
  tp = Toothpicks.new()
  start.upto(finish) do
    |x|
    toothpick_calc, cost = tp.smallest_summable(x)
    puts "#{x}: #{toothpick_calc}  (#{cost})"
  end
end

case ARGV.size
when 1
  show_toothpicks(ARGV[0].to_i)
when 2
  show_toothpicks(ARGV[0].to_i, ARGV[1].to_i)
else
  puts "Usage: ruby toothpick.rb <value>  -or-  <first> <last>"
end