I want to write about something very cool I learned about in my Linear Algebra class the other day.
Since since the sum of two continuous functions is continuous, and a continuous function multiplied by a scalar is continuous, the set of all continuous functions defined on the domain [a,b] is a vector space.
You can define an inner product [F|G] as the integral of the product F*G from point a to b (This operation has everything it takes to be an inner product). The inner product naturally gives us a norm. ||F|| = sqrt([F|F]), and an angle between functions: [F|G] = cos(theta) * ||F||||G||. The norm gives us a distance ||F-G||.
So now we have distance between functions and angles between functions. That means we can project a function onto another the same way that we can project a vector onto another in R^n. That's awesome! And potentially useful. =P
(Edit: Yes, it's useful. You can deduce the Fourier Series by noting that the cosine and sine as basis for this vector space)
Tuesday, October 21, 2008
Wednesday, October 1, 2008
Word Challenge cheating program
I have been playing Word Challenge on facebook, it is a very fun game. It made me start playing with anagrams, and I decided to write an anagram-solving program. However, I read about Donald Knuth's insight that if you sort a word and its anagram alphabetically, it will give the same word.
Example:
sergio -> egiors
orgies -> egiors
That means 'orgies' is an anagram of my name =P.
So, using a hash table it is pretty easy to find anagrams in constant time. You just have to associate a word made up of ordered letters to a list of all the possible anagrams. You can do it in O(n) by iterating through a dictionary file. There's no problem to solve when there is already an optimal solution.
I then decided to write a program that finds every possible word that can be formed by a group of letters (Which would be perfect to use if I ever wanted to cheat on Word Challenge. Which of course I never would! =P) .
I wrote an algorithm on top of Knuth's idea that is stupidly slow.
It takes n letters, and sorts them. It then finds all the anagrams associated to that sorted word and adds them to a set. Then it recurses to each possible word created by removing one letter, until it reaches the minimum number of letters. Which is, by default, 3.
I haven't proven it, but if my math is right, my algorithm is O( (n^2)(n-1)! ).
It works instantly on my machine when n<9.
http://sites.google.com/site/bigmonachus/Home/wc-py
It reads any dictionary file that is composed of single lines containing words on some language.
It is written in English, but there is some Spanish output. (You can probably figure out what it says.)
I was thinking of not uploading it, but there are probably already a lot of web applets that do the exact same thing, and I guess your average cheater wouldn't go through the trouble of running a Python script if he/she can't go through the trouble of practicing to get better at the game.
There are some obvious optimizations that could be made, like taking into account repeated letters.
There is also the option to change the data structure: First, load the dictionary to a list. Then order that list by the size of the words (from short to long).
For each word, create a key and append that word to the hash map with that key.
Create n sub-keys, where n is the number of letters in that key. Each sub-key has a letter removed. Since the key is sorted, each sub-key is also sorted. That means it is a valid key. Since it is shorter, it has already been added to the hash map (unless it doesn't have any anagrams or it is below our limit. In those cases, we ignore it). We add the values associated to these sub-keys to the value of the hash-map for the current key.
We are using dynamic programming, since we are eliminating the need for recursion by saving state. I don't know if I explained myself right..
There is no implementation for this idea since I came up with it as I was writing it =D. The new data structure would allow us to get all possible words for n letters in constant time!. And that structure can probably be filled pretty fast.
I'll edit this post when I have a working implementation =D
Update: New implementation.
I implemented the idea I wrote about, and it worked! (Sort of..)
First off, it takes a lot more memory. I have a Spanish dictionary with around 80,000 words, and my program is consuming about 177 MB of memory. This can be hugely improved by using indexes instead of storing strings.
The good news is that if you input any word to the program, and that word or any of its anagrams are in my dictionary, the program outputs all the possible words that can be formed by those letters in constant time.
The bad news is that if you input any word whose key is not in the hash table, the program can't tell you anything.
The solution to this was to check for this problem, and in those cases, iterate recursively through the possible sub-keys until we find the ones that are in the hash map.
This solution will cause the program to be extremely slow when you input large strings whose keys are not in the hash table.
Link to the new version.
Again, there are a lot of things that can still be improved. But this version works better than the last one.
Example:
sergio -> egiors
orgies -> egiors
That means 'orgies' is an anagram of my name =P.
So, using a hash table it is pretty easy to find anagrams in constant time. You just have to associate a word made up of ordered letters to a list of all the possible anagrams. You can do it in O(n) by iterating through a dictionary file. There's no problem to solve when there is already an optimal solution.
I then decided to write a program that finds every possible word that can be formed by a group of letters (Which would be perfect to use if I ever wanted to cheat on Word Challenge. Which of course I never would! =P) .
I wrote an algorithm on top of Knuth's idea that is stupidly slow.
It takes n letters, and sorts them. It then finds all the anagrams associated to that sorted word and adds them to a set. Then it recurses to each possible word created by removing one letter, until it reaches the minimum number of letters. Which is, by default, 3.
I haven't proven it, but if my math is right, my algorithm is O( (n^2)(n-1)! ).
It works instantly on my machine when n<9.
http://sites.google.com/site/bigmonachus/Home/wc-py
It reads any dictionary file that is composed of single lines containing words on some language.
It is written in English, but there is some Spanish output. (You can probably figure out what it says.)
I was thinking of not uploading it, but there are probably already a lot of web applets that do the exact same thing, and I guess your average cheater wouldn't go through the trouble of running a Python script if he/she can't go through the trouble of practicing to get better at the game.
There are some obvious optimizations that could be made, like taking into account repeated letters.
There is also the option to change the data structure: First, load the dictionary to a list. Then order that list by the size of the words (from short to long).
For each word, create a key and append that word to the hash map with that key.
Create n sub-keys, where n is the number of letters in that key. Each sub-key has a letter removed. Since the key is sorted, each sub-key is also sorted. That means it is a valid key. Since it is shorter, it has already been added to the hash map (unless it doesn't have any anagrams or it is below our limit. In those cases, we ignore it). We add the values associated to these sub-keys to the value of the hash-map for the current key.
We are using dynamic programming, since we are eliminating the need for recursion by saving state. I don't know if I explained myself right..
There is no implementation for this idea since I came up with it as I was writing it =D. The new data structure would allow us to get all possible words for n letters in constant time!. And that structure can probably be filled pretty fast.
I'll edit this post when I have a working implementation =D
Update: New implementation.
I implemented the idea I wrote about, and it worked! (Sort of..)
First off, it takes a lot more memory. I have a Spanish dictionary with around 80,000 words, and my program is consuming about 177 MB of memory. This can be hugely improved by using indexes instead of storing strings.
The good news is that if you input any word to the program, and that word or any of its anagrams are in my dictionary, the program outputs all the possible words that can be formed by those letters in constant time.
The bad news is that if you input any word whose key is not in the hash table, the program can't tell you anything.
The solution to this was to check for this problem, and in those cases, iterate recursively through the possible sub-keys until we find the ones that are in the hash map.
This solution will cause the program to be extremely slow when you input large strings whose keys are not in the hash table.
Link to the new version.
Again, there are a lot of things that can still be improved. But this version works better than the last one.
Tuesday, September 30, 2008
Some sound processing ideas..
Today I was spending some time trying to find a really cool thing to do with my Arduino and accelerometers, without having to spend more money on electronics. I came up with what I think is a really neat idea: Acceleration-controlled digital audio processing!, which is fancy-talk for "I want to plug-in my guitar to my computer and do some crazy effects that change as I move some part of my body".
One idea is to use the accelerometer to interface with OpenAL's 3D audio functionality. So if I want to listen through the back speakers of a 5.1 system, I just have to tilt my device backwards!. This would come in handy for testing how well are my Bose Companion 5 speakers working. I think this will be pretty easy to implement on top of my rotating cube idea.
The second idea is a lot more sophisticated. I would like to write some real-time sound effects and run them through some input. Specifically, my guitar =). The idea is to eventually have a device strapped to some body part with a weight associated to each acceleration axis, each associated with an effect, or an effect-parameter. I'll start writing a prototype for the first idea today, as soon as I finish my homework..
One idea is to use the accelerometer to interface with OpenAL's 3D audio functionality. So if I want to listen through the back speakers of a 5.1 system, I just have to tilt my device backwards!. This would come in handy for testing how well are my Bose Companion 5 speakers working. I think this will be pretty easy to implement on top of my rotating cube idea.
The second idea is a lot more sophisticated. I would like to write some real-time sound effects and run them through some input. Specifically, my guitar =). The idea is to eventually have a device strapped to some body part with a weight associated to each acceleration axis, each associated with an effect, or an effect-parameter. I'll start writing a prototype for the first idea today, as soon as I finish my homework..
Monday, August 4, 2008
Interfacing Arduino with C++ and libSerial.
I know that there is a section at the Arduino Playground on interfacing the Arduino with C. However, I found it is much easier, almost trivial, to use libSerial with C++.
(libSerial works on POSIX systems. I guess Windows users could use it through Cygwin but I'm not sure)
(Update: No, they can't)
First, you import your libraries and define the port you will be using:
The above code is assuming that the arduino is bound to /dev/ttyUSB0. Make sure to point the stream to the real device on you computer ;)
A new serial stream "ardu" is created.
Now let's define a simple function to setup the Arduino for communication.
At least in my case, this simple function is enough to have a working serial communication with the microcontroller.
Now I'll write another simple function that sends one byte through the serial port to the arduino and then reads a string, which gets interpreted as an integer..
See? It's easy! :)
If for some reason you must use standard POSIX libraries, here is a great article on POSIX serial programming.
If you have any doubts, post a comment.
(libSerial works on POSIX systems. I guess Windows users could use it through Cygwin but I'm not sure)
(Update: No, they can't)
First, you import your libraries and define the port you will be using:
#include < SerialStream.h >
#include < iostream >
#define PORT "/dev/ttyUSB0" //This is system-specific
SerialStream ardu;
using namespace std;
using namespace LibSerial;
The above code is assuming that the arduino is bound to /dev/ttyUSB0. Make sure to point the stream to the real device on you computer ;)
A new serial stream "ardu" is created.
Now let's define a simple function to setup the Arduino for communication.
void open()
{
ardu.Open(PORT);
/*The arduino must be setup to use the same baud rate*/
ardu.SetBaudRate(SerialStreamBuf::BAUD_9600);
ardu.SetCharSize(SerialStreamBuf::CHAR_SIZE_8);
}
At least in my case, this simple function is enough to have a working serial communication with the microcontroller.
Now I'll write another simple function that sends one byte through the serial port to the arduino and then reads a string, which gets interpreted as an integer..
int get(char out)
{
int res;
char str[SOME_BIG_SIZE];
ardu << out;
ardu >> str;
sscanf(str,"%d",&res);
return res;
}
See? It's easy! :)
If for some reason you must use standard POSIX libraries, here is a great article on POSIX serial programming.
If you have any doubts, post a comment.
Thursday, July 31, 2008
Rotating cubes.
A couple of days ago I got 3 LIS3LV02DQ accelerometers from Sparkfun electronics.
Today I finished a working demo showing a cube that rotates as you rotate the device.
This accelerometer has some good documentation to learn how to use it. There is also a post in some blog with a specific example for the arduino.
That example didn't work for me, but when I wasn't sure about something, it did help to take a peek at it. Reading the datasheet carefully is extremely important.
The arduino has built-in SPI support, which helps a lot since the accelerometer uses SPI (or I^2C) to communicate. However, it is bound to 4 specific pins in the board, and if I'm going to use the 3 accelerometers at the same time without any additional hardware, I am going to have to write a software implementation, since I would be using 12 pins.
The interface to the arduino was written in C++. It uses libSerial, which makes communicating with the arduino almost as trivial as when using Python.
Today I finished a working demo showing a cube that rotates as you rotate the device.
This accelerometer has some good documentation to learn how to use it. There is also a post in some blog with a specific example for the arduino.
That example didn't work for me, but when I wasn't sure about something, it did help to take a peek at it. Reading the datasheet carefully is extremely important.
The arduino has built-in SPI support, which helps a lot since the accelerometer uses SPI (or I^2C) to communicate. However, it is bound to 4 specific pins in the board, and if I'm going to use the 3 accelerometers at the same time without any additional hardware, I am going to have to write a software implementation, since I would be using 12 pins.
The interface to the arduino was written in C++. It uses libSerial, which makes communicating with the arduino almost as trivial as when using Python.
Wednesday, July 9, 2008
Arduino board.
(This devlog used to be on livejournal, but I moved all the entries to blogger using a program I found on the web.)
My new arduino board got delivered today =D. I spent a part of the day doing some electronics experiments. I assassinated my RC Helicopter and a personal fan in order to use their motors. Unfortunately they are not strong enough for my future plans (making an autonomous copter). Turning some LED's on and off was fun for a while too =P.
It's got a nice development environment (it uses a derivative of the C language), but I think I'll be happier using Emacs.
Before it arrived I was starting to incorporate Framebuffer objects into pycave, my little python game. Turns out they're pretty easy to use, and also elegant. The specification is available online and they're a couple of pdf's floating around the web. I'll be using them to improve the shadow effects, and to make them faster.
A couple of days ago I made a model and texture for the ship that according to me looked pretty nice. That hasn't been the general opinion =P
I am also aching to start writing shaders. However, I think that pyCave will stay with a fixed-function pipeline.
CUDA is another thing I would love to get my hands dirty with, but making killer robots is just a bit more interesting right now. Tomorrow I will order some motors (and actuators?) to start doing fun stuff!
I have left the ray tracer alone for now. I do plan to finish it. It's a really basic ray tracer so it shouldn't take long. I have also been gaming a bit too much, I got Call of Duty 4 and it's a kick ass game.
These vacations haven't been as productive as I hoped, since I went on an unexpected trip to the US. But I'm going to squeeze as much time as I can (and as much as COD4 does not take from me) to program =). I will also be managing my time better next semester in order to not be so stagnant.
My new arduino board got delivered today =D. I spent a part of the day doing some electronics experiments. I assassinated my RC Helicopter and a personal fan in order to use their motors. Unfortunately they are not strong enough for my future plans (making an autonomous copter). Turning some LED's on and off was fun for a while too =P.
It's got a nice development environment (it uses a derivative of the C language), but I think I'll be happier using Emacs.
Before it arrived I was starting to incorporate Framebuffer objects into pycave, my little python game. Turns out they're pretty easy to use, and also elegant. The specification is available online and they're a couple of pdf's floating around the web. I'll be using them to improve the shadow effects, and to make them faster.
A couple of days ago I made a model and texture for the ship that according to me looked pretty nice. That hasn't been the general opinion =P
I am also aching to start writing shaders. However, I think that pyCave will stay with a fixed-function pipeline.
CUDA is another thing I would love to get my hands dirty with, but making killer robots is just a bit more interesting right now. Tomorrow I will order some motors (and actuators?) to start doing fun stuff!
I have left the ray tracer alone for now. I do plan to finish it. It's a really basic ray tracer so it shouldn't take long. I have also been gaming a bit too much, I got Call of Duty 4 and it's a kick ass game.
These vacations haven't been as productive as I hoped, since I went on an unexpected trip to the US. But I'm going to squeeze as much time as I can (and as much as COD4 does not take from me) to program =). I will also be managing my time better next semester in order to not be so stagnant.
Saturday, July 5, 2008
SFCave clone update
Last night I didn't sleep since I was at a lan party, so I made a lot of mistakes this morning while working on my little game. I wrote some sprite code to show smoke, after creating a sprite doing some photo-editing in gimp. Then I made a separate display list for the tunnel obstacles so they can cast shadows on the tunnel.
I think it is looking really cool now, so I uploaded a video to YouTube, here it is:
I am still going to put the video on pyCave's website.
I think it is looking really cool now, so I uploaded a video to YouTube, here it is:
I am still going to put the video on pyCave's website.
Wednesday, June 4, 2008
I had to post this
It's only been a couple of hours since the last post... but this is cool:
Lighting works:

The problem was that the python image library needed integers for the color value. Now it's using opengl (just to draw points), where there is a color function that takes r,b,g float parameters.
It's starting to look nice! =) And adding reflections is going to be pretty trivial..
===Edit:
I forgot to mention that I managed to make it quite faster by removing a lot of calls to the Python C API. (i.e. defining C structures and using them instead of python tuples)
Now it is running at 1.08 the speed of the original C module. That means that I traded 8% performance for making the code less than half the size and much more easier to maintain... decent trade-off
Lighting works:
The problem was that the python image library needed integers for the color value. Now it's using opengl (just to draw points), where there is a color function that takes r,b,g float parameters.
It's starting to look nice! =) And adding reflections is going to be pretty trivial..
===Edit:
I forgot to mention that I managed to make it quite faster by removing a lot of calls to the Python C API. (i.e. defining C structures and using them instead of python tuples)
Now it is running at 1.08 the speed of the original C module. That means that I traded 8% performance for making the code less than half the size and much more easier to maintain... decent trade-off
Switched to cython
I had to spend a couple of hours today rewriting some code after reading about Cython.
I rewrote the C module to a Cython file. It runs at about 1.33 the speed of the C module, but I believe that's mainly because I'm using tuples all over the place instead of C structs. My guess is that the decrease in speed would become very moderate after optimizing. The new module also got rid of a bug in the C module where objects would disappear when being too far from the viewing plane.
Even if after optimizing there isn't a huge performance gain, I think the penalty would be well worth it. The code is less than half the length and didn't take long to write..
Here is an image:

Again, two identical, separated spheres.
There is also some primitive lighting. Note the "banding"... It is caused because the program is rounding floats to ints. Shouldn't be very tough to fix.
I rewrote the C module to a Cython file. It runs at about 1.33 the speed of the C module, but I believe that's mainly because I'm using tuples all over the place instead of C structs. My guess is that the decrease in speed would become very moderate after optimizing. The new module also got rid of a bug in the C module where objects would disappear when being too far from the viewing plane.
Even if after optimizing there isn't a huge performance gain, I think the penalty would be well worth it. The code is less than half the length and didn't take long to write..
Here is an image:
Again, two identical, separated spheres.
There is also some primitive lighting. Note the "banding"... It is caused because the program is rounding floats to ints. Shouldn't be very tough to fix.
Sunday, June 1, 2008
More ray tracing
Yesterday I had free time for the first time in weeks!! So I worked a lot on the ray tracer...
All data structures are Python objects. However, all the ray calculation is currently done by a module written in C.
Something that is really cool, is that at the innermost loop of the ray calculation, I have a call to a python function, named "shader". That call isn't really that expensive and it allows me to run python code at the main loop!! Not only that, the objects (for now only spheres) actually have a reference to the shader they want to use. So I can call basically any python function if I plug it into one of the spheres =)
For now, there is only one loop. The shaders will be in charge of running new loops to calculate lighting, make shadows, reflections, etc.. But for now they only fill the pixel with a determined color.
Here is a 600x300 image that took only 0.079 seconds to draw. It is noteworthy that most of that time was spent drawing pixels with the Python Image Library. A faster library will improve it a lot, and adding support for multiple processors will be easy.

They are two spheres of the same size, the green one is farther away from the eye. (The last image I posted had two spheres of different sizes with no perspective)
All data structures are Python objects. However, all the ray calculation is currently done by a module written in C.
Something that is really cool, is that at the innermost loop of the ray calculation, I have a call to a python function, named "shader". That call isn't really that expensive and it allows me to run python code at the main loop!! Not only that, the objects (for now only spheres) actually have a reference to the shader they want to use. So I can call basically any python function if I plug it into one of the spheres =)
For now, there is only one loop. The shaders will be in charge of running new loops to calculate lighting, make shadows, reflections, etc.. But for now they only fill the pixel with a determined color.
Here is a 600x300 image that took only 0.079 seconds to draw. It is noteworthy that most of that time was spent drawing pixels with the Python Image Library. A faster library will improve it a lot, and adding support for multiple processors will be easy.
They are two spheres of the same size, the green one is farther away from the eye. (The last image I posted had two spheres of different sizes with no perspective)
Friday, May 30, 2008
Python ray tracing
I haven't really had time to do anything significant, but I have written an extremely primitive ray tracer in python.
It may seem like a stupid idea to make such a computing intensive task in Python, but that's part of the point... to optimize everything and get some decent speeds. The plan is to use numpy arrays and some inlined C code (with scipy.weave) to optimize the bottlenecks, but to really know where the bottlenecks are I have first to write a working ray tracer. However, in order to do that I need free time, and that's something I don't have right now (says he who is writing on his journal), and the free time I have had I have been spending stupidly deliberating on language choice..
Before 23:59 tonight, I have to turn in a little programming homework, to make an blur image filter. It's a pretty interesting homework for a first programming course, and we have had projects like that all semester.
I am taking a seminar on Mathematics for Computer Graphics, and for the final project I'll be writing a curve (splines) and surface (nurbs) renderer from scrath. So I will be posting that here =)
==Edit:
I forgot, here is a little dump from the raytracer:

Two spheres without any kind of lighting effect =P
It may seem like a stupid idea to make such a computing intensive task in Python, but that's part of the point... to optimize everything and get some decent speeds. The plan is to use numpy arrays and some inlined C code (with scipy.weave) to optimize the bottlenecks, but to really know where the bottlenecks are I have first to write a working ray tracer. However, in order to do that I need free time, and that's something I don't have right now (says he who is writing on his journal), and the free time I have had I have been spending stupidly deliberating on language choice..
Before 23:59 tonight, I have to turn in a little programming homework, to make an blur image filter. It's a pretty interesting homework for a first programming course, and we have had projects like that all semester.
I am taking a seminar on Mathematics for Computer Graphics, and for the final project I'll be writing a curve (splines) and surface (nurbs) renderer from scrath. So I will be posting that here =)
==Edit:
I forgot, here is a little dump from the raytracer:
Two spheres without any kind of lighting effect =P
Subscribe to:
Posts (Atom)