Project Euler Problem #83

P083.java

package euler;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Stream;

public class P083 {

    private static class Node {
        private final int row;
        private final int col;
        private final int val;
        private Node prev;
        private int sum;

        Node(int row, int col, int val) {
            this.row = row;
            this.col = col;
            this.val = val;
        }

        boolean isNeighbor(Node that) {
            if (that == null) return false;
            int dr = Math.abs(this.row - that.row);
            int dc = Math.abs(this.col - that.col);
            return dr + dc == 1;
        }

        @Override
        public String toString() {
            return String.format("(%d, %d)", row, col);
        }

        @Override
        public boolean equals(Object other) {
            if (other == this) return true;
            if (other == null) return false;
            if (other.getClass() != this.getClass()) return false;

            Node node = (Node) other;
            return this.row == node.row && this.col == node.col;
        }
    }

    private static class NodeMatrix {
        private static int weight = 0;
        private final int[][] data;
        private final int[][] sums;

        NodeMatrix(int[][] data) {
            this.data = data;
            this.sums = new int[data.length][data.length];
        }

        Node node(int i, int j) {
            return new Node(i, j, data[i][j]);
        }

        int getSum(int i, int j) {
            return sums[i][j];
        }

        void setSum(int i, int j, int sum) {
            sums[i][j] = sum;
        }

        int dim() {
            return data.length;
        }

        boolean isDest(Node node) {
            return node.row == dim() - 1 && node.col == dim() - 1;
        }

        int manhattan(Node node) {
            return 2 * data.length - node.row - node.col;
        }

        private List<Node> neighbors(Node n) {
            List<Node> neighbors = new ArrayList<>();
            if (n.row > 0) {
                int r = n.row - 1;
                int c = n.col;
                neighbors.add(node(r, c));
            }
            if (n.col > 0) {
                int r = n.row;
                int c = n.col - 1;
                neighbors.add(node(r, c));
            }
            if (n.row < dim() - 1) {
                int r = n.row + 1;
                int c = n.col;
                neighbors.add(node(r, c));
            }
            if (n.col < dim() - 1) {
                int r = n.row;
                int c = n.col + 1;
                neighbors.add(node(r, c));
            }
            return neighbors;
        }

        Comparator<Node> comparator = (o1, o2) -> o1.sum + weight * manhattan(o1) - (o2.sum + weight * manhattan(o2));
    }

    private NodeMatrix matrix;
    private PriorityQueue<Node> minQueue;

    public P083(int[][] data) {
        this.matrix = new NodeMatrix(data);
        this.minQueue = new PriorityQueue<>(matrix.comparator);
    }


    public int solve() {
        long step = 0;
        Node start = matrix.node(0, 0);
        start.sum = start.val;
        matrix.setSum(0, 0, start.val);
        minQueue.add(start);

        while (true) {
            Node current = minQueue.poll();
//            System.out.printf("steps=%d, qsize=%d, %s\n", ++step, minQueue.size(), current);

            if (matrix.isDest(current)) {
                printPath(current);
                return current.sum;
            }

            Node prev1 = current.prev;
            Node prev2 = prev1 != null ? prev1.prev : null;
            for (Node neighbor : matrix.neighbors(current)) {
                if (neighbor.equals(prev1)) continue;
                if (neighbor.isNeighbor(prev2)) continue;;
                neighbor.prev = current;
                neighbor.sum = current.sum + neighbor.val;

                if (matrix.getSum(neighbor.row, neighbor.col) == 0 || neighbor.sum < matrix.getSum(neighbor.row, neighbor.col)) {
                    matrix.setSum(neighbor.row, neighbor.col, neighbor.sum);
                    minQueue.add(neighbor);
                }
            }
        }
    }

    private void printPath(Node node) {
        Node n;
        List<Node> ls = new ArrayList<>();
        for (n = node; n.prev != null; n = n.prev) {
            ls.add(n);
        }
        ls.add(n);
        Collections.reverse(ls);
        System.out.println(ls);
        int s = ls.stream().mapToInt(nd -> nd.val).sum();
        System.out.println("sum=" + s);
    }

    private static int[][] readData() throws IOException {
        try (BufferedReader r = new BufferedReader(new FileReader("JavaTest/src/euler/matrix.txt"))) {
            int[][] data = r.lines()
                .map(line -> Stream.of(line.split(","))
                    .mapToInt(Integer::parseInt).toArray()
                ).toArray(int[][]::new);
            return data;
        }
//        return new int[][]{
//            {131, 673, 234, 103, 18},
//            {201, 96, 342, 965, 150},
//            {630, 803, 746, 422, 111},
//            {537, 699, 497, 121, 956},
//            {805, 732, 524, 37, 331}
//        };
    }

    private static void print(int[][] data) {
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data[i].length; j++) {
                System.out.printf("%5d ", data[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) throws IOException {
        P083 problem = new P083(readData());
//        print(problem.matrix.data);
        int sol = problem.solve();
        System.out.println(sol);
    }
}