Always Turn Left

This is with reference to the Google Code Jam practice problem.

SPOILER WARNING: DISCUSSION ON THE SOLUTION BELOW

This problem initially seemed vexing. After a little bit of thought about using bit twiddling to represent directions, generating the right codes was easy.

If you have any experience with hexadecimal numbers, it should strike you that the direction table with 4 directions each of which can be yes or no, is a big hint that bit twiddles are exactly what is needed. Which means powers of two

N, S, W, E = 1, 2, 4, 8

Now I'm not going to show how you combine them, but here is how you get the code directly in Python ( somewhat similar in C ):

def code(dirs):
return '%x'%dirs

After this I scribbled a lot on paper, mapping the small input to the maze. It was easy to figure out that the problem could easily be solved by going both ways because always turn left means that you will visit every part of the maze if you go both ways. I wasted a lot of time thinking how to orient the grid, until I read the specification that the entrace is always at the north.

But there was another problem, how to generate a perfect size grid for a dynamic problem like that. I didn't want a 10000*10000 grid all the time, that would be very inelegant. First I tried using links for each Cell, but the problem is resolving W-E or N-S relationships would involve backtracking to find the adjacent Cell. This flummoxed me for a LONG time. Then I read João's idea [perfect maze size] and it hit me like a rock. This problem really requires you to break some preconceived notions, like a multidimensional array being the best representation for a Grid. A dictionary with coordinates as keys turned out to be perfect for this problem. After this the solution was dead simple, walk forward, preserving the right coordinates, then turn around and walk back, overlaying existing directions with new ones you find.

Write a simple comparator function for coordinates, and use it to sort the grid and print it, and you have the solution in Python

In general the practice problems are creative, all they require a bit of common sense, some unconventional thinking and perhaps a few years of experience. Mainly it's about how elegant your code can be. I'm just hoping the real ones will be easy too. But irrespective of that, I'm not qualified to receive even a T-shirt, since I'm under age.

Meet Pypes

Pypes is almost done, except for the loops, which shouldn't be there. Have a screenie.

opensocial Last.fm recent tracks

After two days of OpenSocial hacking, here is my app, which fetches the users Recent tracks and displays it on the profile. Now since there is no way to directly fetch the last.fm username, I had to resort to asking the user. Also 1.0 although usable has a few errors which aren't handled smoothly. But they do not pose security risks. For now its in the sandbox, if you have access you can view it here Last.fm Recent Track and give me some feedback. It won't be on Orkut for a few days since there is a pretty large queue for applications waiting to be moderated.

Oh yeah, here's the project page on Google Code.

ColourCode: 1.0 almost done

ColourCode is done. It now has support for PHP and HTML which it didn't have before. Perl support will probably get in before the stable release. This version has been bumped to 1.0. I think I've made a really good project and that it deserves the 1.0 tag. PDF support will not enter the 1.0 release but is on track for 1.1.

All that is left now is testing some highly tweaked files. All the standard test files I've been using are passing well. Also I need to write some documentation about implementing custom language handlers and formatters.

You can download today's development build which fixed all known bugs - colourcode-20070807.tar.gz

Please leave your comments. For usage see the usage.html file under the docs folder.

Introducing Pixelframe

In Trac(k)ing I mentioned the "secret project" I was working on. Well I have decided its time to let the world know what it is, even though its not finished yet.

Its called Pixelframe.

Pixelframe is meant to be a lightweight image gallery. It uses PHP for the backend and my custom javascript toolkit ( called Juice ) for frontend effects and ajax requests. Juice will also be released seperately once it is done. Pixelframe is easy to setup and use and doesn't have ( and won't have ) a lot of features. It is purposely made to be featureless. For description and development status check the Pixelframe page on Google code .

For now those interested can check out the latest bug free build which has the backend almost implemented. --> Demo

Colourcode 0.2 released

ColourCode 0.2 has been released.

In addition to the features mentioned in the previous post it now supports C# and Shellscript and Javascript.

Check it out at the ColourCode homepage

Game Of Life:LOGIN

I am proud to present my latest creation LOGIN or NIkhil's Game Of Life, my very own Conway's Game of Life simulator. Written in C++ using SDL. I wrote it mainly to learn SDL and because I truely enjoy life. Currently it only runs on Linux. Read the README file in the package for instructions on installation and usage.

Here is a nice pic of part of a r-pentomino cycle for your enjoyment:



Features:
Generation count in the titlebar
On the fly change in generation delay

It follows original Life rules and there is no support for reading or writing Life files.

Usage

LOGIN runs in 2 modes. One is when the program is running but the game is not. In this state you can do the following.

• Use the mouse to activate/deactivate cells
• Press 'r' to generate a random fill
• Press 'c' to clear and reset the game
• Press 's' to start the game.

When the game is running you can only do two things

• Press 's' to stop it again
• Press '-' to increase the speed by 10ms (you cannot go faster than 10ms per generation)
  
• Press '+' to decrease the speed by 10ms (there is no limit to how slow you can go)
  

Note that + and - unfortunately do not work continuosly on holding them. The reason they seem contradictory is that well they control the delay. So '+' increases the delay and decreases the speed :)

Download: http://22bits.exofire.net/downloads/login.tar.gz

ColourCode 0.1beta released

I am pleased to announce the release of version 0.1beta of ColourCode. ColourCode is a Ruby program to generate syntax highlighted HTML files. Currently it supports HTML, Java, C++, Ruby and Python. For more information and (not)features see the ColourCode homepage

Glowpad

Glowpad is a small Python/Pygame program to read in a file and generate a word/pattern with randomly coloured squares which morph to white. I basically wrote it after seeing the cool effect that appears at the end of one of the Sony ads(the robot one) where the same effect happens with the word feel. So I hacked this program in just half an hour.

To run the program, extract it to any place on your computer. you NEED to have Python and Pygame installed before you can run it. After you install them just run the program by executing

python glowpad.py 

. Two patterns FEEL and LINUX are included. So to apply the effect on Linux use

python glowpad.py linux

.
To create your own patterns just create a new file in any editor. Make the pattern you want using an uppercase B. The colours are chosen randomly. You can add padding or whatever you want around the characters. The only thing Glowpad makes sense of is an uppercase B, any other character is ignored. So this is an example. Just save the file and run it as shown above

##############################
-B----BBBBB-BBBBB-B---B-B---B-
-B------B---B---B-B---B--BBB--
-B------B---B---B-B---B---B---
-B------B---B---B-B---B--BBB--
-BBBB-BBBBB-B---B-BBBBB-B---B-
##############################

DOWNLOAD:http://22bits.exofire.net/downloads/glowpad.tar.gz