32leaves

Visualizing Sorting Algorithms – my shot

February 8, 2010 – 3:28 am

These days I have to write some sort of reference card for basic sorting algorithms. Of course I wanted some sort of visualization of those algorithms on that card. The coolest sorting algorithm visualization I’ve seen so far has been created by Aldo Cortesi. He used Cairo to draw his stuff (according to his post learning Cairo was the whole point of this excercise).

Personally I still found those diagrams pretty hard to read if you really wanted to follow the algorithm. And of course I wanted to do something with Cairo, too. So I decided to rewrite the whole thing in C. My version shows distinct sections for each loop iteration (as most of those algorithms can be followed by thinking in that iterative loop way). In the diagrams below each number denotes the loop nesting level while B stands for being and E for end.

The source can be downloaded here and is under CC-BY-SA.

Insertion sort:

Selection sort:

Bubble sort:

Shell sort ( $k=\dots, 132, 57, 23, 10, 4, 1$ ):

By Christian | Posted in Studies | Tagged visualization | Comments (0)

Controlling a robot arm using an ez430 Chronos

February 3, 2010 – 2:31 am

A few days ago the ez430 Chronos I ordered from Farnell was delivered. This particular piece of hardware is an evaluation platform for the MSP430 (or the MSP430 as a CC430F6137 SoC to be more precise) which comes as a sports watch. It’s got some pretty neat features such as a temperature sensor, accelerometers on all three axis (which is why I’m using it here) and an RF transceiver built in. The first thing I did to it was to enable the watch to display the current time binary encoded.

After getting this to work (which was not that hard at all) I moved on to trying to get some data using the RF link. In the ez430 Chronos Wiki someone posted a Python program which polls the RF hub for accelerometer data. Having a Mac and not wanting to spend hours on getting pyserial to work, I wrote my own version in Ruby.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

require 'rubygems'

# on my machine a simple require does not work for this library
Kernel.require 'serialport'

SERIAL = SerialPort.new ARGV[0], 115200
SERIAL.read_timeout = 1000
def serial(data); data.each {|c| SERIAL.putc(c) }; SERIAL.flush end

# start access point
serial([0xFF, 0x07, 0x03])

while(true)
# request the data
serial([0xFF, 0x08, 0x07, 0x00, 0x00, 0x00, 0x00])

accel = SERIAL.read(7)
unless accel.nil?
accel = accel.scan(/./).map {|c| c[0] }

if accel[3] == 1
puts accel[4..6].join(" ")
STDOUT.flush
end
end
end

SERIAL.close

That’s pretty nice, but I wanted some real time graphs of the data, so a half an hour later I got a short Processing sketch running which does exactly that.

Next semester I’ll participate in a project in which we’ll built a new hardware interface to some pretty old robot arm hardware (it states “Made in West Germany”, that’s quite some time ago). In order to do that we need some sort of protocol to communicate with the new hardware interface. In preparation for that project I wrote a simulator for the robot (actually that’s supposed to be a part of the project, but I simply couldn’t resist) which uses an early draft of that particular protocol. Just to have that mentioned, the protocol itself is described as a state machine in a DSL which can be compiled to virtually any programming language. I’ll probably write a post about that nice piece of Scala code at some later time.

So with a working robot arm simulator, a watch which has accelerometers built in and is capable of wireless communication what else could I’ve done than to combine those two. That said I got to work and enhanced the script above to communicate with the simulator. About an hour later I got the first movements controlled by the accelerometer data of the watch. You might have seen the video already, if not go and watch it

Update: We had some spare time to spent and did some really basic proof of concept with the real hardware. Here we go:

By Christian | Posted in Development | Tagged ez430, TeachRobot | Comments (0)

Readonly hardware IRC client

January 27, 2010 – 11:28 pm

