Wednesday, July 30, 2008

An adventure to Trolltunga

A little over a year ago on reddit I saw a picture of a guy sitting on the edge of a rock. Not just any rock, but a clip of a rock that jets out of a vertical side of a mountain with a 350 meter drop. In the comments I discovered that the photo was of Trolltunga and is right near by in Odda Norway. Along with some other trolls from Trolltech we rented a car and drove to Odda for a little camping trip. The drive took around five hours, but we were in for a treat as the two lane highway though Norway is filled with fantastic scenery. The highway went through many of the mountains and once there was even a corkscrew tunnel. About half way through the trip you come out of a tunnel up in the top of the mountains dotted with snow. We stopped there and had a snack and took photos before continuing on.

To go with the mountains were numerous waterfalls.

Once we reached Odda we started our journey at the funicular railway which takes you up the side of the mountain which is 960 meters high with a 42 degree angle slope. According to our information the train was not running this summer and we would have to take a very steep path up the side of the mountain with full backpacks of camping gear. This exhausting start to our trip took a little over two hours.

But is was rewarding to reach the top and after a short rest ...

We continued up the path for another hour and finally made camp at a small clearing by a stream. Making dinner we had an absolutely fantastic view of the sunset over the snow topped mountains.

Being so far north the sun was only set for a few hours and in the morning after packing up camp we started off the trip to Trolltunga. On the way:

We walked through snow ...

We saw crystal clear ponds formed from melting snow ...

Saw many streams and waterfalls of every shape and size ...

and walked along the edge of the fjord.

After hiking through the mountains for about four hours we arrived at Trolltunga!

After taking many pictures and having lunch we headed back the way we came. Along the way we met someone who told us that the railway was in fact running, but only twice a day, at ten and six. We hurried back and four hours later arrived just in time for a ride down the insanely steep mountain. Riding in the front of the car it was like a roller coster ride where you go off the edge, except it took ten minutes to get down.

In all we walked around twelve kilometers over the two days. Originally this trip was all about seeing one little site, but it turned into a full adventure with all sorts of things to see at every step of the way. If you every get the opportunity to goto Trolltunga I would highly recommend it and it is without a doubt one of the highlight of my time in Europe.

Update: After submitting this to reddit and getting a bunch of votes I got a reddit header.

Saturday, July 12, 2008

Puzzles, Algorithms, and Qt::Concurrent

ITA software, a very cool Lisp company has for years put programming puzzles up on their website. Although the puzzles are fore hiring, they are still interesting and every once in a while I take a stab at one of them. One that recently caught my eye was this Sling Blade Runner puzzle. Although it is not in the archive of retired puzzles the problem itself is NP so I am not worried about showing off my answer as everyones solution will no doubt be different. I myself wrote several different solutions including a genetic algorithm and it was turning out fantastic results, but it was taking days to run v.s. the solution I present here which takes only minutes. Onto the actual problem:
"How long a chain of overlapping movie titles, like Sling Blade Runner, can you find?"

Use the following listing of movie titles: MOVIES.LST. Multi-word overlaps, as in "License to Kill a Mockingbird," are allowed. The same title may not be used more than once in a solution. Heuristic solutions that may not always produce the greatest number of titles will be accepted: seek a reasonable tradeoff of efficiency and optimality.

The problem description itself is a little vague leading to different goals depending upon how you read it. I choose to count the length by the number of movie titles that were used rather then words or character.

The first part of the problem is just reading in the data (the data file has its own issues for you to solve). Just from googling you will find several blogs where the discussion is mostly all about just reading in the data and running a depth search. This finds chain lengths of around 220 very quickly and while nice doesn't attack the real problem of the algorithm.

Once you read in the data at the core you end up with a list of nodes. Each node contains a list of nodes that it points to (and optionally a list of nodes that point to it). In other words your challenge if you accept it is to find the longest path in a directed graph.

My solution is built upon two algorithms. The first algorithm takes a starting node and produces a list of long paths. This algorithm wont guarantee the return of the longest path for a source node, but it will return very long paths in a very short amount of time. The pseudo-code version of the first algorithm in (called findLongChain in the code):

set1 is populated with a source node
while (set1 is not empty)
for each node in set1 all paths are followed.
If the path to the next node is more then the
currently known length to that node it is
stored and that node is added to set2.
set1 = set2
Using just this algorithm a respectable result can be found.

These long paths can be sent through a second algorithm which attempts to increase a chain length by finding local longer paths using a limited depth search. The pseudo-code version of the second algorithm (called expandChain in the code):

for (i = 0; i < chain.length; ++i)
Starting at i do a depth first search with a max depth
of X where X is a relatively small value to find a longer
path then the current chain[i] -> chain[i + X]. If a longer
path or subpath is found replace it in the chain.

Once the graph is constructed each node is passed to findLongChain which runs its best chain through expandChain before returning it. Once each node has been run through findLongChain the root node of the best chain is run through findLongChain, but this time all the best paths are run through expandChain to see if there is anything longer to find.

Because findLongChain is completely stand alone I was able to take code that was originally something like this:

Chain longChain;
for (int i = 0; i < todo.count(); ++i) {
Chain chain = findLongChain(todo[i]);
if (chain.count() > longChain.count())
longChain = chain;

and change it to use QtConcurrent's mapped reduce function to take fully advantage of my dual and quad core computers. The ease that QtConcurrent lets you scale your solution is fantastic.

Chain longChain = QtConcurrent::mappedReduced(todo, findLongChain, reduce);

While hacking on my solution I came across Jeremy Faller's website who also had been looking at the problem and was able to produce good results. (our approaches were completely different and we didn't see each others code until after we had finished). I took his longest length chain of 318 and ran it through my expandChain function to get a chain with length 326. A very respectable result found by the combination of our two programs.

