-----------------------------------

Cyril

Mon Jul 13, 2009 4:14 am


163: a sport

-----------------------------------

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:
9 * (9 + 9 + (9/9)/9) = 163

[code]
#include 
#include 
#include 
#include 
#include 
#include 

#define BITFIELD_SIZE 64
#define N_OPERATORS 4
#define NUM_TYPE long double
#define INPUTSTREAM fin
#define OPENSTREAM

#define HIGHLIM 1000000
#define LOWLIM -1000000
#define EPSILON 1e-10

#define inb(n) (n>=LOWLIM && n> temp;
		if(temp[0] < '0' || temp[0] > '9') break;
		v[bitsize].insert(pair(atoi(temp.c_str()),""+temp+"x"));
		bitsize  target;
	
	for(int r=1; rfirst;
										if(inb(tempcalc)){
											v[i|j].insert(pair(tempcalc,"("+ai->second.substr(0,ai->second.size()-1)+" - "+bi->second.substr(0,bi->second.size()-1)+")2"));
											if((i|j) == bitsize-1 && tempcalc == target) out = true;
										}
										tempcalc = bi->first-ai->first;
										if(inb(tempcalc)){
											v[i|j].insert(pair(tempcalc,"("+bi->second.substr(0,bi->second.size()-1)+" - "+ai->second.substr(0,ai->second.size()-1)+")2"));
											if((i|j) == bitsize-1 && tempcalc == target) out = true;
										}
									break;
									case '*':
										tempcalc = ai->first*bi->first;
										if(inb(tempcalc)){
											v[i|j].insert(pair(tempcalc,"("+ai->second.substr(0,ai->second.size()-1)+" * "+bi->second.substr(0,bi->second.size()-1)+")3"));
											if((i|j) == bitsize-1 && tempcalc == target) out = true;
										}
									break;
									case '/':
										if(bi->first!=0){
											tempcalc = ai->first/bi->first;
											if(inb(tempcalc)){
												v[i|j].insert(pair(tempcalc,"("+ai->second.substr(0,ai->second.size()-1)+" / "+bi->second.substr(0,bi->second.size()-1)+")4"));
												if((i|j) == bitsize-1 && tempcalc == target) out = true;
											}
										}
										if(ai->first!=0){
											tempcalc = bi->first/ai->first;
											if(inb(tempcalc)){
												v[i|j].insert(pair(tempcalc,"("+bi->second.substr(0,bi->second.size()-1)+" / "+ai->second.substr(0,ai->second.size()-1)+")4"));
												if((i|j) == bitsize-1 && tempcalc == target) out = true;
											}
										}
									break;
								}
								if(out) break;}
						if(out) break;}
					if(out) break;}
					
				if(out) break;}
			if(out) break;}
		if(out) break;}
	if(out) break;}
	
	for(set::iterator ai = v[bitsize-1].begin(); ai!=v[bitsize-1].end(); ++ai){
		if(absd(ai->first,target) < EPSILON){
			cout second.substr(1,ai->second.size()-3)