Universal Rule

Book Reviews

Wednesday, June 9, 2004

Visiting Norway tomorrow -- Comment()
Tomorrow I'll attend the Notur 2004 conference in Tromsø, Norway. The program is promising. Weather will be probably not very warm, about 10°C, but at least there was no promise of rain in the weather forecast yesterday evening.

Generating big mazes (non-recursively) with Python -- Comment()
I once again polished the Python code for making a maze. Now I have a non-recursive implementation of the algorithm. Here is an example of bitmap (PPM) output from the code:

Here is the original recursive part of the code:

    def putr(self, idx, n):
        "Recursively fill the maze updating the current step."
        h, w = idx
        self.table[h,w] = n
        while True:
            free = self.freedir(h,w)
            if free:
                self.putr(choice(free)(h,w),n+1)
            else:
                return

To make this into an iterative version, I only had to add a list for keeping track of the path. This works as follows:

    def put(self, idx, n):
        "Fill the maze keeping track of the path."
        h, w = idx
        tbl = self.table
        tbl[h,w] = n
        path = [(h,w,n)]
        while path:
            free = self.freedir(h,w)
            if free:
                n += 1
                h, w = choice(free)(h,w)
                tbl[h,w] = n
                path.append((h,w,n))
            else:
                h,w,n = path.pop()

I profiled the code, and most of the time (65%) is spend in the freedir function, as expected. The non-recursive implementation of the put function reduces the cpu time slightly, and also makes it possible to generate much bigger mazes, because the memory use is much less. Also, to make a big maze, you don't have to call setrecursionlimit(...). You can now generate mazes with dimensions in the hundreds (or even thousands).

-- Comment()
Passwords Can Sit on Hard Disks for Years: "Typing your password or credit card number into a computer is a moment's work. But if you think your personal details disappear as soon as you hit the Return key, think again: they can sit on the computer's hard disk for years waiting for a hacker to rip them off." [via Slashdot]