The source code for my solution can be found on github in my sling blade runner repository.

After compiling run './sbr' and in around ten minutes on a quad core (subsequent runs last around five minutes). It will print out the best solution that was found which unless you change the code was a length of 312. If you uncomment the DEBUG define at the top of main.cpp the progress through the nodes will be printed as well as the best chain as it is found.

Hacking on this problem has been a lot of fun. Because there is no right solution I was free to try out all sorts of different approaches and spend time reading up on papers on graphs (the ones I didn't have to pay for). Spent some time messing around with Qt::concurrent and how fast I could get it to run. While working on the problem it was fun and motivating as I was able to pass everyone else's (the ones I found via Google) longest chain. The best score found by my code is 313, but I am more happy about the combined length of 326.

Wednesday, July 02, 2008

Cast off

After three weeks I got the cast off my broken hand on Friday and I can use both hands again. It has been an incredibly interesting experience. I took down notes of events throughout the three weeks that were interesting so I could write this blog entry once I could type again.

The word that can best describe the three weeks was "Slow". Everything, and I mean everything took twice to ten times as long to do. Being that I injured my primary hand my left hand was forced into service. I was surprised how quickly I was able to learn how to use my left hand to grasp and manipulate objects. After only a week and a half I was able to manage (not great, but doable) using a fork with my left hand, using scissors, brushing my teeth, and some basic writing. I found that the best way to write with my left hand was mirrored and in reverse which while cool becomes very cryptic if you are sloppy and I had to use a mirror a few times. I also very quickly learned how to use a right handed mouse in my left hand, in the same fashion mirroring the events that my hand should perform, not swapping the buttons.

Meanwhile with my right hand it felt like I was learning how to use it from scratch. After I got my cast even though I had three fingers "free", moving them or really doing anything would result in a lot of pain, and pain for the next five minutes at least. I very quickly learned not to use them. My first accomplishment note for my right hand was the ability to take off my glasses. The first few day my list was little things, but I soon I was able to master buttons and after a week I had acquired the "strength" to pull off my wedding ring on my other hand which is a bit loose to begin with. As the swelling died down I was able to bend the three fingers and finally start using them to type. The lack of strength in my right hand was something that would frustrate the hell out of me all day long as I would crash into my new limitation. I could place my hand on the object, but couldn't actually do anything. From not being able to open windows, doors, eating, typing, opening any packaging, to tying my shoes (My wonderfully supportive wife did that that the first week until I found out how to tie them with one hand) it was slow going. I had to re-learn and re-acquire the strength to do everything and anything with my right hand.

On the computer I very quickly learned a ton of application shortcuts and my bash profile now has dozens of two and three letter aliases (using mostly keys hit with my left hand). The first week or so I had very few compile errors as anything I wanted to code would take forever to type and I would sit there in my head running through the code I wanted to type at 100 miles an hour as I touch typed with my left hand and ten words a minute. Very quickly I learned to sit and think about any problem and explore as much of it in my head before coding anything because coding was just taking ten times as long. A real big plus was that I have a Kinesis Contoured keyboard. On the Kinesis keyboard the return key is on your right hand thumb and not your right hand pinky. After I got my cast off it took another three days before I could even get back the strength to push down the enter key with my pinky on my MacBook keyboard.

As you can see in the photos I got some art on my cast. With my new found situation of not being able to do much I found myself having the ability to spend lots of time drawing on my cast. All the art was drawn with my left hand. The first one I drew was the tail that wraps around and goes into my fist the first night I had the cast. Then a day or two later came the green raptor near my fingers. This was when I had to keep my hand above my heart to prevent lots-o-pain so it was drawn in that location so people could see it. The second one (week 2) I drew was the baby velociraptor scratching its head with its foot. This was when I was holding my hand mostly at a 90 degree angle across my chest so it was facing out. The second one is much better then the first as I understood the medium better. The second one was also drawn upside down from my perspective so everyone else could see it right side up. The last one I drew on the third week was the T-rex and this was when I had my arm at my side most of the time and so it was facing out. This one is definitely better then the other two.

Here is a photo shortly after I got my cast off. The whole right side of my hand is very swollen and green. Lots of pain and aggravation still, but at least the cast is off. An interesting aspect of breaking a bone in my right hand was that my fingernails on my right hand seemed to stop growing while I have cut my left hand fingernails twice. Not something the doctor tells you about. Almost a week after the cast came off and the green is still with me (not as much) so at this rate I figured that will stick around for a month or so and I was told I have three months until it fully heals. On my palm it is a big green circle in the middle which when pressed hurts like hell. Yesterday I tried to kill a bug that was flying around with my hands... it was a really stupid idea. As you can see I can type again and life for the most part is returning to normal. While setting the bone shifted so I no longer have a knuckle and my pink angles slightly to my ring finger, but nothing serious, really just cosmetic.

This experience has been a very interesting one. I was surprised just how much I was able to do with my left hand when given no other option and the process of relearning how to use my right hand was also a bit of an eye opener as I struggled to do the most basic tasks. But this is definitely something I hope never to repeat.

Popular Posts