Counting Toothpicks (#111)


#1

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/

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


#2

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?


#3

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


#4

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


#5

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


#6

Are minus signs allowed?

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

Krishna


#7

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


#8

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


#9

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


#10

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


#11

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

James Edward G. II


#12

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


#13

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.


#14

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

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

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

thanks a lot,

alexander


#15

On 1/26/07, CHubas removed_email_address@domain.invalid wrote:

  1. 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 :wink:

Robert


#16

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


#17

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

Last I checked it was very hard to bend toothpicks without breaking
them. So your 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 :wink:
l _ _ = 100 (1 toothpick)

Blessings,
TwP


#18

On Jan 26, 2007, at 3:05 PM, Tim P. wrote:

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

Zero toothpicks is represented by printing a “Hug a Tree” message. :wink:

James Edward G. II


#19

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 :wink:
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?


#20

-----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 :wink:
l _ _ = 100 (1 toothpick)

Zero toothpicks is represented by printing a “Hug a Tree” message. :wink:

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