Solution to Riddler 10/7/20: https://fivethirtyeight.com/features/can-you-make-24/

riddler_24.py

from itertools import (permutations,
        combinations_with_replacement, product)
from toolz import mapcat
from typing import Tuple, Generator, List
from operator import add, sub, mul, truediv

ops = {'+': add, '-': sub, '*': mul, '/': truediv, '^': pow}

Numbers = Tuple[int]
Equations = Generator[Numbers, None, None]
Expression = List[int]

class NotValidEqnError(BaseException):
    pass

def rpn(expr: Expression) -> int:
    # Interestingly this is ~10x faster than writing the
    # eqn in infix and eval-ing it
    stack = []
    for s in expr:
        if s in ops:
            try:
                n = ops[s](stack.pop(), stack.pop())
                stack.append(n)
            except:
                raise NotValidEqnError
        else:
            stack.append(s)
    if len(stack) > 1: raise NotValidEqnError
    return stack[0]
  
def to_infix(expr: Expression) -> str:
    stack = []
    for s in expr:
        if s not in ops:
            stack = [s] + stack
        else:
            subexpr = f"({stack.pop(0)} {s} {stack.pop(0)})"
            stack = [subexpr] + stack

    return stack[0]


def eqn_nums(nums: Numbers) -> Equations:
    # all combs/perms of ops
    ops = combinations_with_replacement("+-/*^", len(nums) - 1)
    op_perms = mapcat(permutations, ops)
    # all number permutations, compute these now (not a gen)
    # and take the set, this will save on redundant eqns
    num_perms = set(permutations(nums))

    eqns = product(num_perms, op_perms)
    return (list(p) + list(o) for p, o in eqns)


def is_solution(nums: Numbers, t: int) -> bool:
    try:
        return rpn(nums) == t
    except NotValidEqnError:
        return False


def solutions(nums: Numbers, t: int) -> List[Expression]:
    return list(filter(lambda x: is_solution(x, t), eqn_nums(nums)))


if __name__ == "__main__":
    sols = solutions([2, 3, 3, 4], 24)
    for s in sols:
        print(to_infix(s))