Monday, April 5, 2010

10038 Jolly Jumper Solution

Here's my Jolly Jumper solution. It was accepted by UVA online judge. It may not be the best solution but at least its readable.

My Algorithm is designed to fail quickly. As it calculates each sequence number it checks against three simple rules

  1. The sequence(n) number cannot be 0
  2. The sequence(n) number cannot be equal or greater than the input(numbers in my code). If there are 4 numbers then the sequence should contain the numbers 1,2,3
  3. There cannot be duplicates.
My solutions took 0.304 seconds to execute. Compared to the best, my solution is rather slow. The best solutions were written in C++ and ANSI C. Their run time was a flat 0. It would be rather interesting to see if  I could get an even faster run time. The only problem is that I'm using Java which is going to be slow from the get go. On the bright side I am one of 9546 users that have solved this problem.

My solution came as a result of refactoring. My original solution did not fail early. Instead it gathered all sequence numbers, sorted a list and then checked that it had the correct numbers. My original solution had an execution time of about 0.36 well my new solution executed at about 0.304. Although my solution isn't the fastest's I do enjoy its readability.

The problem can be found here

Sunday, April 4, 2010

Algorithms Book Club

Well the book club I am a member of is at it again. This time our book club is tackling Algorithms in all its fun and glory... The book we are reading is "The Algorithm Design Manual" by Stenven S. Skiena.

Our first session covered the wonders of big O notation (asymptotic Notation). I'm happy to say that complexity is growing linearly at O(n)... but some days I swear its like O(n!).

Our second session covered big O again...

Our third session uncovered the mysteries of data structures.

Our next session is perhaps more ambitious. We are going to step into the arena and knockout a few algorithms.

The Arena: http://uva.onlinejudge.org/

My Weapon of Choice: Java

The Problems:

Jolly Jumpers (Solved)
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&categor
y=12&page=show_problem&problem=979


Where's Waldorf?(Unsolved)
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&categor
y=12&page=show_problem&problem=951


Crypt Kicker(Unsolved)
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&categor
y=10&page=show_problem&problem=784


Crypt Kicker II(Unsolved)
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&categor
y=31&page=show_problem&problem=791