Asp Forum - [QUIZ] Getting to 100 (#119

James Gray

4/6/2007 12:56:00 PM

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

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.

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

by Gavin Kistner

The NPR show "Car Talk" has regular quizzes that they call "Puzzlers"[1]. The
one listed on their web site for March 12th[2] is titled "Getting to 100". In
the quiz, you are supposed to write down the digits 1-9 in order, followed by "
= 100", and then insert between them two minus symbols and one plus symbol (in
any order) to make the formula correct. You aren't allowed to re-arrange digits,
or do some toothpick math like combine two minus signs to make a plus. You must
use every digit, and all three operators. For example, here's one incorrect
solution:

123 + 45 - 67 - 89 = 100 (This is an incorrect formula; it totals 12)

The quiz, then, is to solve this problem without thinking, instead letting the
computer think for you. Your program should output every possible equation that
can be formed, and the actual result of that equation. The equation that results
in 100 should have stars around it. At the end, you should print out the number
of formulae that were possible. Here's an excerpt of some example output:

...
12 - 34 - 567 + 89 = -500
12 - 34 + 567 - 89 = 456
12 + 34 - 567 - 89 = -610
************************
123 - 45 - 67 + 89 = 100
************************
123456 - 7 - 8 + 9 = 123450
123456 - 7 + 8 - 9 = 123448
123456 + 7 - 8 - 9 = 123446
...
168 possible equations tested

You should not print the same equation more than once. ("1 - 2 - 3 + 456789" is
the same as "1 - 2 - 3 + 456789", even if the computer thinks that the two minus
symbols come in a different order.)

Extra Credit: Write your program to accept an arbitrary number and ordering of
digits, an arbitrary set of operators (but allowing the same operator more than
once), and an arbitrary target number that the equation is supposed to evaluate
to.

[1] 2007 Puzzler Index: http://www.cartalk.com/content/puzzler...
[2] http://www.cartalk.com/content/puzzler/transcripts/200711/...

54 Answers

Robert Dober

4/6/2007 1:32:00 PM

On 4/6/07, Ruby Quiz <james@grayproductions.net> wrote:
> 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.rub...
>
> 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.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
> by Gavin Kistner
>
> The NPR show "Car Talk" has regular quizzes that they call "Puzzlers"[1]. The
> one listed on their web site for March 12th[2] is titled "Getting to 100". In
> the quiz, you are supposed to write down the digits 1-9 in order, followed by "
> = 100", and then insert between them two minus symbols and one plus symbol (in
> any order) to make the formula correct. You aren't allowed to re-arrange digits,
> or do some toothpick math like combine two minus signs to make a plus. You must
> use every digit, and all three operators. For example, here's one incorrect
> solution:
>
> 123 + 45 - 67 - 89 = 100 (This is an incorrect formula; it totals 12)
>
> The quiz, then, is to solve this problem without thinking, instead letting the
> computer think for you. Your program should output every possible equation that
> can be formed, and the actual result of that equation. The equation that results
> in 100 should have stars around it. At the end, you should print out the number
> of formulae that were possible. Here's an excerpt of some example output:
>
> ...
> 12 - 34 - 567 + 89 = -500
> 12 - 34 + 567 - 89 = 456
> 12 + 34 - 567 - 89 = -610
> ************************
> 123 - 45 - 67 + 89 = 100
> ************************
> 123456 - 7 - 8 + 9 = 123450
> 123456 - 7 + 8 - 9 = 123448
> 123456 + 7 - 8 - 9 = 123446
> ...
> 168 possible equations tested
>
> You should not print the same equation more than once. ("1 - 2 - 3 + 456789" is
> the same as "1 - 2 - 3 + 456789", even if the computer thinks that the two minus
> symbols come in a different order.)
>
> Extra Credit: Write your program to accept an arbitrary number and ordering of
> digits, an arbitrary set of operators (but allowing the same operator more than
> once)

sorry for being picky but I guess it might be useful
- an arbitrary set of operators
+ an array of operators that can come in any order
hopefully somebody will find the correct formal expression to describe
the beast ...
, and an arbitrary target number that the equation is supposed to evaluate
> to.
>
> [1] 2007 Puzzler Index: http://www.cartalk.com/content/puzzler...
> [2] http://www.cartalk.com/content/puzzler/transcripts/200711/...
>
>
For the rest sounds like fun.

Cheers
Robert

--
You see things; and you say Why?
But I dream things that never were; and I say Why not?
-- George Bernard Shaw

James Gray

4/6/2007 1:47:00 PM

On Apr 6, 2007, at 8:32 AM, Robert Dober wrote:

> sorry for being picky but I guess it might be useful
> - an arbitrary set of operators
> + an array of operators that can come in any order
> hopefully somebody will find the correct formal expression to describe
> the beast ...
> , and an arbitrary target number that the equation is supposed to
> evaluate

We had that quiz, though this one is definitely similar:

http://www.rubyquiz.com/...

James Edward Gray II

Kyle Schmitt

4/6/2007 6:11:00 PM

OK only 43 hours to go...

Stupid non spoiler rule

Gavin Kistner

4/6/2007 6:27:00 PM

On Apr 6, 12:11 pm, "Kyle Schmitt" <kyleaschm...@gmail.com> wrote:
> OK only 43 hours to go...
>
> Stupid non spoiler rule

Did you get all the extra credit already?

Kyle Schmitt

4/6/2007 6:42:00 PM

Everything but the arbitrary ordering and number of digits.

And it can run in O(n) time
;)

Carlos

4/6/2007 7:54:00 PM

[Ruby Quiz <james@grayproductions.net>, 2007-04-06 14.55 CEST]
[...]
> The NPR show "Car Talk" has regular quizzes that they call "Puzzlers"[1]. The
> one listed on their web site for March 12th[2] is titled "Getting to 100". In
> the quiz, you are supposed to write down the digits 1-9 in order, followed by "
> = 100", and then insert between them two minus symbols and one plus symbol (in
> any order) to make the formula correct. You aren't allowed to re-arrange digits,
> or do some toothpick math like combine two minus signs to make a plus. You must
> use every digit, and all three operators.

Can the plus and minus symbols be used as unary operators?

--

Gavin Kistner

4/6/2007 8:55:00 PM

On Apr 6, 1:53 pm, Carlos <a...@quovadis.com.ar> wrote:
> [Ruby Quiz <j...@grayproductions.net>, 2007-04-06 14.55 CEST]
> [...]
>
> > The NPR show "Car Talk" has regular quizzes that they call "Puzzlers"[1]. The
> > one listed on their web site for March 12th[2] is titled "Getting to 100". In
> > the quiz, you are supposed to write down the digits 1-9 in order, followed by "
> > = 100", and then insert between them two minus symbols and one plus symbol (in
> > any order) to make the formula correct. You aren't allowed to re-arrange digits,
> > or do some toothpick math like combine two minus signs to make a plus. You must
> > use every digit, and all three operators.
>
> Can the plus and minus symbols be used as unary operators?

Not as described, in the original quiz, but I'd say...sure! :) It
would require that it either be applied before the first digit:
-12345 - 67 + 89
or after another operator:
123 + -45 -6789
but I don't see any reason to disallow that sort of extra logic if you
want to do it.

Sebastian Hungerecker

4/6/2007 9:07:00 PM

Phrogz wrote:
> On Apr 6, 1:53 pm, Carlos <a...@quovadis.com.ar> wrote:

> > Can the plus and minus symbols be used as unary operators?
> [...]
> but I don't see any reason to disallow that sort of extra logic if you
> want to do it.

Well, one reason would be that using a plus as a unary operator is the
same as not using it at all, so that would allow you to circumvent the
use-all-operators-rule.

--
Ist so, weil ist so
Bleibt so, weil war so

Rubén Medellín

4/7/2007 5:39:00 AM

James Gray wrote:
> The three rules of Ruby Quiz:
>

Yay. I remember doing this exercise in math class back there in
secondary school. Not to be conceited, but I remember having so much fun
with that I tried some variations on the exercise, finding around 200
solutions or so. But, of course, I', crazy :D

