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.

on 2007-01-26 15:47

on 2007-01-26 16:46

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?

on 2007-01-26 16:57

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

on 2007-01-26 17:19

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

on 2007-01-26 17:23

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

on 2007-01-26 17:44

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

on 2007-01-26 17:47

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

on 2007-01-26 17:48

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

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

on 2007-01-26 21:27

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

on 2007-01-26 21:48

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

on 2007-01-26 21:49

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

on 2007-01-26 21:50

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

on 2007-01-26 22:41

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.

on 2007-01-26 22:47

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

on 2007-01-26 22:52

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

on 2007-01-26 23:07

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

on 2007-01-26 23:13

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?

on 2007-01-26 23:26

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

on 2007-01-27 03:09

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

on 2007-01-27 04:15

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

on 2007-01-27 14:49

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.

on 2007-01-27 20:22

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.

on 2007-01-28 02:17

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

on 2007-01-28 06:23

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

on 2007-01-28 09:06

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

on 2007-01-28 09:14

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)

on 2007-01-28 09:16

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

on 2007-01-28 09:23

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.

on 2007-01-28 10:06

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)

on 2007-01-28 10:24

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

on 2007-01-28 10:47

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!

on 2007-01-28 11:48

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)

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?

on 2007-01-28 15:28

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

on 2007-01-28 15:30

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

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

on 2007-01-28 16:16

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

on 2007-01-28 16:43

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

on 2007-01-28 16:46

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

on 2007-01-28 16:50

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

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

on 2007-01-28 18:41

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.

on 2007-01-28 19:05

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

on 2007-01-28 21:48

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]

on 2007-01-28 22:15

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

on 2007-01-28 22:48

on 2007-01-29 05:13

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"

on 2007-01-29 14:31

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. :-)

on 2007-01-29 17:16

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

on 2007-01-30 13:36

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?

on 2007-01-31 14:21

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.

on 2007-01-31 23:13

"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