three_coins.py

#!/usr/bin/env python3
#
# Author: Lowell Vaughn
# Answer to The "Fiddler on the Proof" for November 17, 2023 
# https://open.substack.com/pub/thefiddler/p/can-you-flip-the-coins-exactly-as

from collections import Counter
from fractions import Fraction
from typing import Tuple

# A map that takes a number 0-7 and returns the number of bits that or 1's in the 
# binary representation (or in this case, the number of heads)
n_to_heads = {0: 0, 1: 1, 2: 1, 3: 2, 4: 1, 5: 2, 6: 2, 7: 3}

def test_int(n: int) -> Tuple[bool, Tuple[int, int, int, int]]:
    """
        Takes an 21 bit integer and checks if it represents a "1, 3, 3, 1" set of coin flips.
        The integer is the binary representation of the 24 coin flips.  The first 3 bits represent
        the first 3 coin flips, the next 3 bits represent the next 3 coin flips, etc.
        
        For instance 0b111001010100000110101011 (15024555) is a sequence of with one 3 heads flip, 
        three 1 head flips, three 2 head flips, and one 0 head flip.

    Args:
        n (int): The number to check (which is the binary representation of the 24 coin flips)

    Returns:
        bool: Does this represent a "1, 3, 3, 1" set of coin flips
        Tuple[int, int, int, int]: The sequence for the extra credit
    """
    trials = 0
    occurances = [0, 0, 0, 0] # The number of times we see 0 heads, 1 head, etc...
    while trials < 8:
        x = n_to_heads[n % 8]
        occurances[x] += 1  
        n //= 8
        trials += 1
    return occurances == [1,3,3,1], tuple(sorted(occurances, reverse=True))


total_hits = 0
extra_credit = Counter()
for n in range(2**24):
    hit, occurances = test_int(n)
    extra_credit[occurances] += 1
    if hit:
        total_hits += 1
        
final_fraction = Fraction(total_hits, 2**24)
print(f"Part one: { total_hits / (2**24):.7f} ({total_hits}/{2**24}) or ({final_fraction.numerator}/{final_fraction.denominator})")
print("Extra Credit:")
for value, count in extra_credit.most_common():
    print(f"  {value}: {count/(2**24):.6f}")