Forum: Ruby Counting Toothpicks (#111)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
James G. (Guest)
on 2007-01-26 15:47
(Received via mailing list)
The three rules of Ruby Q.:

1.  Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.

2.  Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion.  Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

This quiz was adapted from an ACM programming challenge at the
suggestion of
Gavin K..

Simple math can be done with toothpicks alone.  Positive integers are
just a
count of toothpicks so three becomes |||.  We can use two toothpicks
together to
build a plus sign (+) or even tilt those slightly to get a
multiplication
operator (x).  Putting all of that together, the expression ||x||||+| is
another
way to express the number nine.

This weeks quiz is to write a program that takes a single command-line
argument
which will be a positive integer.  Your code should build a toothpick
expression
to calculate the number using as few toothpicks as possible.  For
example:

  $ruby toothpick.rb 9
  |||x||| = 9 (8 toothpicks)

Don't forget to count those operators!

Posting toothpick expressions and/or counts for a given number is not
spoiler
material.
David C. (Guest)
on 2007-01-26 16:46
(Received via mailing list)
On 1/26/07, Ruby Q. <removed_email_address@domain.invalid> wrote:
>
> count of toothpicks so three becomes |||.  We can use two toothpicks together to
>
> Don't forget to count those operators!
>
> Posting toothpick expressions and/or counts for a given number is not spoiler
> material.

What if there are more than one solution to a given number? For
example, |||||||| and ||X|||| both use 8 toothpicks to evaluate to 8.
Is one preferred?
Robert D. (Guest)
on 2007-01-26 16:57
(Received via mailing list)
On 1/26/07, Ruby Q. <removed_email_address@domain.invalid> wrote:
>
>
> another
>
> Don't forget to count those operators!
>
> Posting toothpick expressions and/or counts for a given number is not
> spoiler
> material.
>
>
This sounds like a great Quiz, worthy to celebrate the number 111 or
should
I say III ;).

Robert
Robert D. (Guest)
on 2007-01-26 17:19
(Received via mailing list)
On 1/26/07, David C. <removed_email_address@domain.invalid> wrote:
> I think that the human eye has much less troubles with II X IIII than with
IIIIIIII.

Cheers
Robert
Krishna D. (Guest)
on 2007-01-26 17:23
(Received via mailing list)
Are minus signs allowed?

    ||||X||||-| = 15 (12 toothpicks)


Krishna
James G. (Guest)
on 2007-01-26 17:44
(Received via mailing list)
On Jan 26, 2007, at 9:22 AM, Krishna D. wrote:

> Are minus signs allowed?
>
>    ||||X||||-| = 15 (12 toothpicks)

Let's stick with just addition and multiplication to keep things
simple.  Feel free to as an option to your program though.

James Edward G. II
James G. (Guest)
on 2007-01-26 17:47
(Received via mailing list)
On Jan 26, 2007, at 8:46 AM, David C. wrote:

> What if there are more than one solution to a given number? For
> example, |||||||| and ||X|||| both use 8 toothpicks to evaluate to 8.
> Is one preferred?

I would probably go with the simpler solution (less math), but either
answer is fine.

James Edward G. II
David C. (Guest)
on 2007-01-26 17:48
(Received via mailing list)
On 1/26/07, James Edward G. II <removed_email_address@domain.invalid> wrote:
> On Jan 26, 2007, at 9:22 AM, Krishna D. wrote:
>
> > Are minus signs allowed?
> >
> >    ||||X||||-| = 15 (12 toothpicks)
>
> Let's stick with just addition and multiplication to keep things
> simple.  Feel free to as an option to your program though.

Aw, man!!! I was already heading towards |||^|| = 9 (7 toothpicks).
Time for an aspirin, and then regroup.

Cheers,
David
Daniel L. (Guest)
on 2007-01-26 20:49
> Aw, man!!! I was already heading towards |||^|| = 9 (7 toothpicks).
> Time for an aspirin, and then regroup.
>
Do we want optimal solutions, or is it just get as low as you can?

