Counting Toothpicks (#111)

Ruby
21

Well if we allow more than addition and summation, any digit can be
written
in LCD with 7 toothpicks or
less, so…

10 =
_
| | |
| |_|

and so on… and we are back to ASCII art almost for sure.

Pedro.

22

From: Lincoln Anderson [mailto:[email protected]]

I missed the answer to the post asking if we should implement roman

numerals. Which is “more” acceptable,

X x X = 100 (6)

or

|||||||||| x |||||||||| = 100 (22)

it’s computer to toothpick and we assume all toothpicks are same without
breaking nor splitting.

X x X => X X X => 30 ?? how do we represent mult in roman num?

maybe, to be fair, we can use roman num but replace X (2 toothpicks)
with * (3 toothpics). exponent can be ** (6 toothpicks). we will use
//\ for M and |_ for L…

so,

X * X = 100 (2+3+2 toothpicks)
X ** X = 10 ** 10 = 10_000_000_1000 (2+3+3+2 toothpicks)

arggh, this quiz looks difficult :slight_smile:

kind regards -botp

23

Hi everyone,

I think I got a solution but I am not sure…can I post answers for
toothpick expressions for numbers 10 to 35 so that I can check whether
I get minimum toothpick counts?

Best regards,

Andrey F.

24

On Jan 27, 2007, at 12:21 PM, Andrey F. wrote:

I think I got a solution but I am not sure…can I post answers for
toothpick expressions for numbers 10 to 35 so that I can check whether
I get minimum toothpick counts?

You bet. Post away!

James Edward G. II

25

10: ||x|||||
11: |||||||||||
12: |||x||||
13: |||||||||||||
14: |||||||x||
15: |||x|||||
16: ||||x||||
17: ||||x||||+|
18: ||||||x|||
19: ||||||x|||+|
20: |||||x||||
21: |||||||x|||
22: |||||||||||x||
23: |||||||x|||+||
24: ||||||x||||
25: |||||x|||||
26: |||||||||||||x||
27: |||x|||x|||
28: ||||x|||||||
29: ||||x|||||||+|
30: |||||x||||||
31: |||||x||||||+|
32: ||||x||x||||
33: |||||||||||x|||
34: ||||x||||+|x||
35: |||||x|||||||

26

Ok, I fixed my code a little (recall the 34):

1: | (1 toothpicks)
2: || (2 toothpicks)
3: ||| (3 toothpicks)
4: |||| (4 toothpicks)
5: ||||| (5 toothpicks)
6: |||||| (6 toothpicks)
7: ||||||| (7 toothpicks)
8: |||||||| (8 toothpicks)
9: |||x||| (8 toothpicks)
10: |||||x|| (9 toothpicks)
11: ||||||||||| (11 toothpicks)
12: ||||x||| (9 toothpicks)
13: ||||||||||||| (13 toothpicks)
14: ||x||||||| (11 toothpicks)
15: |||||x||| (10 toothpicks)
16: ||||x|||| (10 toothpicks)
17: ||||x||||+| (13 toothpicks)
18: |||x|||||| (11 toothpicks)
19: |||x||||||+| (14 toothpicks)
20: ||||x||||| (11 toothpicks)
21: |||x||||||| (12 toothpicks)
22: ||x||||||||||| (15 toothpicks)
23: |||x|||||||+|| (16 toothpicks)
24: ||||x|||||| (12 toothpicks)
25: |||||x||||| (12 toothpicks)
26: ||x||||||||||||| (17 toothpicks)
27: |||x|||x||| (13 toothpicks)
28: |||||||x|||| (13 toothpicks)
29: |||||||x||||+| (16 toothpicks)
30: ||||||x||||| (13 toothpicks)
31: ||||||x|||||+| (16 toothpicks)
32: ||||x||x|||| (14 toothpicks)
33: |||x||||||||||| (16 toothpicks)
34: ||x||||x||||+| (17 toothpicks)
35: |||||||x||||| (14 toothpicks)
36: |||x|||x|||| (14 toothpicks)
37: |||x|||x||||+| (17 toothpicks)
38: ||x|||x||||||+| (18 toothpicks)
39: |||x||||||||||||| (18 toothpicks)
40: |||||x||x|||| (15 toothpicks)
41: |||||x||x||||+| (18 toothpicks)
42: |||||||x|||||| (15 toothpicks)
43: |||||||x||||||+| (18 toothpicks)
44: |||||||||||x|||| (17 toothpicks)
45: |||x|||x||||| (15 toothpicks)
46: ||x|||x|||||||+|| (20 toothpicks)
47: |||x|||x|||||+|| (19 toothpicks)
48: ||||x|||x|||| (15 toothpicks)
49: |||||||x||||||| (16 toothpicks)
50: |||||x||x||||| (16 toothpicks)

27

On Jan 27, 10:22 pm, “Andrey F.” [email protected] wrote:

13: |||||||||||||
26: |||||||||||||x||
34: ||||x||||+|x||

13 and 26 can be done with less. 34 is incorrect: 4 * 4 + 1 * 2 = 16

  • 2 = 18 (I assume it came from (4 * 4 + 1) * 2).
28

Ok, I fixed 13, 26, and 34 (dumb mistakes on my part, I’d say)…

Now all I have left is to figure out my 46…

Thanks.

29

Just for fun - hows this looking? I added the numeric expressions at
the end because my eyes were starting to pop out from reading the
toothpicks. Plus you can stick them back into eval() for testing.
Doesn’t prove that their the shortest, but at least it proves the
calculations are correct.

500: ||||x|||||x|||||x||||| (19 toothpicks - 4555)
501: ||||x|||||x|||||x|||||+| (22 toothpicks - 4555+1)
502: ||||x|||||x|||||x|||||+|| (23 toothpicks - 4555+2)
503: ||||x|||||x|||||x|||||+||| (24 toothpicks - 4555+3)
504: |||x||||x||||||x||||||| (20 toothpicks - 3467)
505: |||x||||x||||||x|||||||+| (23 toothpicks - 3467+1)
506: |||x||||x|||||x|||||||+|||x||||x|||||||+|| (39 toothpicks -
3457+347+2)
507: |||x||||x|||||x|||||||+|||x||||x|||||||+||| (40 toothpicks -
3457+347+3)
508: |||x||||x|||||x|||||||+||||x||||x|||||+||x|||| (42 toothpicks -
3457+445+24)
509: |||x||||x|||||x|||||||+||||x||||x|||||+|||x||| (42 toothpicks -
3457+445+33)
510: ||||x||||x|||||x||||||+|||||x|||||| (32 toothpicks - 4456+56)

30

On Jan 27, 6:17 pm, James Edward G. II [email protected]
wrote:

You bet. Post away!

Here’s what I got. Did anyone get any of them with less toothpicks ?
| = 1 (1 toothpick)
|| = 2 (2 toothpicks)
||| = 3 (3 toothpicks)
|||| = 4 (4 toothpicks)
||||| = 5 (5 toothpicks)
|||||| = 6 (6 toothpicks)
||||||| = 7 (7 toothpicks)
|||||||| = 8 (8 toothpicks)
|||x||| = 9 (8 toothpicks)
||x||||| = 10 (9 toothpicks)
||||||||||| = 11 (11 toothpicks)
|||x|||| = 12 (9 toothpicks)
|+|||x|||| = 13 (12 toothpicks)
||x||||||| = 14 (11 toothpicks)
|||x||||| = 15 (10 toothpicks)
||||x|||| = 16 (10 toothpicks)
|+||||x|||| = 17 (13 toothpicks)
|||x|||||| = 18 (11 toothpicks)
|+|||x|||||| = 19 (14 toothpicks)
||||x||||| = 20 (11 toothpicks)
|||x||||||| = 21 (12 toothpicks)
||x||||||||||| = 22 (15 toothpicks)
||+|||x||||||| = 23 (16 toothpicks)
||||x|||||| = 24 (12 toothpicks)
|||||x||||| = 25 (12 toothpicks)
|+|||||x||||| = 26 (15 toothpicks)
|||x|||x||| = 27 (13 toothpicks)
||||x||||||| = 28 (13 toothpicks)
|+||||x||||||| = 29 (16 toothpicks)
|||||x|||||| = 30 (13 toothpicks)
|+|||||x|||||| = 31 (16 toothpicks)
||||x|||||||| = 32 (14 toothpicks)
|||x||||||||||| = 33 (16 toothpicks)
||+||||x|||||||| = 34 (18 toothpicks)
|||||x||||||| = 35 (14 toothpicks)
|||x|||x|||| = 36 (14 toothpicks)
|+|||x|||x|||| = 37 (17 toothpicks)
||+|||x|||x|||| = 38 (18 toothpicks)
|||x||||||||||||| = 39 (18 toothpicks)
||||x||x||||| = 40 (15 toothpicks)
|+||||x||x||||| = 41 (18 toothpicks)
||||||x||||||| = 42 (15 toothpicks)
|+||||||x||||||| = 43 (18 toothpicks)
||||x||||||||||| = 44 (17 toothpicks)
|||x|||x||||| = 45 (15 toothpicks)
|+|||x|||x||||| = 46 (18 toothpicks)
||+|||x|||x||||| = 47 (19 toothpicks)
||||x|||x|||| = 48 (15 toothpicks)
|||||||x||||||| = 49 (16 toothpicks)
|||||x||x||||| = 50 (16 toothpicks)

31

I get:
500: |||||x|||||x|||||x|||| (25 toothpicks)
I think that you are mis-counting your toothpicks :).

