```Well, here's my solution. (http://pastie.caboo.se/36233)

I leaned heavily on #prime_division, so my solution can be a little
slow for numbers larger than 10^5. I'm not confident that I have a
globally optimal algorithm.

This quiz was quite hard for me, and I spent an unseemly amount of time on it.

Krishna

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

require 'mathn'

# Combines 2s and 3s into 4s and 6s, which are more toothpick-efficient.
# Takes a 'prime division' argument such as [[2,3], [3,2]], which it
# would return as [[3,1], [4,1], [6,1]]. The primes must be in order.
def merge_primes(pd)
if pd[0] && pd[0][0] == 2
if pd[0][1] > 1
pd << [4, (pd[0][1] / 2).to_i] # for some bizarre reason i have
to call to_i here to avoid a fraction
pd[0][1] = pd[0][1] % 2
end
if pd[1] && pd[1][0] == 3 && pd[0][1] == 1
pd << [6, 1]
pd[1][1] -= 1
pd[0][1] -= 1
end
end
pd.reject{|e| e[1] == 0}
end

# Expects an array of 'prime division'-like objects
def to_toothpicks(ar)
ar.map { |pd|
pd.map {|e| Array.new(e[1]){|i| "|" * e[0]}}.join("x")
}.join "+"
end

# Expects an array of 'prime division'-like objects
def cost(ar)
c = 0
for pd in ar
for i, n in pd
c += i*n + n*2
end
end
c -= 2
end

# Returns an array of 'prime division'-like objects
def best_toothpicks(i)
options = []
rem = 0

if i < 8 || i == 11
options <<  [[[i, 1]]]
else
while true
ar = i.prime_division
option = [merge_primes(ar)]
option += best_toothpicks(rem) if rem > 0
options << option

# this is something i'm not happy about. larger numbers (7)
improve performance,
# but i'm afraid smaller ones (3) may find better solutions
if ar.detect {|e| e.first > 5 }
i -= 1
rem += 1
else
break
end
end
end
return options.min {|a, b| cost(a) <=> cost(b) }
end

i = ARGV[0].to_i
puts to_toothpicks(best_toothpicks(i))

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

On 1/26/07, Ruby Quiz <james / grayproductions.net> wrote:
> The three rules of Ruby Quiz:
>
> 1.  Please do not post any solutions or spoiler discussion for this quiz until
> 48 hours have passed from the time on this message.
>
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rubyquiz.com/
>
> 3.  Enjoy!
>
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
> if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
> This quiz was adapted from an ACM programming challenge at the suggestion of
> Gavin Kistner.
>
> Simple math can be done with toothpicks alone.  Positive integers are just a
> count of toothpicks so three becomes |||.  We can use two toothpicks together to
> build a plus sign (+) or even tilt those slightly to get a multiplication
> operator (x).  Putting all of that together, the expression ||x||||+| is another
> way to express the number nine.
>
> 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!
>
> Posting toothpick expressions and/or counts for a given number is not spoiler
> material.
>
>

```