Dan
Ben B. (Guest)
on 2007-01-26 21:27
(Received via mailing list)
On Sat, Jan 27, 2007, James Edward G. II wrote:
> On Jan 26, 2007, at 9:22 AM, Krishna D. wrote:
>
> >Are minus signs allowed?
> >
> >   ||||X||||-| = 15 (12 toothpicks)
>
> Let's stick with just addition and multiplication to keep things
> simple.  Feel free to as an option to your program though.

Another interesting corollary would be to allow any roman numerals that
can be represented with toothpicks...

20 could be represented with 6: X+X, XxII, etc.

*shrug*

Ben
alexander (Guest)
on 2007-01-26 21:48
(Received via mailing list)
hi there,
i´m having a small problem with base64 decoding a string.
i´m porting a php script over to ruby and the decoding gives me
different results in ruby and in php. the problem is that the php
results works for the processing i do afterwards while the ruby version
doesn´t.
here´s the scripts in question:

php:
<?

        $bytes = file_get_contents("test.rgb");
        $bitmap = base64_decode($bytes);

        $header = "";
        $header .= "\xFF\xFE";
        $header .= pack("n2",120,97);
        $header .= "\x01";
        $header .= "\xFF\xFF\xFF\xFF";

        $header .= $bitmap;

        file_put_contents("test_php.gd",$header);
?>

ruby:
require 'rubygems'
require 'fileutils'
require 'base64'

all_bytes = Base64.decode64(IO.read("test.rgb"))

bitmap = "\xFF\xFE"
bitmap << [120,97].pack("n2")
bitmap << "\x01"
bitmap << "\xFF\xFF\xFF\xFF"
bitmap << all_bytes

File.new("test_ruby.gd","w").puts(bitmap)

the ruby version is one byte shorter.

i´m probably missing something rather obvious here, but any pointers to
how i can make the ruby output be like the php output would be greatly
appreciated :)

i´ve uploaded the test.rgb file i´m using to here:

http://rss.fork.de/test.rgb if that´s even needed :)

thanks a lot,

alexander
James G. (Guest)
on 2007-01-26 21:49
(Received via mailing list)
On Jan 26, 2007, at 1:26 PM, Ben B. wrote:

> Another interesting corollary would be to allow any roman numerals
> that
> can be represented with toothpicks...
>
> 20 could be represented with 6: X+X, XxII, etc.

You people scare me.  ;)

James Edward G. II
James G. (Guest)
on 2007-01-26 21:50
(Received via mailing list)
On Jan 26, 2007, at 12:49 PM, Daniel L. wrote:

>
>> Aw, man!!! I was already heading towards |||^|| = 9 (7 toothpicks).
>> Time for an aspirin, and then regroup.
>>
> Do we want optimal solutions, or is it just get as low as you can?

In this problem, we optimize to save wood.

James Edward G. II
CHubas (Guest)
on 2007-01-26 22:41
(Received via mailing list)
On Jan 26, 7:46 am, Ruby Q. <removed_email_address@domain.invalid> wrote:
>
> count of toothpicks so three becomes |||.  We can use two toothpicks together to
>
> Don't forget to count those operators!
>
> Posting toothpick expressions and/or counts for a given number is not spoiler
> material.

Is there any specific rule to do group expressions? I mean, something
like
(( III x III ) + IIIII ) X III
is valid?

Thanks for the quiz.
James G. (Guest)
on 2007-01-26 22:47
(Received via mailing list)
On Jan 26, 2007, at 2:40 PM, CHubas wrote:

> Is there any specific rule to do group expressions? I mean, something
> like
> (( III x III ) + IIIII ) X III
> is valid?

No grouping.  And I think I forgot to mention it in the quiz but
multiplication has precedence over addition.

James Edward G. II
Robert D. (Guest)
on 2007-01-26 22:52
(Received via mailing list)
On 1/26/07, CHubas <removed_email_address@domain.invalid> wrote:
> > 2.  Support Ruby Q. by submitting ideas as often as you can:
> >
> together to
> > to calculate the number using as few toothpicks as possible.  For
>
> Is there any specific rule to do group expressions? I mean, something
> like
> (( III x III ) + IIIII ) X III
> is valid?
>
> Thanks for the quiz.


Ah you spoiled my idea I will try yo have a solution allowing for
parenthesis, imagine a  toothpick bent  like < and >, so I would assume
<II+III>x<I+IIII> (which is stupid of course) being 20 toothpicks.
Actually I feel that it will be easier to do a solution allowing for
parenthesis, but we will see ;)