32

s/their/they’re

33

On 1/28/07, Andrey F. [email protected] wrote:

I get:
500: |||||x|||||x|||||x|||| (25 toothpicks)
I think that you are mis-counting your toothpicks :).

Doh!!! Right you are. I had used X instead of x in my counter, but
switched mid-stream. Ironically, my tests still passed because
counting was off equally for potential solutions. Counts are right now
(I think):

500: ||||x|||||x|||||x||||| (25 toothpicks - 4555)
501: ||||x|||||x|||||x|||||+| (28 toothpicks - 4555+1)
502: ||||x|||||x|||||x|||||+|| (29 toothpicks - 4555+2)
503: ||||x|||||x|||||x|||||+||| (30 toothpicks - 4555+3)
504: |||x||||x||||||x||||||| (26 toothpicks - 3467)
505: |||x||||x||||||x|||||||+| (29 toothpicks - 3467+1)
506: ||||||x|||||||x|||||||||||+||||x||||||||||| (47 toothpicks -
6711+411)
507: ||||||x|||||||x|||||||||||+|||x|||x||||| (45 toothpicks -
6711+335)
508: ||||||x|||||||x|||||||||||+|||x|||x|||||+| (48 toothpicks -
6711+335+1)
509: ||||||x|||||||x|||||||||||+|||x|||x|||||+|| (49 toothpicks -
6711+335+2)
510: ||||x||||x|||||x||||||+|||||x|||||| (40 toothpicks - 4456+5*6)

