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 10^{5} 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

Need I say more ? That 1700 USD pays for my air tickets with enough buffer for exchange fluctuations. Now I have to clean up my act and get my visa papers finalized. Monday is going to be a very busy day indeed.

--**if tcp was less formal, syn/ack probably would be WAZUP/Y0**

Friday night, I show up at my home completely z0nked. I thought I was the only guy who used words like z0nked or b0rked, but apparently lots of people I met during FOSS.in said stuff like that a LOT. Hari had given me a lift back home and I managed to get inside by pure will alone. While taking the camera out of my pocket, wanted to give one last try to make it work - it hadn't worked after I fell down after all the jumping at the phenom concert (which is one reason I don't have too many photos). Anyway, it worked for an instant before I ran out of batteries (see the charger in that image).

A careful observer (or anyone who clicks the link) can make out two terry pratchetts - The Carpet People
(green cover) and the Wee Free Men (the beige one), a google t-shirt. One
un-opened FOSS.in t-shirt (*I nicked f3ew's*), Long Dark Teatime of the
Soul by Douglas Adams, two remotes (mp3/dvd player and music system),
an entire week's worth of newspapers and several other items of interest
to me (like that packet of biscuits near the bed).

After all, what is a bed but a 6x3 foot grave from which you rise everyday.

--**What if life throws you pumpkins ?**