5 ms·

Solving Num: A combinatoric math game

22 points by dangoldin 7y ago

sgdpk 7y 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 7y 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.
  - sgdpk 7y 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 7y ago
There is a similar game that is available for Android and iOS called Calculords (http://calculords.com/ 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 https://github.com/SomeKittens/calculords-solver
gbhn 7y ago
See also Krypto https://en.wikipedia.org/wiki/Krypto_(game) 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.
maest 7y ago
For faster than brute search algos, you probably want to do some dynamic programming. https://en.wikipedia.org/wiki/Dynamic_programming https://en.wikipedia.org/wiki/Dynamic_programming
estomagordo 7y 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 7y 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/thread.html#468792 https://mail.python.org/pipermail/python-list/2008-January/t...
johnday 7y ago
This is exactly what's called the "countdown problem". You might find more details about effective solutions there.
gbronner 7y 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.

22 points by dangoldin 7y 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 7y 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.
- sgdpk 7y 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 7y ago

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

gbhn 7y ago

See also Krypto https://en.wikipedia.org/wiki/Krypto_(game) 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.

maest 7y ago

For faster than brute search algos, you probably want to do some dynamic programming. https://en.wikipedia.org/wiki/Dynamic_programming https://en.wikipedia.org/wiki/Dynamic_programming

estomagordo 7y 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 7y 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/thread.html#468792 https://mail.python.org/pipermail/python-list/2008-January/t...

johnday 7y ago

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

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