Is there any function that can take input(arrays of numbers) and find all possible calculations on them that would result in the desired result(number).
For example if input is 2, 1, 4, 6, 7 and the desired result is 3. It would return something like.
2+1 = 3
7-4 = 3
6/2 = 3
On
What you want to do is to evaluate all possible calculations & find options leading to the correct result.
One easy way to structure it is to implement a RPN calculation (reverse polish notation). https://en.wikipedia.org/wiki/Reverse_Polish_notation
Basically what you have to do is to enumerate stacks of numbers & operators so that you have always one more numebr than operators.
On
I thought that this was a fun problem, so I decided to demonstrate how to do it efficiently. On my system it takes about half a second to find all 4193 solutions.
The trick is to use dynamic programming to build a data structure from which the expressions can all be found efficiently.
from fractions import Fraction
def bit_subset(index, things):
i = 0
bit = 1
answer = []
while bit <= index:
if bit & index:
answer.append(things[i])
i += 1
bit += bit
return answer
def indexes_to_bit_subset(indexes):
answer = 0
for index in indexes:
answer += 2**index
return answer
def calculation_tree (digits):
# Here is the tree structure:
#
# By bit_integer of subset used
# By value reached
# [
# count_of_ways,
# [
# [
# count,
# first subset bit_integer,
# first value,
# op ('+', '-', '*', '/', None),
# second subset bit_integer (may be 0),
# second value (may be None)
# ]
# ]
# ]
#
tree = {}
# Populate with all of the raw numnbers.
for i in range(len(digits)):
# By bit_integer for 1 thing.
tree[2**i] = {
# By value reached (use fractions to avoid roundoff
Fraction(digits[i], 1): [
# Just 1 way to do it.
1,
# What are the ways? Let me tell you!
[[1, 2**i, digits[i], None, 0, None]]
]
}
# This loops over all subsets with something in the first.
for subset_index in range(1, 2**len(digits)):
# The indexes into the chosen subset.
index_subset = bit_subset(subset_index, list(range(len(digits))))
if subset_index not in tree:
subtree = {}
tree[subset_index] = subtree
# Look at ways to split it with something in both sides
for sub_subset_index in range(1, 2**len(index_subset)-1):
co_subset_index = 2**(len(index_subset)) - 1 - sub_subset_index
# We have a split by indexes into index_subset.
# We need to turn that into a split by indexes into digits
# Which we represent by integers representing bits.
index_sub_subset = bit_subset(sub_subset_index, index_subset)
sub_subset_bit_index = indexes_to_bit_subset(index_sub_subset)
index_co_subset = bit_subset(co_subset_index, index_subset)
co_subset_bit_index = indexes_to_bit_subset(index_co_subset)
# Let's pull out the already known calculation results.
subtree1 = tree[sub_subset_bit_index]
subtree2 = tree[co_subset_bit_index]
for value1 in subtree1.keys():
count1 = subtree1[value1][0]
for value2 in subtree2.keys():
count2 = subtree2[value2][0]
# We now have to add each possible operation result to subtree
options = {
'+': value1 + value2,
'-': value1 - value2,
'*': value1 * value2,
}
if value2 != 0:
options['/'] = value1 / value2
for op, value in options.items():
if value in subtree:
subtree[value][0] += count1 * count2
subtree[value][1].append([
count1 * count2,
sub_subset_bit_index,
value1,
op,
co_subset_bit_index,
value2
])
else:
subtree[value] = [
count1 * count2,
[[
count1 * count2,
sub_subset_bit_index,
value1,
op,
co_subset_bit_index,
value2
]]
]
return tree
# Yields the expressions that result in value
def expression_iter (tree, bit_integer, value):
if bit_integer in tree:
subtree = tree[bit_integer]
if value in subtree:
ways = subtree[value][1]
for (
count,
bit_integer1, value1,
op,
bit_integer2, value2
) in ways:
if op is None:
yield str(value1)
else:
for expr1 in expression_iter(tree, bit_integer1, value1):
for expr2 in expression_iter(tree, bit_integer2, value2):
yield f'({expr1} {op} {expr2})'
def all_expressions(digits, target):
tree = calculation_tree(digits)
frac_target = Fraction(target, 1)
for bit_integer, subtree in tree.items():
if frac_target in subtree:
for expr in expression_iter(tree, bit_integer, frac_target):
yield expr
for expr in all_expressions([2, 1, 4, 6, 7], 3):
print(expr)
What I think you can do is you can make it generate random numbers using a rng
module. Make them do random numbers in a rational range and do random operations with them. Print the equations IF they equal a certain number. YOu could also make a simple AI like thing that sets a rational range of the random numbers to make it faster. (Notice/edit, the random range selects a number and the number is converted to one of the input numbers.)
EXAMPLE