Quick- and Mergesort in one line of Python

One-liners are always fun, so as a challenge I decided to implement both Quicksort and Mergesort in one line of Python, one line meaning one expression, no semicolons and no eval(). Quicksort was relatively straightforward, since it only really requires one operation applied recursively:



Mergesort however was more of a challenge. The problem is the merging of two sorted lists - this requires a loop, which is not trivial to implement inside of another recursive function in just one expression. Luckily though, the the process of merging can be achieved through recursion, and so we can pack it into a lambda expression that is called recursively.
We then still have the problem of having a lambda expression call itself inside of another lambda expression - it took some searching, but eventually I found a solution: a Z-combinator.

(lambda f: (lambda x: f(lambda *args: x(x)(*args)))(lambda x: f(lambda *args: x(x)(*args))))

This expression will take as an argument a function that is to be called recursively, and do exactly that. It allows for recursion with anonymous function. So now, all we need to do is pass the merge function to the Z combinator, and then call the resulting expression with the (recursively) mergesorted first and second half  of our list. Here'e the code:


Looks complicated, but you can see that the first lambda is just the Z combinator, followed by a rather long lambda on the variable m, this is our merge function. The reason for all the or and and's is the they are used to replace (if ... else ...) statements, since we can't nest these arbitrarily in lambdas. Also, the (r.append(a[0]) or a.remove(a[0]) or m(a,b,r)) statements simply return the third element (the recursive function call), since append() and remove() simply return none, and (none or [list] ) returns [list] in Python. This is a neat little hack that can be used to not only combine expressions but also to add return values to functions that otherwise return None.

Note that the Mergesort function here is highly recursive, I could only sort lists of around 330 elements before reaching maximum recursion depth. It is still reasonably fast however, taking around 0.004 seconds to sort 330 elements. Quicksort is much faster though, with 0.0002 seconds for the same list.

pybfc, A BF to C Compiler written in Python

So instead of studying for my exams, I decided to be less than productive and wrote a simple brainfuck to C compiler, in Python. I didn't initially mean for this to come out as hacky as it did, but I eventually decided I wanted to buff it down to 10 lines maximum.

Compiling brainfuck to C is pretty simple really, since all instructions in bf can be seen as operations on a single pointer variable in C, so all that needs to be done is replace each character with the appropriate C statement, which I did through a dictionary. There's a bit of code needed to initialize the program, but from then on it's all just one-to-one replacing. Finally, the script calls gcc to compile the code to be executable, using an optional command line argument as the output filename.



To compile bf code, save this as (for example) pybfc, and then run:

./pybfc .bf outputfilename

You can then execute the generated program just by running ./outputfilename.

Here's the source for a "Hello World!" program in brainfuck:

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

This compiles to some rather lengthy C code, I won't post it here, but the compiler will actually generate the C code into a file ("out.c") as well.

Balancing Graphs in O(n*log(n))

The Barnes-Hut algorithm is used to model N-body systems more efficiently, at the expense of precision. However, the improvement in performance is tremendous: from O( n² ) to O( n*log(n) ). For reference, this is what that looks like:

Since our force-based approach to computing graph layout is essentially nothing other than an N-body simulation, and we don't require great precision anyway, this algorithm seems perfect for us to use. The way it works is basically this:

• The set of nodes is sorted into a quadtree, which is essentially a binary tree, but with an added dimension
• Each of the quadtree sectors keeps track of its mass and center of mass
• To compute the forces, the tree is traversed and for points that are "far" from a certain center of mass, only the force from the node to that center of mass is calculated, as opposed to each force between all nodes

This leads to a significant decrease in overall calculations that needs to be done, since distant nodes no longer need to interact directly. There is some overhead on creating the quadtree every frame, but the growth of this is also O(n*log(n)). If you want to learn more, here is a very good explanation of the algorithm complete with pseudocode (in German, but the code is understandable anyway). 

I haven't had time to implement this algorithm in our Qt application to graph Wikipedia, however I managed to code up the basic algorithm in Python. The improvement is tremendous, before I was never able to reasonably run a simulation with more than 80 or so nodes in Python, now even systems up to 350 nodes run at a reasonable framerate.

Illustration of the quadtree (unbalanced)

The same graph after balancing

The algorithm can also be parallelized very well, so the potential of this is tremendous, with good implementation and appropriate hardware we could realistically graph all of the German Wikipedia (~1.3 million articles), maybe more. 