Right after we got the network running on my board (see my previous post) I got the board of the talented hacker mentioned before and started to hack a small read-only IRC client for it (after having a look at RFC1459 and RFC2812. About an hour later I was able to connect to a server, join a channel and listen for messages which are displayed on the OLED display. Unfortunately the display is broken on that particular board. But none the less, there is a lot of cool stuff ahead.

Again we have some screenshots:

By Christian | Posted in Development | Tagged LM3S6965, Luminary | Comments (0)

Getting the network of my LM3S6965 board to work

January 27, 2010 – 7:56 pm

I’ve had this board for about a 1.5 years. All that time I was disliked the fact that the ethernet was not working. No matter what I tried, what example I flashed nothing helped. Today I learned why: the hardware’s simply broken.
That’s no guess too far away, but being a software guy that’s just an unreachable world to me.

Thankfully that’s not the case for a friend of mine. He’s a talented hacker (from today on I know how talented

) and he got this fixed. All the time I was like: “hey, if that’s so easy someone else would have done it already instead of buying that super-expensive Pulse Jack Ethernet Transformer hardware”. None the less he pushed forward and got it to work. As usually pictures say more than a thousand words, so here we go:

By Christian | Posted in Development, Gizmos | Tagged Ethernet, LM3S6965, Luminary | Comments (0)

Unix Friends and User Group Campus Camp 2010

January 18, 2010 – 1:22 am

The UnFUCK2010 just went over. UnFUCK is a three day event organized by students of the Hochschule Furtwangen University (incl. myself) which features a lot of talks on quite a variety of topics. This year – which was the second time UnFUCK took place – we had talks starting from the power of prime numbers to fiddling with the ARM Cortex-M3. The timeline gives some more information about what was going on.

All in all it was a weekend definitely well spent, I had the opportunity to meet a lot of inspiring people and to hear about new and cool ideas. Videos of this conference should be available at the UnFUCK wiki within the next days (unfortunately everything in German).

On Sunday I had the opportunity to hold my Informatik Rockstars (that’s no typo here, it’s German

) talk again. It basically presents people who have delivered extraordinary participation to computer science (with a slight bias towards theoretical computer science) as a trading card game. As I’ve been asked a couple of times now to publish those cards I do so (unfortunately they’re also in German). They are in no particular order, far away from being complete and should be considered to be work in progress. Download link and license are at the end of this post.

You can also download the whole set here.

Informatik Rockstars Trading Cards by Christian Weichel is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License

By Christian | Posted in Fun, Studies | Tagged UnFUCK | Comments (1)

Y combinator in Scala

December 11, 2009 – 12:52 pm

This is just a quick post to share this thing with the world: the Y-combinator in Scala (yipee, anonymous recursion). Unfortunately this can’t be written purely as Scala does not employ lazy evaluation (like Haskell does).

1
2
3
4
5
6
7
8
9

object YCombinator {

def Y[A](f: (A => A) => (A => A)): (A => A) = f(Y(f))(_:A)

def main(args: Array[String]) = {
println(Y( (fact:(Int => Int)) => (x:Int) => if(x == 0) 1 else x * fact(x - 1) )(5))
}

}

By Christian | Posted in Uncategorized | Tagged recursion, Scala | Comments (1)

Raytracing: second shot

November 21, 2009 – 11:27 pm

Alright, this is propably the last shot I’m taking on raytracing. I implemented some pretty neat features. First of all: reflection:

The left picture shows the image without reflection, the right one with reflection enabled. Actually reflection is pretty easy to implement. All we need to do is recursivly trace the reflected rays.

The second feature is also pretty neat: anti-aliasing. Actually that also is not too difficiult to implement. I implemented the most simple way of doing anti-aliasing which is supersampling. The following picture shows the difference between un-aliased and aliased rendering:

To get a better impression on what anti-aliasing does, the following three pictures show the same image with no antialising, 2 times, 4 times and 16 times anti-aliasing:

Of course the changes are in the SVN. The username, as well as the password, is guest

By Christian | Posted in Development | Tagged java, ray tracer | Comments (1)

Raytracing: my first shot

November 18, 2009 – 10:27 pm

After revisiting the Google talk about splines and fractals I had the idea to do this in three-dimensional space by using quaternions instead of complex numbers. It turned out that it wasn’t utterly difficult to render a simple three-dimensional Sierpinski gasket (or Menger-Sponge) using PovRay. At least installing PovRay on my Mac took more time than writting the script.

While fuzzing around with PovRay a crazy idea came to my mind: why not write my own ray tracer. Of course that would only be the simplest possible as I only wanted to get a rough understanding on how this stuff works. After doing a bit of research it turned out that it shouldn’t be a too difficult task. Hey, this is one of the excercises in every “Computer graphics basics” lecture.

Three hours later I had a rough shot, but somehow my maths for calculating the rays was wrong. The day after, a friend of mine and myself went to a maths professor at my University and asked him if he could have a quick look at the formulas. His explanations were (as always) very insightful and simply brilliant. With the ideas he gave us we went on to get the missing bits done. And 4 more hours later we had a working ray tracer. (The sierpinski gasket was not rendered by my ray tracer, but I can’t figure out how to exclude images from the Wordpress gallery).

Of course after 7 hours of work the ray tracer is far from being perfect. There are a few neat features missing (which might follow) such as shadows, reflection and radiosity (which would really be a big task). Also the maths concerning the projection plane are not totaly right. We should rather introduce a coordinate system transformation to get this done than hacking things together as it is right now. All in all it was a lot of fun to write that thing. If you want to have a look at the source code, check it out here (username: guest, password: guest).

By Christian | Posted in Development, Maths | Tagged java, ray tracer | Comments (0)

Note to myself: tail recursion in Haskell does not allow me to stop thinking

November 6, 2009 – 9:04 pm

We’ve propably all heard that tail recursion is the way to go. That’s true, but as I’ve learned today applying this principle does not free you from thinking about your code.
The task was to implement the Josephus game. That’s particularly straight forward in imperative languages such as Java:

1
2
3
4
5
6
7
8
9
10
11
12
13

private int josephus(int amountOfSoldiers, int interval) {
List<Integer> soldiers = new LinkedList<Integer>();
for(int i = 1; i <= amountOfSoldiers; i++) soldiers.add(i);

int index = 1;
while(soldiers.size() != 1) {
for(Iterator<Integer> iter = soldiers.iterator(); iter.hasNext() && iter.next() != null; ) {
if(index++ % 3 == 0) iter.remove();
}
}

return soldiers.get(0);
}

But Java is not much of a challange, so lets give this a shot in Haskell:

1
2
3
4
5
6
7
8
9
10
11
12
13

josephus :: [Int] -> Int
josephus [] = 0
josephus [x] = x
josephus l = josephus_ l 1 where
josephus_ [x] _ = x
josephus_ xs o = let
len = length xs
off = ((o + len) `mod` 3) in
josephus_ (dropByInject o xs) off

dropByInject _ [] = []
dropByInject m (x:xs) | m `mod` 3 == 0 = dropByInject (m + 1) xs
| otherwise = x:(dropByInject (m + 1) xs)

Obviously the dropByInject function is not tail recursive. When we call the following program

1	main = putStrLn (show [josephus [1..l] \| l <- [1..2000]])

which computes the “Josephus number” from 1 to 2000 soldiers, takes roughly 0.792s.

So I did a second shot which is tail recursive:

1
2
3

dropByInject r _ [] = r
dropByInject r m (x:xs) | m `mod` 3 == 0 = dropByInjectAp r (m + 1) xs
| otherwise = dropByInjectAp (r ++ [x]) (m + 1) xs

. And here is where I stopped thinking – which immediately became clear to me as the same task as above takes 23.791s. Wow, that’s not really better than the 0.792s of the not-tail-recursive version. So why is that:
if we take a look at how the list is constructed in the otherwise part of the dropByInject function we see that the x is appended to the end of the list via

1	(r ++ [x])

. And that was the mistake – lists in Haskell are linked lists and appending to linked lists takes $\mathcal{O}(n)$ as we have to find the end of the list first. Upps

Alright, let’s go for a third shot:

1
2
3

dropByInject r _ [] = reverse r
dropByInject r m (x:xs) | m `mod` 3 == 0 = dropByInjectTr r (m + 1) xs
| otherwise = dropByInjectTr (x:r) (m + 1) xs

This version takes only 0.704s. That’s not lightyears of speed gain compared to the first version, but hey at least it’s tail recursive.

By Christian | Posted in Development | Tagged Haskell, recursion | Comments (0)

Yet another PDF utility

October 30, 2009 – 6:13 pm

Today I had the task to write join some PDF files together and creating an outline entry for each file in the new document. As it turned out that was not such a trivial task as it may sound. Merging PDF files is pretty straight forward. Pretty much every tool that has something with PDF in its name is capable of doing so. Unfortunately that’s not the case when it comes to the outline stuff. Even after hours of googling for a solution I didn’t find one. So there was only one way left: write it myself. And so I did (but rather quick and dirty) … the outcome is a neat little helper based on PDFBox. See the help below to get an idea of what it’s capable of:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

usage: pdfutils <tool> <args>
Available tools: merge help title author info dropoutline addoutline
type "pdfutils help <tool>" to get some help for <tool>

usage: pdfutils addoutline
-B <page=title> Add outline entry for page and title. The page can be
in the format "10.20" adding the bookmark to page 20 as
a sublevel to the bookmark for page 10 which must be
given beforehand. As of now it is not possible to add
subnodes to already existing bookmarks.
-f <file> The input file

usage: pdfutils author
-f <file> The file to modify
-v <value> The value to set

usage: pdfutils dropoutline
-f <file> The input file

usage: pdfutils info
-f <file> The input file

usage: pdfutils merge
-i,--input A whitespace seperated list of input files
-n,--no-outline If set no outline is computed - so the outline of the
first source document is used
-o,--output <arg> The output file

usage: pdfutils title
-f <file> The file to modify
-v <value> The value to set

So in case you wanted to merge a bunch of PDF files in the current directory and have a neat outline afterwards, you could issue this command:

1	java -jar pdfutils_0.1.1.jar merge -o ../merged.pdf -i `ls *.pdf`

You can download the binary (including all required libraries, so it’s ready to go) or check out the sources. The username and password for websvn is guest and the code is published under the terms of Apache License 2.0.

Note: Some software readers seam not to care about the outline generated by PDFBox … but e.g. the Sony PRS505 does.

By Christian | Posted in Gizmos | Tagged ebook, PDF, PRS505 | Comments (1)