# Re: Counting Toothpicks (#111)

**URL:** <https://www.ruby-forum.com/t/re-counting-toothpicks-111/83900>\
**Category:** Ruby\
**Created:** [January 30, 2007, 6:23pm UTC](https://www.ruby-forum.com/t/re-counting-toothpicks-111/83900 "2007-01-30T18:23:23Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![BallS\_Donald\_A\_Jr\_S](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/da6949/32.png) [@BallS\_Donald\_A\_Jr\_S](https://www.ruby-forum.com/u/BallS_Donald_A_Jr_S)\
**Post date:** [January 30, 2007, 6:23pm UTC](https://www.ruby-forum.com/t/re-counting-toothpicks-111/83900/1 "2007-01-30T18:23:23Z")

</div>

I cleaned up my solution somewhat, substituting some verbose java-style  
code with rubyisms and changing the ineptly named ‘expansions’ to  
‘reductions’ or ‘factorizations’ as appropriate.

- donald

#!c:\ruby\bin\ruby.exe

# 

# Implements toothpick expressions for integers

# 

# Ruby Q. 111

# 

# Donald B. 2007-01-29

require ‘set’

module Toothpicks

# PRIMES are most succinctly expressed in toothpicks as themselves

PRIMES = [2, 3, 5, 7, 11]

# REDUCTIONS are most succinctly expressed in toothpicks as coded here

REDUCTIONS = {{2=\>3} =\> 8, {2=\>1, 3=\>1} =\> 6, {2=\>2} =\> 4}

module ClassMethods

```
# Expands the given prime factorization into the set of all possible

# reduced factorizations
# e.g. {2=>2, 3=>1} -> [{2=>2, 3=>1}, {2=>1, 6=>1}, {3=>1,

```

4=\>1}].to\_set  
def reductions(factorization)  
reductions = Set.new  
REDUCTIONS.each\_pair do |factors, product|  
new\_factorization = factorization.clone  
factors.each\_pair do |key, value|  
if new\_factorization.has\_key?(key) && new\_factorization[key]

> = value  
> new\_factorization[key] -= value  
> new\_factorization.delete(key) if new\_factorization[key] == 0  
> else  
> new\_factorization = nil  
> break  
> end  
> end  
> next unless new\_factorization  
> new\_factorization[product] ||= 0  
> new\_factorization[product] += 1  
> reductions.merge(self.reductions(new\_factorization))  
> end  
> reductions \<\< factorization  
> end

```
# Returns the cost in toothpicks of the given factorization
# e.g. {3->1, 4->1} -> 9
def toothpick_cost(factorization)
  cost = 0
  operands = 0
  factorization.each_pair do |key, value|
    cost += key*value
    operands += value
  end
  cost += 2*(operands-1)
end

```

end

module ObjectMethods

```
# Factors the given value into a hash of primes, or nil if it's not

```

a  
# product of primes  
# e.g. 12 -\> {2-\>2, 3-\>1}  
def factor  
if self \<= 0  
raise ‘Illegal argument’  
elsif self == 1  
return {1=\>1}  
end  
PRIMES.each do |prime|  
return {prime=\>1} if self == prime  
quotient, modulus = self.divmod(prime)  
next if modulus != 0  
factorization = quotient.factor  
next if factorization.nil?  
factorization[prime] ||= 0  
factorization[prime] += 1  
return factorization  
end  
nil  
end

```
# Returns a string expressing the given value in toothpicks
def to_toothpicks
  add = 0
  value = self
  while (factorization = value.factor).nil?
    value -= 1
    add += 1
  end
  factorization = self.class.reductions(factorization).min do |a,b|
    self.class.toothpick_cost(a) <=> self.class.toothpick_cost(b)
  end
  factors = []
  factorization.sort.reverse.each do |key, value|
    value.times { factors << key }
  end
  toothpicks = []
  factors.each do |factor|
    toothpicks << (1..factor).inject('') { |s, i| s << '|' }
  end
  s = toothpicks.join('x')
  if add > 0
    s << '+' << add.to_toothpicks
  end
  s
end

```

end

end

class Integer  
extend Toothpicks::ClassMethods  
include Toothpicks::ObjectMethods  
end

require ‘test/unit’

class TestToothPicks \< Test::Unit::TestCase

def test\_factor  
assert\_equal({1=\>1}, 1.factor)  
assert\_equal({2=\>1}, 2.factor)  
assert\_equal({2=\>1, 3=\>1}, 6.factor)  
assert\_equal({2=\>3}, 8.factor)  
assert\_equal({2=\>1, 5=\>1}, 10.factor)  
assert\_equal({2=\>2, 5=\>1}, 20.factor)  
assert\_equal({2=\>2, 3=\>1, 5=\>1}, 60.factor)  
assert\_equal({2=\>2, 3=\>1}, 12.factor)  
assert\_nil(13.factor)  
assert\_equal({2=\>2, 7=\>1}, 28.factor)  
assert\_nil(29.factor)  
assert\_nil(26.factor)  
end

def test\_reductions  
# TODO Set equals is broken somehow… suspect reference v.s. value  
equality  
# assert\_equal([{2=\>3}, {2=\>1, 4=\>1}, {8=\>1}].to\_set,  
Integer.reductions(8.factor))  
# assert\_equal([{2=\>4}, {2=\>2, 4=\>1}, {4=\>2}, {2=\>1, 8=\>1}].to\_set,  
Integer.reductions(16.factor))  
# assert\_equal([{2=\>2, 3=\>1}, {4=\>1, 3=\>1}].to\_set,  
Integer.reductions(12.factor))  
# assert\_equal([{2=\>1, 3=\>1}, {6=\>1}].to\_set,  
Integer.reductions(6.factor))  
end

def test\_toothpick\_cost  
assert\_equal(2, Integer.toothpick\_cost({2=\>1}))  
assert\_equal(6, Integer.toothpick\_cost({2=\>2}))  
assert\_equal(11, Integer.toothpick\_cost({2=\>2, 3=\>1}))  
end

def test\_toothpicks  
assert\_equal(’|’, 1.to\_toothpicks)  
assert\_equal(’||||x||||’, 16.to\_toothpicks)  
assert\_equal(’||||x||||+|’, 17.to\_toothpicks)  
assert\_equal(’||||x|||’, 12.to\_toothpicks)  
assert\_equal(’|||x|||x|||’, 27.to\_toothpicks)  
assert\_equal(’|||||||x||||’, 28.to\_toothpicks)  
end

def test\_eyeball  
(1…255).each do |i|  
puts “#{i}: #{i.to\_toothpicks}”  
end  
end

end