The full Python code is here.

The Westermann Programming language!

My CS1 professor is known for repeating the ever-living hell out of a set of buzzwords he has, in fact a friend of mine and I wrote a little program that uses speech recognition to listen for them and gives you an alert whenever he says one - the idea is that this would make an awesome drinking game. And yes, we can drink during our lectures, and it's awesome. Proof:

Buzzword bingo has also been proposed. Anyway, during one particularly boring lecture (on language syntax and regular expressions) I decided it would be fun to create a programming language out of these buzzwords, inspired by Ook!, which simply uses variants of the "Ook!" to represent each instruction in Brainfuck - probably the simplest way to create a programming language! 

I managed to put together a buzzword-to-Brainfuck compiler in a few minutes. It's really simple actually, all one needs to do is decide what buzzword to map to which Brainfuck command, replace each sting with that command and then feed the result to a Brainfuck compiler/interpreter. Amazingly, there's even a Brainfuck interpreter written in Python - in just one line! It's very obfuscated and unreadable, but seems to work as intended: http://www.cs.princeton.edu/~ynaamad/misc/bf.htm.

Here's the "Hello World!" program in the Westermann (name of the prof) language:

"schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend ist klar einfach schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend einfach schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend einfach schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend einfach schlicht und ergreifend also also also also konkret letztendlich einfach schlicht und ergreifend schlicht und ergreifend ganz einfach schlicht und ergreifend ganz schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend ganz ganz schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend ganz einfach schlicht und ergreifend schlicht und ergreifend ganz also also schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend ganz einfach ganz schlicht und ergreifend schlicht und ergreifend schlicht und ergreifend ganz konkret konkret konkret konkret konkret konkret ganz konkret konkret konkret konkret konkret konkret konkret konkret ganz einfach schlicht und ergreifend ganz einfach ganz "

Writing the actual converter was trivial, I'll just leave you the code here:

That code includes functions to convert between the "languages", and also the source code for a "Hello World!" program. I'm calling it the Westermann programming language because that's the name of my prof. Also, yes the words are German, I go to school in Munich.
Finally, I managed to cram the entire converter/interpreter into one line, so saving this next piece of code as wmInterpret.py and running

python wmInterpret.py yourprogramsourcefile

will run the specified program. You could replace any of the words with whatever you want and just like that you've got yourself a programming language - although probably a pretty incomprehensible one. Here's the one-line interpreter:


Anyway, have fun with this, make your own little language if you feel like it. Have a good weekend!

A Chapter in Python List Comprehension Abuse

Apparently Facebook held the qualification to this years Hackercup last weekend, I just came across some of the problems and decided to write a quick solution for one of them. And since Python has this awesome thing called list comprehensions, I managed to cram the solution into a single (ugly) line.
The task is basically this: Given a string, find how many times the string "HACKERCUP" can be formed from its letters without resusing any letters. (Full description here) Seems simple enough, lets see..
First, a little bit on list comprehensions. Usually, to define a list you do the following:


To fill a list, we could to this: But, it turns out there's an easier way - Python lets you create lists "implicitly", so to say. You can iterate over range(10) inside the list and create elements dynamically:

Looks interesting, and there's a lot you can do with this, because there are very few limitations on what you can put inside a list comprehension. You can even nest them to create matrices or do other things. The following line will flatten a list of lists:
For my solution to the problem, I actually read input inside a list comprehension, and then generate a list of that input to work with.

Here's the full code:

EXAMPLE INPUT

5
WELCOME TO FACEBOOK HACKERCUP
CUP WITH LABEL HACKERCUP BELONGS TO HACKER
QUICK CUTE BROWN FOX JUMPS OVER THE LAZY DOG
MOVE FAST BE BOLD
HACK THE HACKERCUP


EXAMPLE OUTPUT

Case #1: 1
Case #2: 2
Case #3: 1
Case #4: 0
Case #5: 1

It's a bit obfuscated, but should still be understandable. The print("\n".join(......)) part prints each element in the following list into a new line, so the output is in the required format. After that, we have the actual generation of our results.
In the last part - [raw_input() for x in range(int(raw_input))] - I read the input. range() takes the number of lines that follow, and then reads that many lines. This list is worked with by the outer list comprehension, which applies a formula to it to count how many times "HACKERCUP" can be formed out of each of the input strings' letters (tC means test case, n is the index of the test case we're on).
The actual formula is this:



We count how many times each letter (the variable c) in "HACKERCUP" occurs in the test case string, and divide by how often it appears in "HACKERCUP" in the first place (rounding down). We store each result in a list, and then take the minimum of that list, giving us our final result.

So, the code is pretty messy and arguably unpythonic, but it demonstrates pretty well how powerful list comprehensions are in Python. Wrap them up in a while(true) loop and you can even create whole mini-games in one line of code!

Automating Graph Layout

When working with graphs (the nodes and edges kind) on a computer, good arrangement and layout of the nodes is an interesting problem. To us, there is usually an obvious or at least visually appealing way to draw a graph, but a computer has no intuition (yet?) so finding a good layout for the graph can be difficult. It isn't hard to represent a graph as such in a computer, in fact things like adjacency matrices are probably much easier for a computer to read than a human, especially as you add more nodes.

There's also the problem of deciding what sort of layout is the right one for a given graph in the first place: Say you want to plot three things: A mesh network, a tree graph and a import/export relations between countries. Should each be laid out according to the same rules? Probably not - in a mesh network, we do not expect edges that reach far from one side of the graph to the other, so we can generally just place adjecent(in the sense that they are connected) nodes adjacent(location) to each other. A tree graph has a much different structure, in fact as the name implies, we would choose a tree-like layout. Import/export routes would of course be graphed according to actual geographical location, and even if not, the nodes are connected much differently. You might also want to assign a heavier weight or larger size to some nodes (according to GDP, for example).

For all of these, one can create different algorithms that find a good, or even optimal layout. Wikipedia actually has a page about some of them. 

You may remember that I briefly wrote about a project I was considering, namely an interactive Wikipedia (or other webpages, for that matter) grapher. The idea is this: you give the program a starting page, and it then represents this page as a single node. When you then click it, the page is parsed for links to other Wikipedia articles, and each is added as a node on the graph, with an edge to the original article. You can repeat this process for each new node, and edges are added whenever one article links to another one on the graph. 

I've started working on this project recently, and have found a good (but unfortunately somewhat slow - about O(n^3) ) algorithm to draw this graph. Force-based layout creates a layout by treating each edge as a spring that pulls adjacent nodes together, while simultaneously repulsing all nodes from each other using something resembling Coulomb's law, and then iterating until an equilibrium of forces is found. For now, I've only implemented a rough version of this algorithm in Python, but for the final program I'll be using C++, mainly to get better performance for the graphing, but also to gain a bit more experience with it. The drawing will probably be done in SDL, it seems simple enough to use. 

Source code of the above animation's algorithm (graph was generated randomly):

Completed Python Logic Circuit Simulator

Project website

Logic gates are interesting, with a few of them you can create circuits with fairly complex functions. Most of the time, the function of the circuit is anything but obvious from just looking at it. For example, consider this one:
That's an adder. You set the inputs A and B to True or False ( 1 or 0), and the circuit will perform a binary addition where S will give you the sum of the two, and C_out the carry bit. The carry bit can then be fed into another full adder at C_in, and you'll also have two more inputs. This can be expanded to any size one wishes.
All currently functioning computers rely on such gates. Most likely, millions and millions of them are in your cellphone.

If you're at least a little familiar with formal logic, more specifically logical connections such as "and", "or", "nor", "xor" (="exclusive or") and so on, the way these circuits work will probably make sense to you very quickly.

I've written a few posts recently about a logic gate simulator I am writing in Python, pyGates. I won't say I finished it, because there are still a few bugs that come up every now and then, but it's far enough along for others to use. Here's a screenshot of what it currently looks like:


You can create new gates by simply dragging them from the left side of the screen, and destroy them by simply dragging them back there. This is actually the only part where I still get bugs every now and then, sometimes cables don't get destroyed properly, but I'll work on fixing this. For now, you can usually work around that by manually deleting the cable - detaching it from the other gate it is connected to, and clicking into empty space.

The website for the project, a zip file with everything you need and the raw source code is located at my website here: http://home.in.tum.de/~dowling/pyGates/.

More pyGates

