https://fivethirtyeight.com/features/the-robot-invasion-has-come-for-our-pool-halls/

robopool.py

#!/usr/bin/env python3

'''
Exhaustive solution to 
    https://fivethirtyeight.com/features/the-robot-invasion-has-come-for-our-pool-halls/

Consider 15 standard pool balls arranged in a triangle (7 solids, 7 stripes, one 8-ball).
- Solids are all equivalent to each other
- Stripes are all equivalent to each other
- Robot can perform one of three operations: rotate 120° CW, rotate 120° CCW, swap 2 balls

Main problems:
1) What is the maximum number of operations the robot may need to perform to rearrange
   the balls into a standard 8-ball rack (see 'standard = ' below)?
2) What starting arrangement gives that number of operations?
3) What is the AVERAGE number of operations required to rearrange balls into the standard
   rack pattern?

Answers via: `robopool.py --above 6`

Extra credit:
1) What is the maximum number of operations the robot would need to rearrange the
   balls between ANY two possible arrangements?
2) What are those starting/ending arrangements?

Answers via `robopool.py --pessimal --above 8`
'''

import argparse
from itertools import cycle
from math import ceil

########################################

# This class represents a triangular arrangement of 15 pool balls:
#   7 solid ('O'), 7 striped ('/'), and one 8-ball ('8')

class Rack(object):
    __slots__ = ('rack',)
    
    def __init__(self, rack, check=True):
        '''Rack input string must contain 7×'O', 7x'/', 1x'8', ignoring whitespace'''
        self.rack = ''.join(c for c in rack if not c.isspace())
        if check:
            self.check()

    def check(self):
        '''Verify the validity of the rack'''
        r = self.rack
        assert len(r) == 15
        assert r.count('8') == 1
        assert r.count('O') == r.count('/') == 7
        
    def rotCW(self):
        '''Rotate 120° clockwise'''
        r = self.rack
        return Rack(
                           r[10] +
                       r[11] + r[6] +
                   r[12] + r[7] + r[3] +
               r[13] + r[8] + r[4] + r[1] +
            r[14] + r[9] + r[5] + r[2] + r[0] )

    def rotCCW(self):
        '''Rotate 120° counterclockwise'''
        return self.rotCW().rotCW()

    def compare(self, other):
        '''Return the number of places where this rack is mismatched to another rack,
        after no rotation, CW rotation, or CCW rotation'''
        nS   = sum(a!=b for a,b in zip(self.rack, other.rack))
        nCW  = sum(a!=b for a,b in zip(self.rotCW().rack, other.rack))
        nCCW = sum(a!=b for a,b in zip(self.rotCCW().rack, other.rack))
        return nS, nCW, nCCW

    def __str__(self):
        r = self.rack
        return (    '    ' + r[0]
                + '\n   '  + ' '.join(r[1:3])
                + '\n  '   + ' '.join(r[3:6])
                + '\n '    + ' '.join(r[6:10])
                + '\n'     + ' '.join(r[10:15]))

########################################

# Give (a) argyle socks and (b) black socks, return all distinct combinations of the (a+b)
# socks via run-length encoding:
#   [take X argyle, take Y black, take Z argyle, take W black, ...]

def interleave(a, b):
    def _x(a, b):
        yield [a, b]                       # take all socks in 2 steps
        for A in range(1, a):
            yield [a-A, b, A]              # take all socks in 3 steps
            for B in range(1, b):
                for l in _x(A, B):
                    yield [a-A, b-B] + l   # take some socks in 2 steps; recurse
                    
    yield from _x(a, b)                    # take from a first
    yield from ([0] + l for l in _x(b, a)) # take from b first

########################################

# standard 8-ball rack

standard = Rack('''
        O
       / O
      O 8 /
     / O / O
    O / / O /''')

# pessimal goal rack (one of many):
#   inverting stripes/solids and swapping the 8 with
#   an edge/corner ball means that neither CW nor CCW
#   rotation will bring >2 balls into alignment

pessimal = Rack('''
        /
       O /               
      O / O             
     / 8 O O
    / O O / /''')

########################################

p = argparse.ArgumentParser()
p.add_argument('--check', action='store_true', help='Sanity checks (slower)')
p.add_argument('--below', default=-1, type=int, help='Show racks requiring no more than this many operations to reach the goal')
p.add_argument('--above', default=99, type=int, help='Show racks requiring at least this many operations to reach the goal')
x = p.add_mutually_exclusive_group()
x.add_argument('--custom', dest='goal', type=Rack, default=standard, help='Custom goal rack (default is 8-ball standard)')
x.add_argument('--pessimal', dest='goal', action='store_const', const=pessimal, help='Goal is worst case-rack')
args = p.parse_args()

ii = 0
opreq_count = [0]*9
all_racks = set()

# Iterate through all the possible triangular arrangements of 15 pool balls. They number:
#     15 positions for 8-ball
#   x 14-choose-7 positions for solids 
#   = 54180

for pos8 in range(15):
    for interleavings in interleave(7, 7):
        without8 = ''.join(c*n for c,n in zip(cycle('O/'), interleavings))
        with8 = without8[:pos8] + '8' + without8[pos8:]

        rack = Rack(with8, args.check)
        if args.check:
            # check that we are not duplicating any patterns
            assert with8 not in all_racks
            all_racks.add(with8)

        # Number of positions differing from goal after no/CW/CCW rotation
        r0, rCW, rCCW = rack.compare(args.goal)

        # Minimum number of operations (2-ball swaps and 120° rotations) required
        # to change this rack arrangement into the goal arrangement.
        #
        #   - Start off with one 120° rotation if that rotation brings AT LEAST
        #     two more balls into the correct position, compared to the unrotated
        #     position. (Thereby saving ≥1 swap.)
        #
        #   - After optional rotation, if N positions contain the wrong ball, then
        #     they can be fixed in ceil(N/2) swaps.
        #
        #   - The order of rotation does not matter, and more than one rotation is
        #     never optimal.
        #     * Rotating, then doing N swaps, then rotating back to undo the first
        #       rotation is entirely equivalent to a different set of N swaps.
        #     * Rotating, then doing N swaps, then rotating again in the same
        #       direction is entirely equivalent to a single rotation in the
        #       opposite direction, plus a different set of N swaps.
        #
        # Operations required, including optional initial rotation:
        op0, opCW, opCCW = ceil(r0/2), 1+ceil(rCW/2), 1+ceil(rCCW/2)
        
        opreq = min(op0, opCW, opCCW)
        opreq_count[opreq] += 1

        ii += 1
        if opreq <= args.below or opreq >= args.above:
            print("Rack %05d has %d/%d/%d misplaced balls after no/CW/CCW rotation; requires %d robot operations to rack" % (ii, r0, rCW, rCCW, opreq))
            print("%s\n" % rack)

if args.check:
    assert ii == 51480 

nn = sum = 0
print("Summary:")
for opreq, count in enumerate(opreq_count):
    print("  %d racks require %d robot operations to rack" % (count, opreq))
    nn += count
    sum += count*opreq
else:
    print("  Average rack requries %g robot operations to rack" % (sum/nn))