Last active
September 29, 2018 21:25
-
-
Save dlenski/c4c3c2c318c1bbba6fdb144d2073beeb to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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