twenty_four_game.py

import operator
import itertools
import math
import collections

_SYMBOL_TO_OP = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.truediv,
                 '!': lambda a, b: b-a, '@': lambda a, b: b/a}
_R_OP = {'!': '-', '@': '/'}


def is_close(a, b, eps=1e-9):
    return math.fabs(a-b) < eps


def is_fraction(num):
    return not is_close(num, round(num))


class ExpressionTree:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data
        self.difficulty = None  # number of calculations resulting fractions

    def is_leaf(self):
        if self.left is None:
            assert self.right is None
            return True
        return False

    def __repr__(self):
        if self.is_leaf():
            return repr(self.data)
        if self.data in _R_OP:
            return '(%s%s%s)' % (self.right, _R_OP[self.data], self.left)
        return '(%s%s%s)' % (self.left, self.data, self.right)

    def calc(self):
        if self.is_leaf():
            self.difficulty = 0
            return self.data
        left = self.left.calc()
        right = self.right.calc()
        self.difficulty = self.left.difficulty + self.right.difficulty
        result = _SYMBOL_TO_OP[self.data](left, right)
        if is_fraction(result):
            self.difficulty += 1
        return result


class TwentyFourGame:
    def __init__(self, target, *, cards=None, deck=None, n_cards=None):
        self.target = target
        self.cards = cards
        self.deck = deck
        self.n_cards = n_cards
        if cards is None:
            assert deck is not None and n_cards is not None
            self.deck, self.replacement = self.deck
        if deck is None or n_cards is None:
            assert cards is not None
            n = len(cards)
            assert n >= 1
            self.n_cards = n

    @staticmethod
    def create_all_trees(card_subset):
        n = len(card_subset)
        if n == 1:
            yield ExpressionTree(card_subset[0])
        else:
            for i in range((n+1)//2, n):
                left_subtrees = TwentyFourGame.create_all_trees(card_subset[:i])
                right_subtrees = list(TwentyFourGame.create_all_trees(card_subset[i:]))
                for left in left_subtrees:
                    for right in right_subtrees:
                        for op in _SYMBOL_TO_OP.keys():
                            root = ExpressionTree(op)
                            root.left = left
                            root.right = right
                            yield root

    def find_solutions(self, difficulty=0):
        lowest_difficulty = collections.defaultdict(lambda: self.n_cards)
        solutions = {}
        if self.cards is None:
            card_sets = itertools.combinations_with_replacement(self.deck, self.replacement)
        else:
            card_sets = [self.cards]
        for cards in card_sets:
            # only one solution for each card set
            signature = tuple(sorted(cards))
            if lowest_difficulty[signature] >= difficulty:
                for perm in itertools.permutations(cards):
                    all_trees = TwentyFourGame.create_all_trees(perm)
                    for tree in all_trees:
                        try:
                            if is_close(tree.calc(), self.target):
                                if tree.difficulty < lowest_difficulty[signature]:
                                    lowest_difficulty[signature] = tree.difficulty
                                    solutions[signature] = tree
                        except ZeroDivisionError:
                            continue
        n_solutions = 0
        if len(solutions) > 0:
            for _, tree in solutions.items():
                if tree.difficulty >= difficulty:
                    print('%s %s %g\tDifficulty: %d' % (repr(tree)[1:-1], '=', self.target, tree.difficulty))
                    n_solutions += 1
        if n_solutions == 0:
            print('No solution!')
        return solutions


if __name__ == '__main__':
    # cards = [1, 5, 7, 10]
    n_cards = 4
    deck = (range(1, 14), 4)
    target = 24
    # game = TwentyFourGame(target, cards=cards)
    game = TwentyFourGame(target, deck=deck, n_cards=n_cards)
    game.find_solutions(difficulty=2)

Usage

1. pass target and cards to TwentyFourGame, then find_solutions will find the solution of the given cards if there's any. Example:

   cards = [3, 3, 8, 8]
   target = 24
   game = TwentyFourGame(target, cards=cards)
   game.find_solutions()  # prints "8/(3-8/3) = 24"

2. or, pass target, deck and n_cards to TwentyFourGame, then find_solutions will find all the solutions from the deck using n_cards cards. Example:

   n_cards = 4
   deck = (range(1, 14), 4)  # (unique numbers in the deck, repetition of each number). Now it is the standard 52-card deck.
   target = 24
   game = TwentyFourGame(target, deck=deck, n_cards=n_cards)
   game.find_solutions()

3. the difficulty of a solution is defined as the number of operations that give fractions. Setting a value for the difficulty argument in find_solutions will let it print the solutions with at least the specified level of difficulty.