Solving Num: A combinatoric math game

https://dangoldin.com/2019/09/14/solving-num-a-combinatoric-math-game/

by dangoldin • 7 years ago

22 10 7 years ago

sgdpk2• 7 years ago

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

dangoldin• 7 years ago

(Author here) Oh that's pretty clever and better than my approach. I was going to point out that subtraction would still need to be supported but realized we don't need to support negative numbers.

sgdpk2• 7 years ago

Exactly :) The polish notation approach is also pretty interesting. I wasn't aware it had the full power of parenthesized expressions.

If you are interested I can share my code (simple Python).

udia• 7 years ago

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

gbhn• 7 years ago

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.

maest• 7 years ago

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

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

estomagordo• 7 years ago

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

dwyart• 7 years ago

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...

johnday• 7 years ago

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

gbronner• 7 years ago

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.

Solving Num: A combinatoric math game

Related Stories