From: David Chelimsky <dchelimsky@...>
Date: 2007-01-28T23:16:01+09:00
Subject: Re: Counting Toothpicks (#111)

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