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 =
ossibly
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 =
ossibly
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