Robert
Tim P. (Guest)
on 2007-01-26 23:07
(Received via mailing list)
On 1/26/07, Robert D. <removed_email_address@domain.invalid> wrote:
> > >
> > > if you can.
> > > count of toothpicks so three becomes |||.  We can use two toothpicks
> > expression
> > > material.
> parenthesis, imagine a  toothpick bent  like < and >, so I would assume
> <II+III>x<I+IIII> (which is stupid of course) being 20 toothpicks.
> Actually I feel that it will be easier to do a solution allowing for
> parenthesis, but we will see ;)
>

Last I checked it was very hard to bend toothpicks without breaking
them. So your <parenthesis> would require two toothpicks apiece.

<ll+lll>x<l+llll> = 25 (24 toothpicks)

I think the same applies to the exponentiation operator ^ used in an
earlier post.

However, ou could Ruby syntax that one

lllllxxll = 25 (11 toothpicks)
lllll^ll = 25 (9 toothpicks)

But that doesn't really save any toothpicks at all.

James, can we omit toothpicks to represent zeros  ;-)
l _ _ = 100 (1 toothpick)


Blessings,
TwP
David C. (Guest)
on 2007-01-26 23:13
(Received via mailing list)
On 1/26/07, Tim P. <removed_email_address@domain.invalid> wrote:
> > > > 48 hours have passed from the time on this message.
> > > message,
> > > just a
> > > > which will be a positive integer.  Your code should build a toothpick
> > > spoiler
> > Ah you spoiled my idea I will try yo have a solution allowing for
>
> James, can we omit toothpicks to represent zeros  ;-)
> l _ _ = 100 (1 toothpick)

Wouldn't the underscores be toothpicks turned sideways? I that *were*
allowed, it's certainly no less than 3 toothpicks.

Who would have thought that there would be so much depth to toothpick
philosophy?
James G. (Guest)
on 2007-01-26 23:26
(Received via mailing list)
On Jan 26, 2007, at 3:05 PM, Tim P. wrote:

> James, can we omit toothpicks to represent zeros  ;-)
> l _ _ = 100 (1 toothpick)

Zero toothpicks is represented by printing a "Hug a Tree" message.  ;)

James Edward G. II
Lincoln Anderson (Guest)
on 2007-01-27 03:09
(Received via mailing list)
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

James Edward G. II wrote:
> On Jan 26, 2007, at 3:05 PM, Tim P. wrote:
>
>> James, can we omit toothpicks to represent zeros  ;-)
>> l _ _ = 100 (1 toothpick)
>
> Zero toothpicks is represented by printing a "Hug a Tree" message.  ;)
>
> James Edward G. II
>
>
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)

or does this post mean that this trumps all:

| "Hug a tree" "Hug a tree" = 100 (1)

Lincoln Anderson
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFFuqYqR8wmeqHdtdcRApWgAKCmAwZbjvFa9Y43/oNiQ9d8VQXMNgCeIsfJ
wyKwsSL6Rn/ASxxJq5l7rwg=
=Y0KH
-----END PGP SIGNATURE-----
Peña, Botp (Guest)
on 2007-01-27 04:15
(Received via mailing list)
From: Lincoln Anderson [mailto:removed_email_address@domain.invalid]
# 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 :)

