FOSS.in had a google stall where they were handing out puzzles to everyone who visited the stall. The puzzles by themselves weren't a big challenge - the second day of the conference I found f3ew, vinayak and pooja sitting the NoC with a puzzle about balancing weights. After proving conclusively that the lengths of the bars from the centre matter, we all headed out and went for dinner.
FOSS.in Day 3, 7:30 AM : I woke up the next day at 7 and by 7:30, instead of heading out for the conference, I found myself sitting in front of my box hacking away a loop based solver for this. This particular question was reduced down to around 5 variables from the original 10 via algebraic simplification. Btw, good programmers are really good at algebra and logical exclusions - the thing they are bad at is arithmetic. Geometry , especially imaginary plane mathematics - which is where geometry meets algebra, is especially useful to pick up for a good coder. It the right sort of training which will let you pick up and track down a pattern from a mess of numbers and curves. That kind of thing is built on some basic fundamentals which we are taught properly - unlike Calculus where most of the time you just have solutions, but not enough raw math is taught there to understand how it came to be.
Problem #3 : there is no 'j' in these equations because seemant just pointed out that when I write, j looks exactly like an i. And I am slightly disorganized in terms of variable naming.
for 5 balance points h = i + 2 * k; d = 2 * b + c; 2 * g = 2 * f + 3 * e; d + b + c = f + g + e; (d + b + c) + (f + g + e) = a + 2 * (i + k + h);
Skipping all the intermediate steps, because the sheet I did my work on went into that google box, you get a basic single equation to start solving.
6 * b + 4 * c = a + 4 * i + 6 * k ;
This results in a loop size of 105 to solve completely. Assuming your code path has ~60 instructions in that tight loop, that comes to 6 x 10 7 instruction in user time on a CPU (since there are no platform calls for this loop). For an AMD64 3400+ IPS cpu, it comes to around 0.0016 seconds of estimated time (excluding pipeline stalls and cache misses) to finish solving this equation in the worst case. Lookin' good..
Well, which is exactly what I did - run a 5-deep loop on that equation. Pull out the answers, calculate d and h from these 5, find the 3 numbers missing in that collection (were from 1-10, with nothing repeating) and re-order according to the e-f-g equations. And the time is now 8:15 on the dot. Download the code from here.
[gopal@phoenix hacks]$ time ./prob2 6 * 3 + 4 * 4 == 34 == 8 + 4 * 5 + 6 * 1 a = 8, b = 3, c = 4, d = 10, e= 2, f = 6, g= 9, h = 7, i = 5, k = 1 real 0m0.003s user 0m0.002s sys 0m0.000s
11:30 AM, Problem #3: I managed to dodge enough traffic and reach palace grounds by 9:30, had a coffee and showed a couple of the guys my solution. I got tejas winded up enough to make him attempt problem #4 sitting at the python stall. By the time it was 11, I was getting bored. There was nothing to do - the Yahoo! stall had 3 people plugged in and working, nobody was talking and I had a lot of coding still left in me. Sat down at the python stall and tried to hack the problem #3 - which also looked easy enough.
I decided to prematurely optimise the problem which had a search space of 2 16. What I did was to use a unsigned short to store this value instead of storing it in 16 different integers like I would've done in python. Alternatively I could have just written a struct bitset too. But I decided to just go ahead and hack this one out - the fast way. This was the question:
| \ | 3 | 7 | 6 | 4 |
| 5 | ||||
| 2 | ||||
| 8 | ||||
| 1 |
Fill each empty cell with either 1 or 9, such that the composite number of the digits in a row or column bear the same relationship as the ones outside.
ordinal relationship between decimal numeric value of a row of digits with any another row is the same as the relationship between the corresponding row headers.
I just used an unsigned short, used bit extraction and did an increment till it hit the maximum value of the search space (65536). These were my work-horse functions.
inline void setvalue(bitset * set, int position, int value)
{
bitset _set = *set;
_set = _set | ((value == 9 ? 1 : 0) << position);
*set = _set;
}
inline int getvalue(bitset set, int position)
{
int v = (set) & ((1 << position));
return v ? 9 : 1;
}
inline int getrowvalue(bitset set, int row)
{
int i = 0, k =0;
for(i = 0; i < ROW_SIZE ; i++)
{
k = k * 10 + getvalue(set, row * ROW_SIZE + i);
}
return k;
}
inline int getcolvalue(bitset set, int col)
{
int i = 0, k = 0;
for(i = 0; i < ROW_SIZE ; i++)
{
k = k * 10 + getvalue(set, i * ROW_SIZE + col);
}
return k;
}
After that it was just smooth sailing, except for the fact that the google guys were really clever and they never gave a test-case with 4x4 squares. Thankfully my code (on x86) will handle 3x3 squares by just changing ROW_SIZE. Anyway here's the real solver -
int columnconstraints[] = { 3, 7, 6, 4 };
int rowconstraints[] = { 5, 2, 8, 1};
while(1)
{
if(validate(b, rowconstraints, columnconstraints))
{
print(b);
}
/* exit when overflow */
if(b == 65535) break;
b++;
}
int validate(bitset set, int * rowconstraints,
int * columnconstraints)
{
int i, j;
for(i = 0; i < ROW_SIZE; i++)
{
for(j = 0; j < ROW_SIZE; j++)
{
if(i == j) continue;
if(compare(getrowvalue(set, i),
getrowvalue(set, j)) !=
compare(rowconstraints[i],
rowconstraints[j]))
{
return 0;
}
if(compare(getcolvalue(set, i),
getcolvalue(set, j)) !=
compare(columnconstraints[i],
columnconstraints[j]))
{
return 0;
}
}
}
return 1;
}
Anyway, that's all it takes. A few loops and the computers do all the number crunching. Programmers are inherently lazy - but that's not such a bad thing after all. We do a lot of work to get out of doing it. Like I had said in my Su Do Ku solver, Never send a man to do a machine's job.
--I propose we leave math to the machines and go play outside.
--- Calvin