Skip to content

Instantly share code, notes, and snippets.

@dlenski
Last active September 29, 2018 21:25
Show Gist options
  • Save dlenski/c4c3c2c318c1bbba6fdb144d2073beeb to your computer and use it in GitHub Desktop.
Save dlenski/c4c3c2c318c1bbba6fdb144d2073beeb to your computer and use it in GitHub Desktop.
#!/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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment