Shortest Path

Euler83.d

import std.array;
import std.algorithm;
import std.conv;
import std.container;
import std.stdio;
import std.string;
import std.typecons;
import std.typetuple;


debug {
        const filename = "small_matrix.txt";
        const LEN = 5;
} else {
        const filename = "matrix.txt";
        const LEN = 80;
}
int[LEN][LEN] cost;
int[LEN][LEN] totals;

struct Record
{
        int[] vals;
        alias vals this;
        this (int[] items ...) {
                vals.length = 3;
                vals[] = items[];
        }

        int opCmp(ref const Record other) {
                return -vals[2] + other[2];
                //return vals[2] - other[2];
        }
}

// loads numbers into the cost matrix
void init(string filename)
{
        auto f = File(filename, "r");
        int row = 0;
        foreach (string line; lines(f)) {
                auto tokens = strip(line).split(",");
                foreach (col; 0 .. tokens.length) {
                        cost[row][col] = to!int(tokens[col]);
                        totals[row][col] = int.max;
                }
                ++row;
        }
}

auto reset_totals() {
        foreach (i; 0 .. LEN)
                foreach (j; 0 .. LEN)
                        totals[i][j] = int.max;
}

void print_array(int[LEN][LEN] m)
{
        writeln("\ncontents of ", m.stringof, ":");
        foreach (row; 0 .. LEN) {
                foreach (col; 0 .. LEN) {
                        writef("%5d ", m[row][col]);
                }
                writeln();
        }
        writeln();
}

int shortest_path(int startRow)
{
        //auto q = BinaryHeap!(Array!(Record), "a[2] < b[2]")();
        auto q = BinaryHeap!(Array!Record)();
        q.insert(Record(startRow, 0, cost[startRow][0]));
        while (q.length) {
                auto node = q.front;
                q.removeFront();
                debug writeln(node);
                auto i = node[0];
                auto j = node[1];

                totals[i][j] = node[2];

                // exit if we are at the end column
                if (j == LEN-1 && i == LEN-1) {
                        writeln("HERE ", node[2]);
                        return node[2];
                }

                // up
                if (i > 0) {
                        auto c = node[2] + cost[i-1][j];
                        if (c < totals[i-1][j])
                                q.insert(Record(i-1,j,c));
                }

                // right
                if (j < LEN-1) {
                        auto c = node[2] + cost[i][j+1];
                        if (c < totals[i][j+1])
                                q.insert(Record(i,j+1,c));
                }

                // down
                if (i < LEN-1) {
                        auto c = node[2] + cost[i+1][j];
                        if (c < totals[i+1][j])
                                q.insert(Record(i+1,j,c));
                }

                // left
                if (j > 0) {
                        auto c = node[2] + cost[i][j-1];
                        if (c < totals[i][j-1])
                                q.insert(Record(i,j-1,c));
                }
        }

        print_array(totals);
        assert(false);
}

void main()
{
        init(filename);
        auto minDist = shortest_path(0);
        writeln(minDist);
}