kind regards -botp
Pedro Fortuny A. (Guest)
on 2007-01-27 14:49
(Received via mailing list)
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.
Andrey F. (Guest)
on 2007-01-27 20:22
(Received via mailing list)
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.
James G. (Guest)
on 2007-01-28 02:17
(Received via mailing list)
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
Andrey F. (Guest)
on 2007-01-28 06:23
(Received via mailing list)
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|||||||
C Erler (Guest)
on 2007-01-28 09:06
(Received via mailing list)
On Jan 27, 6:17 pm, James Edward G. II <removed_email_address@domain.invalid>
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)
Andrey F. (Guest)
on 2007-01-28 09:14
(Received via mailing list)
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)
C Erler (Guest)
on 2007-01-28 09:16
(Received via mailing list)
On Jan 27, 10:22 pm, "Andrey F." <removed_email_address@domain.invalid> 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).
Andrey F. (Guest)
on 2007-01-28 09:23
(Received via mailing list)
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.
David C. (Guest)
on 2007-01-28 10:06
(Received via mailing list)
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 - 4*5*5*5)
501: ||||x|||||x|||||x|||||+| (22 toothpicks - 4*5*5*5+1)
502: ||||x|||||x|||||x|||||+|| (23 toothpicks - 4*5*5*5+2)
503: ||||x|||||x|||||x|||||+||| (24 toothpicks - 4*5*5*5+3)
504: |||x||||x||||||x||||||| (20 toothpicks - 3*4*6*7)
505: |||x||||x||||||x|||||||+| (23 toothpicks - 3*4*6*7+1)
506: |||x||||x|||||x|||||||+|||x||||x|||||||+|| (39 toothpicks -
3*4*5*7+3*4*7+2)
507: |||x||||x|||||x|||||||+|||x||||x|||||||+||| (40 toothpicks -
3*4*5*7+3*4*7+3)
508: |||x||||x|||||x|||||||+||||x||||x|||||+||x|||| (42 toothpicks -
3*4*5*7+4*4*5+2*4)
509: |||x||||x|||||x|||||||+||||x||||x|||||+|||x||| (42 toothpicks -
3*4*5*7+4*4*5+3*3)
510: ||||x||||x|||||x||||||+|||||x|||||| (32 toothpicks - 4*4*5*6+5*6)
David C. (Guest)
on 2007-01-28 10:08
(Received via mailing list)
s/their/they're
Andrey F. (Guest)
on 2007-01-28 10:24
(Received via mailing list)
I get:
500: |||||x|||||x|||||x|||| (25 toothpicks)
I think that you are mis-counting your toothpicks :).
David C. (Guest)
on 2007-01-28 10:47
(Received via mailing list)
On 1/28/07, Andrey F. <removed_email_address@domain.invalid> 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 - 4*5*5*5)
501: ||||x|||||x|||||x|||||+| (28 toothpicks - 4*5*5*5+1)
502: ||||x|||||x|||||x|||||+|| (29 toothpicks - 4*5*5*5+2)
503: ||||x|||||x|||||x|||||+||| (30 toothpicks - 4*5*5*5+3)
504: |||x||||x||||||x||||||| (26 toothpicks - 3*4*6*7)
505: |||x||||x||||||x|||||||+| (29 toothpicks - 3*4*6*7+1)
506: ||||||x|||||||x|||||||||||+||||x||||||||||| (47 toothpicks -
6*7*11+4*11)
507: ||||||x|||||||x|||||||||||+|||x|||x||||| (45 toothpicks -
6*7*11+3*3*5)
508: ||||||x|||||||x|||||||||||+|||x|||x|||||+| (48 toothpicks -
6*7*11+3*3*5+1)
509: ||||||x|||||||x|||||||||||+|||x|||x|||||+|| (49 toothpicks -
6*7*11+3*3*5+2)
510: ||||x||||x|||||x||||||+|||||x|||||| (40 toothpicks - 4*4*5*6+5*6)

Thanks for pointing that out!
Sander L. (Guest)
on 2007-01-28 11:48
(Received via mailing list)
On 1/28/07, David C. <removed_email_address@domain.invalid> wrote:
> 504: |||x||||x||||||x||||||| (26 toothpicks - 3*4*6*7)
> 505: |||x||||x||||||x|||||||+| (29 toothpicks - 3*4*6*7+1)
> 506: ||||||x|||||||x|||||||||||+||||x||||||||||| (47 toothpicks - 6*7*11+4*11)
> 507: ||||||x|||||||x|||||||||||+|||x|||x||||| (45 toothpicks - 6*7*11+3*3*5)
> 508: ||||||x|||||||x|||||||||||+|||x|||x|||||+| (48 toothpicks - 6*7*11+3*3*5+1)
> 509: ||||||x|||||||x|||||||||||+|||x|||x|||||+|| (49 toothpicks -
> 6*7*11+3*3*5+2)
> 510: ||||x||||x|||||x||||||+|||||x|||||| (40 toothpicks - 4*4*5*6+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 <removed_email_address@domain.invalid> 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)
Daniel L. (Guest)
on 2007-01-28 14:00
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?
Waldemar Dick (Guest)
on 2007-01-28 15:28
(Received via mailing list)
Hi,

