Universal Rule

Book Reviews

Wednesday, June 9, 2004

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]

-- Comment()
Infected Windows PCs Now Source Of 80% Of Spam: "[Study] blames Microsoft Zombies for 80% of all spam. The study goes on to claim that 90% filtering is not effective given the unprecedented volume and that sophisticated trojans are able to drop spam directly on end user's computers despite current efforts." [Privacy Digest]