[QUIZ] Countdown (#7)

ruby-talk
1

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.

2

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

3

Ruby Quiz wrote:

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.

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

···

---
target: 522
sources: [100,5,5,2,6,8]
....

4

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

James Edward Gray II

···

On Nov 12, 2004, at 8:19 AM, Ruby Quiz wrote:

  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

5

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

6

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

···

--
Brian Schröder
http://www.brian-schroeder.de/

7

That's how I read it.

James Edward Gray II

···

On Nov 12, 2004, at 10:47 AM, Brian Schröder wrote:

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

8

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

James Edward Gray II

···

On Nov 12, 2004, at 5:33 PM, Hans Fugal wrote:

Ruby Quiz wrote:

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.

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

9

James Edward Gray II wrote:

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 Numbers Game Solver FAQ - crossword tools .com - Online tools for crosswords and more )

daz

10

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

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

···

On Sun, 14 Nov 2004 02:48:14 +0900 "Florian G. Pflug" <fgp@phlo.org> wrote:

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
http://www.brian-schroeder.de/

11

Brian Schröder wrote:

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.

That's a nice solution, but reading through the code I have one question regarding the memoized version:

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

Shouldn't each_term_over call the block for each term when the terms for this set of sources was already generated before as well? Now it just returns the terms but each_term_over itself just ignore the return value. But maybe I just didn't understand the code correctly, after all, it appears to work well (although using too much memory on my machine :wink:

12

On Mon, Nov 15, 2004 at 03:25:54AM +0900, Brian Schr?der scribed:

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.

   Sounds like my solution, which is appended below, is
pretty similar. The only cleverness in it is doing things
pairwise to easily eliminate commutativity when possible. The
code is a little opaque - sorry. :slight_smile: Typically finds a solution within
12 seconds if you use the memoization, and 120 seconds if you
don't. I have another version that uses less memory by more
aggressively pruning the space, but because it does more tests,
it actually ends up being a little slower. Oops.

  Usage: quiz.rb [-m] [target] [val1] [val2] ... [valn]

I don't suggest running it with more than 6 sub-values, however,
unless you're really patient. the runtime is roughly:

   6^5 * 6*5 * 5*4 * 4*3 * 3*2 * 2*1

It's not elegant, but it works. I do apologize profusely
for my terribly lame use of "raise" to exit early from the
processing loop. But it saved a lot of typing. :slight_smile:

   -Dave

#!/usr/local/bin/ruby

# The exit from the processing loop is a little ugly. Would be
# better to cascade the return values, but that required more
# tests. :wink:

···

#
# Use with "-m" to memoize parts of the solution space and avoid
# duplicate configurations. Requires about 14 megs of ram; runs
# about 10x faster.

raise "usage: quiz.rb [-m] [target] [source1] [source2] ...\n" if ARGV.length < 2

$lots_of_memory = ARGV.delete("-m")
target, *source = ARGV.map { |a| a.to_i }

$closest_diff = target
$closest_stack = nil
$nodupes = Hash.new if $lots_of_memory
$itercount = 0

def fs(stack, target, source)
  $itercount += 1
  recent = source[-1]
  raise "#{stack[-1]}" if (recent == target)
  return false if recent == 0
  if ($lots_of_memory)
    wholeid = source.sort.join(" ")
    return false if ($nodupes.has_key?(wholeid))
    $nodupes[wholeid] = true
  end
  if (recent - target).abs < $closest_diff
    $closest_diff = (recent - target).abs
    $closest_stack = stack[-1]
  end
  return false if (source.length == 1)
  i = j = ns = nt = ival = istack = jval = jstack = myid = 0
  observed = Hash.new
  (0...source.length).each do |i|
    ival, istack = source[i], stack[i]
    (i+1...source.length).each do |j|
      jval, jstack = source[j], stack[j]
      # Linear space duplicate suppression is cheap; use always
      myid = (ival < jval) ? "#{ival}-#{jval}" : "#{jval}-#{ival}"
      next if (observed[myid])
      observed[myid] = true
      ns = source[0...i] + source[i+1...j] + source[j+1..-1]
      nt = stack[0...i] + stack[i+1...j] + stack[j+1..-1]
      fs(nt + ["(#{istack} + #{jstack})"], target, ns + [ival + jval])
      if (ival != jval)
        fs(nt + ["(#{istack} - #{jstack})"], target, ns + [ival - jval])
        fs(nt + ["(#{jstack} - #{istack})"], target, ns + [jval - ival])
      end
      if (ival != 1 && jval != 1)
        fs(nt + ["(#{istack} * #{jstack})"], target, ns + [ival * jval])
        if (0 == (ival % jval))
    fs(nt + ["(#{istack} / #{jstack})"], target, ns + [ival / jval])
        end
        if (0 == (jval % ival))
    fs(nt + ["(#{jstack} / #{istack})"], target, ns + [jval / ival])
        end
      end
    end
  end
end

begin
  raise "Source contains target." if source.include? target
  fs(source.dup, target, source)
  p $closest_stack
rescue => err
  print "Done: #{err}\n"
ensure
  print "Itercount: #{$itercount}\n"
end

13

James Edward Gray II wrote:

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

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

···

On Nov 12, 2004, at 10:47 AM, Brian Schröder wrote:

14

My Program found

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

is this not a solution?

Thanks,

Brian

···

On Sat, 13 Nov 2004 15:23:24 +0900 "daz" <dooby@d10.karoo.co.uk> wrote:

James Edward Gray II wrote:
>
> 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.

--
Brian Schröder
http://www.brian-schroeder.de/

15

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

···

On Sun, 14 Nov 2004 03:27:22 +0900 Brian Schröder <ruby@brian-schroeder.de> wrote:

On Sun, 14 Nov 2004 02:48:14 +0900 > "Florian G. Pflug" <fgp@phlo.org> wrote:

[snip]

Regards,

Brian

--
Brian Schröder
http://www.brian-schroeder.de/

--
Brian Schröder
http://www.brian-schroeder.de/

16

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

Real nastiness here:
Numbers Game Solver - crossword tools .com - Online tools for crosswords and more

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

James Edward Gray II

···

On Nov 13, 2004, at 12:23 AM, daz wrote:

17

Brian Schröder wrote:

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

18

each_term_over calls the block once for each unique term it generates. When a set of terms is already memoized, the block has been called for each of the terms in the set, so it is not neccessary to call it again.

This additionally speeds up the process.

Regards,

Brian

···

On Mon, 15 Nov 2004 04:08:22 +0900 Dennis Ranke <dennis.ranke@epost.de> wrote:

Brian Schröder wrote:
> 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.

That's a nice solution, but reading through the code I have one question
regarding the memoized version:

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

Shouldn't each_term_over call the block for each term when the terms for
this set of sources was already generated before as well? Now it just
returns the terms but each_term_over itself just ignore the return
value. But maybe I just didn't understand the code correctly, after all,
it appears to work well (although using too much memory on my machine :wink:

--
Brian Schröder
http://www.brian-schroeder.de/

19

Just FYI, Ruby's catch/throw is probably a good choice here. It should work just like your exception throw, but is probably better style.

Nice solution.

James Edward Gray II

···

On Nov 14, 2004, at 3:21 PM, David G. Andersen wrote:

# The exit from the processing loop is a little ugly. Would be
# better to cascade the return values, but that required more
# tests. :wink:

20

Absolutely.

James Edward Gray II

···

On Nov 12, 2004, at 12:26 PM, James Britt wrote:

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

100 + 1

True?