Andrey F. wrote:
> Ok, I fixed my code a little (recall the 34):
>
> 34: ||x||||x||||+| (17 toothpicks)
I read 2*4*4+1 = 33 not 34.
(My algorithm missed the second +1 too)

Greeting
Waldemar
Frank F. (Guest)
on 2007-01-28 15:30
(Received via mailing list)
On 2007-01-28, Daniel L. <removed_email_address@domain.invalid> 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 :)

Frank
Daniel L. (Guest)
on 2007-01-28 16:11
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
David C. (Guest)
on 2007-01-28 16:16
(Received via mailing list)
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
Sander L. (Guest)
on 2007-01-28 16:43
(Received via mailing list)
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')
Krishna D. (Guest)
on 2007-01-28 16:46
(Received via mailing list)
Well, here's my solution. (http://pastie.caboo.se/36233)

I leaned heavily on #prime_division, so my solution can be a little
slow for numbers larger than 10^5. I'm not confident that I have a
globally optimal algorithm.

This quiz was quite hard for me, and I spent an unseemly amount of time
on it.

Krishna

----------------------------------------------

require 'mathn'

# Combines 2s and 3s into 4s and 6s, which are more toothpick-efficient.
# Takes a 'prime division' argument such as [[2,3], [3,2]], which it
# would return as [[3,1], [4,1], [6,1]]. The primes must be in order.
def merge_primes(pd)
  if pd[0] && pd[0][0] == 2
    if pd[0][1] > 1
      pd << [4, (pd[0][1] / 2).to_i] # for some bizarre reason i have
to call to_i here to avoid a fraction
      pd[0][1] = pd[0][1] % 2
    end
    if pd[1] && pd[1][0] == 3 && pd[0][1] == 1
      pd << [6, 1]
      pd[1][1] -= 1
      pd[0][1] -= 1
    end
  end
  pd.reject{|e| e[1] == 0}
end

# Expects an array of 'prime division'-like objects
def to_toothpicks(ar)
  ar.map { |pd|
    pd.map {|e| Array.new(e[1]){|i| "|" * e[0]}}.join("x")
  }.join "+"
end


# Expects an array of 'prime division'-like objects
def cost(ar)
  c = 0
  for pd in ar
    for i, n in pd
      c += i*n + n*2
    end
  end
  c -= 2
end

# Returns an array of 'prime division'-like objects
def best_toothpicks(i)
  options = []
  rem = 0

  if i < 8 || i == 11
    options <<  [[[i, 1]]]
  else
    while true
      ar = i.prime_division
      option = [merge_primes(ar)]
      option += best_toothpicks(rem) if rem > 0
      options << option

      # this is something i'm not happy about. larger numbers (7)
improve performance,
      # but i'm afraid smaller ones (3) may find better solutions
      if ar.detect {|e| e.first > 5 }
        i -= 1
        rem += 1
      else
        break
      end
    end
  end
  return options.min {|a, b| cost(a) <=> cost(b) }
end

i = ARGV[0].to_i
puts to_toothpicks(best_toothpicks(i))

----------------------------------------------
Frank F. (Guest)
on 2007-01-28 16:50
(Received via mailing list)
It's my first time on ruby-quiz. So here's my solution. It's some kind
of dynamic-programming:

# Number to calculate with toothpicks
class ToothNumber
    attr_reader :value, :num, :pic
    def initialize value, num=value, pic=("|"*num)
  @value, @num, @pic = value, num, pic
    end

    def + x; operation(:+, 2, "+", x); end

    # TODO: uncomment line for use of '-' ############
    #def - x; operation(:-, 1, "-", x); end

    def * x; operation(:*, 2, "x", x); end

    def <=> x; @num <=> x.num; end

    def to_s; "#{@pic} = #{@value} (#{@num} Toothpicks)"; end

    private
    # create new ToothNumber using an operation
    def operation meth, n_operator_sticks, operator, x
  ToothNumber.new @value.send(meth, x.value),
                @num + x.num + n_operator_sticks,
      @pic + operator + x.pic
    end
end

