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!

ICPC @ TUM and a Quick State of the Union

Guess what's coming to TUM:

Alright, you didn't actually have to guess.
The ICPC is a yearly programming contest at universities around the world, so naturally I was very excited today to find out that TUM is also participating. Teams can have between two and three members, and I've already recruited Robert for my team, which is definitely something to be excited about aswell, given that he's been coding since he was about 12 years old.
I've been doing a lot of problems on Project Euler lately, in fact I've recently hit 50 solved problems, but competing in a live event will be a very different feeling I expect.
The competition is Saturday in a week (04/02/2012), and will go on for 5 hours as far as I know, during which everyone needs to try and solve as many out of 10 problems as they can. On first glance I was hesitant to spend all Saturday at uni, but then I found out there's gonna be pizza so that was that.

If you're studying at TUM and are looking for a team to join for ICPC, drop me a comment here or send me an email! You can find more info on ICPC here: http://cm.baylor.edu/welcome.icpc and here: http://icpc.in.tum.de/index.php/Main_Page

By the way, Robert is also the guy who's working on the WikiGraph (still unsure of that name) project with me. He's been talking about starting a Blog, so I'll be sure to post a link on here once that happens. Seriously, the guy has skills.
Speaking of Wikigraph, there are some news on what's going on with that as well:

• We're getting good graphs for networks of up to fifteen thousand or so nodes, but beyond that our computational capacities don't allow for completing graphs in a reasonable amount of time.
• I've talked to two of my professors, and it looks like we may be able to get time on a 30-40 core cluster to run our program, which might allow us to graph the entire German Wikipedia (1.2 million articles). This would be pretty amazing, but we're definitely going to have to work on properly scaling the algorithm so we don't get buggy as the network gets huge. 
• I'm also working on a way to read the input from a database (specifically the Wikipedia dumps of all pages and pagelinks, which is available at  http://dumps.wikimedia.org/), but I'll post some technical stuff on that later. The gist of it is that I have to combine the pages dump (320MB) and pagelinks dump (2.6GB) to get a full description of all the connections. I'm still unsure of what the best way to do it is, and I don't want to waste time trying to do it inefficiently when dealing with these huge amounts of data. Finding disconnected subgraphs may also present itself to be a problem.
• Different datasets are also being worked on, one thing I'm particularly interested in is mapping Darknet/Meshnet, so I'm looking for a way to actually extract the entire set of nodes and their connections. I'm not sure if it's actually possible either, I'll have to look more closely into it.
• Finally, I used some of the source code from this project to create a simulation of planets/particles interacting through gravity - a planetary system, basically. It's almost more fun to play around with, in fact. Also more on that soon.

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)

MaterialMaker tool for TUM informatics

I've been meaning to try out some C# programming, so I collaborated with a friend of mine who is pretty experienced with it on a small but useful project - a tool to automatically download and display our class materials. He had already coded up the interface and execution logic during a particularly boring lecture, but it was all hardcoded to his filesystem and required the materials to already be downloaded and in the right folders. I figured it would be useful to add some functionality and let the program automatically download the latest materials and organize these in a generic directory it creates itself.

To get to the materials, I used RSS links that contained .pdfs and .zips of all the files. I wrote some parsing logic for these, which basically looks for tags and then extracts the direct link to the file. The filename is then checked with the local folders, and if it isn't already there, the file is downloaded.
Screenshot:


If you're a CS student at TUM and would like to use this tool, you can download it from my website: http://home.in.tum.de/~dowling/index.html. It shouldn't be too hard for me to add support for other classes, if you're interested just shoot me a message.

An update

