Giant Cat Army riddle

giant_cat_army.py

#!/usr/bin/env python3

# Enumerate all solutions to the TED-Ed riddle
# https://www.youtube.com/watch?v=YeMVoJKn1Tg


def main():
    target = [0, 2, 10, 14]
    count = 0
    unique_code_sets = set()
    unique_keypresses = set()
    for seq in find_sequences(target):
        # You can switch the commented lines below to inspect either code
        # sequences or keypresses.
        print(" ".join(map(lambda x: str(x), seq)))
        # print(" ".join(decode(seq)))
        count += 1
        unique_code_sets.add(tuple(sorted(seq)))
        unique_keypresses.add(tuple(sorted(decode(seq))))
    print(f"SOLUTION COUNT: {count}")
    print(f"UNIQUE CODE SETS: {len(unique_code_sets)}")
    print(f"UNIQUE KEYPRESS SETS: {len(unique_keypresses)}")
    # NOTE: Interestingly, there are exactly 98 unique codes and 98 unique code
    # point sets. In other words, no acceptable code sequence is a permutation
    # of another. On the other hand, there is exactly _one_ set of permissible
    # keypresses. Moreover, by inspecting the output, you see that the sqrt
    # operations always come at the same spot and always produce the same
    # values. The code rules (no duplicate codes, etc.) make for a generally
    # messy combinatorial structure. For example, _some_ spots always have the
    # same keypress operations, while others can interchange +5 and +7. However,
    # the number of subsequences within a given "exchangeable" 5/7 sequence
    # cannot be counted using binomial coefficients due to the uniqueness
    # constraint.


def find_sequences(target):

    def rec(suffix, target):
        if len(target) == 0:
            yield suffix
        for pred in predecessors(suffix):
            if pred == target[-1]:
                # We just produced the next target. Make sure to lop that off of
                # the existing target before recursing.
                yield from rec([pred] + suffix[:], target[:-1])
            elif pred not in target:
                # Otherwise, we did not produce the next target value. In that
                # case, we need to ensure that the new head of the list is not
                # some _earlier_ target, which cannot come next in our sequence.
                # In this case, we prepend to the suffix but do not update
                # target.
                yield from rec([pred] + suffix[:], target)

    # NOTE: By ensuring that suffix is always non-empty, we simplify the
    # predecessors logic below.
    yield from rec([target[-1]], target[:-1])


def predecessors(suffix):
    head = suffix[0]
    if head >= 5 and (head - 5 not in suffix):
        yield head - 5
    if head >= 7 and (head - 7 not in suffix):
        yield head - 7
    if head < 8 and (head * head not in suffix):
        yield head * head


def decode(seq):
    # Convert the observed sequence of numbers into the keypresses that
    # generated them.
    for a, b in zip(seq[:-1], seq[1:]):
        if a + 5 == b:
            yield "+5"
        elif a + 7 == b:
            yield "+7"
        elif a == b * b:
            yield "sqrt"
        else:
            raise Exception(f"invalid transition: {a} -> {b}")


if __name__ == "__main__":
    main()