Skip to content
August 3, 2011 / oop123

Project Euler #83 – Java

You can see the problem here: Problem #83.

This is a simple question once I learned the Dijkstra’s algorithm (here’s wikipedia entry on it). The following codes are just an implementation of it, nothing too interesting. I used the same algorithm for question #82 too (just some small changes).

.main(String[] args) body:

final int SIZE = 80;
BufferedReader in = new BufferedReader(new FileReader("matrix.txt"));

//read in all the Nodes
Node[][] nodes = new Node[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
	String[] temp = in.readLine().split(",");
	for (int j = 0; j < SIZE; j++) {
		nodes[i][j] = new Node(Integer.parseInt(temp[j]), i, j);
	}
}

//initialize beginning
PriorityQueue<Node> notVisited = new PriorityQueue<Node>();
nodes[0][0].totalCost = nodes[0][0].travelCost;
notVisited.add(nodes[0][0]);

//algorithm
for (int i = 0; i < SIZE * SIZE - 1; i++) {
	Node node = notVisited.remove();
	node.visited = true;
	int row = node.row;
	int column = node.column;

	if (row == SIZE - 1 && column == SIZE - 1) break;
			
	if (row != 0) {
		update(node, nodes[row - 1][column], notVisited);
	}
	if (row != SIZE - 1) {
		update(node, nodes[row + 1][column], notVisited);
	}
	if (column != SIZE - 1) {
		update(node, nodes[row][column + 1], notVisited);
	}
	if (column != 0) {
		update(node, nodes[row][column - 1], notVisited);
	}
}

System.out.println(nodes[SIZE - 1][SIZE - 1].totalCost);

The Node class and one of the method for the algorithm.

static class Node implements Comparable<Node> {
	public int totalCost = Integer.MAX_VALUE;
	public boolean visited = false;

	public int travelCost;
	public int row;
	public int column;

	public Node(int cost, int row, int column) {
		travelCost = cost;
		this.row = row;
		this.column = column;
	}

	@Override
	public int compareTo(Node node) {
		if (node.totalCost > this.totalCost) {
			return -1;
		} else if (node.totalCost < this.totalCost) {
			return 1;
		}
		return 0;
	}
}

	
static void update(Node start, Node target, PriorityQueue<Node> queue) {
	start.visited = true;
	if (start.totalCost + target.travelCost < target.totalCost) {
		target.totalCost = start.totalCost + target.travelCost;
	}
	if (!target.visited && !queue.contains(target)) {
		queue.add(target);
	}
}

Runs in around 125 milliseconds on my computer. Nothing to this problem if you know (how to google for) path finding algorithms.

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: