File information
Filename: arithmetic-combinatorics.py Uploaded: Sun, 8th Nov 2009 04:46:52
Size (bytes): 4.9 KiB md5 checksum: 37dfb6724ca56827776aa8b227fada10
Description:

Ever had people present a set of numerical terms and said:

"How can you get this specific result when you construct an expression out of these given numerical terms?"

This program computes all possible solutions derived from all possible combinations of a set of terms and a set of binary operators that are equal to the given target result.

```"""
Ever had people present a set of numerical terms and said "How can you get this
specific result when you construct an expression out of these given numerical
terms?". This program is to hard-compute all possible solutions derived from all
possible combinations of a set of terms and a set of binary operators that are
equal to the given target result.

Coded for educational and hobbyist purposes only.
"""

__author__ = "doug@neverfear.org"

import sys, getopt

available_operators = {
"s": "-", # Subtraction
"a": "+", # Addition
"m": "*", # Multiplication
"d": "/", # Division
"e": "**" # Exponentiation
}

def usage(name):
print "Usage: %s [OPTIONS] TERMS" % name
print "Options:"
print "-h  --help              Show this help."
print "-t  --target TARGET     Set the target result."
print "-s  --subtraction       Use subtraction."
print "-m  --multiplication    Use multiplication."
print "-d  --division          Use division."
print "-e  --exponentiation    Use exponentiation."
print "If no arithmetic operations are specified then -samde is assumed"
print

def test(expr, target):
try:
return eval(expr) == target
except: # Protect against things like ZeroDivisionError
return False

def solve(terms, target, operators, expr = None):
count = 0
solutions = []

if not expr:
# Generate the first operation
for i, a in enumerate(terms):
for j, b in enumerate(terms):
if i != j:
newterms = list(terms)
newterms.remove(a)
newterms.remove(b)

for operator in operators:
newexpr = "%.1f %s %.1f" % (a, operator, b)
if newterms:
s, n = solve(newterms, target, operators, newexpr)
count += n
solutions += s
else:
count += 1
if test(newexpr, target):
solutions.append(newexpr)

else:
# Combine another term into the existing expression
for a in terms:
newterms = list(terms)
newterms.remove(a)

for operator in operators:

expressions = ["(%s) %s %.1f" % (expr, operator, a),
"%.1f %s (%s)" % (a, operator, expr)]

if newterms:
for expression in expressions:
s, n = solve(newterms, target, operators, expression)
count += n
solutions += s
else:
for expression in expressions:
count += 1
if test(expression, target):
solutions.append(expression)

return (solutions, count)

operators = []

terms  = []
target = None
try:
opts, args = getopt.getopt(sys.argv[1:], "ht:samde",
["help",
"target=",
"subtraction",
"multiplication",
"division",
"exponentiation"])
except getopt.GetoptError, err:
print str(err)
usage(sys.argv[0])
sys.exit(2)

for name, value in opts:
if   name == "-h":
usage(sys.argv[0])
sys.exit(0)

elif name in ["-s", "-a", "-m", "-d", "-e"]:
operators.append(available_operators[name[1]])

elif name in ["--subtraction", "--addition", "--multiplication",
"--division", "--exponentiation"]:
operators.append(available_operators[name[2]])

elif name in ("-t", "--target"):
try:
target = float(value)
except:
print "Invalid target", value
sys.exit(3)

if target is None:
print "No target given"
usage(sys.argv[0])
sys.exit(4)

for arg in args:
try:
terms.append(float(arg))
except:
print "Invalid term", arg
sys.exit(5)

if not terms:
print "No terms given"
usage(sys.argv[0])
sys.exit(6)

if not operators:
operators = available_operators.values()

(solutions, count) = solve(terms, target, operators)

print count, "combinations tested and found", len(solutions), "solutions"
print "Solutions:"
format = "Solution #%%-%dd: %%s" % (len(str(len(solutions))))
for i, solution in enumerate(solutions):
print format % (i + 1, solution)

```
Powered by Debian, Guinness, and excessive quantities of caffeine and sugar.