Saturday, October 29, 2005

Propositional logic in Python

Propositional logic inference via compressed truth tables. Module entail is presumably slower than your industrial-grade C inference algorithm, but logical statements are given as Python expressions, and entailment can be checked at the interactive prompt. This makes the module easy to use, and fun. (Source Code).

Sunday, October 23, 2005


Hyperventilate + loquacious = ventiloquate, to freak out and speak too much, too fast, and use way more breath than is actually needed to explain the idea. I assumed that this word existed, but I guess it actually doesn't.

Friday, October 14, 2005

Basic factorization algorithms

A paper which gives pseudocode and the reasoning behind some basic factorization algorithms: Fermat factorization, Pollard rho, Pollard p-1, and Brent's method. Public domain. (PDF document).

Saturday, October 08, 2005

Memoization with cache clear on return of last function call

Memoization is nice, but in dynamic programming, it can eat up ever-increasing amounts of memory as your memoized function is called with various arguments. A simple solution is to clear the cache when the last function call returns. (Python Recipe).

Thursday, October 06, 2005

mw2html -- Export Mediawiki to static, traditional website

mw2html is a Python program which exports a Mediawiki site to a traditional-looking HTML site. No indices are generated, and Wikipedia sidebars and extra formatting are removed to give a simple, streamlined site (you can substitute in your own sidebars if you wish). The outputted HTML source code is Monobook-specific and rather verbose at the moment. But the sites thus exported don't look bad. (Source code).

Tuesday, October 04, 2005

List of bits in Python

A memory compacted list of bits (uses 1 byte per every 8 elements). Instantiate from a list or string of bits. Otherwise behaves just like the builtin Python list class. Uses the ListMixin class also published on this page. (Source code).

Sunday, October 02, 2005

Why books suck

An essay. Click comments for the text.

Timing a function (pytime)

Python's timing facilities are...unPythonic. Module timeit requires you to specify the number of iterations for the timing loop. But that number varies according to the speed of the machine you're running on, level of optimization of your code, etc. It's more Pythonic to calculate the number of iterations in the timing procedure. As so: (Source code).

Python htmldata module

Extract and modify URLs in an HTML/XHTML/CSS document. Translate HTML/XHTML documents to and from list data structures. Use cases: robots, proxy CGI scripts, filtering of HTML and CSS, and flexible wget-like mirroring. (Module website).

List mixin for Python

You can use UserDict.DictMixin to create custom dictionary classes. Now you can use listmixin.ListMixin to create custom list classes. (Source code).

Infinity in Python

Negative infinity:

>>> None < -1e308

Positive infinity:

>>> () > 1e308

Modified Dijkstra's algorithm in Python

Algorithm: perform a breadth-first search, always expand the vertex with the smallest cost, and don't remove duplicate vertices in the cost-priority-queue.

This algorithm turns out to be nearly equivalent to Dijkstra's algorithm. For n vertices and m edges, it requires O(n+m) space, O(m*log(m)) time, and always finds the shortest path.

The strategy of not removing duplicate vertices is particularly helpful in Python, where the builtin priority queue class doesn't support the DECREASE-KEY operation. See my comment at David Eppstein's recipe (the comment is public domain).

AI algorithms in Python

Uninformed search algorithms: breadth-first, depth-first, depth-limited, uniform cost, iterative deepening DFS, and bidirectional (in both tree and graph modes). (Source code).

Informed search algorithms: greedy best-first, beam, A* (in both tree and graph modes). (Source code).