Algorithm.co.il

Python

Elegant Line Clipping Algorithm

Posted on by Leave a Comment

I actually wrote about that a long time ago, in the wiki that once was algorithm.co.il. Since the wiki is long gone, and I figured this is a very elegant algorithm, I decided I should write about it.

First, some background – while writing Ascii-Plotter, I had to plot lines. To plot lines correctly I had to clip them. Now since this was a fun project, I decided I wanted to figure out how to do that myself, even though the problem is really solved. So I sat down with pen and paper, and did a little thinking, and I came up this nice algorithm.

The idea is simply this: consider a line, that is not parallel to any of the axes. This line intersects all the four lines that make up the limits of our screen. Here is a diagram:

An intersection of a line with a bounding box

Now notice that there are six points of interest: the four intersection points, and the two endpoints of the line. For each point, we find its parameter in the parametric representation of the line, where a and b are the endpoints:

x(t) = a+t(b-a)

To find out the actual endpoints of the clipped line, we sort the six points according to their parameter, and take the two innermost points (with zero based indexing, those would be 2 and 3). What if the line is outside the box you say? We check that the result points’ parameters are between 0 and 1 (which correspond to the original endpoints).

Note that for a line parallel to one of the axes, a similar method applies, but without two of the intersection points. However, it is probably easier to just calculate the clipping directly in that case.

Here is some sample code, without all the surrounding checks (for parallelism with the axes, trivial clipping etc…).
The full version is available in the code of Ascii-Plotter.

points_t = [0.0,1.0]
 
points_t.append( float(rect_bottom_left[0]-line_pt_1[0])/(line_pt_2[0]-line_pt_1[0]) )
points_t.append( float(rect_top_right[0]-line_pt_1[0])/(line_pt_2[0]-line_pt_1[0]) )
points_t.append( float(rect_bottom_left[1]-line_pt_1[1])/(line_pt_2[1]-line_pt_1[1]) )
points_t.append( float(rect_top_right[1]-line_pt_1[1])/(line_pt_2[1]-line_pt_1[1]) )
 
points_t.sort()
if points_t[2] < 0 or points_t[2] >= 1 or points_t[3] < 0 or points_t[2]>= 1:
	return None
result = [(pt_1 + t*(pt_2-pt_1)) for t in (points_t[2],points_t[3]) for (pt_1, pt_2) in zip(line_pt_1, line_pt_2)]
return (result[0],result[1]), (result[2], result[3])

Python module usage statistics – Cont.

Posted on by 3 Comments

Well, very embarrassingly for me, turns out I had a bug in my original post and code. As per Doug’s suggestion, I tried running the script I wrote on the standard library, and got results I didn’t quite believe. So I checked them, opened socket.py, and there was an “import _socket”. However module “_socket” was not listed in my results. After some digging around, (and feeling my face getting red hot…) I found the bug. It was the smallest thing: I forgot to add re.MULTILINE as an argument to re.search, so the start of my regexp, “^[ \t]*import” didn’t match except on the beginning of the file. #@&*!!! Just no words to express how I felt at that moment.

So, I fixed the bug, tested my code a bit, fixed some more (very minor) bugs, and here are the top 25 of the (hopefully correct this time!) results:

  • sys,1426
  • os,1250
  • unittest,566
  • time,446
  • re,383
  • string,321
  • types,298
  • setuptools,264
  • pkg_resources,217
  • cStringIO,184
  • zope.interface,177
  • datetime,173
  • shutil,167
  • os.path,162
  • gtk,143
  • StringIO,143
  • random,136
  • tempfile,132
  • copy,131
  • threading,128
  • distutils.core,127
  • doctest,126
  • md5,125
  • setuptools.command.e,116
  • logging,116

Except the larger numbers, the arrangement pretty much stayed the same.

(This seems to at least confirm my claim that the results were representative)
Here are the results for the standard library (/usr/lib/python2.5/):

  • sys,1309
  • os,1065
  • ctypes,588
  • re,496
  • string,493
  • types,435
  • time,374
  • numpy,297
  • warnings,254
  • os.path,204
  • cStringIO,196
  • common,185
  • math,159
  • traceback,158
  • gettext,152
  • codecs,147
  • StringIO,147
  • copy,133
  • __future__,128
  • tempfile,126
  • random,119
  • threading,117
  • unittest,108
  • numpy.testing,105
  • errno,100

