NAME

OddBall - solve the ``Odd Ball Challenge'', perlmonks node 469482


SYNOPSIS

 ./odd_ball          # Solve the 12 ball with 3 weighings puzzle.
 ./odd_ball numbers  # Print puzzle numbers without searching.

or

 ./odd_ball 13 3     # Try 13 balls, 3 weighings; report failure.
 ./odd_ball 16 4     # Find answer for 16 ball, 4 weighings.
 ./odd_ball 24 4     # Run out of memory and crash.


CHALLENGE

 From http://perlmonks.org/index.pl?node_id=469482 :
   There is a well known riddle as follows:
     You are presented with 12 balls identical in appearance 
     but 1 of the 12 is either heavier or lighter than the other 11.
     Your task is to identify which is the odd ball and whether 
     if it is heavy or light. You're only allowed to make 3 
     weighings using a balance.
   Challenge:
     Start out not knowing how to solve the riddle 
     and write code that tells you how.


OUTPUT

 ./odd_ball
 Searching for odd ball in 12 balls with 3 weighings ...
   '' : at node=1 
      ... 1 partitions (4 L's, 0 different)
       'b' : at node=2 
          ... 11 partitions (1 L's, 4 different)
          ... 32 partitions (2 L's, 4 different)
           'bb' : at node=3 
              ... 2 partitions (1 L's, 1 different)
           'bl' : at node=7 
              ... 7 partitions (1 L's, 3 different)
           'br' : at node=11 
              ... 7 partitions (1 L's, 3 different)
       'l' : at node=15 
          ... 443 partitions (2 L's, 8 different)
          ... 37 partitions (1 L's, 8 different)
          ... 1610 partitions (3 L's, 8 different)
           'lb' : at node=16 
              ... 4 partitions (1 L's, 2 different)
           'll' : at node=20 
              ... 7 partitions (1 L's, 3 different)
           'lr' : at node=24 
              ... 7 partitions (1 L's, 3 different)
       'r' : at node=28 
          ... 443 partitions (2 L's, 8 different)
          ... 37 partitions (1 L's, 8 different)
          ... 1610 partitions (3 L's, 8 different)
           'rb' : at node=29 
              ... 4 partitions (1 L's, 2 different)
           'rl' : at node=33 
              ... 7 partitions (1 L's, 3 different)
           'rr' : at node=37 
              ... 7 partitions (1 L's, 3 different)
 done.  Solution found after 40 nodes and 2147 partitions.
 In what follows, (L,R,o) means 'Left', 'Right', and 'off scale',
 and (b,l,r) mean 'balanced', 'left tilt', and 'right tilt'.
 start => [ L L L L R R R R o o o o ]
     b => [ R o o o o o o o L L R o ]
     l => [ L R o o L L R R o o o o ]
     r => [ L L R R L R o o o o o o ]
    bb => [ R o o o o o o o o o o L ]
    bl => [ o o o o o o o o L R o o ]
    br => [ o o o o o o o o L R o o ]
    lb => [ o o L R o o o o o o o o ]
    ll => [ o o o o o o L R o o o o ]
    lr => [ o o o o L R o o o o o o ]
    rb => [ o o o o o o L R o o o o ]
    rl => [ o o L R o o o o o o o o ]
    rr => [ L R o o o o o o o o o o ]
   bbl => ball 12 is heavy.
   bbr => ball 12 is light.
   blb => ball 11 is light.
   bll => ball 9 is heavy.
   blr => ball 10 is heavy.
   brb => ball 11 is heavy.
   brl => ball 10 is light.
   brr => ball 9 is light.
   lbl => ball 3 is heavy.
   lbr => ball 4 is heavy.
   llb => ball 1 is heavy.
   lll => ball 8 is light.
   llr => ball 7 is light.
   lrb => ball 2 is heavy.
   lrl => ball 6 is light.
   lrr => ball 5 is light.
   rbl => ball 7 is heavy.
   rbr => ball 8 is heavy.
   rlb => ball 5 is heavy.
   rll => ball 4 is light.
   rlr => ball 3 is light.
   rrb => ball 6 is heavy.
   rrl => ball 2 is light.
   rrr => ball 1 is light.
 Double check : 
  scenario 0 gives rrr => 0 : OK
  scenario 1 gives rrl => 1 : OK
  scenario 2 gives rlr => 2 : OK
  scenario 3 gives rll => 3 : OK
  scenario 4 gives lrr => 4 : OK
  scenario 5 gives lrl => 5 : OK
  scenario 6 gives llr => 6 : OK
  scenario 7 gives lll => 7 : OK
  scenario 8 gives brr => 8 : OK
  scenario 9 gives brl => 9 : OK
  scenario 10 gives blb => 10 : OK
  scenario 11 gives bbr => 11 : OK
 Looks good.


DESCRIPTION

The following is mustly just thinking out loud, so feel free to skip ahead to whatever part of the code seems appropriate. The execution starts in the ``Main'' section, if that helps.

First, any one of 12 balls may be heavier or lighter than the others, so there are 24 different scenarios that the program is to decide between.

Since each of the 3 weighings gives one of 3 results, we have a tree of possible outcomes :

                                 |
                                [1]
            +--------------------+--------------------+
            |balanced            |left                |right
            |                    |                    |
           [2]                  [3]                  [4]
     +------+------+      +------+------+      +------+------+     
     |b     |l     |r     |b     |l     |r     |b     |l     |r
     |      |      |      |      |      |      |      |      |
    [5]    [6]    [7]    [8]    [9]    [A]    [B]    [C]    [D]
   +-+-+  +-+-+  +-+-+  +-+-+  +-+-+  +-+-+  +-+-+  +-+-+  +-+-+
   b l r  b l r  b l r  b l r  b l r  b l r  b l r  b l r  b l r

A strategy for weighing the balls will partition them into groups at each node, specifiying which balls go on the left and right pans depending on the results of the previous weighings.

For a given strategy (the ball partitions at each node), the 24 scenarios will filter through the tree, taking various paths to the bottom (e.g. (b,b,b), (l,b,r), (l,r,l), ...), and end up distributed across the 27 bottom branches.

A solution to the puzzle needs to avoid putting any two scenarios in the same bottom node; otherwise, the correct ball and its weight is not uniquely determined. Therefore all we need is search the strategies for those with this property. The search here isn't looking for a single node, but for a property of the whole tree.

The numbers turn out like this.

  Puzzle Numbers
  With 12 balls there are 2*12 = 24 scenarios.
  Balls are weighed 3 times, so the number of outcomes is 3**3 = 27.
  (No solution is possible when outcomes < scenarios.)
  The number of nodes in the tree is { sum(3**(i-1)) for i=1..3 } = 13.
  The number of ball partitions is 3**12 = 531441.
  The number of brute force strategies is (531441**3)*(3**2) = 1.351e+18.
  e.g. for 12 balls, p*(p*(p+p+p)+p*(p+p+p)+p*(p+p+p))=(p**3)*(3**2).
  The partitions where L's = R's, displayed as 'm: C(12,m)*C(12-m,m)', are 
    1: 132   2: 2970   3: 18480   4: 34650   5: 16632   6: 924   
  The sum of these is = 73788.
  The number of strategies is then (73788**3)*(3**2) = 3.616e+15.
  The number of partitions with (i) L's=R's, (ii) n balls taken as different,
  and (iii) leaving out those with first R before first L :
    0: 6       1: 11      2: 26      3: 65      4: 168     5: 430    
    6: 1080    7: 2620    8: 6031    9: 12811  10: 24068  11: 36894  
  Using the numbers of different balls vs depth as (0 9 3),
  the number of strategies is 6 * 12811 * 65 * 3**2 = 4.497e+07.

Here are some ways to reduce the first naive estimate of the size of the search space, 1e18, down to something manageable.

I)
Putting a different number of balls on the left and right pans doesn't give us interesting information: for small weight differences, the pan with more balls always goes down. While this fact is one that a brute force search could find, and which may therefore be part of what the program is supposed to figure out, out, I'll assume otherwise, and put that as part of the ``built-in'' knowledge.

II)
The intitial ball grouping can be permuted without disturbing the overall strategy; therefore, we only need 6 (i.e. n_balls/2) different initial groupings. (In other words, none of the balls are different from the others at the root node.) To be more specific, and using a notation that described below,
  $root_partitions = [  [ L  R  o  o  o  o  o  o  o  o  o  o ],
                        [ L  L  R  R  o  o  o  o  o  o  o  o ],
                         ...
                        [ L  L  L  L  L  L  R  R  R  R  R  R ] ];

III)
For the nodes below the top of the tree, we can use the fact that many of the balls are no longer possible heavy or light candidates in any remaining scenarios to remove permutations over identical balls. For example, at the bottom of the tree, say, node [5], there are at most 3 viable scenarios, implying at least 9 balls that are already known to be of normal weight. There's no need to look at different permutations of those 9 balls; therefore we need look at only (12-9)**3 = 27 different permutations for the terminal nodes.

IV)
Because the puzzle is symetric between left and right, a strategy for, say, (l,l,b) will also work for (r,r,b) once all L's and R's are swapped. That lets us cut the original 13 nodes down to 7, as shown below, where ``*'' means ``use the earlier node with left and right swapped''. | [1] +--------------------+--------------------+ |balanced |left |right | | | [2] [3] * +------+------+ +------+------+ |b |l |r |b |l |r | | | | | | [5] [6] * [8] [9] * +-+-+ +-+-+ +-+-+ +-+-+ b l * b l r b l r b l r

V)
Besides this node left-right symmetry, there's also a partition left-right symmetry, since swapping the the balls on the left and right pans for any given weighing only swaps the parity of what follows. Therefore, without loss of generality, any partition such as [R o R L L o ] can be replaced by [L o L R R o]. This cuts the number of partitions in half, at least for those with $n_different != 0.

Putting together (I) through (V), and assuming 3 identical balls at nodes [2] and [3], and 9 identical balls at nodes [5]..[9], an exhaustive search need not consider more than [1] [2] [5] [6] [3] [8] [9] ( 6 ) * ( 12811 * ( 65 + 65 ) + 12811 * ( 65 + 65 ) ) = 19_985_160 possible weighing schemes.

VI)
Moreover, only partitions which divide the scenarios fairly evenly need be considered. This pruning is applied top down, eliminating big chunks of the search as we go. For example, nodes [2], [3], and [4] only have 9 terminal branches below them each; therefore, any weighing scheme at node [1] that puts more than 9 possible scenarios in one of the nodes below may be discarded without further search. In fact, it turns out that only one of the possible six weighings at the top of the tree is viable, thus immediately pruning the tree by a factor of six. Note that this implies we shouldn't do a straight depth-first search, but instead should look briefly across the (b l r) branches before descending.

In practice this reduces the search drastically.

The upshot of all this is that for twelve balls, the whole tree can be searched to find the puzzle answers.

As the number of balls increases, the search space will quickly get too big for an exhaustive search: permutations are like that. however, solutions can still probably be found by wandering through some the strategies by using heuristics and a method like steepest descent, monte-carlo, or a genetic algorithm. genetic algorithms, beam searches, and so on. My guess is that this problem is similar to eight-queens in that it has a number of possible solutions, and that a reasonable heuristic (such as how evenly each node partitions the scenarios) would let head towards a solution. But I haven't done this myself.

I wouldn't be surprized if there's an analytic constructive solution f or arbitrary n that a literature search would reveal

The current permutation over partitions is problematic in this implementation : for a given n_balls, n_different, n_left, I generate all of them at once and save 'em in memory. That gets too expensive around n_balls=24 or so, at least with 1Gig of memory. I had a hard time coming up with an iterator to do the same thing, turning it into a time rather than space problem. I'm sure that can be done, but even then I think an exhastive search is going to have problems fairly quickly as n increases.

 Here are some questions to look at for $n_balls != 12.

How fast does the search space grow, and when does an exhaustive search become impractical?

Answer: Real fast. Exhaustive search - even clever exhaustive search - fails fairly quickly.

Finally, a few specific definitions of terms, data formats, and implementation notes.


MORE OUTPUT

./odd_ball 4 2

 Searching for odd ball in 4 balls with 2 weighings ...
   '' : at node=1 
      ... 1 partitions (1 L's, 0 different)
      ... 1 partitions (2 L's, 0 different)
 done.  Solution not found after 1 nodes and 2 partitions.

./odd_ball 3 2

 Searching for odd ball in 3 balls with 2 weighings ...
   '' : at node=1 
      ... 1 partitions (1 L's, 0 different)
       'b' : at node=2 
          ... 2 partitions (1 L's, 1 different)
           'bb' : at node=3 
           'bl' : at node=4 
           'br' : at node=5 
       'l' : at node=6 
          ... 3 partitions (1 L's, 2 different)
           'lb' : at node=7 
           'll' : at node=8 
           'lr' : at node=9 
       'r' : at node=10 
          ... 3 partitions (1 L's, 2 different)
           'rb' : at node=11 
           'rl' : at node=12 
           'rr' : at node=13 
 done.  Solution found after 13 nodes and 6 partitions.
 In what follows, (L,R,o) means 'Left', 'Right', and 'off scale',
 and (b,l,r) mean 'balanced', 'left tilt', and 'right tilt'.
 start => [ L R o ]
     b => [ R o L ]
     l => [ o L R ]
     r => [ L o R ]
   bl => ball 3 is heavy.
   br => ball 3 is light.
   lb => ball 1 is heavy.
   lr => ball 2 is light.
   rb => ball 2 is heavy.
   rr => ball 1 is light.
 Double check : 
  scenario 0 gives rr => 0 : OK
  scenario 1 gives lr => 1 : OK
  scenario 2 gives br => 2 : OK
 Looks good.

./odd_ball 13 3

 Searching for odd ball in 13 balls with 3 weighings ...
   '' : at node=1 
      ... 1 partitions (4 L's, 0 different)
      ... 1 partitions (3 L's, 0 different)
      ... 1 partitions (5 L's, 0 different)
      ... 1 partitions (2 L's, 0 different)
      ... 1 partitions (6 L's, 0 different)
      ... 1 partitions (1 L's, 0 different)
 done.  Solution not found after 1 nodes and 6 partitions.

./odd_ball 13 4

 Searching for odd ball in 13 balls with 4 weighings ...
   '' : at node=1 
      ... 1 partitions (4 L's, 0 different)
       'b' : at node=2 
          ... 16 partitions (1 L's, 5 different)
           'bb' : at node=3 
              ... 7 partitions (1 L's, 3 different)
           'bl' : at node=16 
              ... 4 partitions (1 L's, 2 different)
           'br' : at node=29 
              ... 4 partitions (1 L's, 2 different)
       'l' : at node=42 
          ... 443 partitions (2 L's, 8 different)
           'lb' : at node=43 
              ... 11 partitions (1 L's, 4 different)
           'll' : at node=56 
              ... 4 partitions (1 L's, 2 different)
           'lr' : at node=69 
              ... 4 partitions (1 L's, 2 different)
       'r' : at node=82 
          ... 443 partitions (2 L's, 8 different)
           'rb' : at node=83 
              ... 11 partitions (1 L's, 4 different)
           'rl' : at node=96 
              ... 4 partitions (1 L's, 2 different)
           'rr' : at node=109 
              ... 4 partitions (1 L's, 2 different)
 done.  Solution found after 121 nodes and 485 partitions.
 In what follows, (L,R,o) means 'Left', 'Right', and 'off scale',
 and (b,l,r) mean 'balanced', 'left tilt', and 'right tilt'.
 start => [ L L L L R R R R o o o o o ]
     b => [ o o o o o o o o L R o o o ]
     l => [ o o o o L L R R o o o o o ]
     r => [ L L R R o o o o o o o o o ]
    bb => [ o o o o o o o o o o L R o ]
    bl => [ o o o o o o o o R L o o o ]
    br => [ o o o o o o o o L R o o o ]
    lb => [ L R o o o o o o o o o o o ]
    ll => [ o o o o o o L R o o o o o ]
    lr => [ o o o o L R o o o o o o o ]
    rb => [ o o o o L R o o o o o o o ]
    rl => [ o o L R o o o o o o o o o ]
    rr => [ L R o o o o o o o o o o o ]
   bbb => [ R o o o o o o o o o o o L ]
   bbl => [ R o o o o o o o o o o L o ]
   bbr => [ R o o o o o o o o o L o o ]
   blb => [ L R o o o o o o o o o o o ]
   bll => [ L R o o o o o o o o o o o ]
   blr => [ R o o o o o o o o L o o o ]
   brb => [ L R o o o o o o o o o o o ]
   brl => [ L R o o o o o o o o o o o ]
   brr => [ R o o o o o o o L o o o o ]
   lbb => [ o o L R o o o o o o o o o ]
   lbl => [ L R o o o o o o o o o o o ]
   lbr => [ R L o o o o o o o o o o o ]
   llb => [ L R o o o o o o o o o o o ]
   lll => [ R o o o o o o L o o o o o ]
   llr => [ R o o o o o L o o o o o o ]
   lrb => [ L R o o o o o o o o o o o ]
   lrl => [ R o o o o L o o o o o o o ]
   lrr => [ R o o o L o o o o o o o o ]
   rbb => [ o o o o o o L R o o o o o ]
   rbl => [ R o o o L o o o o o o o o ]
   rbr => [ R o o o o L o o o o o o o ]
   rlb => [ L R o o o o o o o o o o o ]
   rll => [ R o o L o o o o o o o o o ]
   rlr => [ R o L o o o o o o o o o o ]
   rrb => [ L R o o o o o o o o o o o ]
   rrl => [ R L o o o o o o o o o o o ]
   rrr => [ L R o o o o o o o o o o o ]
   bbbl => ball 13 is heavy.
   bbbr => ball 13 is light.
   bblb => ball 11 is heavy.
   bblr => ball 12 is light.
   bbrb => ball 12 is heavy.
   bbrr => ball 11 is light.
   blrb => ball 9 is heavy.
   blrr => ball 10 is light.
   brrb => ball 10 is heavy.
   brrr => ball 9 is light.
   lbbl => ball 3 is heavy.
   lbbr => ball 4 is heavy.
   lbll => ball 1 is heavy.
   lbrl => ball 2 is heavy.
   lllr => ball 8 is light.
   llrr => ball 7 is light.
   lrlr => ball 6 is light.
   lrrr => ball 5 is light.
   rbbl => ball 7 is heavy.
   rbbr => ball 8 is heavy.
   rbll => ball 5 is heavy.
   rbrl => ball 6 is heavy.
   rllr => ball 4 is light.
   rlrr => ball 3 is light.
   rrlr => ball 2 is light.
   rrrr => ball 1 is light.
 Double check : 
  scenario 0 gives rrrr => 0 : OK
  scenario 1 gives rrlr => 1 : OK
  scenario 2 gives rlrr => 2 : OK
  scenario 3 gives rllr => 3 : OK
  scenario 4 gives lrrr => 4 : OK
  scenario 5 gives lrlr => 5 : OK
  scenario 6 gives llrr => 6 : OK
  scenario 7 gives lllr => 7 : OK
  scenario 8 gives brrr => 8 : OK
  scenario 9 gives blrr => 9 : OK
  scenario 10 gives bbrr => 10 : OK
  scenario 11 gives bblr => 11 : OK
  scenario 12 gives bbbr => 12 : OK
 Looks good.

./odd_ball 20 4

 Searching for odd ball in 20 balls with 4 weighings ...
   '' : at node=1 
      ... 1 partitions (6 L's, 0 different)
       'b' : at node=2 
          ... 443 partitions (2 L's, 8 different)
           'bb' : at node=3 
              ... 11 partitions (1 L's, 4 different)
              ... 32 partitions (2 L's, 4 different)
           'bl' : at node=16 
              ... 11 partitions (1 L's, 4 different)
           'br' : at node=29 
              ... 11 partitions (1 L's, 4 different)
       'l' : at node=42 
          ... 85010 partitions (4 L's, 12 different)
           'lb' : at node=43 
              ... 11 partitions (1 L's, 4 different)
           'll' : at node=56 
              ... 4 partitions (1 L's, 2 different)
           'lr' : at node=69 
              ... 142 partitions (2 L's, 6 different)
       'r' : at node=82 
          ... 85010 partitions (4 L's, 12 different)
           'rb' : at node=83 
              ... 11 partitions (1 L's, 4 different)
           'rl' : at node=96 
              ... 4 partitions (1 L's, 2 different)
           'rr' : at node=109 
              ... 142 partitions (2 L's, 6 different)
 done.  Solution found after 121 nodes and 85653 partitions.
 In what follows, (L,R,o) means 'Left', 'Right', and 'off scale',
 and (b,l,r) mean 'balanced', 'left tilt', and 'right tilt'.
 start => [ L L L L L L R R R R R R o o o o o o o o ]
     b => [ o o o o o o o o o o o o L L R R o o o o ]
     l => [ R R o o o o L L L L R R o o o o o o o o ]
     r => [ L L L L R R R R o o o o o o o o o o o o ]
    bb => [ R o o o o o o o o o o o o o o o L L R o ]
    bl => [ o o o o o o o o o o o o o o L R o o o o ]
    br => [ o o o o o o o o o o o o L R o o o o o o ]
    lb => [ o o L R o o o o o o o o o o o o o o o o ]
    ll => [ o o o o o o o o o o L R o o o o o o o o ]
    lr => [ o o o o o o L L R R o o o o o o o o o o ]
    rb => [ o o o o o o o o L R o o o o o o o o o o ]
    rl => [ o o o o L R o o o o o o o o o o o o o o ]
    rr => [ L L R R o o o o o o o o o o o o o o o o ]
   bbb => [ R o o o o o o o o o o o o o o o o o o L ]
   bbl => [ o o o o o o o o o o o o o o o o L R o o ]
   bbr => [ o o o o o o o o o o o o o o o o L R o o ]
   blb => [ o o o o o o o o o o o o L R o o o o o o ]
   bll => [ R o o o o o o o o o o o o o o L o o o o ]
   blr => [ R o o o o o o o o o o o o o L o o o o o ]
   brb => [ o o o o o o o o o o o o o o L R o o o o ]
   brl => [ R o o o o o o o o o o o o L o o o o o o ]
   brr => [ R o o o o o o o o o o o L o o o o o o o ]
   lbb => [ o o o o L R o o o o o o o o o o o o o o ]
   lbl => [ R o L o o o o o o o o o o o o o o o o o ]
   lbr => [ R o o L o o o o o o o o o o o o o o o o ]
   llb => [ L R o o o o o o o o o o o o o o o o o o ]
   lll => [ R o o o o o o o o o o L o o o o o o o o ]
   llr => [ R o o o o o o o o o L o o o o o o o o o ]
   lrb => [ L R o o o o o o o o o o o o o o o o o o ]
   lrl => [ o o o o o o o o L R o o o o o o o o o o ]
   lrr => [ o o o o o o L R o o o o o o o o o o o o ]
   rbb => [ o o o o o o o o o o L R o o o o o o o o ]
   rbl => [ R o o o o o o o L o o o o o o o o o o o ]
   rbr => [ R o o o o o o o o L o o o o o o o o o o ]
   rlb => [ L R o o o o o o o o o o o o o o o o o o ]
   rll => [ R o o o o L o o o o o o o o o o o o o o ]
   rlr => [ R o o o L o o o o o o o o o o o o o o o ]
   rrb => [ o o o o o o L R o o o o o o o o o o o o ]
   rrl => [ o o L R o o o o o o o o o o o o o o o o ]
   rrr => [ L R o o o o o o o o o o o o o o o o o o ]
   bbbl => ball 20 is heavy.
   bbbr => ball 20 is light.
   bblb => ball 19 is light.
   bbll => ball 17 is heavy.
   bblr => ball 18 is heavy.
   bbrb => ball 19 is heavy.
   bbrl => ball 18 is light.
   bbrr => ball 17 is light.
   blbl => ball 13 is heavy.
   blbr => ball 14 is heavy.
   bllr => ball 16 is light.
   blrr => ball 15 is light.
   brbl => ball 15 is heavy.
   brbr => ball 16 is heavy.
   brlr => ball 14 is light.
   brrr => ball 13 is light.
   lbbl => ball 5 is heavy.
   lbbr => ball 6 is heavy.
   lbll => ball 3 is heavy.
   lbrl => ball 4 is heavy.
   lllr => ball 12 is light.
   llrr => ball 11 is light.
   lrbl => ball 1 is heavy.
   lrbr => ball 2 is heavy.
   lrll => ball 10 is light.
   lrlr => ball 9 is light.
   lrrl => ball 8 is light.
   lrrr => ball 7 is light.
   rbbl => ball 11 is heavy.
   rbbr => ball 12 is heavy.
   rbll => ball 9 is heavy.
   rbrl => ball 10 is heavy.
   rllr => ball 6 is light.
   rlrr => ball 5 is light.
   rrbl => ball 7 is heavy.
   rrbr => ball 8 is heavy.
   rrll => ball 4 is light.
   rrlr => ball 3 is light.
   rrrl => ball 2 is light.
   rrrr => ball 1 is light.
 Double check : 
  scenario 0 gives rrrr => 0 : OK
  scenario 1 gives rrrl => 1 : OK
  scenario 2 gives rrlr => 2 : OK
  scenario 3 gives rrll => 3 : OK
  scenario 4 gives rlrr => 4 : OK
  scenario 5 gives rllr => 5 : OK
  scenario 6 gives lrrr => 6 : OK
  scenario 7 gives lrrl => 7 : OK
  scenario 8 gives lrlr => 8 : OK
  scenario 9 gives lrll => 9 : OK
  scenario 10 gives llrr => 10 : OK
  scenario 11 gives lllr => 11 : OK
  scenario 12 gives brrr => 12 : OK
  scenario 13 gives brlr => 13 : OK
  scenario 14 gives blrr => 14 : OK
  scenario 15 gives bllr => 15 : OK
  scenario 16 gives bbrr => 16 : OK
  scenario 17 gives bbrl => 17 : OK
  scenario 18 gives bblb => 18 : OK
  scenario 19 gives bbbr => 19 : OK
 Looks good.

./odd_ball 24 4

 Searching for odd ball in 24 balls with 4 weighings ...
   '' : at node=1 
      ... 1 partitions (8 L's, 0 different)
       'b' : at node=2 
          ... 443 partitions (2 L's, 8 different)
           'bb' : at node=3 
              ... 11 partitions (1 L's, 4 different)
              ... 32 partitions (2 L's, 4 different)
           'bl' : at node=16 
              ... 11 partitions (1 L's, 4 different)
           'br' : at node=29 
              ... 11 partitions (1 L's, 4 different)
       'l' : at node=42 
 perl(359) malloc: *** vm_allocate(size=8421376) failed (err code=3)
 perl(359) malloc: *** error: can't allocate region
 perl(359) malloc: *** set a breakpoint in szone_error to debug
 Out of memory!


AUTHOR

Jim Mahoney, Marlboro College (mahoney@marlboro.edu)


COPYRIGHT

Copyright 2005 Jim Mahoney

This program is free software; you may redistribute it and/or modify it under the same terms as Perl itself.