William James
2/16/2016 6:03:00 PM
Given a list of integers, use the 3 basic arithmetic operators
to construct an expression in RPN (reverse polish notation)
that will evaluate to a given number. Each of the integers
must be used exactly once.
Maximal depth of stack allowed: 2
Let's see solutions in Lispy languages (i.e., not in CL).
Here's an attempt in Ruby:
def solve numbers, goal
result = []
numbers.permutation{|perm|
[:+,:-,:*].repeated_permutation(numbers.size-1){|ops|
val = perm.drop(1).zip(ops).
reduce(perm[0]){|acc,(n,op)| acc.send(op, n)}
if val == goal
result << [perm[0], perm[1..-1].zip(ops)].join(" ")
end } }
result.uniq
end
solve([1,1,2,3,5,8], 196)
===>
["2 3 + 8 * 1 - 5 * 1 +", "3 2 + 8 * 1 - 5 * 1 +"]
solve([1,2,3,50,72,96], 202)
===>
["96 50 - 3 * 1 - 2 * 72 -"]
solve([1,2,3,50,72,96], 245)
===>
["96 72 - 3 * 50 + 2 * 1 +"]
solve [1,1,1,3,50,100], 403
===>
["1 1 + 50 * 1 + 3 * 100 +"]
--
[T]he two races, equally free, cannot live under the same
government. --- Thomas Jefferson
Let us be brought to believe it is ... favorable to ... our interest to
transfer the African to his native clime, and we shall find a way to do it,
however great the task may be. --- A. Lincoln, Sept. 22, 1856