I want to suggest some extra credits for all those crazy people put
there ;D

- You can use parenthesis to change precedence of operators (if you use
ore than addition and subtraction)
- You can use decimal dot in numbers. As for example: .1 - 2 + (3 * 4) +
5 + 6 + 78.9 = 100
- Given the set of numbers, rules and operations, say if it can yield
all numbers on a given range, or try to find the largest range possible.

Certainly I love these quizes. =D

--
Posted via http://www.ruby-....

Rick DeNatale

4/8/2007 1:55:00 PM

Here's my solution. It handles both extra credit suggestions, and
adds control over the verbosity of the output, and some options for
finding 'interesting' inputs.

I found this quiz rather easy. I had a basic solution in about 15
minutes, and spent about another half hour or so generalizing it.

The main problem was partitioning the string of digits in order to
place the operators. I did this with a recursive method on String
which iterates over the possible partitionings using block
composition.

In order to generalize the inputs I used Florian Frank's permutation
gem to get the permutations of the operators.

require 'rubygems'
require 'permutation'

class String

# yield each partitioning of the receiver into count partitions
#
# This is a recursive implementation using composition of the block argument.
#
# The approach is to iteratively split the string into two parts,
# an initial substring of increasing length, and the remainder.
# For each initial substring we yield an array which is the concatenation
# of the initial substring and the partitioning of the remainder of
the string # into count-1 partitions.
def each_partition(count, &b)
# if the count is 1 then the only partition is the entire string.
if count == 1
yield [self]
else
# Iterate over the initial substrings, the longest initial
substring must leave
# at least count-1 characters in the remaining string.
(1..(size-(count-1))).each do |initial_size|
self[initial_size..size].each_partition(count-1) {|remaining|
b.call([self[0,initial_size]] + remaining)}
end
end
end
end

# print combinations of digits and operators which evaluate to a goal
#
# Arguments are supplied by a hash the keys are:
#
# Main arguments
# :goal - the number being sought, default is 100
# :digits - a string of digits, default is "123456789"
# :ops - an array of strings representing the operators to be inserted into
# digits, default is %w[- - +]
#
# Additional arguments
# :verbose - unless false, print all attempts, default is false
# :return_counts - unless false, return an array of value, count arrays for
# values with multiple solutions, used to find interesting
# inputs, default is false
def get_to(options={})
options = {
:goal => 100,
:digits => '123456789',
:ops => %w[- - +],
:verbose => false,
:return_counts => false
} .merge(options)
digits= options[:digits]
goal, digits, ops, verbose, return_counts =
*options.values_at(:goal, :digits, :ops, :verbose, :return_counts)
operators = Permutation.for(ops).map{|perm| perm.project}.uniq
puts "Looking for #{goal}, digits=#{digits}, operators=#{ops.inspect}"
counts = Hash.new(0)
found_in_a_row = 0
digits.each_partition(ops.size + 1) do |numbers|
operators.each do |ops|
op_index = -1
eqn = numbers.zip(ops).flatten.compact.join(' ')
val = eval(eqn)
counts[val] += 1 if return_counts
found = val == goal
puts "********************************" if found_in_a_row == 0 && found
puts "********************************" unless found_in_a_row ==
0 || found
puts "#{eqn} = #{val}" if verbose || goal == val
found_in_a_row = found ? found_in_a_row + 1 : 0
end
end
return_counts ? counts.select {|key,value| value > 1} : nil
end

get_to
get_to(:verbose=> true)
get_to(:goal => 357, :ops => %w[+ - +], :verbose=> true)
get_to(:goal => 302, :digits => '987654321')
get_to(:goal => 98, :verbose => true)
p get_to(:goal => 336)
get_to(:goal => -355)

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denh...

comp.lang.ruby

[QUIZ] Getting to 100 (#119

James Gray

Robert Dober

James Gray

Kyle Schmitt

Gavin Kistner

Kyle Schmitt

Carlos

Gavin Kistner

Sebastian Hungerecker

Rubén Medellín

Rick DeNatale

x Login to ForumsZone