const std = @import("std");
const path = "../data/day15/input.txt";
const RetType = u12;
const exp_size = 5;
const grid_cols = 100;
const grid_rows = 100;
const GridValue = u4;
const Grid = [exp_size * grid_rows][exp_size * grid_cols]GridValue;
const Distance = [exp_size * grid_rows][exp_size * grid_cols]RetType;
const Point = struct {
row: usize,
col: usize,
cost: RetType,
};
fn lowerThan(context: void, a: Point, b: Point) std.math.Order {
_ = context;
return std.math.order(a.cost, b.cost);
}
const Queue = std.PriorityQueue(Point, void, lowerThan);
const directions = [4][2]i2{
.{ 0, 1 },
.{ 0, -1 },
.{ 1, 0 },
.{ -1, 0 },
};
fn parseInput() anyerror!Grid {
const input = @embedFile(path);
var lines = std.mem.tokenize(u8, input, "\n");
var ret: Grid = undefined;
var row: usize = 0;
while (lines.next()) |line| : (row += 1) {
for (line) |_, col| {
const curr =
try std.fmt.parseUnsigned(GridValue, line[col .. col + 1], 10);
for ([_]usize{ 0, 1, 2, 3, 4 }) |x| {
for ([_]usize{ 0, 1, 2, 3, 4 }) |y| {
ret[row + y * grid_rows][col + x * grid_cols] = @intCast(GridValue, (curr + x + y) % 10) + @intCast(GridValue, (curr + x + y) / 10);
}
}
}
}
// for (ret) |line| {
// std.debug.print("\n", .{});
// for (line) |item, idx| {
// if (idx % 10 == 0) {
// std.debug.print("|", .{});
// }
// std.debug.print("{d}", .{item});
// }
// }
return ret;
}
pub fn second() anyerror!RetType {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
var g = try parseInput();
var distance = [_][exp_size * grid_cols]RetType{[_]RetType{~@as(RetType, 0)} ** (exp_size * grid_cols)} ** (exp_size * grid_rows);
distance[0][0] = 0;
var queue = Queue.init(allocator, {});
defer queue.deinit();
// add starting item to the queue
try queue.add(Point{ .row = 0, .col = 0, .cost = 0 });
while (true) {
var ret = try dijkstra(&g, &distance, &queue);
if (ret != null) return ret.?;
// XXX: distance grid is not finalized!
}
unreachable;
}
fn dijkstra(grid: *Grid, dist: *Distance, queue: *Queue) !?RetType {
const curr = queue.remove();
// std.debug.print("D: {d} {d} -> {d}\n", .{curr.row, curr.col, curr.cost});
if (curr.row == (exp_size * grid_rows - 1) and (curr.col == exp_size * grid_cols - 1)) return curr.cost;
for (directions) |dir| {
const diffrow = @intCast(isize, curr.row) + dir[0];
if (diffrow < 0 or diffrow >= exp_size * grid_rows) continue;
const dr = @intCast(usize, diffrow);
const diffcol = @intCast(isize, curr.col) + dir[1];
if (diffcol < 0 or diffcol >= exp_size * grid_cols) continue;
const dc = @intCast(usize, diffcol);
const d = dist[curr.row][curr.col] +
grid[dr][dc];
if (d < dist[dr][dc]) {
dist[dr][dc] = d;
try queue.add(Point{ .row = dr, .col = dc, .cost = d });
// XXX: queue.update() needs == operator, which does not work with
// structs. We just grow the queue bigger and bigger...
// queue.update(Point{ .row = dr, .col = dc, .cost = dist[dr][dc] }, Point{ .row = dr, .col = dc, .cost = d }) catch |err| switch (err) {
// error.ElementNotFound => try queue.add(Point{ .row = dr, .col = dc, .cost = d }),
// else => return err,
// };
}
}
return null;
}
pub fn main() anyerror!void {
var timer = try std.time.Timer.start();
const ret = try second();
const t = timer.lap() / 1000;
try std.testing.expectEqual(@as(RetType, 2829), ret);
std.debug.print("Day 15b result: {d} \t\ttime: {d}µs\n", .{ ret, t });
}
test "day15a" {
try std.testing.expectEqual(@as(RetType, 2829), try second());
}