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.

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.

Bonus: by sorting the input values, you can consider half of the trees, because the operations either commute (x+y = y+x) or don't make sense to reverse in the integers (4/2 vs. 2/4).

There is a similar game that is available for Android and iOS called Calculords (http://calculords.com/) 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.

I like this solver, which uses a dynamic programming/search approach to find solutions. https://github.com/SomeKittens/calculords-solver

See also Krypto https://en.wikipedia.org/wiki/Krypto_(game)

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's a fun programming problem. :-)

There's a mobile version of Krypto as well.

1) 39+525+7-8 also works if I understand the problem. 2) You can optimize using various number-theoretic principles -- checked division and subtraction

3) C++ is much much faster for this -- less than a second on my boxes.

Not sure where people get the idea of dynamic programming -- you can do some dynamic tree cutting (e.g. if you don't have enough operators to get to your target), but there's no real objective function here.

You should be able to find some info with the keyword "countdown". This is a TV game which seems very close (identical ?) to yours.

E.G.: https://mail.python.org/pipermail/python-list/2008-January/t...

This is exactly what's called the "countdown problem". You might find more details about effective solutions there.

Nice read!

I've been toying around with a few hypothetical improvements on my machine.

For this case:

nums = [100, 6, 5, 100, 4, 4] desired_result = 743

My machine finished the original implementation in:

07:53

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):

08:24

My next idea was to replace the set lookup with an isinstance() check:

09:01

My third proposed change is the only one that has given me a speed-up:

Moving the list() call of r to inside the try:

06:47

For faster than brute search algos, you probably want to do some dynamic programming.

https://en.wikipedia.org/wiki/Dynamic_programming