These results seem different. ctypes seems to be the biggest change. Note that these results might be slanted, as some stdlib modules are implemented in C, and I didn’t test a ‘clean’ Python installation (but rather one with all my non-default modules installed).

Here is a link to the new results, the new stdlib results, and the new fixed graph. I created it using the first 325 module. The fixed R squared value is now approx. 0.99. Here is the code.

I would like to apologize to anyone who was misled by the original results, and again state that it is quite possible that there are still more bugs there, but I still claim the results to be represntative.

Python module usage statistics

Posted on by 5 Comments

IMPORTANT UPDATE: The code I used to create these statistics had some bugs. The fixed statistics are available here.

After reading Doug Hellman’s post about python stdlib modules he needs the documentation to, I commented there that I need the documentation for logging because I don’t use it too frequently. Later, I thought a little bit more about it, and I wanted to check which modules are actually used often, and which rarely.

My first step was to “grep import *.py” on my python scripts directory. Later I progressed to writing a simple script which basically does the same thing, but also rates each imported module according to frequency (it looks for “import <modules>” and “from <module> import bla”). The results weren’t interesting enough. Before going any further, I sat down, and wrote my expected list of frequent stdlib modules:

  • sys
  • os
  • re
  • math
  • thread
  • urllib2
  • time
  • random
  • struct
  • socket
  • itertools
  • operator

My next step was to try Google Codesearch. Some time ago I wrote a little script to harvest results from Google Codesearch, but enough time has passed, and the script doesn’t work anymore. Parsing their output is messy enough, and their results don’t seem that helpful anyway. (They don’t return all the results in a project). So I thought about using koders.com, when I had a flash. I can use Cheeseshop! easy_install must have a way to just download the source of a project! (For those who don’t know: you can do easy_install SQLObject, and easy_install will look for the module in the PyPI, download it and then install it for you). Indeed, easy_install had this option (-eb), and I was in luck. Quickly, I got a list of all the modules in PyPI, shuffled it, and picked 300 randomly. (Actually, downloading them wasn’t that quick, and about 20 didn’t download right :).

I ran my statistics script, but non-stdlib modules were also listed. I fixed some bugs, improved the script a little, and (partially) disallowed inner project imports using a little heuristic. These are the improved results:

  • sys,113
  • os,107
  • setuptools,57
  • common,50
  • unittest,50
  • __future__,25
  • distutils.core,24
  • zope.interface,22
  • re,19
  • pygame,18
  • time,13
  • datetime,11
  • string,10
  • zope,10
  • pyglet.gl,9
  • types,8
  • random,7
  • pkg_resources,7
  • gtk,6
  • struct,6
  • ez_setup,6
  • zope.component,5
  • math,5
  • logging,5
  • sqlalchemy,5

(Please note that I do not argue that these results are completely true, as my code might still contain problems, and it probably filters too much. However, I do claim that these results are representative).

Well, some surprises… I didn’t expect setuptools and types to be there. Especially types… who needs it anymore (and anyway)? Seeing unittest so high in the list gives me a pretty good feeling about opensource. __future__ being there is amusing… Seems that we just can’t wait for the next version. And indeed, logging is pretty low, but not as low as I thought it will be.

Another curiosity: the module frequencies seem (unsurprisingly) to obey Zipf’s law. Here is a small graph showing the results: module imports on a log-log graph

(plotted with Google Docs). The R squared value is 0.92. For the original results (where inner dependencies were allowed), it seemed that the law was even stronger.

For those interested in the full results, here is a csv file containing them.

One final note: while these results are true for projects in Python, they don’t represent usage in interactive mode. Since I use interactive mode a lot, and during interactive work I use os and re quite a lot, I bet the results would be changed if we somehow could count interactive mode usage.


Simple word lookup for crosswords and such…

Posted on by Leave a Comment

I am swamped with university homework. I did manage to come up with some small somewhat useful utility.

Do you know when you need a word that ends with a double letter and then an ‘n’? you would want to write it like this: “xxN$”. Well, I wrote a simple tool that translates a ‘word lookup syntax’ into regular expressions, and then does a lookup for the word.

This raises a two questions:

What exactly is the syntax?
Small letters stand for any letter, and big letter stand for their specific letters. So for example, “bEEn” would match “been”, “seen” and “keep”, but not “boon”. Punctuation is left unchanged, so you can use $,^, (?!xy) and so on. I didn’t work too too much on it, so [] doesn’t translate well (the letters inside it will come out garbled).

What is the data for the lookup?
Well, I used the excellent natural language toolkit (obviously in Python). Very easy to start using it, with a nice tutorial. It’s nice knowing that such a tool is available. The source data is actually an extract from the Gutenberg project. The result words are sorted according to frequency in the source language, and the 20 most frequent words are returned.

Without further ado, here are some code snippets. (The compiled regexp is printed. Note how ugly (yet simple) it is :)
(Note: I did cut out some of the output…)

In [1]: fd = words.create_word_index()
 
In [2]: words.find_words("^bEEn$",fd)
^(?P<b>.)EE(?!((?P=b))|(E))(?P<n>.)$
Out[2]:
['BEEN',
 'SEEN',
 'KEEP',
 'FEET',
 'FEEL',
 'SEEK',
 'SEED',
 'MEET',
 'DEEP',
 'NEED',
 'SEEM',
 ...]
 
In [3]: words.find_words("^jvfpf$",fd)
^(?P<j>.)(?!((?P=j)))(?P<v>.)(?!((?P=j))|((?P=v)))(?P<f>.)(?!((?P=j))|((?P=f))|((?P=v)))(?P<p>.)(?P=f)$
Out[3]:
['THERE',
 'THESE',
 'WHERE',
 'JESUS',
 'MOSES',
 'HOSTS',
 'LINEN',
 'PIECE',
 'SCENE',
 'WHOSO',
 'POSTS',
 'EPHAH',
 ...]

Note that if you find some of the result words a bit too uncommon for your taste (e.g. Ephah), I would suggest removing the bible from the source data… :)

The (very ugly, uncommented, draft code) is available here. I apologize for its unseemliness, but I figured that it’s better to make it available in its current form, rather than never put it online for lack of time and will. It could also be seen that the code isn’t terribly efficient. It is however, ‘good enough’ for interactive work.

Distorm3 progress and SVN

Posted on by Leave a Comment

Finally, Distorm3 is progressing. With heaps of work done by Gil, and some more by me, the project will soon be on its feet. One thing that really gave us a feeling of progress, is setting up Subversion. We thought of setting our own, but finally decided on using Assembla, after a good friend recommended it. There are other options, but Assembla seems really good, although it does have its drawbacks. (Your code goes in clear-text for one).

When I was using windows I worked with TortoiseSVN, but now on my Ubuntu, I’m using RapidSVN, with meld as my diff tool. Although Rapid is cool, I liked Tortoise better. It was faster, much more intuitive, and I liked the commit window better. It gave me a choice on what to commit, and I could (from the commit window) run a diff on each file I changed, and using the diff write a short comment on my changes in the commit comment. While RapidSVN obviously also allows for commit comments, I have to do all the work beforehand. It’s a bit more cumbersome.

Another thing – I’m working on unit-testing using the excellent unittest module. Using coverage.py along with the testing makes my code so much better, and me so much happier. Since we have a little bit of c-code generation, one of the (a little bit hackish) tests I wrote was running gcc on some sample output, and making sure there were no errors or warnings. Fun. One of my next todos is compiling a few small executables, and making sure that they run without errors, all from within the unit-testing of the code generation module.

All in all, it’s good to finally be working organized.

Small Python Utility Functions 2

Posted on by Leave a Comment

So I finished some time ago the first assignment in Numerical Analysis. Ahh, such a joyous occasion. Why you ask? Well, because I wrote the programming assignments in Python, and not some annoying made-up pseudo-code language. I know, I know, I should use Matlab, Maple or Mathematica… but well, so far I’m doing fine with Python and numpy. Besides, finally I’m required to do formally what I did informally in the homework for calculus (check out limits in Python to verify my calculations).

While doing the homework, I thought of one small utility function that will never make it. I found myself doing (x)range(n-1,-1,-1), or maybe reversed(range(n))… the first is ugly, and the second is (relatively) slow and takes memory. It would have been nice to have something like reverse_range(n) that will do just that. I’ve happened upon that use only a few times so far, so it’s really not that important. Now I wonder, what should the ‘policy’ be? To write those functions and encourage their use, or the other way around?

What do you think?

Misc. Projects: a preview for the new (academical) year

Posted on by 2 Comments

So now it’s been too long since I’ve written a post, and that’s mostly because I haven’t been programming lately, as I’ve been busy with buying a car\moving\studying. This is going to change now that I’m finally settling in.

There are however few directions I’m going to go about, and I’d like to mention them here. If you are interested in reading more about any of them, just drop me a line in the comments, and that direction will get a bit more attention.

The first direction (and the most serious one) is a website I’m building. I’ll still not talk about the website itself, at least until a beta version is done, but I will say I’m doing it with TurboGears. I’ve always looked for a good Python framework for writing websites, and for now, TurboGears seems to do the trick, although I’m just starting with it. I am going to write a little bit about my experience with TurboGears, and my opinions. Stay tuned.

Another subject that I thought of writing about is a small tank game I wrote with pygame. This game actually works, although I didn’t do the finish. I intended to make it multi player (over the ‘net) but then found out that it is really not that simple. So I intend to work it out sometime in the future, and write about it. For now, I will say a few words about the game. It started when a friend of mine said that he wanted some simple tank game for one-on-one games, with some certain behaviors (such as bullets ricocheting off walls). I heard him talking about it, and told him, “hey, that’s really simple, I can do that”, so I went home, and during five days, one hour a day, I worked it out. That was an interesting experience in itself. Maybe I’ll write a little about that as well.

Other small projects I’ve been working on include doing some more IMDB mining (which I started to talk about), and maybe expanding that to allmusic.com as well. One thing I find missing in Amarok, is choosing music according to musical relations between singers and bands. Maybe I’ll even write a plugin :)

Some other ideas I had include 3d l-strings. I actually implemented those, but to my disappointment, they didn’t turn out as aesthetically pleasing as I’d hoped. Still, it was a curious result (with PyOpenGL doing the drawing). I wanted to implement more simple fractals. I’ll probably write more of those when I break from writing more serious projects. Other small ideas I had include more ascii-art, for example, ascii-art drawing of some vector image format seems very interesting, or maybe a 3d engine (maybe with cell-shading) which renders the result in ascii-art, and then writing an FPS with it… The options are endless!

All of this of course if I have the time when I’m not working on one of the other current projects, which include distorm, and my studies. Among the courses I’m taking there is a seminar on graph algorithms, a course in compilation and a course in cryptography.

This is going to be a very interesting year indeed!

Pagerank recommends movies

Posted on by 1 Comment

So how was your Yom Kippur? After Yom Kippur ended, I sat down to write something that was nagging me for quite some time. I wanted to see what pagerank had to say about movies. I’ve always liked to picture things as graphs, and looking at movies and actors as nodes in a graph is very intuitive. I also think that the idea has some merit. I like most of the movies that Edward Norton appears in, so it makes sense to give him a high score, and see which other movies Edward Norton “recommends”.

So I fired up my IDE, and started to work.

Well, at first I was a little bit disappointed, because IMDbPY doesn’t have code to read the IMDB charts. Well, I was going to extend it a little bit, but then I remembered that I already downloaded all the data I needed some time ago (more than half a year I believe), and that was good enough. So I opened up some old pickle file I had lying around, and Voila! after some playing around with the format, I had a weighted graph at my disposal. I weighted the graph according to the IMDB listing – if an actor appeared higher on the cast, his (or hers) weight to and from that movie will be higher.

I implemented a quick and dirty pagerank, and then added some code to score my recommendations higher. I did that by adding each iteration my recommendation’s weight to the movie’s score.

Without recommendations, the top spots were:

  • 24
  • The Sopranos
  • The Wizard of Oz
  • JFK
  • Cidade de Deus
  • Citizen Kane
  • King Kong
  • Voyna i mir
  • Dolce vita, La
  • The Patriot