# contains minimal multiplication-only toothpick for each number
$tooths = Hash.new {|h,n| h[n] = tooth_mul n}
$tooths_add = Hash.new {|h,n| h[n] = toothpick n}

# should return the minimal toothpick-number
# should only use multiplication
def tooth_mul n
    ways = [ToothNumber.new(n)] +
  (2..(Math.sqrt(n).to_i)).map{|i|
    n % i == 0 ? ($tooths[i] * $tooths[n/i]) : nil
        }.compact
    ways.min
end

# returns minimal toothpick-number with multiplication and addition
def toothpick n
    ways = [$tooths[n]] +
    # TODO: uncomment the following line for use of '-'
    # I do not know, if n = (x+i) - i for i \in {1,2,...,n} is ok
    #   (1..n).map{|i| $tooths[n+i] - $tooths[i]} +
        (1..(n/2)).map{|i| $tooths[n-i] + $tooths_add[i] }
    ways.min
end

for i in 1..ARGV[0].to_i
    puts $tooths_add[i]
end
Daniel L. (Guest)
on 2007-01-28 17:30
Well here is my solution. I thought it was pretty good until I saw yours
Frank :)
It:
(1) produces optimal solutions
(2) returns minimal plus counts in tie break situations (there are no
integers that need 3 pluses before 20000 btw)

Exactly like Franks it is recursive on multiplication and bi-partitions.
Unlike franks it does not do clever things with class operators and hash
defaults that would reduce the LOC by 50%. Ah well.

# $ ruby toothpick.rb 510
# 510:  (5x6x17) -> 32

# Will return the toothpick expression with the minimum
# number of toothpicks. In the case of tie-breaks, it will return
# the number with the fewest '+' signs.

# toothpick expressions are stored like:
# [[1], [3 ,4], [5, 6]] ~ 1 + 3*4 + 5*6

class Integer
  def divisors
    (2..(self-1)).select do |i|
      self.divmod(i)[1] == 0
    end
  end
end

class Toothpicks
  # contains the factorizations of integers with the minimum toothpick
counts
  FACTORIZATIONS        = [nil, [1], [2], [3], [4], [5], [6], [7]]
  # contains the best toothpick expression for each integer
  SIMPLIFICATIONS       = [nil, [1], [2], [3], [4], [5], [6], [7]]
  # contains the best toothpick expression's toothpick count
  SIMPLIFICATION_COUNTS = [nil, 1, 2, 3, 4, 5, 6, 7]
  # contains the best toothpick expressions + count
  PLUS_COUNTS           = [nil, 0, 0, 0, 0, 0, 0, 0]

  def self.go(int, print=false)
    r = nil
    1.upto(int) do |i|
      r = simplify(i)
      puts "#{i}:  "+display(r) if print
    end
    r
  end

  # counts toothpicks in an array
  def self.count(array)
    array.flatten.inject{|sum, el| sum+el} + 2*array.flatten.length - 2
  end

  # just pretty prints the toothpick expression
  def self.display(array)
    str = "("
    array.each do |el|
      if el.is_a? Array
        str << el.join("x")
      elsif el.is_a? Integer
        str << el.to_s
      end
      str << " + "
    end
    str[0..(str.length-4)] << ") -> #{count(array)}"
  end

  # factorize an integer using the fewest toothpicks possible.
  # Recursive on multiplication.
  def self.factorize(int)
    if FACTORIZATIONS[int]
      result = FACTORIZATIONS[int]
    else
      best = [int]
      best_value = count(best)
      sqrt = Math::sqrt(int.to_f).to_i
      int.divisors.select{|d| d <= sqrt}.each do |div|
        current = [factorize(div), factorize(int/div)].flatten
        value = count(current)
        if value < best_value
          best = current
          best_value = value
        end
      end
      FACTORIZATIONS[int] = best
    end
  end

  # simplify an integer into a sum of factorized integers using
  # the fewest toothpicks possible.
  # (assumes that all simplifications less that int have already been