Thanks for pointing that out!

34

On 1/28/07, David C. [email protected] wrote:

504: |||x||||x||||||x||||||| (26 toothpicks - 3467)
505: |||x||||x||||||x|||||||+| (29 toothpicks - 3467+1)
506: ||||||x|||||||x|||||||||||+||||x||||||||||| (47 toothpicks - 6711+411)
507: ||||||x|||||||x|||||||||||+|||x|||x||||| (45 toothpicks - 6711+335)
508: ||||||x|||||||x|||||||||||+|||x|||x|||||+| (48 toothpicks - 6711+335+1)
509: ||||||x|||||||x|||||||||||+|||x|||x|||||+|| (49 toothpicks -
6711+335+2)
510: ||||x||||x|||||x||||||+|||||x|||||| (40 toothpicks - 4456+5*6)

Thanks for pointing that out!

500: |||||x|||||x|||||x|||| (25)
501: |||||x|||||x|||||x||||+| (28)
502: |||||x|||||x|||||x||||+|| (29)
503: |||||x|||||x|||||x||||+||| (30)
504: ||||||x||||x|||x||||||| (26)
505: ||||||x||||x|||x|||||||+| (29)
506: ||||||x||||x|||x|||||||+|| (30)
507: ||||||x||||x|||x|||||||+||| (31)
508: ||||||x||||x|||x|||||||+|||| (32)
509: ||||||x||||x|||x|||||||+||||| (33)
510: ||||||x|||||x||||||||||||||||| (32)

