[QUIZ] Countdown (#7)

[Ruby Quiz]

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.grayproductions.net/ruby_quiz/

3. Enjoy!

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

by Brian Candler

One of the longest-running quiz shows on UK TV is called Countdown, and has
a "numbers round". There are some cards laid face down in front of the host
- the top row contains 'large' numbers (from the set 25, 50, 75, 100), and
the rest are 'small' (1 to 10). Six cards are picked and displayed: the
choice is made by one of the contestants, who typically will ask for one
large number and five small ones.

Next, a machine called "Cecil" picks a target number between 100 and 999 at
random. The contestants then have 30 seconds to find a way of combining the
source numbers using the normal arithmetic operators (+, -, *, /) to make
the target number, or to get as close as possible.

Each source card can be used no more than once. The same applies to any
intermediate results, although of course you don't have to explicitly show
the intermediate results.

Example: source 100 5 5 2 6 8, target 522

100 * 5 = 500
5 + 6 = 11
11 * 2 = 22
500 + 22 = 522

or more succinctly, (5*100)+((5+6)*2) = 522

Another solution is (100+6)*5-8 = 522

Normal arithmetic rules apply, and in particular you are not allowed to use
integer rounding. That is, 7 divided by 3 is 2 1/3, not 2.

The quiz is to write a program which will accept one target number and a
list of source numbers, and generate a solution which calculates the target
or a number as close to the target as possible.

 

[Brian Schröder]

Next, a machine called "Cecil" picks a target number between 100 and 999 at

random. The contestants then have 30 seconds to find a way of combining the
source numbers using the normal arithmetic operators (+, -, *, /) to make
the target number, or to get as close as possible.

Each source card can be used no more than once.

I suspect that this means, each may (not be used or used exactly once)?

Regards,

Brian

 

[James Edward Gray II]

I suspect that this means, each may (not be used or used exactly once)?

That's how I read it.

James Edward Gray II

 

[James Britt]

That's how I read it.

James Edward Gray II

So, if the target is 101, and among your numbers are 100 and 1, an
acceptable answer would be

100 + 1

True?


James

 

[James Edward Gray II]

So, if the target is 101, and among your numbers are 100 and 1, an
acceptable answer would be

100 + 1

True?

Absolutely.

James Edward Gray II

 

[James Edward Gray II]

Is the input interactive, or whitespace-delimited, or what? YAML
perhaps?

The quiz didn't specify an input format. Personally, I'm using
command-line arguments. That seems pretty easy to me, but use whatever
you like.

Just don't make it too hard on me come testing time, please.

James Edward Gray II

 

[James Edward Gray II]

Example: source 100 5 5 2 6 8, target 522

100 * 5 = 500
5 + 6 = 11
11 * 2 = 22
500 + 22 = 522

or more succinctly, (5*100)+((5+6)*2) = 522

Another solution is (100+6)*5-8 = 522

Anyone find a tricky example? I doubt my algorithm, but I can't find
the right test to topple it.

James Edward Gray II

 

[daz]

Anyone find a tricky example? I doubt my algorithm, but I can't find
the right test to topple it.

Target: 926
-------------------------------
Selection: 75 2 8 5 10 10
-------------------------------

p (75 - 5 + 8) * (2 + 10) - 10 #-> 926

This is the only solution and is difficult to find.

-----

Real nastiness here:
http://www.crosswordtools.com/numbers-game/?n1=25&n2=6&n3=3&n4=3&n5=7&n6=50&target=712

( this, and others, described in http://www.crosswordtools.com/numbers-game/faq.php )


daz

 

[Brian Schröder]

Target: 926
-------------------------------
Selection: 75 2 8 5 10 10
-------------------------------

p (75 - 5 + 8) * (2 + 10) - 10 #-> 926

This is the only solution and is difficult to find.

My Program found

((((75.0 - (2.0 / 5.0)) + 8.0) + 10.0) * 10.0) = 926.0

is this not a solution?

Thanks,

Brian

 

[daz]

My Program found

((((75.0 - (2.0 / 5.0)) + 8.0) + 10.0) * 10.0) = 926.0

is this not a solution?

It's not allowed in the television game:

"... all the steps to the solution must be whole numbers.
e.g. You cannot start by dividing 7 by 5 and then use
1.4 in subsequent steps."


Nevertheless, I look forward to seeing your program.
If you leave it to find "all" possible solutions,
this should be 1.0 of them.

(75.0 - 5.0 + 8.0) * (2.0 + 10.0) - 10.0 #-> 926.0




daz

 

[James Edward Gray II]

It's not allowed in the television game:

"... all the steps to the solution must be whole numbers.
e.g. You cannot start by dividing 7 by 5 and then use
1.4 in subsequent steps."

This is interesting information, especially to someone like me who is
not familiar with the game show. To be fair, it was not mentioned in
the quiz, that I can see.

James Edward Gray II

 

[Brian Schröder]

This is interesting information, especially to someone like me who is
not familiar with the game show. To be fair, it was not mentioned in
the quiz, that I can see.

James Edward Gray II

Even the opposite applies:

From the quiz:

Normal arithmetic rules apply, and in particular you are not allowed to >use integer rounding. That is, 7 divided by 3 is 2 1/3, not 2.

I conlude from this, that it is allowed to calculate using fractions.

I think it is really interesting to see, that in this quiz as in the real world a perfect specification is only achievable with an unproportional amount of work. So that is where the classic waterfall modell has its weakness. /Lets all programm pragmatically, and include feedback/ .

Regards,

Brian

 

[Florian G. Pflug]

Hi

I just starten thinking about an algorithm to solve this - and I
stumbled upon the following:

The "Countdown"-Quiz kind of a generalization of a Knapsack-Problem,
isn't it? If I recall correctly, solving a Knapsack means to find
a way to construct a given number by chosing which numbers (from a given
set) to _sum_ up - or did I mix this up with something else?

If a further recall correctly that solving a general Knapsack is
NP-hard, the Countdown-Quit is NP-hard too, isn't it?

I'd appreciate any comment on this.

Greetings, Florian Pflug

 

[Brian Schröder]

Hi

I just starten thinking about an algorithm to solve this - and I
stumbled upon the following:

The "Countdown"-Quiz kind of a generalization of a Knapsack-Problem,
isn't it? If I recall correctly, solving a Knapsack means to find
a way to construct a given number by chosing which numbers (from a given
set) to _sum_ up - or did I mix this up with something else?

If a further recall correctly that solving a general Knapsack is
NP-hard, the Countdown-Quit is NP-hard too, isn't it?

I'd appreciate any comment on this.

Greetings, Florian Pflug

Knapsack is a maximization problem.

You have objects o_i = (v_i, w_i) with a value v_i and a weight w_i.

Your Knapsack is limited to a total weight of 1.0.

Now choose a subset S of the objects, such that \sum_{o_i\in S} v_i is maximized.

It is true that this is np-hard.

Countdown is no direct superset of knapsack, but I'm shure its reductible on it.

It is possible to approximate knapsack (see scaled knapsack). But in this case we have a fixed and low number of cards, so it is possible to simply take on the combinatorial explosion and enumerate every solution.

One could also try to find an approximate solution, but those will be harder for JEGII to test automatically

The simplest implementation that uses only constant memory takes around three minutes for six cards on my machine.

A more memory intensive version can do this in about half to third of the time.

Regards,

Brian

 

[Brian Schröder]

Hi

I just starten thinking about an algorithm to solve this - and I
stumbled upon the following:

The "Countdown"-Quiz kind of a generalization of a Knapsack-Problem, >

[snip]
Countdown is no direct superset of knapsack, but I'm shure its reductible on it.

Should have been Knapsack is reductible on countdown. (It seems impossible, not to make this error

[snip]

Regards,

Brian

 

[James Edward Gray II]

Target: 926
-------------------------------
Selection: 75 2 8 5 10 10
-------------------------------

p (75 - 5 + 8) * (2 + 10) - 10 #-> 926

This is the only solution and is difficult to find.

This example is ruining my day. Thanks a lot.

Real nastiness here:
http://www.crosswordtools.com/numbers-game/?
n1=25&n2=6&n3=3&n4=3&n5=7&n6=50&target=712

Well, that thing's sure zippy, isn't is?

James Edward Gray II

 

[Steven Jenkins]

It is possible to approximate knapsack (see scaled knapsack). But in
this case we have a fixed and low number of cards, so it is possible to
simply take on the combinatorial explosion and enumerate every solution.

The simplest implementation that uses only constant memory takes
around three minutes for six cards on my machine.

I need a faster computer or a faster brain. I've got a brute force
algorithm that appears to work, but it won't complete in anything like
three minutes.

I guess I won't reveal the number until tomorrow, but my count of the
distinct calculation expressions you can form with six numbers and four
operators (not accounting for commutativity) is uhh... big.

Steve

 

[Dennis Ranke]

I need a faster computer or a faster brain. I've got a brute force
algorithm that appears to work, but it won't complete in anything like
three minutes.

I expect this quiz to yield a great amount of different solutions and
I'm already looking forward to seeing the first of them tomorrow.
Choosing different approaches will result in wildly differing runtimes,
as I have found out myself.
My first try took about one hour (intelligent guess, i never let it run
that long) in the worst case (ie. when there was no exact solution). My
new implementation takes... well... a bit less...

 

[David G. Andersen]

I need a faster computer or a faster brain. I've got a brute force
algorithm that appears to work, but it won't complete in anything like
three minutes.

3 minutes is doable - you'll get it. Mine takes either 110 seconds
or 11 seconds depending on the setting of the magic option that
might be a spoiler to talk about. The difference between my
implementation's time and the previous poster's is probably due
more to machine speed differences than anything.

I guess I won't reveal the number until tomorrow, but my count of the
distinct calculation expressions you can form with six numbers and four
operators (not accounting for commutativity) is uhh... big.

It's probably not giving too much away to say that the number is
still expressable as 32-bit integer.

Now if only I could figure out how to make the code more
elegant. This is a terrible time-suck!

-Dave

 

[Brian Schröder]

Hello Group,

This was quite an interesting quiz. I tried different solutions of varying complexity, but it turned out that the simplest approach worked best.

The problem is exponential in the number of source cards. It is solvable for six cards, but this algorithm is not a general solution for an arbitrary number of cards.

I recursively generate each possible term, and evaluate it. In my recursive generation process, each subterm is generated multiple times, so I used optional memoization to speed up the search. An exhaustive search takes around 300s without and 110s with memoization, but memoization uses a lot of ram.

If you only need one solution, it is usually found within 20s.

The full programm with commandline parsing and different implementations - Integer-Only vs. Float
- Brute Force vs. Memoization

can be found at:

http://ruby.brian-schroeder.de/quiz/

There is also a only version, that solves a random problem.

Following are the main routines of the program:

The Term structure is a direct implementation of the term-tree:

# Node of a Term Tree.
class Term
attr_reader :left, :right, peration

def initialize(left, right, operation)
@left = left
@right = right
@operation = operation
end

def to_s
"(#{@left} #{operation} #{@right})"
end

def value
@value || (@value = (@left.value).send(@operation, (@right.value)))
end

def ==(o)
return false unless o.is_a?Term
to_s == o.to_s
end
end

The methods I use to create all the terms are:

Brute Force:
def Integral.each_term_over(source)
if source.length == 1
yield source[0]
else
source.each_partition do | p1, p2 |
each_term_over(p1) do | op1 |
yield op1
each_term_over(p2) do | op2 |
yield op2
if op2.value != 0
yield Term.new(op1, op2, :+)
yield Term.new(op1, op2,
yield Term.new(op1, op2, :'/') if op2.value != 1 and op1.value % op2.value == 0
end
if op1.value != 0
yield Term.new(op2, op1,
if op1.value != 1
yield Term.new(op2, op1, :'/') if op2.value % op1.value == 0
yield Term.new(op1, op2, :*) if op2.value != 0 and op2.value != 1
end
end
end
end
end
end
end

With Memoization:

def Integral.each_term_over(source, memo = {}, &block)
return memo[source] if memo[source]

result = []
if source.length == 1
result << source[0]
else
source.each_partition do | p1, p2 |
each_term_over(p1, memo, &block).each do | op1 |
each_term_over(p2, memo, &block).each do | op2 |
if op2.value != 0
result << Term.new(op1, op2, :+)
result << Term.new(op1, op2,
result << Term.new(op1, op2, :'/') if op2.value != 1 and op1.value % op2.value == 0
end
if op1.value != 0
result << Term.new(op2, op1,
if op1.value != 1
result << Term.new(op2, op1, :'/') if op2.value % op1.value == 0
result << Term.new(op1, op2, :*) if op2.value != 0 and op2.value != 1
end
end
end
end
end
end

result.each do | term | block.call(term) end
memo[source] = result
end


# Extending Array with simple set functions
class Array
# Returns each true partition (containing no empty set) exactly once.
def each_partition
return nil if empty?
head, *tail = *self
tail._each_partition do | subset, rest |
yield [subset.unshift(head), rest] unless rest.empty?
end
end

protected
# Returns each partition twice, as (s1, s2) and (s2, s1)
def _each_partition
if empty?
yield([], [])
return nil
end
head, *tail = *self
tail._each_partition do | s1, s2 |
yield([head] + s1, s2)
yield(s1, [head] + s2)
end
end
end