toast.py

from itertools import permutations, pairwise
from pprint import pprint
from typing import Iterable

"""
https://fivethirtyeight.com/features/can-you-turn-digits-into-numbers/
From Jeremy Dixon comes a “toasty” treat of a puzzle:

You have a toast rack with five slots, arranged in an array. Each slot has a slice of 
toasted bread, which you are removing one at a time. However, you are quite 
superstitious, and you know it's bad luck to remove adjacent pieces of toast one after 
the other. (What? You've never heard that before? It's totally a thing!)

How many different ways can you remove the slices of toast?

Extra credit: Instead of five slots, suppose you have a rack with six slots and six 
slices of toast. Now how many different ways can you remove the slices without ever 
removing adjacent pieces one after the other?
"""


def is_bad(v: Iterable) -> bool:
    for a, b in pairwise(v):
        if (a - b) in (-1, 1):
            return True
    return False


def find_good_perms(n_slices: int) -> list[tuple[int, ...]]:
    a = tuple(range(1, n_slices + 1))
    return [p for p in permutations(a) if not is_bad(p)]


if __name__ == "__main__":
    gp = find_good_perms(6)
    pprint(gp)
    print(f"\nThere were {len(gp)} good permutations")