done)
  # Recursive on bi-partition.
  def self.simplify(int)
    factorization = factorize(int)
    best = 0
    best_value = count(factorization)
    best_plus_count = 0
    # iterate over all possible bi-partitions of int, and save the best
    1.upto(int/2) do |i|
      value = SIMPLIFICATION_COUNTS[i] + SIMPLIFICATION_COUNTS[-i] + 2
      if value < best_value
        best = i
        best_value = value
        best_plus_count = PLUS_COUNTS[i] + PLUS_COUNTS[-i] + 1
      elsif value == best_value
        plus_count = PLUS_COUNTS[i] + PLUS_COUNTS[-i] + 1
        if plus_count < best_plus_count
          best = i
          best_value = value
          best_plus_count = plus_count
        end
      end
    end
    SIMPLIFICATION_COUNTS[int] = best_value
    PLUS_COUNTS[int] = best_plus_count
    if best == 0
      SIMPLIFICATIONS[int] = [factorization]
    else
      SIMPLIFICATIONS[int] = SIMPLIFICATIONS[best] +
SIMPLIFICATIONS[-best]
    end
  end
end


if ARGV[0] == "test"
  require 'test/unit'
  class TestToothpick < Test::Unit::TestCase
    def test_factorize
      assert_equal [3, 4], Toothpicks.factorize(12)
      assert_equal [13],   Toothpicks.factorize(13)
      assert_equal [2, 7], Toothpicks.factorize(14)
    end

    def test_count
      assert_equal 12, Toothpicks.count( [[3,4], [1]] )
      assert_equal 11, Toothpicks.count( [[3,6]] )
      assert_equal 14, Toothpicks.count( [[1], [3,6]] )
    end

    def test_simplify_through_go
      assert_equal [[1]], Toothpicks.go(1)
      assert_equal [[3]], Toothpicks.go(3)
      assert_equal [[3, 3]], Toothpicks.go(9)
      assert_equal [[1], [3, 6]], Toothpicks.go(19)
    end
  end
else
  r = Toothpicks.go(ARGV[0].to_i)
  puts "#{ARGV[0].to_i}:  "+Toothpicks.display(r)
end
David C. (Guest)
on 2007-01-28 18:41
(Received via mailing list)
On 1/28/07, Sander L. <removed_email_address@domain.invalid> wrote:
>   pos_mul = k.divisors.map{|d| h[d] + 'x ' + h[k/d] }
>
Is there voting in this thing? If so, this gets my vote. I'm going
back to school.
Marcel W. (Guest)
on 2007-01-28 19:05
(Received via mailing list)
On 26/01/07, Ruby Q. <removed_email_address@domain.invalid> wrote:
> This weeks quiz is to write a program that takes a single command-line argument
> which will be a positive integer.  Your code should build a toothpick expression
> to calculate the number using as few toothpicks as possible.  For example:
>
>         $ruby toothpick.rb 9
>         |||x||| = 9 (8 toothpicks)
>
> Don't forget to count those operators!

Here is my solution.  It is an iterative solution using two caches:
one for "multipicable" toothpick strings (i.e. those that do not
contain any addition signs) and another for "summable" toothpick
strings.

I take the approach that you can multiply as many previous
multiplicable strings together and then add a summable string, knowing
that the result will be valid.

I did start off by preferring shorter toothpick strings (as well as
less toothpicks) but after seeing the talk here decided that
minimising the number of operators (either + or x) is preferable
(again, for equal number of toothpicks).  It turns out this should
favour multiplication over addition anyway.

Arghh, now my favourite coffee shop will have closed for the evening ;)

Thanks James & Gavin and to other participants for the helpful example
expressions.

Marcel