On 1/28/07, C Erler [email protected] wrote:

Here’s what I got. Did anyone get any of them with less toothpicks ?

My 1-50 counts are the same.

A few higher ones:
9997: |||||||||||||||||x||||x|||||||x|||||||x|||+| (49)
9998: |||||||||||||||||x||||x|||||||x|||||||x|||+|| (50)
9999: |||||||||||||||||x||||x|||||||x|||||||x|||+||| (51)
10000: |||||x|||||x|||||x|||||x||||x|||| (38)
10001: |||||x|||||x|||||x|||||x||||x||||+| (41)
10002: |||||x|||||x|||||x|||||x||||x||||+|| (42)
10003: |||||x|||||x|||||x|||||x||||x||||+||| (43)

And one with two ‘+’ operations:
10043: |||||x|||||x|||||x|||||x||||x||||+|||||||x||||||+| (58)

35

Hi,

Andrey F. wrote:

Ok, I fixed my code a little (recall the 34):

34: ||x||||x||||+| (17 toothpicks)
I read 244+1 = 33 not 34.
(My algorithm missed the second +1 too)

Greeting
Waldemar

36

On 2007-01-28, Daniel L. [email protected] wrote:

1273: (1 + 3x4 + 5x7x6x6) → 44
1293: (1 + 3x4 + 4x5x4x4x4) → 43
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)

Anyone know which the first one to need 3 is?
Not yet :slight_smile:

Frank

37

Frank F. wrote:

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:

Nuts, forgot about tiebreaking. OK I get the same now.

Dan

38

Sander L. wrote:

A few higher ones:
9997: |||||||||||||||||x||||x|||||||x|||||||x|||+| (49)
9998: |||||||||||||||||x||||x|||||||x|||||||x|||+|| (50)
9999: |||||||||||||||||x||||x|||||||x|||||||x|||+||| (51)
10000: |||||x|||||x|||||x|||||x||||x|||| (38)
10001: |||||x|||||x|||||x|||||x||||x||||+| (41)
10002: |||||x|||||x|||||x|||||x||||x||||+|| (42)
10003: |||||x|||||x|||||x|||||x||||x||||+||| (43)

same here

According to my program here are the first ten integers that need two
'+'s:
373: (1 + 3x4 + 3x6x4x5) -> 38
958: (1 + 3x4 + 3x3x3x5x7) -> 43
1069: (1 + 3x4 + 11x4x4x6) -> 45
1113: (1 + 3x4 + 5x5x4x11) -> 45
1117: (1 + 4x4 + 5x5x4x11) -> 46
1119: (1 + 3x6 + 5x5x4x11) -> 47
1165: (1 + 3x4 + 4x6x3x4x4) -> 43
1169: (1 + 4x4 + 4x6x3x4x4) -> 44
1273: (1 + 3x4 + 5x7x6x6) -> 44
1293: (1 + 3x4 + 4x5x4x4x4) -> 43

Anyone know which the first one to need 3 is?

39

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 }
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] }
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’)

40

Well, I think enough time has passed. Here’s my first attempt at the
quiz - posted below and at Parked at Loopia.
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 ==
“34"
end
specify “34” do
ToothpickExpression.find_short_expression(34).to_s(true).should ==
"244+2"
end
specify “100” do
ToothpickExpression.find_short_expression(100).to_s(true).should ==
"455"
end
specify “509” do
ToothpickExpression.find_short_expression(509).to_s(true).should ==
"6711+33*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