# GDC Project Euler: problem 83 – Jaroslaw Pawlak

**Solved:**Problem 83

**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.

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

## Leave a comment

## Comments 0