After adding “Edward Norton” and “Tom Hanks” as recommendations, I got the following results:

  • American History X
  • Fight Club
  • 24
  • Red Dragon
  • The Sopranos
  • Catch Me If You Can
  • The Wizard of Oz
  • JFK
  • Forrest Gump
  • Cidade de Deus

Well, I was surprised a little to see 24 and the Sopranos rank so high, and also a little bit disappointed. The recommendations didn’t really add enough information, and more work will have to be done for this to work properly. It has the right ‘smell’ however. It looks like it has potential to be useful – I can just see the program, having a small table with a ‘seen/unseen’ checkbox, and a place to write your favorites, and the program will tell which movies you should watch next. This reminds me a little bit of the recommendations on soulseek and Amarok. It would be really fun to write a total recommendation engine, with the best of all worlds. Someone probably already implemented it.

In any case, I’ll work on it some more. This is interesting.

If anyone wants the code, tell me, and I’ll make it ‘online worthy’…

Testing, 1 2 3, Testing

Posted on by Leave a Comment

Finally, I’m after the test in complex functions. Not that it went as well as I wanted, but hey, you can’t have it all. Maybe gonna try again sometime later. In the meantime, I got this “today is the first day of the rest of your life” feeling. After finishing with my previous work, and the previous semester, I’m going to move to Haifa (with my girlfriend) in less than a month, start the next (and last) semester soon, and also start real work on some real projects (one of those being diStorm). Here’s to starting and ending things.

On the flipside, after finishing the test, I had some testing issues to work out. See – let’s say you got a piece of code you change. Well, the obvious thing to do is make sure it works. It is also good to find all the places that reference that piece of code, and make sure these are updated, and test those as well. It is even better if you also have some unit-testing code available (built using the easy-to-use unittest module). It’s even better if your test code actually checks the relevant pieces of code.

But alas, it can all fail due to human stupidity. In that particular instance, mine. After all this work, not running the damn unit-test code is just plain stupid. So, I hope I’ve learned my lesson. Again. Never commit untested code.

And while we are on the subject of testing, check out coverage.py, over at Ned Batchelder’s place (I also happen to read and like his blog). Coverage is an excellent tool to improve your test code. Just run your test code with coverage.py, likewise:

coverage.py -x test_exputils.py

and then run:

coverage.py -r

and get some nice looking, informative results:

Name                                        Stmts   Exec  Cover
---------------------------------------------------------------
exptree                                        65     33    50%
exputils                                       85     48    56%
template_gen                                  100     67    67%
test_exputils                                  41     41   100%
...
...

Excellent. You can also get an annotated version of the source, telling you which line was run, and which wasn’t. It just doesn’t get anymore useful then that. So happy testing. I hope you fare better then me.

Small Python Utility Functions

Posted on by 3 Comments

While working with Gil Dabach on Distorm3, I found out that I’ve been missing a lot of utility functions. I’m going to write about some of them now.

def classify_to_dict(seq, key_func):
    result = {}
    for item in seq:
        key = key_func(item)
        if key in result:
            result[key].append(item)
        else:
            result[key] = [item]
    return result

This is really a simple function, but a very powerful one. Here is a simple demonstration:

>>> base_tools.classify_to_dict(range(5), lambda k: k%2)
{0: [0, 2, 4], 1: [1, 3]}

Note the similarity and difference from groupby.
If any of you can suggest a better name then classify_to_dict (maybe just classify?), I’ll be happy to hear it.

Some other very useful functions include arg_min and arg_max, which respectively return the index of the maximum and minimum element in a sequence. I also like to use union and intersection, which behave just like sum, but instead of using the + operator, use the | and & operators respectively. This is most useful for sets, and on some rare occasions, for numbers.

Another function I like (but rarely use) is unzip. I know, I know, paddy mentioned it is pretty obvious, and I know that it could just as well be called transpose, however, I still find using unzip(seq) a better choice then the much less obvious zip(*seq). Readability counts.

What are your favorite utility functions?

A minor update: I’ve incorporated the use of a syntax highlighter now, and it should be enabled for comments as well by the next challenge (which will be soon enough).