Wednesday, January 12, 2005

Programming Puzzle

I recently heard a great little puzzle that I thought I would share with everyone.

Given a pointer to the head of a link list write a function that returns 0 if the link list ends in NULL or 1 if it is a circular link list. Note that a final node in a circular link list doesn't necessarily point to the first node, but could point to any node in the list.

Part 1) Make the function solve in O(n*n)
Part 2) Make the function solve in O(n)

I was able to solve part one without any trouble, but wasn't able to figure out part two until given a hint (use two pointers). And really it is one of those Aaha! moments so it isn't really fair as a test question, but still a example of how algorithms are fun.

Friday, January 07, 2005

ASCII A-maze-ment Puzzle

ITASoftware put up a little puzzle to write a program that can solve some ascii mazes. Finding it fun I sat down for an evening and wrote up a solution. The source contains two programs (solmaze and genmaze). genmaze will generate a maze of any size in two different ASCII styles. solmaze will solve the above problem. solmaze's solution uses a recursive back track solution and will uses stack space up to the size of the maze. genmaze will only use the amount of memory equivalent to two rows in generating the maze. For much more detail see the source code files.

You can download the source code off github.

The original problem text:
ASCII Maze. Write a program that reads in a simple 2-D ASCII maze and outputs the same maze, but with the solution filled in.

The input is guaranteed to be a well-formed maze and to have a unique solution path from the bottom left grid cell to the top right grid cell. Your program should re-output the maze with the solution path filled in.
Input:

_______________________END
| | | |
|__ |_____ | ______|
| | | |
| ___ |_____ | |
| | | | | |
| | | ___ | | |
| | | | | | |
| |_____ |__|__|__| |
| | |
Start|__|____________________|

Output:

_______________________END
| | |XX XX XX|
|__ |_____ | ______|
|XX XX XX| XX| |
| ___ |_____ | |
|XX| |XX XX XX XX| | |
| | | ___ | | |
|XX| | | | | |
| |_____ |__|__|__| |
|XX| |
Start|__|____________________|

Wednesday, January 05, 2005

Code to be proud of

I remember back in school there was a girl who always had perfect code. Indented, commented, well thought out variable names, the whole nine yards. I was impressed until I watched her code. She spent too much time cleaning it up rather then just seeing if the code would work that she didn't get all that much done and wasn't having much fun.

Over the years my coding style has improved dramatically. I am not perfect, but am much better then I was ten years ago that is for sure. These days I try to spend a few extra minutes cleaning up my code whenever I go back to old code. Little things like checking to see if all the headers are required, renaming some variables, adding comments, and thinking about if that function I wrote a year ago is still needed.

Just about every job interview I have been on has asked me to present some code. Starting a year or two ago I started thinking that rather then having that one little bit of code (that is perfect) to show off I make it be all my code. That way I can just let them visit my website and let them pick anything they want. It is a win-win. They get to see that I can produce consistant clean code and slowly my code becomes cleaner and easier to maintain.

The only downside is that there is always that code that I never got around to fixing and am embarrassed to show people. But at least I am not alone as there is plenty of bad code out there. I have come across plenty of comments saying something along the lines of "Fix up later" or "TODO: comment". To go with that I have seen plenty of version 0.01 applications that are released that are very small, but at that same time very messy and the developer even brings that up without being asked saying it will be cleaned up for 0.02. One has to wonder if they didn't have the time to clean up the small amount of code for 0.01 when they were the only user what makes them want to clean it up for 0.02 when they have users asking for features? Luckily (for those developers) a lot of open source applications don't go beyond version 0.01 and so no one sees the code.

One reason why this topic hits home so much is the nature of open source and KDE. Your typical KDE developer might not have all of KDE cvs on his local computer, but at least the module he is working on. So inevitably others will look at any code you put into KDE's CVS, good or bad.

Recently I was looking through kwin's code (the KDE window manager) trying to understand how it worked. I discovered that the code was quite clean and consistant. It was very nice. So I want to invite other developers who have spent time in KDE's CVS to share code that you found to be particularly well maintained, organized and clean. A fun public way to say thanks to those developers for taking the time to write clean code they should be proud of.

Popular Posts