I'm making some more progress on pyGates, as you can see above. To my surprise, all the logic in the circuits worked out the first time I tested it, which is unusual for my code... Anyway, the logic for the wires has turned out to be much harder than anything else (connecting, disconnecting, reconnecting, in-sockets vs out-out sockets, etc.) I'm close to having it all work out though. Next, I'll have to add functionality to be able to delete Gates, which should be fairly easy. Finally, I'll make the cables look nicer (right now its just a fairly shitty bezier curve, which it will remain, but hopefully less shitty), and then I'll share the source code either on here or on my webpage, since it's really a bit too long to post here in full.

(By the way, the above circuit will constantly change state when you actually build it)

Project Ideas

Doing is the best way to learn, and since learning is what we're here for, let's do some stuff. I've had a number of different ideas for projects recently and not so recently, so to offer you some inspirations and perhaps for me to see if any of these still make sense when you see them typed out, I've compiled a little list of them. (Some of these are actually projects I've already started working on)

• "Multiplayer" Paint. Basically, this would be like a chat program that lets two (or more?) people draw on the same canvas as one would in mspaint. I would implement this in C++, just because I want to learn more about it (and graphics / network programming) but also because most people don't have Python interpreters with pygame on their machine. It might be time for something different :)
• Javascript multiplayer Paint! Use a JS canvas for client side, and save the changes to canvas stored server side (maybe use php, or node.js for serverside scripting?) Then, everyone who visits the page can draw on it for everyone else to see. Obvious downsides of this however are the fact that this is still the internet, and I suspect sooner or later (sooner) it will meet a similar fate tot that of Chatroulette
  
• A 3-4 DoF Robotic arm. It doesn't have to be a very good one either, just to keep costs down. Forward and inverse kinematics are pretty interesting, and this would be a good way to learn and practice both. Servos can be picked up pretty cheaply as well, and the whole thing could be run from an Arduino - the only real difficulty in this would be the mechanical parts, I have no good way of making them properly. I got this idea from...
  
• .. building a hexapod. 3DoF would be minimum for each leg to be able tog et decently smooth motion, the problem is that this would be a rather costly product (for me, at least)
• A simple webcrawler. I don't know what you would use it for, but my ideas were perhaps a Reddit bot (find/keep track of reposts, produce statistics based on comments, find most used pun of the day, etc.), or a Wikipedia crawler (create a graph of pagelinks, those are always neat)
• On a similar note, implementing a graphing layout algorithm - finding a good layout for graphs (graph meaning a set of nodes connected by edges) automatically. There are different ways to implement this, the spring model seems like the simplest: each edge is like a spring that pulls two connected nodes together, or pushes them apart based on their distance from each other. One could also base the pushing/pulling force on the "weight" of each node (weight could be number of incoming edges, for example)
• implement quantitative stock trading algorithms. This is something I personally find really interesting, though I haven't worked on it much. Wikipedia has a nice page about the different algorithms that are used today. A technical problem that needs to be solved first is getting a decent sample of historical data for a given stock, as this is very often necessary for such algorithms.

Of course these all aren't new ideas, but I've found that I usually have good ideas while working on something else, and these are just inspirations for you anyway. Potentially all of these are good for learning something new!

Progress on pyGates

Yesterday I wrote a short paragraph about a project I recently started, a logic gate simulator written in Python (short: pyGates). I spent a night and most of todays classes coding on it, and it's starting to get to a point where it's almost usable. I still need to implement a few more things such as switches and lightbulbs, perhaps I'll add some higher-level logic chips later on, but the basic structure is put together and the wires will also finally behave properly (in terms of connecting to the right sockets and staying there, that is).

Next up is fixing up the graphics, the main thing here is to put in the standardized symbols for the different gates, and making the wires look nice (I'll probably have them hang down as though they were loose cables, similar to logicly). Below is a screenshot of what the program currently looks like (yes, the gates look the same even though they serve different functions).

Basic stock price functions in Python

I've been reading a bit into algorithmic stock trading lately, and thought I'd try and actually simulate a few of the trades strategies. The first thing I needed was a way to get at the stock prices, I figured the easiest way might be scraping either Yahoo or Google Finance. Turns out someone else has done this before, so no need to code it up myself. I think Google Finance has been updated since that module was written, because the regex used doesn't properly fetch the actual price. All I had to do was modify the function in a few places and everything was working as expected.
A neat thing about it is that you don't need to pass the exact ticker symbol you want to get a quote for into the get_quote function, since the stirng gets passed as a query to Google Finance, which autocorrects it.

I also added a stock class, as well as long and shot sell functions. This should be a good enough start to simulate some algorithmic trading.

pyGates

Something I've recently thought about was creating a small logic gate simulator which lets you build simple digital circuits. I've seen this elsewhere before (http://logic.ly/), with a very neat implementation but unfortunately that software now costs money. It shouldn't be too hard to brew something like this together, so I'll give this a shot over the next couple of days and see how it goes. I'll be using python for now just because I like working with it the most, but I might take this as an opportunity to learn JavaScript and host this online. I've already started working on this and have the basic structure together, all it is really is a pygame canvas with gate-objects and a few other things, but it may still take some time until it all comes together in a usable way. I'll keep you posted.

Another post in the Quining series

The other day I revisited some of the scripts I wrote when messing with self-replication /-modification, and noticed that it wouldn't be hard to automate the process of turning a program into a quining one. So I decided to write a little script that does exactly that - you simply give the filename of the python script you want quined, and it will produce a new script with the source code of the old one, plus additional code that will make that script return its own source code in a new file when exectuted. Hopefully this isn't too confusing, but it was certainly at times confusing to write, even though it's a fairly short script.



The real fun starts when you execute this script on itself.. you get a quining quine. Now repeat ad-infinitum.

Quine time!

So this morning I was randomly reminded of quines, computer programs that take no input and return their own source code. The term was coined by Douglas Hofstadter in Gödel, Escher, Bach, referring primarily to sentence structures - simply a sentence fragment preceded by its own quotation. This can create some fun paradoxes, such as this one:

"Yields falsehood when quined" yields falsehood when quined

I decided to try to write a quine on Python, a script that returns its own source code. Here's what I came up with after a few minutes:

l= ['print "l=", l', 'for a in l:', '    print a']

print "l=", l

for a in l:

print a

This is probably one of the simplest quines there are in Python, I wouldn't be surprised if others came up with something similar before, but I just thought this was kind of a neat piece of code.

It should be pretty to follow, too. The first line holds most of the rest of the script in text form. The second line simply prints the first line, and the for-loop prints out the text defined in the first line.

Now, here is something neat: we can add code that does pretty much anything after the first print statement, and as long as we also add this code into the list in the first line, the program is still a quine. This means that this turns out to e a template for self-replicating programs - you could have this script do whatever you want, and then replicate itself.

Preliminary robot control script

I haven't updated in a while, mainly because I kept on changing and adding things about the code which controls the robot. This mostly includes ROS (Robot Operating System) functionality related to Android devices, as my plan is to mount my G2 to the robot for things like GPS and orientation polling, automatic navigation or webcam feeds. I'm coming along on that code, but for now I'll just share the bare-bones python code which lets a user control the robot with the arrow buttons on a keyboard.

import serial
import pygame
import time
import sys
pygame.init()
forward=False
left=False
right=False
back=False
q=False
speed=220
screen = pygame.display.set_mode((100,100))

#ser=serial.Serial("/dev/ttyUSB0")
ser=serial.Serial("COM12")

while True:
    pygame.event.pump()
    key=pygame.key.get_pressed()

    forward=key[pygame.K_UP]
    left=key[pygame.K_LEFT]
    right=key[pygame.K_RIGHT]
    back=key[pygame.K_DOWN]
    q=key[pygame.K_q]
    
    if forward and not ((left or right) or back):
        LDirection="+"
        RDirection="+"
        LSpeed=chr(254)
        RSpeed=chr(254)
    elif back and not ((left or right) or forward):
        LDirection="-"
        RDirection="-"
        LSpeed=chr(254)
        RSpeed=chr(254)
    elif left and not ((forward or right) or back):
        LDirection="-"
        RDirection="+"
        LSpeed=chr(254)
        RSpeed=chr(254)
    elif right and not ((forward or left) or back):
        LDirection="+"
        RDirection="-"
        LSpeed=chr(254)
        RSpeed=chr(254)
    elif (forward and left) and not (right or back):
        LDirection="+"
        RDirection="+"
        LSpeed=chr(200)
        RSpeed=chr(254)
    elif (forward and right) and not (left or back):
        LDirection="+"
        RDirection="+"
        LSpeed=chr(254)
        RSpeed=chr(200)
    elif (back and right) and not (left or forward):
        LDirection="-"
        RDirection="-"
        LSpeed=chr(254)
        RSpeed=chr(200)
    elif (back and left) and not (right or forward):
        LDirection="-"
        RDirection="-"
        LSpeed=chr(200)
        RSpeed=chr(254)
    else:
        LDirection="-"
        RDirection="-"
        LSpeed=chr(0)
        RSpeed=chr(0)
    #checksum=ord(LDirection)+ord(LSpeed)+ord(RDirection)+ord(RSpeed)
    string="s"+LDirection+LSpeed+RDirection+RSpeed+"0"+"e"
    ser.write(string)
    print string
    if q:
        pygame.quit()
        sys.exit()
        ser.close()
    time.sleep(0.1)

As you can see, pygame is used for the keyboard input (which is probably not optimal, but I will later use the pygame window to display actual data). Checksum is not implemented yet, mainly because I'm lazy, and also because the robot has been working fine without it anyway. I'll still fix it at some point just for good practice.

Robot schematic and Arduino sketch

Last week I posted some pictures of a robot I've started building, at the moment it's really just a remote controlled car. I've put together a schematic showing the various pin connections. I use an Arduino Uno, an XBee radio, and an L293D motor driver chip, as well as two motors (mine are 9v).

Blue and red obviously represent power and ground lines, green connections represent digital or PWM signals from and to the Arduino, and the magenta lines are PWMs from the L293D, I chose a different color because they will run at a higher voltage than the Arduino PWMs, and they power the motors.

On the Arduino, I'm running the following sketch:

char index;
char serialbuff[7];
char ch;
int x=0;
int lSpeed;
int rSpeed;

int LMOTOR_DIR = 12;       // Non PWM pin for direction control
int LMOTOR_PWM = 11;       // PWM controlled pin.
int RMOTOR_DIR = 7;
int RMOTOR_PWM = 6;


void setup() {
Serial.begin(9600);

// Set the pins to output.
pinMode(LMOTOR_DIR, OUTPUT);
pinMode(LMOTOR_PWM, OUTPUT);
pinMode(RMOTOR_DIR, OUTPUT);
pinMode(RMOTOR_PWM, OUTPUT);
// And set these to a initial value to make sure.
digitalWrite(LMOTOR_DIR, LOW);
digitalWrite(LMOTOR_PWM, LOW);
digitalWrite(RMOTOR_DIR, LOW);
digitalWrite(RMOTOR_PWM, LOW);
}

void loop() {
 switch(x){
   case 0:{
     ch=(char)Serial.read();
     if(ch=='s'){
       x=1;
       serialbuff[0]=ch;
       index=1;
     }
   }
   break;
  
   case 1:{
     ch=(char)Serial.read();
     if(ch!=-1){
       serialbuff[index]=ch;
       index++;
       if(index==7){
        x=2;
       }
     }
   }
   break;
  
   case 2:{
     if(serialbuff[6]=='e'){
       x=3;
     }
     else{
     x=4;
   }
   }
   break;
    
   case 3:{
     if(serialbuff[1]=='+'){
       digitalWrite(LMOTOR_DIR, HIGH);
       lSpeed = 255-serialbuff[2];
     }
     else{
       digitalWrite(LMOTOR_DIR, LOW);
       lSpeed = serialbuff[2];
     }
     
     if(serialbuff[3]=='+'){
       digitalWrite(RMOTOR_DIR, HIGH);
       rSpeed = 255-serialbuff[4];
     }
     else{
       digitalWrite(RMOTOR_DIR, LOW);
       rSpeed = serialbuff[4];
     }
     
     analogWrite(LMOTOR_PWM, lSpeed);
     analogWrite(RMOTOR_PWM, rSpeed);
     
     x=4;
    }
   break; 
  
   case 4:{
     index=0;
     x=0;
   }
   break;
}
} 

As you can see, the Arduino will read its serial port (the XBee) for the character "s", which will indicate the start of a control packet. once it's found this, it reads the next characters, these will make up the rest of the packet:

• serialbuff[1] is either "+" or "-", indicating the direction of the left motor.
• serialbuff[2] is the speed of the left motor and can be between 0 and 255
• serialbuff[3] and [4] are the same as [1] and [2], but for the right motor
• serialbuff[5] will eventually act as a checksum, though I haven't implemented this properly yet
• serialbuff[6] must be "e" to indicate the end of a packet, otherwise the packet is discarded and loop restarts

You can see from this that the direction and speed of both motors can be completely controlled remotely, which gives us more opportunities as to how to steer the robot. For instance, instead of just using arrow buttons of the computer keyboard, one could write a script that converts accelerometer data (e.g. from a phone) into the appropriate motor speeds, allowing the robot to effectively be controlled through a phone.

Next up: the PC side script that sends packets to the robot.

Simulating birds

TL;DR: I wrote a simulation of swarming birds in Python using Pygame. The code can be found here.

So a while ago I caught a a bit of a documentary about swarming behavior in birds and fish, and I was interested to see if I could manage to write a little program to simulate such behavior. It's pretty interesting how the behavior of each bird is pretty simple and easy to model, yet on the macroscopic side, complex patterns emerge in such a system.

It's not too difficult to think about the behavior of each bird in a swarm:

1. Primarily, it will try to stay with the rest of the swarm, which on one hand means that it will stay relatively close to the groups "center" (i.e. their average position), and on the other that it will roughly match the velocity of its neighbors (especially in terms of direction).
   
2. Each bird also has it's own free will. On average of the whole group, this will determine the swarms tendency of movement.
3. Finally, the swarm as a whole may be drawn to some type of goal (e.g. food), which means that when simulating a swarm, each bird will sooner or later move towards this goal, though it will likely be more influenced by where the rest of the group is going.
   

I won't tediously take you through every line of the program I ended up with, but I think for anyone interested in this type of program, there's two major things about my model that are worth noting.

View

It should be taken into account that birds will only be drawn to the birds that they actually see, so for my program I implemented a view angle that is used to determine what other birds each bird uses to orient itself.
In an earlier version of this program, each birds navigation was based on all birds within a certain radius, which ended up having the swarm group together much more closely, but ultimately didn't look natural.

So how can it be determined if one bird can see another? The simplest (and really the only practical) way to do it involves the scalar product of the "seeing" birds' (B1) velocity vector and the vector from that bird to the one the whose visibility we are trying to determine (B2).








If theta is smaller than the defined viewing angle of the birds, then B1 can indeed see B2.

In Python, we can write the following function:

def isinview(x, y):                      
 if x==y:                              
     return False

 b1b2v = [birds[y][1][0]-birds[x][1][0],
     birds[y][1][1]-birds[x][1][1]]

 if (b1b2v[0]*birds[x][2][0] + b1b2v[1]*birds[x][2][1])/(vmag(b1b2v)*vmag(birds[x][2])) <= viewangle:
     return True
 else:
     return False

Note: The viewangle variable is stored as the cosine of the desired view angle, so that acos() doesn't need to be called hundreds of times in every frame.)

To clarify, in the program, the birds variable is a list containing the data for each bird:

• birds[n] is the nth bird
• birds[n][0] is the nth bird's "name" (for debugging, highlighting certain birds, etc.)
• birds[n][1] refers to the nth birds' position
• birds[n][2] is the velocity
• birds[n][3] and [4] are the last two velocity vectors, these are used as a component for the velocity calculation in every frame to simulate inertia, so that individual birds don't change direction so suddenly, leading to a more natural looking flight path.

Weighting

The other thing that needs to be considered is the weighting of the individual velocity components. Each birds' velocity in every frame is based on a number of factors: their free will (in the program, this is a random vector), the visible birds' positions, their velocities, a goal point, the birds past velocity vectors (inertia), and if so desired, the positions and velocities of all birds within a certain radius.
It needs to be decided how strongly each of these components should influence the birds flight. For instance, the random vector should probably be a weaker component than the inertia component, or the component that points towards the average position of the other birds should be fairly weak, otherwise the swarm will almost certainly never spread apart much.

The velocity vectors are therefore calculated this way: each component is assigned a "weight" in the beginning of the program. Each component vector is multiplied by its corresponding weight, and then all components are added together. Finally, the two numbers making up this sum vector are then each divided by the sum of the weights. This effectively creates sort of a weighted average. Perhaps this is not the most mathematically valid way to do it, but it enables us to alter the swarms behavior by playing with the weights of the individual components. For example, we can make the swarm more likely to spread apart by lowering the weight of the visible birds' positions to velocity.

If you would like to try out or play with the simulation yourself, the full code can be found here.

If you found this interesting, you may also be interested in Craig Reynolds' website on boids, he created and continues to work on sophisticated model of this phenomenon since 1986, there's tons of reading material on related subjects there, too.