Algorithm.co.il

lorg

Fractals in 10 minutes No. 5: Sierpinski Chaos Game

Posted on by Leave a Comment

A few years back, I was in some course where they also taught me some Matlab. One of the exercises was to draw the Sierpinski triangle using a method of progressing a point randomly. I was quite surprised at the time, because I thought the Sierpinski triangle was more of an analytical thing: you drew it using inverted triangles.

I wanted to check up on it, and it turns out the method has a name: Chaos Game.
To generate a Sierpinski triangle using this method, one starts with a some point inside the triangle. Then, at each step, the next point is half the distance from the current point to one of the corners selected at random. I think this method of generating the Sierpinski triangle is even easier than the analytical one.

A sierpinski triangle generated using a chaos game

I used pylab (matplotlib) to create this image.
As I usually do, I also wanted to draw it using ascii-art. However, I must confess, I am not satisfied with the result:

              %6
             6*%8
            %8  66
           %6%*6%%6
          6%'    '66
         6866'  '6%86
        %6* 86 '%8 *66
       %**%%'***%6***%%
      8'6            6*8
     6%%*8          %*'*6
    6%6'666        86# 86%
   %%*''**%6      %**''*'%6
  *%8'   '6%6    668'   '#%%
 %% '6' '#*'6%  *% %8' '6''6*
%68%#6#*#68*86*%6#%8%8'6%6*6%*

The code isn’t really good, as I didn’t put much thought into it and just hacked it up. Still, I’m putting it up, and I might improve it someday.

Fractals in 10 minutes No. 4: Mandelbrot and Julia in Ascii Art

Posted on by Leave a Comment

I felt like it’s about time I tackled the Mandelbrot and Julia sets, in Ascii-Art. Heck, the Mandelbrot fractal is on the logo of this Blog! However, being the most well-known fractal, this issue was tackled already, with satisfactory results.

Still, I took the ten minutes required to draw them in Python, using numpy:

def get_mandelbrot(x, num_iter = 10):
    c = x
    for i in range(num_iter):
        x = x**2 + c
    return abs(x)>2
 
def get_julia(x, c, num_iter = 10):
    for i in range(num_iter):
        x = x**2 + c
    return abs(x)>2

“Hey!” you might say, “There’s no loop in here!”. Indeed, with numpy loops can sometimes be avoided, when using arrays. When the expression x**2 + c is applied to an array x, it is applied element-wise, allowing for implicit loops. The actual magic happens in the following function:

def get_board(bottom_left, top_right, num_x, num_y):
    x0, y0 = bottom_left
    x1, y1 = top_right
    x_values = numpy.arange(x0, x1, (x1-x0)/float(num_x))
    y_values = numpy.arange(y0, y1, (y1-y0)/float(num_y))
    return numpy.array([[x+1j*y for x in x_values] for y in y_values])

The result of get_board will be used as the “x input” later on. It should be noted though that while that’s a cute trick this time, it might grow unhandy for more complicated computations. For example, making each element to reflect the iteration number on which it “escaped”.
So, here are the results:

############################   ##############
###########################   ###############
##########################     ##############
#####################                ########
####################                #########
############ #######                 ########
############                         ########
#########                           #########
#########                           #########
############                         ########
############ #######                 ########
####################                #########
#####################                ########
##########################     ##############
###########################   ###############

############################################################
############################################################
############################################################
############################ ###############################
######################### ##   #############################
############## #######           ###########################
######## ##      ###              ##########  ##############
#########  ###        ###         ######       #############
##############       ######         ###        ###  ########
###############  ##########              ###      ## #######
############################           ####### #############
##############################   ## ########################
################################ ###########################
############################################################
############################################################

Here’s the code. (With the usual bsd-license slapped on top of it :)

Small Python Interactive Interface Trick

Posted on by 9 Comments

Not too long ago, I helped someone with some research work, and one of the research tools was also used from the Python interactive prompt.
The interface used was handy enough for development: intuitive, readable, short, and useful. Still, for interactive research it wasn’t handy enough.
To improve the script, I decided to use a trick I heard about a long time ago – using __repr__:

class NoParens(object):
    def __init__(self, obj):
        self.obj = obj
    def __call__(self, *args, **kwargs):
        return self.obj(*args, **kwargs)
    def __repr__(self):
        result = self.obj()
        return str(result)

And using it looks like this:

In [2]: import noparens
 
In [3]: def test():
   ...:     return 4**4
   ...:
 
In [4]: t = noparens.NoParens(test)
 
In [5]: t
Out[5]: 256
 
In [6]: t,t,t
Out[6]: (256, 256, 256)

For research consoles that interact with other programs or devices, such as debuggers and sniffers I found this useful, and made work a bit less annoying.

Open Question No. 1: Persistent Predicates?

Posted on by 6 Comments

Lately I’ve been developing a website. One issue that I’ll probably need to address in the near future is “persistent predicates”. By “persistent predicates” I mean the problem of treating predicates as data.

Consider the following situation: you are developing some big rss reader/aggregator and you want to allow users to specify handling rules. How would you keep these rules in memory, and how would you keep them on disk?
Obviously, this problem was solved before. Just consider email filters, or even packet filters in ethereal.

One way of approaching the problem is implementing simple predicate templates:
“%field contains %s” where field is subject, or body, etc.
Once that is accomplished, you can specify that a “filter” is some combination (for example logical and, or logical or) of multiple predicates. To store this, we’ll have an actual predicate table (or pickle) with their data, and a one-to-many mapping of filters to predicates.

Another option is allowing just some very simple predicates, and a filter will just “point” to (have an id/name of) the required predicate, and the required data. In this option, all data is stored with the filter.

A more complicated solution is to implement some logical serialize-able lanugage (such as the expression trees I used for diStorm or PyKoan). Using this language, the predicates can be very dynamic, and be combined and manipulated programmatically. This solution might be overkill for many projects though.

An interesting issue regarding handling of predicates, is their application to constraint solving. However, this is an issue for a future post. Suffice it to say, that when writing PyKoan I’m using a constraint solver. Since I’m representing predicates with expression trees, the ability to analyze and manipulate predicates is very handy.

Besides looking at existing solutions, I’m very curious to hear other peoples’ opinions. Feel free to write about your preferred solution in the comments.

PyKoan – The Logic Game

Posted on by Leave a Comment

As you can probably tell, I’m back from my undeclared hiatus. I’ve got lots of stuff to talk about, and I’ll be starting with PyKoan, one small project I’ve been working on lately in my spare time.

A few weeks ago I stumbled upon an article in wikipedia, regarding a logic game. This game fascinated me, especially because of the “Godel Escher Bach” connection. Quoting from Wikipedia:

Zendo is a game of inductive logic designed by Kory Heath in which one player (the “Master”) creates a rule for structures (“koans”) to follow, and the other players (the “Students”) try to discover it by building and studying various koans which follow or break the rule. The first student to correctly state the rule wins.

As it happens I’m also taking a mathematical logic course this semester. Having read about the game, I wanted to write a similar computer game. Hence – PyKoan.

PyKoan is a game where the goal is to discover some logical rule, for example, “For each x holds x%2 == 0”. This rule is applied to a koan – a list of integers. An example koan that “has Buddha nature” (follows the rule) is [0,2,8]. One which doesn’t is [1].

To implement this idea, I wrote an implementation of an expression tree very similar to the one used in vial, but with a different implemented language. I also did some experimentation with the design. Since I’ve been talking a lot about expression trees without giving a full explanation, in a future post I’ll write about the implementation used in PyKoan.

So far I didn’t code a lot of the game, just the expression tree framework, and a simple rule builder. When using Python’s interactive prompt, one can get a taste of how the game might feel:

In [19]: r = rulegen.create_rule(rulegen.easy_grammer, rulegen.easy_grammer_start)
 
In [20]: r.eval([])
Out[20]: False
 
In [21]: r.eval([0])
Out[21]: False
 
In [22]: r.eval([1])
Out[22]: False
 
In [23]: r.eval([2])
Out[23]: True
 
In [24]: r.eval([2,2])
Out[24]: True
 