# Marcel W.   <wardies ^a-t^ gmaildotcom>
# Sunday, 28 January 2007
# Solution for Ruby Q. number 111 - Counting Toothpicks
#
class Toothpicks
  def initialize
    # Lookups are value indexed arrays that maps to triplets
    # of elements representing:
    # 1. The shortest toothpick string form of the value
    # 2. The number of toothpicks used
    # 3. The number of operators used, i.e. multiply or add
    @lookup_multiplicable = []
    @lookup_summable = []
    @max_cached_value = 0
  end

  def cache_next()
    target = @max_cached_value + 1
    # Find the best multiplicable tootpick expression by trying to
    # multiply together two existing numbers from the multiplicable
    # cache (we only need to search from 2..sqrt(target))
    best_multiplicable = [one() * target, target, 0]
    tpick_op, price_op = multiply()
    x = 2
    while x**2 <= target
      y,remainder = target.divmod(x)
      if remainder == 0
        tpick_x, price_x, ops_x = @lookup_multiplicable[x]
        tpick_y, price_y, ops_y = @lookup_multiplicable[y]
        price = price_x + price_op + price_y
        if (price < best_multiplicable[1]) ||
            (price == best_multiplicable[1] &&
              ops_x + ops_y + 1 < best_multiplicable[2])
          best_multiplicable = [tpick_x + tpick_op + tpick_y, price,
            ops_x + ops_y + 1]
        end
      end
      x += 1
    end

    best_summable = best_multiplicable.dup
    # Now try summing up two existing, cached values to see if this
    # results in a shorter toothpick sum than the multiplicable one.
    tpick_op, price_op = sum()
    x = 1
    y = target - x
    while x <= y
      tpick_x, price_x, ops_x = @lookup_summable[x]
      tpick_y, price_y, ops_y = @lookup_summable[y]
      price = price_x + price_op + price_y
      if (price < best_summable[1]) ||
          (price == best_summable[1] &&
            ops_x + ops_y + 1 < best_summable[2])
        best_summable =[tpick_y + tpick_op + tpick_x, price,
          ops_x + ops_y + 1]
      end
      x += 1
      y -= 1
    end
    @max_cached_value += 1
    @lookup_multiplicable[target] = best_multiplicable
    @lookup_summable[target] = best_summable
  end

  def one()
    "|"
  end

  def multiply()
    ["x", 2]
  end

  def sum()
    ["+", 2]
  end

  def smallest_summable(value)
    # Cache any missing values
    @max_cached_value.upto(value - 1) {cache_next()}
    @lookup_summable[value].dup
  end
end

def show_toothpicks(start, finish=start)
  tp = Toothpicks.new()
  start.upto(finish) do
    |x|
    toothpick_calc, cost = tp.smallest_summable(x)
    puts "#{x}: #{toothpick_calc}  (#{cost})"
  end
end

case ARGV.size
when 1
  show_toothpicks(ARGV[0].to_i)
when 2
  show_toothpicks(ARGV[0].to_i, ARGV[1].to_i)
else
  puts "Usage: ruby toothpick.rb <value>  -or-  <first> <last>"
end
C Erler (Guest)
on 2007-01-28 21:48
(Received via mailing list)
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 (Guest)
on 2007-01-28 22:15
(Received via mailing list)
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[i] }#{ 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 (Guest)
on 2007-01-28 22:48
(Received via mailing list)
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[i] }#{ 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 F. (Guest)
on 2007-01-29 05:13
(Received via mailing list)
Here is my solution...works in most case, fails in some (like 34)

#!/usr/bin/ruby
# Written by Andrey F.

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 O. (Guest)
on 2007-01-29 14:31
(Received via mailing list)
On 1/29/07, Sander L. <removed_email_address@domain.invalid> wrote:
> 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 C. (Guest)
on 2007-01-29 17:16
(Received via mailing list)
On 1/29/07, George O. <removed_email_address@domain.invalid> wrote:
>       @d ||= (2..Math.sqrt(self)).select{|i| self % i == 0 }
> >   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 O. (Guest)
on 2007-01-30 13:36
(Received via mailing list)
On 1/30/07, David C. <removed_email_address@domain.invalid> wrote:
> On 1/29/07, George O. <removed_email_address@domain.invalid> wrote:
> > On 1/29/07, Sander L. <removed_email_address@domain.invalid> wrote:
> >     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 W. (Guest)
on 2007-01-31 14:21
(Received via mailing list)
On 28/01/07, Frank F. <removed_email_address@domain.invalid> wrote:
> warranty - are:
> |||x|||x||||x||||||x|||||||+||||x||||+| = 1529 (46 Toothpicks)
>
> > Anyone know which the first one to need 3 is?
> 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.
Christian N. (Guest)
on 2007-01-31 23:13
(Received via mailing list)
"George O." <removed_email_address@domain.invalid> writes:

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

You reminded me of
      http://butunclebob.com/ArticleS.UncleBob.PerformanceTuning
This topic is locked and can not be replied to.