www.main.lv

2009-05-07 PyGame Attractors

I have found old article about attractors that is resoult what I have done with playing with attractor values. Attractor formula is very simple but result is interesting.

2009-11-15 Pascal Triangle

This is Pascal Triangle. And colors is choseen by reminder of division.
There are 2 ways how thats is made:
1. Simple if division reminder is 0 then red else green
2. Reminder is like alpha chanell of red color.
In gallery shown images are generated by dividing on (17,19,23,41,42,43). There is easy to see that
prime numbers (17,19,41,43) has very structured triangle but not prime (42) is different.
./chessboard div_number - simply show triangle divided by number
./chessboard div image.tga - save programm screen to image.tga
./chessboard div img.tga ant_parm - changes to second coloring type
Why it I call it chessboard? I were trying make such with OpenGL bet result is Pascal Triangle.


Source

2010-01-16 Vector Library

Library with 2D vector functions.

I have tested this library with ChipMunk vector and with VLvectors
My implementation performs some +% in speed.
Source

2010-07-20 Python MIT Binary Trees

After reading chapter form MIT Introduction in algorithms about trees I have implemented same algorithm in python
I haven't tryed to make best perfomance only easy to understund and one to one like is in pseudo-code

Tree python class that are used to represent BinaryTree.

class Tree:
	p = None
	left = None
	right = None
	key = 0

pseudo-code

Inorder_Tree_Walk( x )
if x != NIL
    then Inorder_Tree_Walk( left[x] )
        print key[x]
        Inorder_Tree_Walk( right[x] )

python code

def inorder_tree_walk( t ):
    if t != None:
        inorder_tree_walk( t.left )
        print t.key,
        inorder_tree_walk( t.right )

pseudo code

Tree_Search( x , k )
if x = NIL or k = key[x]
    then return x
if k < key[x]
    then return Tree_Search( left[x] , k )
    else return Tree_Search( right[x] , k )

python code

def tree_search( t , k ):
    if (t == None) or (k == t.key):
        return t
    if k < t.key:
        return tree_search( t.left, k )
    return tree_search( t.right, k )

pseudo code

Tree_Minimum( x )
while left[x] != NIL
    do x <- left[x]
return x

python code

def tree_minimum( t ):
    while t.left != None:
        t = t.left
    return t

pseudo code

Tree_Maximum( x )
while right[x] != NIL
    do x <- right[x]
return x

python code

def tree_maximum( t ):
    while t.right != None:
        t = t.right
    return t

python code

def tree_root( t ):
    while ( t.p != None):
        t = t.p
    return t

pseudo code

Tree_Successor( x )
if right[x] != NIL
    then return Tree_Minimum( right[x] )
y <- p[x]
while y != NIL and x = right[y]
    do  x <- y
        y <- p[y]
return y

python code

def tree_successor( t ):
    if t.right != None:
        return tree_minimum( t.right )
    y = t.p
    while (y != None) and (t == y.right):
        t = y
        y = y.p
    return y

pseudo code

Tree_Insert( T , z )
y <- NIL
x <- root[T]
while x != NIL
    do y <- x
        if key[z] < key[x]
            then x <- left[x]
            else x <- right[x]
p[x] <- y
if y = NIL
    then root[T] <- z
    else if key[z] < key[y]
        then left[y] <- z
        else right[y] <- z

python code

def tree_insert( t , z ):
    y = None
    x = tree_root( t )
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.p = y
    if y == None:
        r = tree_root( t )
        r = z
    else:
        if z.key < y.key:
            y.left = z
        else:
            y.right = z

           

def tree_insert_recrusive( t , z ):
    if t.left == None and t.right == None:
        if z.key < t.key:
            t.left = z
        else:
            t.right = z
        return
    if z.key < t.key:
        tree_insert_recrusive( t.left , z )
    else:
        tree_insert_recrusive( t.right , z )

pseudo code

Tree_Delete( T , z )
if left[z] = NIL or right[z] = NIL
    then y <- z
    else y <- Tree_Successor( z )
if left[y] != NIL
    then x <- left[y]
    else x <- right[y]
if x != NIL
    then p[x] <- p[y]
if p[y] = NIL
    then root[T] <- x
    else if y = left[p[y]]
        then left[p[y]] <- x
        else right[p[y]] <- x
if y != z
    then key[z] <- key[y]
return y

python code

def tree_delete( t , z ):
    if (z.left == None) or (z.right == None):
        y = z
    else:
        y = tree_successor( z )
    if y.left != None:
        x = y.left
    else:
        x = y.right
    if x != None:
        x.p = y.p
    if y.p == None:
        r = tree_root( t )
        r = x
        t = r
    else:
        if y == y.p.left:
            y.p.left = x
        else:
            y.p.right = x
    if y != z:
        z.key = y.key
    return y

Example of usage:
Now we can use out tree. There is some more functions like create_tree that creates binary tree from given array.
And print_tree that print all ree values.

keys = [10,6,1,0,3,8,7,9,21,15,11,17,25,23,46]
max_deep = log(len(keys),2)

def create_tree( n=0 , p=None):
    if (len(keys) == 0) or (n >= max_deep):
        return None
    t = Tree()
    t.p = p
    t.key = keys.pop(0)
    t.left = create_tree( n+1 , t )
    t.right = create_tree( n+1 , t)
    return t

   
   

def print_tree( t ):
    if (t != None) and (t.key != None):
        if t.left == t.right == None:
            print "Key:%d "%(t.key)
            return
        if t.left.key == None:
            print "Key:%d Right:%d"%(t.key,t.right.key)
            print_tree( t.right )
            return
        if t.right.key == None:
            print "Key:%d Left:%d"%(t.key,t.left.key)
            print_tree( t.left )
            return
        print "Key:%d Left:%d Right:%d"%(t.key,t.left.key,t.right.key)
        print_tree( t.left )
        print_tree( t.right )

t = create_tree()
r = tree_search( t, 10 )
n = Tree()
n.key = 150
tree_insert_recrusive( t , n )
inorder_tree_walk( t )
print ""
tree_delete( t , r )
inorder_tree_walk( t )
print ""
r = tree_root( t )
print r.key

Source