A brute-force solution to Carnac the Magnificent

carnac.py

"""Carnac the Magnificent!

http://raganwald.com/2015/05/08/carnac-the-magnificent.html
https://news.ycombinator.com/item?id=9511700
"""

import itertools
import sys


INPUT_STR = '123456789'


def permutation_str(permutation):
    result = INPUT_STR[0]
    for i, permutation_op in enumerate(permutation, start=1):
        result += "%s%s" % (permutation_op.strip(), INPUT_STR[i])
    return result


def eval_permutation(permutation):
    # print "permutation: %s" % permutation_str(permutation)
    result = 0
    next_op = '+'
    next = INPUT_STR[0]
    for i, permutation_op in enumerate(permutation, start=1):
        # print (i, permutation_op, next, next_op, result)
        if permutation_op != ' ':
            if next_op == '+':
                result += int(next)
            elif next_op == '-':
                result -= int(next)
            else:
                raise Exception("Unknown op %s" % next_op)
            next_op = permutation_op
            next = ''
        next += INPUT_STR[i]
    if next_op == '+':
        result += int(next)
    elif next_op == '-':
        result -= int(next)
    return result


def do_all():
    good = bad = 0
    all_permutations = itertools.product(' +-', repeat=8)
    for permutation in all_permutations:
        if eval_permutation(permutation) == 100:
            print "good permutation: %s" % permutation_str(permutation)
            good += 1
        else:
            bad += 1
    print "good=%s bad=%s" % (good, bad)


def _test_permutation(permutation, expected_result):
    print "\ttesting %s ..." % permutation_str(permutation)
    result = eval_permutation(permutation)
    assert result == expected_result, "eval_permutation() returned %s (not %s) for %s" % (
        result,
        expected_result,
        permutation_str(permutation)
    )

def test():
    print "testing..."
    _test_permutation(('+', ' ', ' ', '+', '-', '-', '+', '-'), 226)
    print "tests pass"


def main():
    if len(sys.argv) > 1 and sys.argv[1] == 'test':
        return test()
    do_all()


if __name__ == '__main__':
    main()