[QUIZ] Counting Toothpicks (#111)

[C Erler]

A bit slow, but it should produce optimal output :

#!/usr/bin/env ruby

class String
def toothpick_count
count('|+*-') + count('+*')
end
end

class Array
def add_in operation
each_with_index do |expression, i|
(1..i).each do |j|
position = i.__send__(operation, j)
if (1...length).include? position
combination = "#{ expression }#{ operation }#{ self[j] }"
self[position] = combination if self[position] and
combination.toothpick_count < self[position].toothpick_count
end
end unless i.zero?
end
end
end

def output number, expression
puts "#{ expression.gsub /\*/, 'x' } = #{ number }
(#{ expression.toothpick_count } toothpick#{ 's' unless
expression.toothpick_count == 1 })"
end

result_wanted = ARGV.first.to_i

results = (0..result_wanted).map { |i| '|' * i }
results.add_in :*
results.add_in :+

output result_wanted, results[result_wanted]

 

[C Erler]

With a bit less ugliness :

#!/usr/bin/env ruby

class String
def toothpick_count
count('|-') + 2*count('+*')
end

def toothpick_value
if count('|').zero?
0
else
eval(gsub(/(\+|\*|-|\Z)/, ')\1').gsub(/(\A|\+|\*|-)\|/,
'\1(1').gsub(/\|/, '+1'))
end
end

def toothpick_information
"#{ gsub /\*/, 'x' } = #{ toothpick_value } (#{ toothpick_count }
toothpick#{ 's' unless toothpick_count == 1 })"
end
end

class Array
def add_in operation
1.upto(length - 1) do |i|
1.upto(i) do |j|
position = i.__send__(operation, j)
if (1...length).include? position
combination = "#{ self }#{ operation }#{ self[j] }"
self[position] = combination if combination.toothpick_count
< self[position].toothpick_count
end
end
end
end
end

results = Array.new(ARGV.first.to_i + 1) { |i| '|' * i }
results.add_in :*
results.add_in :+
puts results.last.toothpick_information

 

[C Erler]

With a bit less ugliness :

#!/usr/bin/env ruby

class String
def toothpick_count
count('|-') + 2*count('+*')
end

def toothpick_value
if count('|').zero?
0
else
eval(gsub(/(\+|\*|-|\Z)/, ')\1').gsub(/(\A|\+|\*|-)\|/,
'\1(1').gsub(/\|/, '+1'))
end
end

def toothpick_information
"#{ gsub /\*/, 'x' } = #{ toothpick_value } (#{ toothpick_count }
toothpick#{ 's' unless toothpick_count == 1 })"
end
end

class Array
def add_in operation
1.upto(length - 1) do |i|
1.upto(i) do |j|
position = i.__send__(operation, j)
if (1...length).include? position
combination = "#{ self }#{ operation }#{ self[j] }"
self[position] = combination if combination.toothpick_count
< self[position].toothpick_count
end
end
end
end
end

results = Array.new(ARGV.first.to_i + 1) { |i| '|' * i }
results.add_in :*
results.add_in :+
puts results.last.toothpick_information

 

[Andrey Falko]

Here is my solution...works in most case, fails in some (like 34)

#!/usr/bin/ruby
# Written by Andrey Falko

def factor(n)
factors = []

if (n < 8)
factors.push(n)
return factors
end

itr = 4
itr = (n / 4).to_i if (n < 25)
while (itr < n - (n / 2) + 1)
if (n % (itr) == 0)
factors.concat(factor(itr))
factors.concat(factor(n / itr))
else
itr = itr + 1
next
end

itr = itr + 1
prod = 1
for num in factors
prod = prod * num
end

return factors if (prod == n)
end

factors.push(n) if (factors.length == 0) # Primes

return factors
end

def count(picks)
cnt = 0
strs = picks.split('x')
for str in strs
cnt += 2
cnt += str.length
cnt += 1 if (str =~ /\+/)
end

return cnt - 2
end

def minPicks(n)
if (n <= 8)
return '|' * n
else
factors = factor(n)
str = ''
if ((factors.length == 1 && factors[0] == n && n > 11)
|| n == 34)
len = n
itr = 1
while (8 < n - itr)
try = minPicks(n - itr) + '+' + ('|' * itr)
itr += 1
if (len > (tmp = count(try)))
len = tmp
store = try
end
end

return store
end

for fac in factors
if (fac == n && n <= 11) # Primes <= 11
return '|' * n
else
str = str + minPicks(fac) + 'x'
end
end

str = str.gsub(/x$/, '')
return str
end
end

n = $*[0].to_i
picks = minPicks(n)

print n.to_s + ": " + picks.to_s + " (" + count(picks).to_s + " toothpicks)\n"

 

[George Ogata]

Here is my solution, a simple brute force + cache.
http://pastie.caboo.se/36232

class Fixnum
def divisors
@d ||= (2..self/2).select{|i| self % i == 0 }

You've probably already realized this, but this would be a lot faster:

@d ||= (2..Math.sqrt(self)).select{|i| self % i == 0 }

end
end

best_mul = Hash.new{|h,k|
pos_mul = k.divisors.map{|d| h[d] + 'x ' + h[k/d] }
h[k] = (pos_mul << '|'*k).sort_by{|tp|tp.length}.first
}

