```Well, I think enough time has passed. Here's my first attempt at the
quiz - posted below and at http://pastie.caboo.se/36231.
Hope its not too nuts:

#tootpick_spec.rb
require 'spec'
require 'toothpick'

context "Fixnum should convert itself to toothpick expression. Example..." do
specify "1" do
1.to_t.should == "|"
end

specify "2" do
2.to_t.should == "||"
end

specify "7" do
7.to_t.should == "|||||||"
end

specify "8" do
8.to_t.should == "||x||||"
end

specify "9" do
9.to_t.should == "|||x|||"
end

specify "12" do
12.to_t.should == "|||x||||"
end

specify "27" do
27.to_t.should == "|||x|||x|||"
end

specify "34" do
34.to_t.should == "||x||||x||||+||"
end

specify "100" do
100.to_t.should == "||||x|||||x|||||"
end

specify "138" do
138.to_t.should == "|||x||||||x|||||||+|||x||||"
end

specify "509" do
509.to_t.should == "||||||x|||||||x|||||||||||+|||x|||x|||||+||"
end

# This one runs really slow!!!!
specify "verify results" do
(1..300).each do |n|
eval(n.toothpick_expression.to_s(true)).should == n
end
end
end

context "ToothpickExpression should say number of toothpicks for" do
specify "1" do
ToothpickExpression.find_short_expression(1).toothpick_count.should == 1
end

specify "11" do
ToothpickExpression.find_short_expression(11).toothpick_count.should == 11
end

specify "12" do
ToothpickExpression.find_short_expression(12).toothpick_count.should == 9
end

specify "34" do
ToothpickExpression.find_short_expression(34).toothpick_count.should == 18
end

specify "100" do
ToothpickExpression.find_short_expression(100).toothpick_count.should == 18
end

specify "509" do
ToothpickExpression.find_short_expression(509).toothpick_count.should == 49
end
end

context "ToothpickExpression should provide numeric expression for" do
specify "1" do
ToothpickExpression.find_short_expression(1).to_s(true).should == "1"
end
specify "11" do
ToothpickExpression.find_short_expression(11).to_s(true).should == "11"
end
specify "12" do
ToothpickExpression.find_short_expression(12).to_s(true).should == "3*4"
end
specify "34" do
ToothpickExpression.find_short_expression(34).to_s(true).should == "2*4*4+2"
end
specify "100" do
ToothpickExpression.find_short_expression(100).to_s(true).should == "4*5*5"
end
specify "509" do
ToothpickExpression.find_short_expression(509).to_s(true).should ==
"6*7*11+3*3*5+2"
end
end

#toothpick.rb
class Fixnum
def to_t
toothpick_expression.to_s
end

def toothpick_count
toothpick_expression.toothpick_count
end

def toothpick_expression
@toothpick_expression ||= ToothpickExpression.find_short_expression(self)
end
end

class ToothpickExpression
def initialize(n,s)
@n = n
multipliers << @n/s
multipliers << s if s > 1
end

def to_s(numeric=false)
ms = multipliers.collect { |m| numeric ? m.to_s : no_math_expression(m)}
result = numeric ? ms.join("*") : ms.join("x")
remainder_expression = ToothpickExpression.find_short_expression(remainder)
result << "+" << remainder_expression.to_s(numeric) unless remainder == 0
result
end

def multipliers
@multipliers ||= []
@multipliers.delete(1)
@multipliers << 1 if @multipliers.empty?
@multipliers.sort!
end

def no_math_expression(n)
(1..n).inject("") { |result,n| result << "|" }
end

def remainder
ms = multipliers.collect { |m| m.to_s }
expression = ms.join("*")
@n - eval(expression)
end

def toothpick_count
return to_s.split('').inject(0) do |v,c|
v = v + 1 if c == '|'
v = v + 2 if ['+','x'].include?(c)
v
end
end

def self.find_short_expression(n)
expression = self.find_candidate_short_expression(n)
expression.expand_multipliers
expression.contract_multipliers
expression
end

def self.find_candidate_short_expression(n)
candidate = ToothpickExpression.new(n, 1)
(2..n).each do |i|
break if i > n/i
potential_candidate = ToothpickExpression.new(n, i)
if potential_candidate.has_fewer_toothpicks_than?(candidate) or
(
potential_candidate.has_as_many_toothpicks_as?(candidate) and
potential_candidate.has_more_multipliers_than?(candidate)
)
candidate = potential_candidate
end
end
candidate
end

def has_fewer_toothpicks_than?(other)
toothpick_count < other.toothpick_count
end

def has_as_many_toothpicks_as?(other)
toothpick_count == other.toothpick_count
end

def has_more_multipliers_than?(other)
multipliers.length > other.multipliers.length
end

def expand_multipliers
done_expanding = false
until (done_expanding)
done_expanding = :possibly
multipliers.clone.each do |e|
sub_expression = ToothpickExpression.find_candidate_short_expression(e)
if sub_expression.multipliers.length > 1
multipliers.delete(e)
sub_expression.multipliers.each {|m| multipliers << m }
done_expanding = false
end
end
end
end

def contract_multipliers
done_contracting = false
until (done_contracting)
done_contracting = :possibly
if multipliers[0] == 2
if multipliers.length > 1 && multipliers[1] <= 3
multipliers << (multipliers.shift*multipliers.shift)
done_contracting = false
end
end
end
end
end

def convert(n)
"#{n}: #{n.to_t} (#{n.toothpick_count} toothpick#{n == 1 ? '' : 's'}
- #{n.toothpick_expression.to_s(:numeric)})"
end

if ARGV[0].to_i > 0
if ARGV.length > 1
(ARGV[0].to_i..ARGV[1].to_i).each do |n|
puts convert(n)
end
else
puts convert(ARGV[0].to_i)
end
else
puts <<-USAGE
This program will try to find the toothpick expression that
uses the least number of toothpicks for any positive integer.

You can tell it to process one number or a range of numbers:

\$ruby toothpick.rb 37
\$ruby toothpick.rb 37 362

USAGE
end

```