<jupyter_start><jupyter_text><NAME>012; updated August 2019 Weighing Twelve Balls on a Balance Scale > *You are given twelve identical-looking balls and a two-sided scale. One of the balls is of a different weight, although you don't know whether it's lighter or heavier. How can you use just three weighings of the scale to determine not only what the different ball is, but also whether it's lighter or heavier?*This is [a classic](https://en.wikipedia.org/wiki/Balance_puzzle) brain-teaser puzzle (first appearing in 1945), meant to be solved with paper and pencil.  But I want to solve not just this specific puzzle, but related puzzles where you can vary (a) the number of balls, (b) the number of weighings allowed, and (c) whether the odd ball might be heavier, lighter, or either, or neither. So I'll need a computer program, not a pencil. (I originally wrote this program in 2012, but am republishing it here in revised form because the puzzle was mentioned in the [538 Riddler](https://fivethirtyeight.com/features/which-billiard-ball-is-rigged/) for 16 August 2019. It also appeared in a [Numberplay](https://wordplay.blogs.nytimes.com/2014/07/21/12coin/) column in 2014 (with coins instead of balls) among other venues.)    🎱🎱🎱🎱⚖🎱🎱🎱🎱 DesignHere are the concepts I'm dealing with:- **balls**: In the general case I have N balls. I'll represent them with a list like `[1, 2, 3]` for N = 3.- **possible oddballs**: Exactly one of the balls is different in its weight; I'll use the term **oddball** to indicate which ball is different, and how.I'll represent the situation where ball N is heavier as +N, and where ball N is lighter as -N.  With N = 3, the set of all possible oddballs is `{+1, -1, +2, -2, +3, -3}`. (As an extension that is not needed for the stated puzzle but is useful for similar puzzles: I'll represent the situation where all the balls weigh the same&mdash;no ball is odd&mdash;with `0`.)- **puzzle**: I'll express the puzzle stated above with `Puzzle(N=12, weighings=3)`. A puzzle is defined by the balls involved, the number of weighings allowed, and the possible oddballs. (I'll add a few complications later.)- **weighing**: I can weigh a collection of balls on the left versus a collection on the right, and the result will be that the left side is greater than, equal to, or less than the right in weight. I'll denote that with the call `weigh(L, R, oddball)`, which returns a string, `'gt'`, `'eq'`, or `'lt'`.- **weight**: I'll arbitrarily say that a normal ball weighs 100, a lighter ball 99, and a heavier ball 101.- **solution**: Given a puzzle, a solution is a **strategy tree** that can correctly discover the odd ball, whatever it is, in the allowable number of weighings. Since a tree with W weighings has 3W possible outcomes (leaf nodes), we can deduce that it is impossible to find a solution in W weighings if there are more than 3W possible oddballs.- **strategy tree**: A tree whose leaf nodes are all oddballs (ints), and whose interior nodes have 5 components:  `Tree(L, R, gt, eq, lt)` is a node where `L` and `R` are the collections of balls to be weighed, and `gt`, `eq`, and `lt` are branches for subtrees corresponding to the three possible results of the weighing. (I'll also use `None` to mean "could not find a valid tree.")- **following a path in a tree**: I'll use `follow(tree, oddball)` to say *follow the path through the tree, doing each weighing under the assumption of the given oddball, and return the leaf node reached by the path&mdash;the oddball that the tree predicts.* Note that the function `follow` gets to see what the oddball is, but the `tree` never gets direct access to that; the tree has to figure it out by doing weighings.- **valid tree**: A tree is a valid solution to a puzzle if no branch uses more than the allowable number of weighings, and if, for every possible oddball in the puzzle, following the path through the tree correctly returns that oddball as the answer. I'll use `valid(tree, puzzle)` for this.Note: I have an idea for the definition of the `Puzzle` class: by default, the oddballs are all the "lighter" and "heavier" versions of the puzzle's balls. But if you want a different kind of puzzle, I'll allow two options: you can specify the keyword argument `oddballs=` and give a set of oddballs; whatever you want. Or you can specify the keyword argument `oddities`, whose value can be any subset of `{-1, 0, +1}`, where `-1` means "any one ball might be lighter," `+1` means "any one ball might be heavier," and `0` means "it might be that no ball is odd; they all weigh the same." ImplementationLet's start implementing the concepts:<jupyter_code>from collections import namedtuple
import random

#### Types

Ball = Oddball = int

class Puzzle:
    "Represent a specific ball-weighing puzzle."
    def __init__(self, N=12, weighings=3, oddities={-1, +1}, oddballs=None):
        # If `oddballs` is None, compute them via `oddities`.
        self.balls     = list(range(1, N + 1))
        self.weighings = weighings
        self.oddballs  = (oddballs if oddballs is not None else
                          {b * o for b in self.balls for o in oddities})
        
Tree = namedtuple('Tree', 'L, R, gt, eq, lt')

#### Functions
    
def weigh(L, R, oddball) -> str:
    "Weigh balls L against balls R, given the oddball; return 'gt', 'eq', or 'lt'."
    diff = sum(weight(b, oddball) for b in L) - sum(weight(b, oddball) for b in R)
    return ('gt' if diff > 0 else
            'lt' if diff < 0 else
            'eq')

def weight(ball, oddball) -> int: 
    "How heavy is this ball (given that we know what the oddball is)?"
    return 101 if +ball == oddball else 99 if -ball == oddball else 100
    
def solve(puzzle) -> Tree or None:
    "Return a valid tree (one that solves the puzzle), or None."
    tree = find_tree(puzzle, puzzle.oddballs, puzzle.weighings)
    return tree if valid(tree, puzzle) else None
    
def follow(tree, oddball) -> Oddball:
    "Follow a path through the tree and return the oddball that the tree leads us to."
    if is_leaf(tree):
        return tree
    else:
        branch = weigh(tree.L, tree.R, oddball)
        return follow(getattr(tree, branch), oddball)
    
def valid(tree, puzzle) -> bool:
    "Does the strategy tree solve the puzzle correctly for all possible oddballs?"
    return (tree is not None and
            depth(tree) <= puzzle.weighings and 
            all(follow(tree, oddball) == oddball 
                for oddball in puzzle.oddballs))

def depth(tree) -> int:
    "Maximum depth (number of weighings) in tree."
    return (0 if is_leaf(tree) or tree is None
            else 1 + max(depth(tree.gt), depth(tree.eq), depth(tree.lt)))

def is_leaf(node): return isinstance(node, Oddball)<jupyter_output><empty_output><jupyter_text>Let's try out some of these functions:<jupyter_code>p8 = Puzzle(8) 

p8.weighings, p8.balls, p8.oddballs
# If we weigh balls 1, 2 against 3, 4, and the oddball is that 5 is lighter, the result should be 'eq'
weigh([1, 2], [3, 4], -5)
weight(1, oddball=-5)
weight(5, oddball=-5)
is_leaf(-3)
is_leaf(Tree([1], [2], +1, +3, +2))<jupyter_output><empty_output><jupyter_text>Finding a Valid TreeNow we've got all the pieces we need to find a valid tree to solve a puzzle. The key concept is that a **weighing** gives us information by making a **partition** of the possible **oddballs** into branches for each of the three possible weighing results: `gt`, `eq`, or `lt`. If each of the partitions is small enough, subsequent weighings can handle each of them. Here's what I mean by a partition:<jupyter_code>def partition(L, R, oddballs) -> dict:
    "Build a dict that partitions the possible outcomes (oddballs) resulting from weighing L versus R."
    part = dict(gt=set(), eq=set(), lt=set())
    for odd in oddballs:
        part[weigh(L, R, odd)].add(odd)
    return part<jupyter_output><empty_output><jupyter_text>For example, with 12 balls, if we weigh balls 1 and 2 on the left versus 11 and 12 on the right, then there are 4 ways  the left side can be greater than the right: either 11 or 12 is lighter or  1 or 2 is heavier. Similarly there are 4 ways of getting a `lt` weighing result. The remaining 16 possibilities&mdash;balls 3 through 10 being either heavier or lighter&mdash;show up in the `eq` branch of the partition:<jupyter_code>p12 = Puzzle(12, 3)

partition([1, 2], [11, 12], p12.oddballs)<jupyter_output><empty_output><jupyter_text>If this was the first weighing in our strategy tree, could we go on to solve the puzzle in 3 weighings? **No!** With two remaining weighings we can handle at most  3 &times; 3 = 9 possibilities; here we have 16 possibilities in the `eq` branch, which is too many. We call this a **bad partition**.The following is a **good partition** because each of the branches has 8 possibilities, and 8 is less than 9.<jupyter_code>partition([1, 2, 3, 4], [9, 10, 11, 12], p12.oddballs)<jupyter_output><empty_output><jupyter_text>(Note: being a good partition does not guarantee that the puzzle is solvable from there; but being a bad partition guarantees that it is not solvable. Also note that this is a good partition with 2 remaining weighings, but would be a bad partition with only one remaining weighing.) So now we have a viable approach to implementing `find_tree`:   - We call `find_tree(puzzle, oddballs, weighings)`. At the top level, the oddballs and number of weighings come from the puzzle. At recursive levels, we will reduce the number of oddball possibilities according to the partition, and the number of remaining weighings by 1 each time.   - We handle trivial cases when there are zero or one oddballs remaining, or no weighings remaining.   - Otherwise, we generate random partitions of the balls, and examine the good ones.   - Given a good partition, all we have to do is find good trees (i.e. not `None`) for each of the three branches. If we can find that, return the tree as a solution.   - If we can't find good trees for any partition, return `None` to indicate failure.   The rest of the work is done by `good_partitions`:   - We randomly select two lists of balls to be weighed, `L` and `R`, both of length `B`.   - We systematically consider all reasonable values of `B`. (All values from 1 up to 1/3 the number of balls, rounded up.)   - We then see what partition `L` and `R` gives us.   - If it is good, the function yields the `(L, R, partition)` tuple.   - In any case, we repeat the process 100 times. That number was chosen to have a very good chance of randomly selecting a good partition for solvable puzzles, and of terminating in just a few seconds for unsolvable puzzles. (If I wanted to solve puzzles  with thousands of balls, I would come back and improve `good_partitions`.)<jupyter_code>def find_tree(puzzle, oddballs, weighings) -> Tree or Oddball or None:
    "Find a strategy tree that covers all the oddballs in the given number of weighings."
    if len(oddballs) == 1:
        return next(iter(oddballs)) # One possibility left; we're done; leaf node
    elif len(oddballs) == 0:
        return 0                    # No oddball
    elif weighings == 0:
        return None                 # No solution within allowable weighings; fail
    else:
        for L, R, part in good_partitions(puzzle, oddballs, weighings - 1):
            subtrees = {r: find_tree(puzzle, part[r], weighings - 1) for r in part}
            if None not in subtrees.values(): 
                return Tree(L, R, **subtrees)
    
def good_partitions(puzzle, oddballs, weighings, tries=100):
    "Yield random (L, R, partition) tuples with no partition branch longer than 3**weighings."
    balls = list(puzzle.balls)
    for _ in range(tries): 
        for B in range(1, (len(balls) + 2) // 3 + 1):
            random.shuffle(balls)
            L, R = balls[:B], balls[-B:]
            part = partition(L, R, oddballs)
            longest = max(part.values(), key=len)
            if len(longest) <= 3 ** weighings:
                yield L, R, part<jupyter_output><empty_output><jupyter_text>Here we see that  `good_partitions` does its job:<jupyter_code>next(good_partitions(p12, p12.oddballs, 2))<jupyter_output><empty_output><jupyter_text>Solving Some PuzzlesNow we're ready to solve puzzles!<jupyter_code>solve(p12)<jupyter_output><empty_output><jupyter_text>OK, that's hard to read&mdash;my bad. Let's look at a much easier puzzle: 3 balls, 1 weighing allowed, and the odd ball can only be lighter:<jupyter_code>tree = solve(Puzzle(3, 1, {-1}))
tree<jupyter_output><empty_output><jupyter_text>This tree says you weigh one ball against another (leaving the third unweighed), and the three possible weighing results tell you which of the three balls  is lighter.   Prettier OutputLet's make the output easier to read. I'll use `[1·2·3·4]⚖[9·10·11·12] ➔` to mean *"Weigh balls 1,2,3,4 versus 9,10,11,12 to get a result..."*. I'll indent each interior node in the tree, and I'll use `>:` to mean *the result when the left hand side is greater than the right in weight is...*<jupyter_code>def do(puzzle):
    "Print the solution to the puzzle as indented text."
    print(indented(solve(puzzle)))
    
def indented(tree, i=0, prefix='') -> str:
    "Pretty, indented string representing a strategy tree."
    if tree == 0 or tree == None:
        return f'{prefix}{tree}'
    elif is_leaf(tree):
        return f'{prefix}{tree:+d}'
    else:
        subtrees = (indented(tree.gt, i+1, '>:'), indented(tree.eq, i+1, '=:'), indented(tree.lt, i+1, '<:'))
        indent   = ('' if i == 0 else ('\n' + ' ' * 5 * i))
        return f'{indent}{prefix}{side(tree.L)}⚖{side(tree.R)} ➔ {" ".join(subtrees)})'
    
def side(balls) -> str: return str(sorted(balls)).replace(', ', '·')<jupyter_output><empty_output><jupyter_text>Also, note that at the root node of a tree, there's no sense randomly shuffling the balls&mdash;the only choice that matters is how many balls, `B`, to put on each side. Putting `1·2·3·4` on the left is no different than `3·7·9·12`, because each ball is undifferentiated at the start. I'll alter `good_partitions` to do this.<jupyter_code>def good_partitions(puzzle, oddballs, weighings, tries=100):
    "Yield random (L, R, partition) tuples with no partition branch longer than 3**weighings."
    at_root = (oddballs == puzzle.oddballs)
    balls   = sorted(puzzle.balls)
    for _ in range(1 if at_root else tries): 
        for B in range(1, (len(balls) + 2) // 3 + 1):
            if not at_root: random.shuffle(balls)
            L, R = balls[:B], balls[-B:]
            part = partition(L, R, oddballs)
            longest = max(part.values(), key=len)
            if len(longest) <= 3 ** weighings:
                yield L, R, part
# 3 balls, 1 weighing, only lighter balls possible
do(Puzzle(3, 1, {-1}))
# 3 balls, 2 weighings, lighter or heavier balls possible
do(Puzzle(3, 2))
# The original puzzle with 12 balls, 3 weighings
do(p12)
# A different solution to the same puzzle
do(p12)<jupyter_output>[1·2·3·4]⚖[9·10·11·12] ➔ 
     >:[1·9·11]⚖[3·10·12] ➔ 
          >:[1·10]⚖[5·8] ➔ >:+1 =:-12 <:-10) 
          =:[2·10]⚖[3·12] ➔ >:+2 =:+4 <:0) 
          <:[2·6·10·11]⚖[1·7·9·12] ➔ >:-9 =:+3 <:-11)) 
     =:[2·7·9·12]⚖[3·4·5·6] ➔ 
          >:[1·5·10]⚖[2·6·11] ➔ >:-6 =:+7 <:-5) 
          =:[1·2·10]⚖[5·8·12] ➔ >:-8 =:0 <:+8) 
          <:[6·12]⚖[5·11] ➔ >:+6 =:-7 <:+5)) 
     <:[3·4·8·11]⚖[1·5·7·10] ➔ 
          >:[10·12]⚖[1·3] ➔ >:-1 =:+11 <:0) 
          =:[8·10·12]⚖[3·6·9] ➔ >:+12 =:-2 <:+9) 
          <:[4·10]⚖[1·12] ➔ >:+10 =:-3 <:-4)))<jupyter_text>I note that the traditional answer to the puzzle weighs 4 balls on each side of the first weighing, three balls on the second weighing, and 2 balls on the third weighing. But my program is not so orderly. It always weighs 4 balls on the first weighing, but from there it can vary; it has no inclination to minimize the number of balls on each side of the scale, or to make one branch of the tree be similar to another branch. Other Puzzles: 3 Weighings We can do **12 balls in 3 weighings** even when we add in the possibility that all the balls weigh the same (we use `0` to denote this situation):<jupyter_code>do(Puzzle(12, 3, {-1, 0, +1}))<jupyter_output>[1·2·3·4]⚖[9·10·11·12] ➔ 
     >:[4·6·9·11]⚖[2·5·7·12] ➔ 
          >:[3·4]⚖[7·8] ➔ >:+4 =:-12 <:0) 
          =:[3·9]⚖[1·4] ➔ >:+3 =:-10 <:+1) 
          <:[7·11·12]⚖[4·6·9] ➔ >:-9 =:+2 <:-11)) 
     =:[2·6·8]⚖[7·9·10] ➔ 
          >:[1·4·5·11]⚖[6·7·10·12] ➔ >:-7 =:+8 <:+6) 
          =:[5·7·9·12]⚖[1·4·6·8] ➔ >:+5 =:0 <:-5) 
          <:[2·3·11·12]⚖[4·7·8·10] ➔ >:-8 =:-6 <:+7)) 
     <:[4·5·9]⚖[1·3·10] ➔ 
          >:[1·7]⚖[3·8] ➔ >:-3 =:+9 <:-1) 
          =:[2·5·12]⚖[6·7·9] ➔ >:+12 =:+11 <:-2) 
          <:[2·3·4·5]⚖[6·8·11·12] ➔ >:0 =:+10 <:-4)))<jupyter_text>Can we solve the **13-balls in 3 weighings** puzzle, which has 26 possibilities? After all, 26 is less than 33.<jupyter_code>do(Puzzle(13))<jupyter_output>None<jupyter_text>**No**, and the reason is that there is no first weighing that partitions the 26 possibilities into 9/9/8; the best we can do is partition into 8/10/8 or 10/6/10, and 10 possibilities can't be distinguished in the remaining two weighings:<jupyter_code>partition([1, 2, 3, 4], [10, 11, 12, 13], Puzzle(13).oddballs)
partition([1, 2, 3, 4, 5], [9, 10, 11, 12, 13], Puzzle(13).oddballs)<jupyter_output><empty_output><jupyter_text>We can do **27 balls in 3 weighings** if we know that the odd ball can only be lighter, not heavier:<jupyter_code>do(Puzzle(27, 3, {-1}))<jupyter_output>[1·2·3·4·5·6·7·8·9]⚖[19·20·21·22·23·24·25·26·27] ➔ 
     >:[9·10·13·20·21·22]⚖[7·11·15·23·24·27] ➔ 
          >:[2·4·7·8·12·14·17·23]⚖[3·6·11·13·18·19·21·24] ➔ >:-24 =:-27 <:-23) 
          =:[1·6·10·13·19·22·23]⚖[3·9·12·18·21·26·27] ➔ >:-26 =:-25 <:-19) 
          <:[4·5·6·13·14·18·19·20·25]⚖[2·7·9·12·15·17·21·24·26] ➔ >:-21 =:-22 <:-20)) 
     =:[3·7·8·12·13·18·19·21·25]⚖[1·4·5·6·10·16·17·22·24] ➔ 
          >:[3·4·10·26]⚖[8·16·19·20] ➔ >:-16 =:-17 <:-10) 
          =:[3·11]⚖[14·24] ➔ >:-14 =:-15 <:-11) 
          <:[1·4·6·16·17·18]⚖[3·5·12·24·26·27] ➔ >:-12 =:-13 <:-18)) 
     <:[3·6·8·10·12·17·19·21·25]⚖[1·2·5·13·14·16·22·23·24] ➔ 
          >:[1·3·14·15·16·25·27]⚖[2·6·7·19·22·23·24] ➔ >:-2 =:-5 <:-1) 
          =:[1·7·8·12·14·18·23]⚖[9·13·16·20·21·22·26] ➔ >:-9 =:-4 <:-7) 
          <:[1·2·6·10·13·17·22·23·27]⚖[3·7·9·11·15·20·21·25·26] ➔ >:-3 =:-8 <:-6)))<jupyter_text>And we can do **26 balls** under the condition that either one ball is lighter or all the balls weigh the same. In both these puzzles there are 27 possibilities, the maximum number we can handle in 3 weighings.<jupyter_code>do(Puzzle(26, 3, {-1, 0}))<jupyter_output>[1·2·3·4·5·6·7·8·9]⚖[18·19·20·21·22·23·24·25·26] ➔ 
     >:[3·6·8·9·11·17·19·21·23]⚖[1·4·5·7·10·15·18·20·26] ➔ 
          >:[9·12·17·18·21·22]⚖[1·7·15·23·25·26] ➔ >:-26 =:-20 <:-18) 
          =:[5·12·13·14·15·17·21·25]⚖[1·2·4·6·8·9·16·24] ➔ >:-24 =:-22 <:-25) 
          <:[2·8·19·24]⚖[6·10·21·25] ➔ >:-21 =:-23 <:-19)) 
     =:[5·9·11·13·15·18·19·21]⚖[2·3·4·10·14·16·20·25] ➔ 
          >:[2·10·20]⚖[7·16·17] ➔ >:-16 =:-14 <:-10) 
          =:[3·7·11·12·14·25·26]⚖[5·9·15·17·18·19·24] ➔ >:-17 =:0 <:-12) 
          <:[1·11·20]⚖[12·13·16] ➔ >:-13 =:-15 <:-11)) 
     <:[2·5·9·10·20·21·26]⚖[1·6·8·11·12·15·23] ➔ 
          >:[6·19·20]⚖[1·9·23] ➔ >:-1 =:-8 <:-6) 
          =:[2·3·8·12]⚖[7·15·16·26] ➔ >:-7 =:-4 <:-3) 
          <:[8·9·10·19·26]⚖[1·4·5·15·18] ➔ >:-5 =:-2 <:-9)))<jupyter_text>Here's a puzzle with **25 balls** with an unusual set of possibilities: either one of the odd-numbered balls is heavier, or one of the even-numbered balls is lighter, or no ball is odd.<jupyter_code>N = 25
p = Puzzle(N, 3, oddballs={(+b if b % 2 else -b) for b in range(N + 1)})
print(p.oddballs)
do(p)<jupyter_output>[1·2·3·4·5·6·7·8·9]⚖[17·18·19·20·21·22·23·24·25] ➔ 
     >:[2·4·6·9·13·17·20·21·25]⚖[3·7·10·11·12·14·15·18·22] ➔ 
          >:[4·5·9·15·19·22]⚖[1·2·8·12·16·23] ➔ >:+9 =:-18 <:-22) 
          =:[5·6·7·9·16·19·25]⚖[1·3·11·14·17·21·23] ➔ >:+5 =:-24 <:+1) 
          <:[9·12·21·25]⚖[7·11·18·20] ➔ >:-20 =:+3 <:+7)) 
     =:[5·7·9·12·13·16·17·23]⚖[2·6·8·10·14·18·20·25] ➔ 
          >:[2·3·9·17·22]⚖[8·13·14·21·23] ➔ >:-14 =:-10 <:+13) 
          =:[2·3·6·8·13·14·15·19·22]⚖[1·4·9·11·12·16·17·18·20] ➔ >:+15 =:0 <:+11) 
          <:[3·4·10·17·21·25]⚖[5·8·11·12·20·24] ➔ >:-12 =:-16 <:0)) 
     <:[4·7·9·13·16·17·24]⚖[5·6·8·12·18·21·25] ➔ 
          >:[1·2·12·15·22·23]⚖[7·8·10·13·14·17] ➔ >:-8 =:-6 <:+17) 
          =:[1·3·9·15·20·22·24]⚖[2·8·11·13·19·21·25] ➔ >:-2 =:+23 <:+19) 
          <:[1·10·14·21]⚖[9·17·22·25] ➔ >:+21 =:-4 <:+25)))<jupyter_text>Another variation: **27 balls, 3 weighings**, the odd ball can only be lighter, but one ball (number 27) is radioactive and can't be touched or placed on the balance scale. It might, however be the lighter ball, and you still need to report it as such if it is. (That happens when all three weighings are equal.)<jupyter_code>do(Puzzle(26, 3, oddballs=range(-27, 0)))<jupyter_output>[1·2·3·4·5·6·7·8·9]⚖[18·19·20·21·22·23·24·25·26] ➔ 
     >:[3·7·10·13·17·18·24·25]⚖[1·2·4·9·12·21·23·26] ➔ 
          >:[8·18·23]⚖[7·13·21] ➔ >:-21 =:-26 <:-23) 
          =:[5·10·12·14·18·19·21]⚖[1·3·8·11·22·24·25] ➔ >:-22 =:-20 <:-19) 
          <:[22·25·26]⚖[20·23·24] ➔ >:-24 =:-18 <:-25)) 
     =:[2·3·6·7·11·12·13·19·26]⚖[1·4·8·10·15·16·21·22·24] ➔ 
          >:[4·12·13·15·26]⚖[2·10·17·24·25] ➔ >:-10 =:-16 <:-15) 
          =:[3·9·12·15·17·26]⚖[8·11·14·21·24·25] ➔ >:-14 =:-27 <:-17) 
          <:[7·9·10·13·18·23·24]⚖[1·5·6·11·20·22·25] ➔ >:-11 =:-12 <:-13)) 
     <:[4·5·8·23]⚖[2·3·6·15] ➔ 
          >:[1·3·8·9·15·16·18·20·22]⚖[2·5·10·11·12·21·24·25·26] ➔ >:-2 =:-6 <:-3) 
          =:[2·4·9·10·18·19·21·24·26]⚖[5·6·7·8·14·15·16·22·23] ➔ >:-7 =:-1 <:-9) 
          <:[4·11·14·21]⚖[2·3·5·18] ➔ >:-5 =:-8 <:-4)))<jupyter_text>4 WeighingsWe can tackle larger puzzles. With 4 weighings, we can theoretically handle up to 34 = 81 possibilities. Can we solve for **40 balls**?<jupyter_code>p40 = Puzzle(40, 4)

do(p40)<jupyter_output>None<jupyter_text>Unfortunately, **no**. We always end up with at least one branch with 28 possibilities, but we need 27 or less:<jupyter_code>def partition_sizes(puzzle, B):
    "How big is each branch of a partition with B balls on both sides?"
    part = partition(puzzle.balls[:B], puzzle.balls[-B:], puzzle.oddballs)
    return {branch: len(part[branch]) for branch in part}
partition_sizes(p40, 13)
partition_sizes(p40, 14)<jupyter_output><empty_output><jupyter_text>How about **39 balls**, with the possibility that no ball is odd. That's 39 &times; 2 + 1 = 79 possibilities, but it turns out we can find a good partition, and a solution:<jupyter_code>p39 = Puzzle(39, 4, {-1, 0, +1})
partition_sizes(p39, 13)
do(p39)<jupyter_output>[1·2·3·4·5·6·7·8·9·10·11·12·13]⚖[27·28·29·30·31·32·33·34·35·36·37·38·39] ➔ 
     >:[2·3·6·12·14·24·26·28·29·30·37·38]⚖[1·4·5·17·19·23·25·27·31·32·33·36] ➔ 
          >:[4·6·13·17·18·24·25·33·37·38·39]⚖[1·2·5·10·12·16·20·23·28·31·36] ➔ 
               >:[8·16·18·27·28·35·36·37·39]⚖[5·7·10·12·14·20·30·31·34] ➔ >:-31 =:+6 <:-36) 
               =:[8·11·12·22·24·29·30·34·35·37·38]⚖[3·4·13·14·15·17·18·19·23·26·32] ➔ >:-32 =:-27 <:+3) 
               <:[2·3·11·13·17·30·31·38]⚖[5·7·12·25·27·28·29·35] ➔ >:+2 =:-33 <:+12)) 
          =:[1·2·9·12·13·15·18·21·31]⚖[3·8·10·11·14·16·36·38·39] ➔ 
               >:[4·5·17·19·23·32·35·38]⚖[9·10·21·24·27·29·37·39] ➔ >:-39 =:+13 <:+9) 
               =:[2·9·13·16·19·24·29·31·32·37·39]⚖[1·4·7·10·12·17·23·26·27·30·34] ➔ >:-34 =:-35 <:+7) 
               <:[2·6·8·15·18·22·24·26·34·39]⚖[7·10·12·13·14·23·28·31·36·38] ➔ >:+8 =:+11 <:+10)) 
          <:[1·5·11·12·22·23·29·30·33·38]⚖[2·3·13·17·20·27·28·31·34·35] ➔ 
               >:[3·4·5·10·11·17·28·29·34·37]⚖[[...]<jupyter_text>How about **80 balls** under the condition that no ball can be heavier (thus, 81 possibilities):<jupyter_code>do(Puzzle(80, 4, {-1, 0}))<jupyter_output>[1·2·3·4·5·6·7·8·9·10·11·12·13·14·15·16·17·18·19·20·21·22·23·24·25·26·27]⚖[54·55·56·57·58·59·60·61·62·63·64·65·66·67·68·69·70·71·72·73·74·75·76·77·78·79·80] ➔ 
     >:[2·3·4·7·8·10·12·18·24·34·38·40·44·49·53·58·59·62·64·72·73·76·77·78]⚖[11·14·15·20·22·23·25·27·31·32·35·42·43·50·52·54·55·56·60·63·65·66·70·79] ➔ 
          >:[1·2·4·11·14·24·30·32·37·39·40·46·48·49·52·53·54·56·60·61·62·67·76·77]⚖[12·17·18·20·22·23·25·28·29·31·33·34·36·41·44·45·51·58·63·65·66·68·69·73] ➔ 
               >:[11·14·15·16·20·22·26·33·40·42·47·57·60·65·68·69·70·77]⚖[1·6·10·17·19·25·30·32·35·43·58·59·62·64·66·73·74·78] ➔ >:-66 =:-63 <:-65) 
               =:[2·3·10·12·13·14·15·17·28·30·37·39·47·50·63·65·79]⚖[1·4·6·8·20·23·26·27·34·38·40·43·54·55·61·67·71] ➔ >:-55 =:-70 <:-79) 
               <:[3·4·9·16·23·24·33·41·42·49·53·56·57·63·64·66·69·70·71·77·79·80]⚖[6·7·11·12·13·15·17·18·19·34·35·37·44·46·47·51·58·59·60·62·67·75] ➔ >:-60 =:-54 <:-56)) 
          =:[4·8·13·14·17·18·20·22·23·24·27·30·40·41·48·50·53·67·70·[...]<jupyter_text>Looking good (except that the output is longer than the line length, and so again is hard to read). 5 WeighingsWith 5 weighings, 35 = 243, so I might be able to handle up to 121 lighter-or-heavier balls (242 possibilities). Let's try:<jupyter_code>do(Puzzle(121, 5))
partition_sizes(Puzzle(121, 5), 41)<jupyter_output><empty_output><jupyter_text>Nope, that didn't work. Let's back off to 2 &times; 120 + 1 = 241 possibilities:<jupyter_code>do(Puzzle(120, 5, {-1, 0, +1}))<jupyter_output>[1·2·3·4·5·6·7·8·9·10·11·12·13·14·15·16·17·18·19·20·21·22·23·24·25·26·27·28·29·30·31·32·33·34·35·36·37·38·39·40]⚖[81·82·83·84·85·86·87·88·89·90·91·92·93·94·95·96·97·98·99·100·101·102·103·104·105·106·107·108·109·110·111·112·113·114·115·116·117·118·119·120] ➔ 
     >:[4·6·7·11·13·14·18·21·23·35·36·38·40·42·47·49·61·65·69·71·73·74·75·78·79·80·86·88·93·95·98·99·100·104·105·113·114·115·116]⚖[2·8·9·12·15·17·19·20·25·27·29·34·37·41·44·45·46·53·55·58·62·64·66·72·76·84·90·91·92·96·97·101·102·103·108·110·111·117·118] ➔ 
          >:[10·21·22·26·34·36·43·46·48·49·50·51·53·56·57·61·62·66·67·68·70·71·82·89·91·93·100·110·111·114·119·120]⚖[4·6·13·14·16·17·24·35·39·40·41·42·47·52·55·59·60·65·75·81·90·92·94·96·98·101·102·103·105·109·115·117] ➔ 
               >:[1·6·8·14·17·18·23·25·26·28·29·35·38·48·49·51·58·60·66·69·76·81·82·85·87·88·93·94·100·102·103·108·112·115]⚖[2·7·9·12·15·19·24·27·32·36·37·39·41·43·53·55·56·59·61·63·65·70·73·80·84·90·92·97·99·106·107·110·111·117] ➔ 
                    >:[4·5·66[...]<jupyter_text>That works.Or, I could solve a puzzle with 243 possibilites (the maximum possible with 5 weighings): 242 lighter-only balls, plus the possibility that no ball is odd:<jupyter_code>do(Puzzle(242, 5, {-1, 0}))<jupyter_output>[1·2·3·4·5·6·7·8·9·10·11·12·13·14·15·16·17·18·19·20·21·22·23·24·25·26·27·28·29·30·31·32·33·34·35·36·37·38·39·40·41·42·43·44·45·46·47·48·49·50·51·52·53·54·55·56·57·58·59·60·61·62·63·64·65·66·67·68·69·70·71·72·73·74·75·76·77·78·79·80·81]⚖[162·163·164·165·166·167·168·169·170·171·172·173·174·175·176·177·178·179·180·181·182·183·184·185·186·187·188·189·190·191·192·193·194·195·196·197·198·199·200·201·202·203·204·205·206·207·208·209·210·211·212·213·214·215·216·217·218·219·220·221·222·223·224·225·226·227·228·229·230·231·232·233·234·235·236·237·238·239·240·241·242] ➔ 
     >:[2·3·5·8·16·17·20·21·22·31·34·37·38·43·45·47·48·49·51·52·53·58·61·67·71·72·73·74·76·79·80·84·85·91·95·96·99·102·115·120·121·123·125·127·129·132·135·139·140·146·148·155·159·161·164·171·172·177·181·182·184·185·188·189·190·195·204·206·207·211·213·214·215·220·224·225·230·231·234·235·240]⚖[1·9·10·11·12·14·19·24·26·27·32·33·36·46·54·55·57·64·66·68·69·75·78·81·82·83·86·87·88·90·93·98·101·103·105·106·109·110·113·114·117·118·119·122·[...]
{'fraction_non_alphanumeric': 0.18461094685223914, 'fraction_numerical': 0.15670296387106078, 'mean_word_length': 4.19284778131436, 'pattern_counts': {'":': 0, '<': 186, '<?xml version=': 0, '>': 204, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '25', 'dir': 'jupyter-structured-clean-dedup', 'id': '118685', 'license': 'MIT', 'n_tokens_mistral': 14054, 'n_tokens_neox': 11387, 'n_words': 3088, 'path': 'ipynb/TwelveBalls.ipynb', 'repo_name': 'howtodowtle/pytudes', 'size': '27741'}