In [25]: r.eval([2,2,3])
Out[25]: True
 
In [26]: r.eval([3])
Out[26]: False
 
In [27]: r.eval([4])
Out[27]: False
 
In [28]: print r
x exists such that x == 2

Here is how I would generate such an expression manually:

In [3]: from exptree import exps
 
In [4]: exps.Exists('x',exps.Eq('x',2))
Out[4]: exps.Exists(exps.Var(x), exps.Eq(exps.Var(x), exps.Imm(2)))
 
In [5]: print _
x exists such that x == 2

The game has many interesting possibilities for research, for example, computer players. Other possibilities include “just” guessing koans (not the rule itself), creating interesting and playable rules, and so on. There’s a lot to do.

This time, instead of just publishing the (unfinished) code, I decided to do something different. I’ve opened a space in assembla, with public read access. I’m opening this project for participation: if you want to join then leave a comment, or send me an email.

(Since Assembla seems to be going through some connectivity issues right now, here’s a link to a copy).

Singleton: my use-case for class decorators

Posted on by 2 Comments

It seems that class decorators will finally be making an appearance in Python 3 and Python 2.6. I’ve thought about using them from time to time, but the use-cases weren’t that common. However, I did find myself writing a lot of singletons.

This time I wanted to write a bunch of boiler-plate objects, that should all be singletons. So I thought of class decorators, to avoid repetition. Here is my singleton implementation, and it seems to work under Python2.6:

>>> def eq_is(self, other):
...     return self is other
...
>>> def singleton(cls):
...     cls.__eq__ = eq_is
...     return cls()
...
>>> @singleton
... class a(object):
...     def __repr__(self):
...         return 'foobar'
...
>>> a
foobar
>>> a == a
True

I just can’t wait for the new Pythons to come out of alpha!

Breaking Rapidshare's Annoying Captcha the Easy Way

Posted on by 1 Comment

Like many others, I got stuck in front of Rapidshare’s captcha. After more than five attempts at reading different letters with kittens and other critters hidden behind them, I was thinking of giving up. Especially because each time I failed I had to wait a half a minute again. However, in one instance I went *back* via my browser, and tried solving the same captcha again. Turns out this works, and I got the file.

I know I could probably have solved it in a smarter fashion, but it wasn’t worth the effort.

My lesson:

When someone writes crappy software, their software is probably crappy in more than one way.

This is not the first time I’ve seen this happen.

Python + Curses + Numpy -> Ascii Art Rotating Cube

Posted on by 6 Comments

Well, the title says it all, or at least most of it.
If you are still not convinced, a picture’s worth 500 dwords:


        / |\
       /  | \
      /   |  \
    //    |   \\
   /      |     \
  /       \      \
 |       / \      |
 |\     /   \    /|
 | \   /     \\ / |
 |  \ /       //  |
 |  /\       /  \ |
 | /  \\    /    \|
 |/     \  /      |
 /       \/       /
  \       |      /
   \      |     /
    \\    |   //
      \   |  /
       \  | /
        \  /

I’ve been toying with the idea of writing a roguelike, and I thought that it would be really fun if it had an ‘Eye-Of-The-Beholder’ kind of view as well, just in ascii-art. There are plenty of things I wanted to do with ascii-art, since it’s such a nice toy. So I started writing some code, and this is a small test on the way.

Nowadays, when I discuss 3d ascii-art, people usually think about a picture transformed with aalib or something similar. Although it is a (very) nice idea, I think it would be more fun to play with ascii-art directly.

Other playing possibilities include a ray-tracer. You could write some fps with ray-tracing ascii-art graphics, because there are so few pixels.
Maybe I’ll write one, when I get to it.

Oh! The code, what about the code?
Here it is.
A few notes:
1. The code ain’t too pretty, as it is a work in progress that doesn’t get much time invested in it. However, I’d still rather publish it.
2. It uses curses. Under windows you’ll have to get some replacement module.
3. It uses numpy. If you don’t have it already, be sure to get it.
4. Run ‘test_cube.py’. Use the direction keys to rotate the cube, ‘q’ to exit.