best_plus = Hash.new{|h,k|
pos_plus = (k/2...k).map{|p| best_mul[p] + '+ ' + h[k-p] }

The speedup here would be negligable, but hey:

pos_plus = (1..k/2).map{|p| best_mul[p] + '+ ' + h[k-p] }

h[k] = (pos_plus << best_mul[k]).sort_by{|tp|tp.length}.first
}.merge(1=>'|')

puts best_plus[ARGV[0].to_i].gsub(' ','').sub(/^$/,'Hug a Tree')

Sweet solution, though.

 

[David Chelimsky]

Here is my solution, a simple brute force + cache.
http://pastie.caboo.se/36232

class Fixnum
def divisors
@d ||= (2..self/2).select{|i| self % i == 0 }

You've probably already realized this, but this would be a lot faster:

@d ||= (2..Math.sqrt(self)).select{|i| self % i == 0 }

end
end

best_mul = Hash.new{|h,k|
pos_mul = k.divisors.map{|d| h[d] + 'x ' + h[k/d] }
h[k] = (pos_mul << '|'*k).sort_by{|tp|tp.length}.first
}

best_plus = Hash.new{|h,k|
pos_plus = (k/2...k).map{|p| best_mul[p] + '+ ' + h[k-p] }

The speedup here would be negligable, but hey:

pos_plus = (1..k/2).map{|p| best_mul[p] + '+ ' + h[k-p] }

I get a stack overflow w/ this.

h[k] = (pos_plus << best_mul[k]).sort_by{|tp|tp.length}.first
}.merge(1=>'|')

puts best_plus[ARGV[0].to_i].gsub(' ','').sub(/^$/,'Hug a Tree')

Sweet solution, though.

I think so too, though I did find that the toothpicks weren't being
counted correctly because it counted characters in each expression,
but not the extra toothpicks for + and x. So 11 was getting |||x|||+||
instead of |||||||||||.

This helped:

#in best_plus
h[k] = (pos_plus << best_mul[k]).sort_by{|tp|tp.length +
tp.split(/[x\+]/).length - 1}.first

 

[George Ogata]

The speedup here would be negligable, but hey:

pos_plus = (1..k/2).map{|p| best_mul[p] + '+ ' + h[k-p] }

I get a stack overflow w/ this.

Darn, it does too. Calling best_mul[] on the larger addend (like
Sander's original algo) helps:

pos_plus = (1..k/2).map{|p| best_mul[k-p] + '+ ' + h[p] }

It wasn't so obvious to me that it's still correct that way, actually,
but I'm convinced it is.

I think so too, though I did find that the toothpicks weren't being
counted correctly because it counted characters in each expression,
but not the extra toothpicks for + and x. So 11 was getting |||x|||+||
instead of |||||||||||.

Hmm, I didn't get that behavior.

Note that he adds '+ ' (plus-space) and 'x ' (x-space) in the strings,
so I believe the string length does actually represent the toothpick
count correctly. Perhaps the spaces somehow disappeared when you
copied it?

 

[Marcel Ward]

I think you're wrong. Some of those numbers don't need two '+', for
example:
||||x|||||||x|||||||||||||+|||x||| = 373 (38 Toothpicks)
||x||||x|||||||x|||||||||||||||||||+||||| = 1069 (45 Toothpicks)
|||x|||||x|||||||x|||||||||||+||x||||| = 1165 (43 Toothpicks)
so my program says the first ten numbers with two '+' - but without
warranty - are:

|||x|||x|||x|||||x|||||||+|||x||||+| = 958 (43 Toothpicks)
||||x|||||x|||||x|||||||||||+|||x||||+| = 1113 (45 Toothpicks)
||||x|||||x|||||x|||||||||||+||||x||||+| = 1117 (46 Toothpicks)
||||x|||||x|||||x|||||||||||+|||x||||||+| = 1119 (47 Toothpicks)
|||x||||x||||x||||x||||||+||||x||||+| = 1169 (44 Toothpicks)
|||x|||x||||x|||||x|||||||+|||x||||+| = 1273 (44 Toothpicks)
||||x||||x||||x||||x|||||+|||x||||+| = 1293 (43 Toothpicks)
|||x|||x|||x|||x||||x||||+|||x|||||||+|| = 1319 (48 Toothpicks)
|||x|||x|||x|||||||x|||||||+|||x||||||+| = 1342 (47 Toothpicks)
|||x|||x||||x||||||x|||||||+||||x||||+| = 1529 (46 Toothpicks)

Not yet

Well, after over 13 hours of CPU time (2GHz laptop)...

... on the 3rd revision of my code to ensure that it's only using
170Mb of memory well into the 700_000s range (my initial version's
"|" * 700_000 is NOT the most efficient calculation at this stage and
what results is certainly not going to be of any use!)...

.... I am pleased (and relieved) to announce the first and (I think)
the lowest toothpick calculation with 3 plusses...

775437: |||x||||x||||x||||x||||x||||x||||||x||||||x|||||||+||||x||||x||||x||||x|||||+|||x||||+|
(103)

I sense some kind of exponential increase so I'm not going to even
think about trying to attempt finding 4 plusses.