| Python module to produce the textual ASCII art representation of a given binary tree:
http://www.fantascienza.net/leonardo/so/index.html#btreep
Output examples:
hello
+---------------+
1 1
+-------+ +-------+
2 3 2 3
+---+ +---+ +---+ +---+
4 5 6 4 5 6
X
+-------------------+
X X
+---------+ +---------+
X X X X
+----+ +----+ +----+ +----+
X X X X X X X X
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+
X X X X X X X X X X X X X X X X
hello
┌───────┴───────┐
1 1
┌───┴───┐ ┌───┴───┐
2 3 2 3
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
4 5 6 4 5 6
The module uses a lazy printing algorithm to find the positions of the subtrees. For me it's a complex enough algorithm, so it may interest to ![[info]](http://p-stat.livejournal.com/img/userinfo.gif) 11011110 too :-) | comments: 2 comments or Leave a comment   |
| | Tags: | algorithms, python | | Subject: | "Names in a Database" Kurukshetra problem | | Time: | 01:40 am |
|
| Kurukshetra problems:
http://opc.kurukshetra.org.in/opc/problems/
Here are all their solutions (but if you like to program I suggest you to try to solve them yourself, some of them require some time and some brain, but they seem nice problems, they cover most of the basic ideas of CS courses, like graphs, dynamic programming, etc):
http://psriram.wordpress.com/files/2007/01/kopc.pdf
This is the "Names in a Database" problem:
http://opc.kurukshetra.org.in/opc/problems/2/
My Python implementation of the solution of the "Names in a Database":
http://www.fantascienza.net/leonardo/js/names_in_a_database.py
There is a solution for Psyco and Pyrex too.
On a random string 300000 chars long the Psyco solution is about 4 times faster than my faster Pyrex solution! This is quite strange, and I don't know why. The faster Psyco solution I have created is reeeally fast, it runs in 0.04 seconds only on the very long test string. it uses an array.array, it seems psyco optimizes ord() away too:
last_occurance = array("l", [-1] * 256)
x = last_occurance[ord(string[i])]
...
Most of the versions come from the solution found in the "kopc.pdf" document. There is a little solution of mine, but it's too much slow (the problem requires the solution to require less than 2 seconds for the 300000 long string). Later I have tried to create a faster solution, but I have stopped trying after some tries (I wasn't going to find the given fastes O(1) solution, it seems).
Later I have tried to solve the "Three Brothers" problem too, the offered solution looks simple enough, I think but you need to remember your CS courses if you want to solve it :-) | | comments: Leave a comment |
|