Rewriting a coin flipping script
February 1, 2025 at 11:20 AM by Dr. Drang
I recently came across this post, written ten years ago, in which I used a short Python script to solve a simple enumeration puzzle. Looking at the code, I realized how differently I would look at this problem today; partly because I know more Python libraries than I did then, and partly because I now consciously try to work at a higher level of abstraction.
The puzzle is this: Eight people are sitting around a circular table. Each has a coin. They all flip their coins. What is the probability that no two adjacent people will get heads?
Here’s the script from ten years ago. I’ve updated it only in the shebang line and the print
statements to allow it to work in Python 3.
python:
1: #!/usr/bin/env python3
2:
3: f = 8
4: flips = list('-' * (f))
5: seqs = []
6:
7: def sequpdate(flips):
8: global seqs
9: heads = flips.count('H')
10: circle = flips[-1] + ''.join(flips)
11: if circle.find('HH') == -1:
12: seqs.append('%d heads: %s' % (heads, ''.join(flips)))
13:
14: def sequence(m):
15: global flips
16: if m == 1:
17: flips[-m] = 'T'
18: sequpdate(flips)
19: flips[-m] = 'H'
20: sequpdate(flips)
21: else:
22: flips[-m] = 'T'
23: sequence(m-1)
24: flips[-m] = 'H'
25: sequence(m-1)
26:
27: sequence(f)
28: print('%d sequences' % len(seqs))
29: seqs.sort()
30: print("\n".join(seqs))
No imported libraries, just recursion to build up a list of sequences that meet the “no adjacent heads” criterion.
Here’s how I would (and did) write it now:
python:
1: #!/usr/bin/env python3
2:
3: from itertools import product
4:
5: seats = 8
6:
7: # Generate all possible coin flip sequences. Append the first flip
8: # to the end because those seats are adjacent.
9: circles = [ ''.join(x) + x[0] for x in product('HT', repeat=seats) ]
10:
11: # Print the number of sequences without adjacent heads.
12: # Remove the appended flip from each sequence.
13: nonadjacent = [ x[:-1] for x in circles if 'HH' not in x ]
14: print(f'{len(nonadjacent)} sequences')
15:
16: # Sort the nonadjacent sequences according to number of heads and print them.
17: nonadjacent.sort(key=lambda s: s.count('H'))
18: for s in nonadjacent:
19: print(f'{s.count('H')} heads: {s}')
Yes, it’s shorter, but I think it’s also clearer, at least if you understand what the product
function from the itertools
module does. It works out what in linear algebra would be called the outer product and what in set theory would be called the Cartesian product. Typically, you give it two or more iterables as arguments and it returns an iterable of every possible tuple of the elements of the inputs. For example,
list(product('HT', 'HT'))
returns
[('H', 'H'),
('H', 'T'),
('T', 'H'),
('T', 'T')]
(I wrapped the product
call in a list
to get all the items of the iterable.)
This is all the possible ways to flip two coins. To get all the possibilities when flipping three coins, we use
list(product('HT', 'HT', 'HT'))
to get
[('H', 'H', 'H'),
('H', 'H', 'T'),
('H', 'T', 'H'),
('H', 'T', 'T'),
('T', 'H', 'H'),
('T', 'H', 'T'),
('T', 'T', 'H'),
('T', 'T', 'T')]
We could continue in this way to get the possibilities when flipping eight coins, but there’s a shortcut via the repeat
parameter when the input is just multiples of the same thing. So
list(product('HT', repeat=4))
returns
[('H', 'H', 'H', 'H'),
('H', 'H', 'H', 'T'),
('H', 'H', 'T', 'H'),
('H', 'H', 'T', 'T'),
('H', 'T', 'H', 'H'),
('H', 'T', 'H', 'T'),
('H', 'T', 'T', 'H'),
('H', 'T', 'T', 'T'),
('T', 'H', 'H', 'H'),
('T', 'H', 'H', 'T'),
('T', 'H', 'T', 'H'),
('T', 'H', 'T', 'T'),
('T', 'T', 'H', 'H'),
('T', 'T', 'H', 'T'),
('T', 'T', 'T', 'H'),
('T', 'T', 'T', 'T')]
This is what we use in the list comprehension of Line 9 to get all 256 possiblities for eight coin flips. Line 9 also uses the join
function to turn each tuple into a string, and it adds the first coin flip to the end of each string so we can later (in Line 13) prune this list down to just those possibilities that don’t have two adjacent heads.
To get output that matches that of the original script, we sort the nonadjacent
list (Line 17) by the number of heads in each sequence (note that the trailing coin flip that was added in Line 9 is removed in Line 13) before printing the list of sequences along with the head counts. The output is
47 sequences
0 heads: TTTTTTTT
1 heads: HTTTTTTT
1 heads: THTTTTTT
1 heads: TTHTTTTT
1 heads: TTTHTTTT
1 heads: TTTTHTTT
1 heads: TTTTTHTT
1 heads: TTTTTTHT
1 heads: TTTTTTTH
2 heads: HTHTTTTT
2 heads: HTTHTTTT
2 heads: HTTTHTTT
2 heads: HTTTTHTT
2 heads: HTTTTTHT
2 heads: THTHTTTT
2 heads: THTTHTTT
2 heads: THTTTHTT
2 heads: THTTTTHT
2 heads: THTTTTTH
2 heads: TTHTHTTT
2 heads: TTHTTHTT
2 heads: TTHTTTHT
2 heads: TTHTTTTH
2 heads: TTTHTHTT
2 heads: TTTHTTHT
2 heads: TTTHTTTH
2 heads: TTTTHTHT
2 heads: TTTTHTTH
2 heads: TTTTTHTH
3 heads: HTHTHTTT
3 heads: HTHTTHTT
3 heads: HTHTTTHT
3 heads: HTTHTHTT
3 heads: HTTHTTHT
3 heads: HTTTHTHT
3 heads: THTHTHTT
3 heads: THTHTTHT
3 heads: THTHTTTH
3 heads: THTTHTHT
3 heads: THTTHTTH
3 heads: THTTTHTH
3 heads: TTHTHTHT
3 heads: TTHTHTTH
3 heads: TTHTTHTH
3 heads: TTTHTHTH
4 heads: HTHTHTHT
4 heads: THTHTHTH
This is the same output returned by the original script. I checked this by running
ksdiff <(./coin-flips-recurse.py) <(./coin-flips-product.py)
where coin-flips-recurse.py
is the original script, coin-flips-product.py
is the new one, and ksdiff
is the command line tool that opens Kaleidoscope, the nicely graphical diffing app. If you’re unfamiliar with the <(command)
syntax, it’s what’s called process substitution and treats the output of the command inside the parentheses like a file to be sent to another command. I’ve linked to the bash documentation for process substitution; the same syntax works in zsh.
Obviously, you don’t have to use Kaleidoscope. The standard diff
command also works
diff <(./coin-flips-recurse.py) <(./coin-flips-product.py)
but it won’t show anything. diff
shows only the differences between its inputs, and there aren’t any in this case.
There was no particular reason for me to rewrite this script, but it’s nice to know that old dogs can learn new tricks. Especially when you’re the old dog.