Solving Num: A combinatoric math game

Coincidentally I was just solving (a variant of) this problem today. The approach I took is taking the list of numbers and recursively replacing each pair (x, y) with x+y (replace + with any operation), until one element remains.<p>You can separate the process by transforming the list of numbers into a binary tree and applying the operators at the nodes. You then consider all possible binary trees and all combinations of operators.<p>Bonus: by sorting the input values, you can consider half of the trees, because the operations either commute (x+y = y+x) or don&#x27;t make sense to reverse in the integers (4&#x2F;2 vs. 2&#x2F;4).

There is a similar game that is available for Android and iOS called Calculords (<a href="http:&#x2F;&#x2F;calculords.com&#x2F;" rel="nofollow">http:&#x2F;&#x2F;calculords.com&#x2F;</a>) The goal is to apply arithmetic operations on a set of numbers in order to get outputs which correspond to your available attacks. It is not as strict as Num, where only one output is expected.<p>I like this solver, which uses a dynamic programming&#x2F;search approach to find solutions. <a href="https:&#x2F;&#x2F;github.com&#x2F;SomeKittens&#x2F;calculords-solver" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;SomeKittens&#x2F;calculords-solver</a>

See also Krypto <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Krypto_(game)" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Krypto_(game)</a><p>Some friends and I were hooked on this game in college. We eventually wrote a program to solve particularly tough hands. It turns out there are a few potential hands that are actually impossible to solve, but not very many! It&#x27;s a fun programming problem. :-)<p>There&#x27;s a mobile version of Krypto as well.

1) 3<i>9+5</i>25+7-8 also works if I understand the problem. 2) You can optimize using various number-theoretic principles -- checked division and subtraction<p>3) C++ is much much faster for this -- less than a second on my boxes.<p>Not sure where people get the idea of dynamic programming -- you can do some dynamic tree cutting (e.g. if you don&#x27;t have enough operators to get to your target), but there&#x27;s no real objective function here.

You should be able to find some info with the keyword &quot;countdown&quot;. This is a TV game which seems very close (identical ?) to yours.<p>E.G.: <a href="https:&#x2F;&#x2F;mail.python.org&#x2F;pipermail&#x2F;python-list&#x2F;2008-January&#x2F;thread.html#468792" rel="nofollow">https:&#x2F;&#x2F;mail.python.org&#x2F;pipermail&#x2F;python-list&#x2F;2008-January&#x2F;t...</a>

This is exactly what&#x27;s called the &quot;countdown problem&quot;. You might find more details about effective solutions there.

Nice read!<p>I&#x27;ve been toying around with a few hypothetical improvements on my machine.<p>For this case:<p>nums = [100, 6, 5, 100, 4, 4] desired_result = 743<p>My machine finished the original implementation in:<p>07:53<p>I then tried skipping the set of operators and just doing list lookups (figuring the set overhead defeats the advantage when the collection is so small):<p>08:24<p>My next idea was to replace the set lookup with an isinstance() check:<p>09:01<p>My third proposed change is the only one that has given me a speed-up:<p>Moving the list() call of r to inside the try:<p>06:47

For faster than brute search algos, you probably want to do some dynamic programming.<p><a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Dynamic_programming" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Dynamic_programming</a>