Older blog entries for fzort (starting at number 61)

Grand Master Turing once dreamed that he was a machine.  
When he awoke he exclaimed:                              
 
    "I don't know whether I am Turing dreaming that I am 
     a machine, or a machine dreaming that I am Turing!." 

                                 -- The Tao Of Programming

The other day I dreamt an idea for a small game. I've been coding it in my free time since monday. This is pretty exciting.

jarod: Advogato is an international forum. Please try to use English. It's a matter of common courtesy.

You might also like to check out the paper A Killer Adversary for Quicksort, in case you haven't already. :)

So, Team Bandersnatch (bi and I) got in the top-50, which entitles us to t-shirts. I did one problem, he did three. :)

I'd post my solution to problem 6, like he did, but it looks fugly - it took a lot of hammering to make the square peg fit in the star-shaped hole.

Some of the problems were hardcore. None of the teams did problems 3 or 4.

Buzzword Assault

A company called D-Wave demo'ed an alleged superconducting 16-qubit quantum computer. Their PR department seems to claim it's able to solve NP-complete problems in polynomial time, which sounds like BS, but the thing looks pretty darn cool anyway. In both senses of the word (ha, ha).

I got pwned. Big time.

That is all.

q = ((a<<3) + a) >> 6

q = ((a<<6) + (a<<3) + a) >> 9

q = ((a<<9) + (a<<6) + (a<<3) + a) >> 12

q = ((a<<12) + (a<<9) + (a<<6) + (a<<3) + a) >> 15

...

and so on (in binary, 1/7 is .001001001...). Optionally, the result can be fixed with something like

r = a - q*7; while (r >= 7) { q++; r -= 7; }

The multiplication by 7 can be replaced with shifts and adds, of course.

My performance was dismal. I did the easy problem, then moved straight to the hard one. Then I threw away 20 minutes because I jumped straight to the code before understanding completely the problem statement and then had to start all over again, wasted another 20 minutes tracking down a stupid off-by-one bug, panicked for about 5 minutes, and finally ended up submitting a /wrong/ solution. Guess I need to work on the think-crush-under-pressure thing.

What makes it so frustrating is that the problem was not really that hard, and I was able to concoct a correct solution (here) without major difficulties afterwards, when the time pressure was gone.

Gah.

The qualification round was easier than I expected. It's probably just meant to filter out the curious. I was able to do both problems in about 30 minutes, and qualified to the next phase.

Tupper's Self-Referential Formula

... seems to be making the rounds on the internet. Two different people sent me the link. It's cute, but there's nothing magical about it, really - perhaps if some people look at it as a simple Perl script they'll realize that it's just a way to rasterize the big number, and the bitmap could be anything.

So, tomorrow is Google Code Jam Latin America. I'll give it a try, but I expect to get my arse kicked. Although I've been practicing a bit at SPOJ and acm.uva.es, I really suck at thinking under pressure. Ah well, let's see how it goes.

1.

#define is_odd(x) (((x)&1) != 0)
#define is_even(x) (((x)&1) == 0)

2. if you're out to disprove the Collatz conjecture, use GMP or something.