163: a sport

[Cyril]

Okay, so I have invented this game, which I've exhibited at two fairly big math camps so far. A couple of crazy IMO candidate people from national camp have promised to spread the news for me. If, somehow, someone I met at national camp is reading this, I hope this brings back some nerdy memories.

The game is simply a variant of 24: use six cards (with A,J,Q,K = 1,11,12,13) and the four basic arithmetic operations (+-*/) to make 163. Why 163? Because it's a prime, which reduces the number of trivial games, it's nicely balanced for six cards, and it's a generally awesome number, as e^(pi*rt163) is within a trillionth of an integer. It can turn out to be a very fast-paced game- after practice, we were able to get most solutions within 10 seconds. It wasn't very competitive- rather, it was a nice way for us to get to know each other in terms of problem solving insight. As far as social arithmetic games go, 163 is pretty cool.

Also, some of the more elegant cases afford nice puzzles:

9 9 9 9 9 9 (credit to Joe Zeng)
2 2 4 4 8 8 (exponents allowed for this one)
2 3 4 5 6 7
1 3 5 7 9 11
2 4 6 8 10 12

And for whoever's interested (...):

The next question: how do we write a program to solve this? The natural approach is to go for RPN permutation bash, but the O(n(2n+1)!4^n) time makes this less than attractive. There does exist a better method; that's why I'm up at 4:50 AM. It's sort of like the DP algorithm for the travelling salesman problem. Keep a binary indexed array of binary search trees: values you can obtain with a certain subset of elements, along with their corresponding expressions. Then we can traverse all pairs of disjoint subsets, verifying their disjointness using bitwise AND, combining the elements of their binary search trees using arithmetical operators, and putting them into a binary search tree that has the index of the bitwise OR of the two disjoint subsets. Repeat this n-1 times, where n is the number of cards, and all solutions for the entire set of cards are obtained. Of course, optimizations are possible- specify the STL set's comparison function to remove redundancy, and set bounds so that hopelessly large or small numbers get pruned.

Below is my code for the DP method- it might be interesting to some. Input comes from 163input.txt in format "a b c d e f = g". It is pretty fast- unlike the brute force method, the program can do it faster than the heuristically advantageous human mind. Maybe someone can think of a better method...? It's a work in progress- I don't really want to bother finishing exponents, some more optimizations, and the redundant parenthesis removing stuff right now. Oh yeah... it's past 5 now. I should sleep, huh?

Solution to first puzzle:

Spoiler:

9 * (9 + 9 + (9/9)/9) = 163

[aramadia]

So I'm trying to understand your post here:

The RPN brute force is O(n(2n+1)!4^n)
-I assume n is the number of operators, so there are 2n + 1 tokens, (2n + 1)! ways to arrange them, 4^n for the permutations of the tokens, and n to process each RPN "string".
-So for 163 game, n = 5 which I think is still practical for regular brute force with some simple optimizations

I checked your solution out and it works pretty well. I'm not sure what the complexity is (2^n space? and some kind of exponential time too) but I tried it with 8 numbers. It solved it in under 5 minutes (wasn't timing it really):

Input:
2 3 4 5 6 25 2 12 = 317
Output:
2 - (25 + (6 * (5 * (4 * ((2 / 12) - 3))))) = 317

Anyways I thought that was pretty cool.

I was sort of tinkering with my own solutions, but found it was remarkably similar to Cyrils. One optimization which may be more useful for larger number of cards is to first assume that you are given a unlimited number of cards of each number. So if you had 2 5 7 8 10 13 you can use six 8s for example. Since, it might be possible to build the number x from many different subsets, but it is still impossible to arrive at the target number, you can prune large chunks fairly easily. Once you have a smaller subset of potential intermediate steps using unlimited number of cards, it should be fairly easy to work backwards and check if its possible using one of each type of card. Haven't tested this so I hope someone can confirm if this makes sense.

[Cyril]

Ah, sorry, should be (2n-1)!. 4^n combinations of operators, and (2n-1)! permutations of n tokens and n-1 operators. It wouldn't be horrible to obtain a catalan[n] time solution with brute force, but it gets a bit messy.

Your optimization would be helpful in removing redundancies from repeated cards, but wouldn't it eat up too much memory for large n?

edit: and yeah, I think the complexity of my method is (some exponential) * (some polynomial) * (some log factor). Just by looking at the loop structure, we get an extreme upper bound of something like n * log n * 12^2n, but that's a very naive estimate.

[aramadia]

Yeah now I think about it, it probably will.

I wish I had more time to do programming contests and the like cuz I find this stuff really fun. The ICPC is out of my league right now.

[Zren]

There's a simplier solution to Q1 btw...
Unless your forced to use the order of operations in a specific way?

Spoiler:

(9*9)+(9*9)+(9/9)

[Cyril]

Ah, right. In my sleep-deprived state, I just put 9 9 9 9 9 9 in my program, hence the blindness to simplicity. o_O