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.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-01-26 14:47
(Received via mailing list)
The three rules of Ruby Quiz:

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 Quiz 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 Talk 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 Kistner.

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.
5d38ab152e1e3e219512a9859fcd93af?d=identicon&s=25 David Chelimsky (Guest)
on 2007-01-26 15:46
(Received via mailing list)
On 1/26/07, Ruby Quiz <james@grayproductions.net> 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?
703fbc991fd63e0e1db54dca9ea31b53?d=identicon&s=25 Robert Dober (Guest)
on 2007-01-26 15:57
(Received via mailing list)
On 1/26/07, Ruby Quiz <james@grayproductions.net> 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
703fbc991fd63e0e1db54dca9ea31b53?d=identicon&s=25 Robert Dober (Guest)
on 2007-01-26 16:19
(Received via mailing list)
On 1/26/07, David Chelimsky <dchelimsky@gmail.com> wrote:
> I think that the human eye has much less troubles with II X IIII than with
IIIIIIII.

Cheers
Robert
8222471351de475ccbc18f42350a04d8?d=identicon&s=25 Krishna Dole (Guest)
on 2007-01-26 16:23
(Received via mailing list)
Are minus signs allowed?

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


Krishna
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-01-26 16:44
(Received via mailing list)
On Jan 26, 2007, at 9:22 AM, Krishna Dole 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 Gray II
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-01-26 16:47
(Received via mailing list)
On Jan 26, 2007, at 8:46 AM, David Chelimsky 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 Gray II
5d38ab152e1e3e219512a9859fcd93af?d=identicon&s=25 David Chelimsky (Guest)
on 2007-01-26 16:48
(Received via mailing list)
On 1/26/07, James Edward Gray II <james@grayproductions.net> wrote:
> On Jan 26, 2007, at 9:22 AM, Krishna Dole 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
0158871402c1ecfa57952e8a379cfd10?d=identicon&s=25 Daniel Lucraft (lucraft)
on 2007-01-26 19: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
90a73d9875462aaa9fab2feffafbffe7?d=identicon&s=25 Ben Bleything (Guest)
on 2007-01-26 20:27
(Received via mailing list)
On Sat, Jan 27, 2007, James Edward Gray II wrote:
> On Jan 26, 2007, at 9:22 AM, Krishna Dole 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
7a03066e8719f4d938bf622351ce4e7b?d=identicon&s=25 alexander (Guest)
on 2007-01-26 20: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
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-01-26 20:49
(Received via mailing list)
On Jan 26, 2007, at 1:26 PM, Ben Bleything 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 Gray II
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-01-26 20:50
(Received via mailing list)
On Jan 26, 2007, at 12:49 PM, Daniel Lucraft 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 Gray II
F2c730957ef0aec5616091b30fe88075?d=identicon&s=25 CHubas (Guest)
on 2007-01-26 21:41
(Received via mailing list)
On Jan 26, 7:46 am, Ruby Quiz <j...@grayproductions.net> 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.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-01-26 21: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 Gray II
703fbc991fd63e0e1db54dca9ea31b53?d=identicon&s=25 Robert Dober (Guest)
on 2007-01-26 21:52
(Received via mailing list)
On 1/26/07, CHubas <CHubas7@gmail.com> wrote:
> > 2.  Support Ruby Quiz 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
4d5b5dd4e263d780a5dfe7ac8b8ac98c?d=identicon&s=25 Tim Pease (Guest)
on 2007-01-26 22:07
(Received via mailing list)
On 1/26/07, Robert Dober <robert.dober@gmail.com> 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
5d38ab152e1e3e219512a9859fcd93af?d=identicon&s=25 David Chelimsky (Guest)
on 2007-01-26 22:13
(Received via mailing list)
On 1/26/07, Tim Pease <tim.pease@gmail.com> 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?
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-01-26 22:26
(Received via mailing list)
On Jan 26, 2007, at 3:05 PM, Tim Pease 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 Gray II
29b25ecfc0229634cd39f4d7b2f4727d?d=identicon&s=25 Lincoln Anderson (Guest)
on 2007-01-27 02:09
(Received via mailing list)
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

James Edward Gray II wrote:
> On Jan 26, 2007, at 3:05 PM, Tim Pease 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 Gray 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-----
6087a044557d6b59ab52e7dd20f94da8?d=identicon&s=25 Peña, Botp (Guest)
on 2007-01-27 03:15
(Received via mailing list)
From: Lincoln Anderson [mailto:ayblinkin@gmail.com]
# 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
864898c3a94a64bac0e47d41eb18b9db?d=identicon&s=25 Pedro Fortuny Ayuso (Guest)
on 2007-01-27 13: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.
034c4cf05cfad09c66d1b0bc3cb4a6b5?d=identicon&s=25 Andrey Falko (Guest)
on 2007-01-27 19: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 Falko
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-01-28 01:17
(Received via mailing list)
On Jan 27, 2007, at 12:21 PM, Andrey Falko 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 Gray II
034c4cf05cfad09c66d1b0bc3cb4a6b5?d=identicon&s=25 Andrey Falko (Guest)
on 2007-01-28 05: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|||||||
E2a9d30a2487a924165aaaa016b54f87?d=identicon&s=25 C Erler (Guest)
on 2007-01-28 08:06
(Received via mailing list)
On Jan 27, 6:17 pm, James Edward Gray II <j...@grayproductions.net>
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)
034c4cf05cfad09c66d1b0bc3cb4a6b5?d=identicon&s=25 Andrey Falko (Guest)
on 2007-01-28 08: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)
E2a9d30a2487a924165aaaa016b54f87?d=identicon&s=25 C Erler (Guest)
on 2007-01-28 08:16
(Received via mailing list)
On Jan 27, 10:22 pm, "Andrey Falko" <ma3ox...@gmail.com> 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).
034c4cf05cfad09c66d1b0bc3cb4a6b5?d=identicon&s=25 Andrey Falko (Guest)
on 2007-01-28 08: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.
5d38ab152e1e3e219512a9859fcd93af?d=identicon&s=25 David Chelimsky (Guest)
on 2007-01-28 09: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)
5d38ab152e1e3e219512a9859fcd93af?d=identicon&s=25 David Chelimsky (Guest)
on 2007-01-28 09:08
(Received via mailing list)
s/their/they're
034c4cf05cfad09c66d1b0bc3cb4a6b5?d=identicon&s=25 Andrey Falko (Guest)
on 2007-01-28 09:24
(Received via mailing list)
I get:
500: |||||x|||||x|||||x|||| (25 toothpicks)
I think that you are mis-counting your toothpicks :).
5d38ab152e1e3e219512a9859fcd93af?d=identicon&s=25 David Chelimsky (Guest)
on 2007-01-28 09:47
(Received via mailing list)
On 1/28/07, Andrey Falko <ma3oxuct@gmail.com> 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!
38d738b4c7b89ab44ad6c0f7d56fb2e4?d=identicon&s=25 Sander Land (Guest)
on 2007-01-28 10:48
(Received via mailing list)
On 1/28/07, David Chelimsky <dchelimsky@gmail.com> 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 <erlercw@gmail.com> 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)
0158871402c1ecfa57952e8a379cfd10?d=identicon&s=25 Daniel Lucraft (lucraft)
on 2007-01-28 13:00
Sander Land 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?
F463fb05733d8ea5a73b5e8db01fbe97?d=identicon&s=25 Waldemar Dick (Guest)
on 2007-01-28 14:28
(Received via mailing list)
Hi,

Andrey Falko 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
24a8cf5c16ccb69ceb7750cec315c77d?d=identicon&s=25 Frank Fischer (Guest)
on 2007-01-28 14:30
(Received via mailing list)
On 2007-01-28, Daniel Lucraft <dan@fluentradical.com> 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
0158871402c1ecfa57952e8a379cfd10?d=identicon&s=25 Daniel Lucraft (lucraft)
on 2007-01-28 15:11
Frank Fischer 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
5d38ab152e1e3e219512a9859fcd93af?d=identicon&s=25 David Chelimsky (Guest)
on 2007-01-28 15: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
38d738b4c7b89ab44ad6c0f7d56fb2e4?d=identicon&s=25 Sander Land (Guest)
on 2007-01-28 15: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')
8222471351de475ccbc18f42350a04d8?d=identicon&s=25 Krishna Dole (Guest)
on 2007-01-28 15: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))

----------------------------------------------
24a8cf5c16ccb69ceb7750cec315c77d?d=identicon&s=25 Frank Fischer (Guest)
on 2007-01-28 15: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
0158871402c1ecfa57952e8a379cfd10?d=identicon&s=25 Daniel Lucraft (lucraft)
on 2007-01-28 16: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
5d38ab152e1e3e219512a9859fcd93af?d=identicon&s=25 David Chelimsky (Guest)
on 2007-01-28 17:41
(Received via mailing list)
On 1/28/07, Sander Land <sander.land@gmail.com> 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.
25ccc253b07d00223a40bfa698f1483d?d=identicon&s=25 Marcel Ward (Guest)
on 2007-01-28 18:05
(Received via mailing list)
On 26/01/07, Ruby Quiz <james@grayproductions.net> 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 Ward   <wardies ^a-t^ gmaildotcom>
# Sunday, 28 January 2007
# Solution for Ruby Quiz 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
E2a9d30a2487a924165aaaa016b54f87?d=identicon&s=25 C Erler (Guest)
on 2007-01-28 20: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]
E2a9d30a2487a924165aaaa016b54f87?d=identicon&s=25 C Erler (Guest)
on 2007-01-28 21: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
E2a9d30a2487a924165aaaa016b54f87?d=identicon&s=25 C Erler (Guest)
on 2007-01-28 21: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
034c4cf05cfad09c66d1b0bc3cb4a6b5?d=identicon&s=25 Andrey Falko (Guest)
on 2007-01-29 04:13
(Received via mailing list)
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"
C515daf003a781a638d8a01e41a935a0?d=identicon&s=25 George Ogata (Guest)
on 2007-01-29 13:31
(Received via mailing list)
On 1/29/07, Sander Land <sander.land@gmail.com> 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.  :-)
5d38ab152e1e3e219512a9859fcd93af?d=identicon&s=25 David Chelimsky (Guest)
on 2007-01-29 16:16
(Received via mailing list)
On 1/29/07, George Ogata <george.ogata@gmail.com> 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
C515daf003a781a638d8a01e41a935a0?d=identicon&s=25 George Ogata (Guest)
on 2007-01-30 12:36
(Received via mailing list)
On 1/30/07, David Chelimsky <dchelimsky@gmail.com> wrote:
> On 1/29/07, George Ogata <george.ogata@gmail.com> wrote:
> > On 1/29/07, Sander Land <sander.land@gmail.com> 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?
25ccc253b07d00223a40bfa698f1483d?d=identicon&s=25 Marcel Ward (Guest)
on 2007-01-31 13:21
(Received via mailing list)
On 28/01/07, Frank Fischer <frank.fischer@s2001.tu-chemnitz.de> 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.
7264fb16beeea92b89bb42023738259d?d=identicon&s=25 Christian Neukirchen (Guest)
on 2007-01-31 22:13
(Received via mailing list)
"George Ogata" <george.ogata@gmail.com> 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.