xkcd “Self-Description” solved with python+pygame
Well, something about this xkcd comic drew me in …
The 3rd panel reminded me of a study I did in college on iterated function system fractals. These fractals are known for creating ferns, trees, and the Sierpinski triangle. There are a number of ways of creating these fractals, but one of them is called (something like) the reducing photo copier method. Where you can start with ANY starting image on your photo copier, and just shrink the images, make a few copies, position them on the copier, and repeat. Eventually your image converges towards the fern / triangle / whatever if you are precise. (This can be done with a ‘Real Life’ photo copier for simple IFS like the Sierpinski triangle.)
So as a way to avoid work that I’m supposed to be doing this evening, I figured I’d see how “accurate” this comic was. Here’s my pygame code that checks it out. If you run main.py it will start with an image (the xkcd logo) and each time you press a key it will do an iteration of re-creating the comic. You can see it flashing between the current iteration and the original strip. After about 4-5 iterations the images converge (pretty closely.)
The most interesting bit was trying different starting images and seeing how long it took to converge. Starting with all black it takes 6 iterations. Starting with all white takes 5 iterations. And starting with the xkcd logo takes 4 iterations. The logo probably goes the quickest because it has some black and white in it (like this image) so it converges faster. (You can edit main.py towards the bottom page to try these different starting points.)
So .. there ya go! Enjoy!
-Phil
January 14th, 2010 at 3:00 am
Ahah brilliant!
January 14th, 2010 at 8:14 am
I particularly like the way the two label lines into the pie chart exactly cancel each other out so the pie chart remains correct.
January 14th, 2010 at 1:43 pm
Very interesting.
Just a note for Ubuntu users. You need pygame installed:
# aptitude install python-pygame
January 14th, 2010 at 3:19 pm
When I run it I get:
Traceback (most recent call last):
File “main.py”, line 88, in
main()
File “main.py”, line 62, in main
screen.blit(pygame.transform.smoothscale(pygame.image.load(‘xkcdLogo.png’),(SW,SH)),(0,0)) # 4 iterations
AttributeError: ‘module’ object has no attribute ‘smoothscale’
I’m on debian, I could not find any package with a file called transform.
January 14th, 2010 at 3:19 pm
When I run it I get:
Traceback (most recent call last):
File “main.py”, line 88, in
main()
File “main.py”, line 62, in main
screen.blit(pygame.transform.smoothscale(pygame.image.load(‘xkcdLogo.png’),(SW,SH)),(0,0)) # 4 iterations
AttributeError: ‘module’ object has no attribute ‘smoothscale’
I’m on debian, I could not find any package with a file called smoothscale.
January 14th, 2010 at 7:35 pm
Ariel: you need to update your python-pygame package. I had same problem, “apt-get update; apt-get install python-pygame” fixed the problem (unstable)
January 14th, 2010 at 8:32 pm
Sorry, about the double post. Delete the first one.
I changed smoothscale to scale and it ran, and I made this sequence of images, so people who don’t have phygame, etc, can see it:
http://news.ycombinator.com/item?id=1054079
January 14th, 2010 at 9:13 pm
smoothscale is in the latest pygame, so yeah, older builds of it won’t have it.
Thanks for taking screenshots 🙂