Okay, so I've been pretty busy/on vacation lately and haven't been working on ROAMR very much, but I have made some progress which I'll talk about in a bit. First of all though, I wanted to share that I've finally setteld on where I'll be studying this fall. A while ago I had gotten accepted into Jacobs University Bremen, and I was pretty excited about it. However, they didn't offer me any scholarships so I decided not to take the offer. I was then considering KIT (Karlsruhe Institute of Technology), and was still waiting for a decision from the Technical University of Munich. I settled on TUM after getting the decision the night before my birthday. KIT and TUM are ranked pretty similarly by most sources (KIT tends to do a bit better, to be fair), but I decided on TUM because Munich is simply a much more exciting place to live, and I like their campus better. Also, they have slides in the Computer Science and Mathematics building. In addition, they appear to serve Pretzels and free beer during freshman orientation.

I believe if those slides were in the faculty for Physics, they would probably just lead right into each other.

I spent the last few days in Munich looking for an apartment (or a room, rather), and I finally found a nice one close to the campus.
I can't wait to move in, I should be getting there sometime in September.

So, now for the ROAMR project. I decided that for this sort of robot, it would be useful to implement a SLAM algorithm for mapping of the environment and autonomous navigation of the robot. The obvious sensor choice to be was a Kinect sensor, as it is fairly cheap and allows for full RGB-D mapping of the robots environment.
The downside of using a Kinect sensor is of course the fact that the robot will now become significantly bigger, and heavier. The Kinect feeds a very large amount of data, certainly too much for an Arduino to handle (not that the drivers exist anyway), so I find myself forced to mount a laptop (or at least a netbook) onto the robot, as well as a 12V battery to power the Kinect (which also dissipates energy at about 12W).
ROAMR is meant to be an experimental and (self-)educational project, I'm not looking to implement anything revolutionary or something that will have enormous potential for practical application, it's really just for fun. For this reason, I don't mind that adding a Kinect and Laptop will make it rather big and heavy in comparison to what it started out as. If someone (or me, later) was to build such a robot with similar hardware but needs it to be smaller, something like a Beagleboard could be used to transfer the Kinect data remotely through, for instance, a ROS topic. I am also considering a Raspberry Pi, but I will have to wait and see if anyone can get the Kinect drivers to work on it. The calculations and SLAM would then be done from another machine, the ROS Master node if you will, which effectively acts as the brain for the robot. The problem one runs into with this, however, is again the large amount of ata produced by the Kinect - not all (if any, I have not gotten it to work yet) WLAN connections will be able to provide the bandwidth necessary, and as far as i know ROS stops publishing to topics once the bandwidth is too high. So perhaps some kind of pre-processing or compression would need to be done onboard the robot.
In any case, here is what I plan to implement or look into for ROAMR:

• Since I have two Laptops at my disposal (one significantly more powerful than the other, let's call it the Thinkpad), I will first attempt to get the less powerful one to publish the Kinects data to the Thinkpad, so it can then run a SLAM algorithm, teleoperation, etc.
• If this does not work, I will simply mount the Thinkpad onto the robot and do the computation on board. The robot could then perhaps be controlled by another computer through VNC, or SSH (although VNC is more useful, as a GUI is of course a nice thing to have when you want to actually see the robot mapping it's environment)
• I will most likely implement the RGBD-6D-SLAM algorithm that can be found here, it utilizes both ROS and the Kinect, and allows for full 3D mapping and localization. i will have to find out how to extract the robot's perceived position in the map, and a way to implement a navigation algorithm. Another problem is presented, again, by the enoumous amounts of data produced. After a few minutes, these 3D point clouds can be as big as several gigabytes.
  
• The alternative SLAM algorithm is this 2D-SLAM, which is nice because it is simple to use and has navigation already implemented, however it was made for the TurtleBot, so I'd have to re-code most of my robots steering (i.e. how the Arduino receives and interprets commands). Also, the algorithm needs odometry, which ROAMR doesn't currently provide. however, in comparison to RGBD-6D-SLAM, the maps produced by this algorithm should be much smaller in filesize, and perhaps more CPU (and especially GPU) firendly.

Diagrams and pictures soon, then this will perhaps make a lot more sense.