GDC Project Euler: problem 83 – Jaroslaw Pawlak

  • Difficulty: intermediate

  • Techniques used:

Array implementation of Dijkstra’s algorithm in Java.

  • How much time did it take:

Two days for implementation, 30ms for runtime.

  • First / final solution:

I have used two arrays: P with penalties and C’ with total cost of the cheapest path leading to the particular cell. I have also used PriorityQueue and my own version of comparable Point, but it might be a set as well. So in the pseudocode:

set C[0][0] = P[0][0]
add Point(0, 0) to the queue
while (queue is not empty) {

remove head H of the queue
for each of adjacent cell T {

if (T is out of the array) {

skip

} else if (C[T.x][T.y] == 0

|| C[H.x][H.y] + P[T.x][T.y] < C[T.x][T.y]) {

set C[T.x][T.y] = C[H.x][H.y] + P[T.x][T.y]
add T to the queue

}

}

}

The head in the priority queue is a cell with the cheapest cost of total path which did not have its adjacent cells considered yet.

  • Problems encountered:

I have used Dijkstra’s algorithm in the past but I forgot implementation details and was unable to implement it without reminding it and creating a design for this problem.

  • What I have learnt:

Firstly, I have overrated my skills and memory. Few months ago I have spent a lot of time on the research of path finding algorithms for the purpose of Software Engineering Group Project. I knew that Dijkstra’s algorithm is the best choice to solve this problem. I thought that I am able to implement it without any preparation, but eventually I had to read how exactly the algorithm works, because I forgot the steps.

Secondly, I tried few times to implement the algorithm without any sketch of its design. I have done it after I have finally drawn what it has to do.

About Jaroslaw Pawlak

I have done MSci in Computer Science at King’s College London and currently work as Software Engineer specialising in Java. I spend most of my time in front of computer improving my programming (and other) skills or just relaxing with a good game. I also train some sports but at the moment I am not a member of any club. I love cycling and volleyball, but I have also played a lot of football, tennis and trained martial arts.

Posted on July 8, 2011, in GDC Project Euler Challenge, Project Euler. Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: