I made it harder than it was. luckily I already had all the information I needed for part 2 to work immediately.
Solution 1
const std = @import("std");
//const input = @embedFile("./tiny3.inp");
//const input = @embedFile("./small.inp");
//const input = @embedFile("./small2.inp");
const input = @embedFile("./big.inp");
const dir_t = enum(usize) { north, east, south, west };
const obj_t = enum { empty, wall, start, end };
fn smallest(arr: [4]usize) usize {
var sm = arr[0];
for (arr[1..]) |e| {
if (e < sm) {
sm = e;
}
}
return sm;
}
const tile_t = struct {
obj: obj_t,
dist: usize,
nrot: usize,
score: [4]usize,
};
const maze_t = struct {
nrows: usize,
ncols: usize,
start: [2]usize,
end: [2]usize,
score: usize,
tiles: std.ArrayList(tile_t),
const Self = @This();
pub fn init(allocator: std.mem.Allocator) Self {
const maze = Self{
.nrows = undefined,
.ncols = undefined,
.start = undefined,
.end = undefined,
.score = undefined,
.tiles = std.ArrayList(tile_t).init(allocator),
};
return maze;
}
pub fn deinit(self: *Self) void {
self.nrows = undefined;
self.ncols = undefined;
self.start = undefined;
self.end = undefined;
self.score = undefined;
_ = self.tiles.deinit();
}
pub fn get_idx(self: Self, irow: usize, icol: usize) usize {
return irow * self.ncols + icol;
}
pub fn get_coord(self: Self, idx: usize) [2]usize {
const icol = @mod(idx, self.ncols);
const irow = @divExact(idx - icol, self.ncols);
return [2]usize{ irow, icol };
}
pub fn read(self: *Self, inputstr: []const u8) !void {
var lines = std.mem.tokenizeScalar(u8, inputstr, '\n');
var irow: usize = 0;
self.nrows = 0;
while (lines.next()) |line| : (irow += 1) {
self.nrows += 1;
var object: obj_t = undefined;
for (line, 0..) |char, icol| {
const dist: usize = 0;
const nrot: usize = 0;
const score = [4]usize{ std.math.maxInt(usize), std.math.maxInt(usize), std.math.maxInt(usize), std.math.maxInt(usize) };
switch (char) {
'S' => {
self.start = [2]usize{ irow, icol };
object = .start;
},
'E' => {
self.end = [2]usize{ irow, icol };
object = .end;
},
'#' => {
object = .wall;
},
'.' => {
object = .empty;
},
else => {
unreachable;
},
}
try self.tiles.append(tile_t{ .obj = object, .dist = dist, .nrot = nrot, .score = score });
}
}
self.ncols = self.tiles.items.len / self.nrows;
}
pub fn print(self: Self) void {
std.debug.print("\n", .{});
std.debug.print("{d}x{d}\n", .{ self.nrows, self.ncols });
for (0..self.nrows) |irow| {
for (0..self.ncols) |icol| {
const pos = self.get_idx(irow, icol);
var char: u8 = undefined;
switch (self.tiles.items[pos].obj) {
.wall => char = '#',
.start => char = 'S',
.end => char = 'E',
.empty => {
char = switch (smallest(self.tiles.items[pos].score)) {
18446744073709551615 => ' ',
else => '.',
};
},
}
std.debug.print("{c}", .{char});
}
std.debug.print("\n", .{});
}
}
pub fn print_curr(self: Self, crow: usize, ccol: usize) void {
std.debug.print("\n", .{});
std.debug.print("{d}x{d}\n", .{ self.nrows, self.ncols });
for (0..self.nrows) |irow| {
for (0..self.ncols) |icol| {
const pos = self.get_idx(irow, icol);
var char: u8 = undefined;
if (irow == crow and icol == ccol) {
char = 'O';
} else {
switch (self.tiles.items[pos].obj) {
.wall => char = '#',
.start => char = 'S',
.end => char = 'E',
.empty => {
char = switch (smallest(self.tiles.items[pos].score)) {
18446744073709551615 => ' ',
else => '.',
};
},
}
}
std.debug.print("{c}", .{char});
}
std.debug.print("\n", .{});
}
}
fn flood(self: *Self, irow: usize, icol: usize, dir: dir_t, nrot: usize, dist: usize) void {
const idx = self.get_idx(irow, icol);
if (self.tiles.items[idx].obj == .wall) {
return;
}
const myScore = 1000 * nrot + dist;
//self.print_curr(irow, icol);
// already visited this field in this direction and it was better.
if (myScore > self.tiles.items[idx].score[@intFromEnum(dir)]) {
return;
}
// already visited this field in the opposite direction and it was better
const redScore = if (myScore > 2002) myScore - 2002 else 0;
if (redScore > self.tiles.items[idx].score[@mod(@intFromEnum(dir) + 2, 4)]) {
return;
}
self.tiles.items[idx].nrot = nrot;
self.tiles.items[idx].dist = dist;
self.tiles.items[idx].score[@intFromEnum(dir)] = myScore;
if (irow == self.end[0] and icol == self.end[1]) {
return;
}
switch (dir) {
.east => {
self.flood(irow, icol + 1, .east, nrot, dist + 1);
self.flood(irow - 1, icol, .north, nrot + 1, dist + 1);
self.flood(irow + 1, icol, .south, nrot + 1, dist + 1);
},
.west => {
self.flood(irow, icol - 1, .west, nrot, dist + 1);
self.flood(irow - 1, icol, .north, nrot + 1, dist + 1);
self.flood(irow + 1, icol, .south, nrot + 1, dist + 1);
},
.north => {
self.flood(irow - 1, icol, .north, nrot, dist + 1);
self.flood(irow, icol + 1, .east, nrot + 1, dist + 1);
self.flood(irow, icol - 1, .west, nrot + 1, dist + 1);
},
.south => {
self.flood(irow + 1, icol, .south, nrot, dist + 1);
self.flood(irow, icol + 1, .east, nrot + 1, dist + 1);
self.flood(irow, icol - 1, .west, nrot + 1, dist + 1);
},
}
}
pub fn solve(self: *Self) void {
self.flood(self.start[0], self.start[1], .east, 0, 0);
const idx_end = self.get_idx(self.end[0], self.end[1]);
self.score = self.tiles.items[idx_end].dist + 1000 * self.tiles.items[idx_end].nrot;
self.score = smallest(self.tiles.items[idx_end].score);
}
};
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var maze = maze_t.init(allocator);
defer _ = maze.deinit();
try maze.read(input);
//maze.print();
maze.solve();
//maze.print();
std.debug.print("Score of best path: {d}\n", .{maze.score});
}
Solution 2
const std = @import("std");
//const input = @embedFile("./tiny3.inp");
//const input = @embedFile("./small.inp");
//const input = @embedFile("./small2.inp");
const input = @embedFile("./big.inp");
const dir_t = enum(usize) { north, east, south, west };
const obj_t = enum { empty, wall, start, end };
fn smallest(arr: [4]usize) usize {
var sm = arr[0];
for (arr[1..]) |e| {
if (e < sm) {
sm = e;
}
}
return sm;
}
const tile_t = struct {
obj: obj_t,
dist: usize,
nrot: usize,
used: bool,
score: [4]usize,
};
const maze_t = struct {
nrows: usize,
ncols: usize,
start: [2]usize,
end: [2]usize,
score: usize,
tiles: std.ArrayList(tile_t),
path: std.ArrayList([2]usize),
const Self = @This();
pub fn init(allocator: std.mem.Allocator) Self {
const maze = Self{
.nrows = undefined,
.ncols = undefined,
.start = undefined,
.end = undefined,
.score = undefined,
.tiles = std.ArrayList(tile_t).init(allocator),
.path = std.ArrayList([2]usize).init(allocator),
};
return maze;
}
pub fn deinit(self: *Self) void {
self.nrows = undefined;
self.ncols = undefined;
self.start = undefined;
self.end = undefined;
self.score = undefined;
_ = self.tiles.deinit();
_ = self.path.deinit();
}
pub fn get_idx(self: Self, irow: usize, icol: usize) usize {
return irow * self.ncols + icol;
}
pub fn get_coord(self: Self, idx: usize) [2]usize {
const icol = @mod(idx, self.ncols);
const irow = @divExact(idx - icol, self.ncols);
return [2]usize{ irow, icol };
}
pub fn read(self: *Self, inputstr: []const u8) !void {
var lines = std.mem.tokenizeScalar(u8, inputstr, '\n');
var irow: usize = 0;
self.nrows = 0;
while (lines.next()) |line| : (irow += 1) {
self.nrows += 1;
var object: obj_t = undefined;
for (line, 0..) |char, icol| {
const dist: usize = 0;
const nrot: usize = 0;
const score = [4]usize{ std.math.maxInt(usize), std.math.maxInt(usize), std.math.maxInt(usize), std.math.maxInt(usize) };
switch (char) {
'S' => {
self.start = [2]usize{ irow, icol };
object = .start;
},
'E' => {
self.end = [2]usize{ irow, icol };
object = .end;
},
'#' => {
object = .wall;
},
'.' => {
object = .empty;
},
else => {
unreachable;
},
}
try self.tiles.append(tile_t{ .obj = object, .dist = dist, .nrot = nrot, .score = score, .used = false });
}
}
self.ncols = self.tiles.items.len / self.nrows;
}
pub fn print(self: Self) void {
std.debug.print("\n", .{});
std.debug.print("{d}x{d}\n", .{ self.nrows, self.ncols });
for (0..self.nrows) |irow| {
for (0..self.ncols) |icol| {
const pos = self.get_idx(irow, icol);
var char: u8 = undefined;
switch (self.tiles.items[pos].obj) {
.wall => char = '#',
.start => char = 'S',
.end => char = 'E',
// .empty => char = 'X',
.empty => char = if (self.tiles.items[pos].used) 'O' else ' ',
}
//if (char == 'X') {
// const sc = smallest(self.tiles.items[pos].score);
// if (self.tiles.items[pos].score[0] == sc) {
// char = '^';
// }
// if (self.tiles.items[pos].score[1] == sc) {
// char = '>';
// }
// if (self.tiles.items[pos].score[2] == sc) {
// char = 'v';
// }
// if (self.tiles.items[pos].score[3] == sc) {
// char = '<';
// }
//}
std.debug.print("{c}", .{char});
}
std.debug.print("\n", .{});
}
}
pub fn print_curr(self: Self, crow: usize, ccol: usize) void {
std.debug.print("\n", .{});
std.debug.print("{d}x{d}\n", .{ self.nrows, self.ncols });
for (0..self.nrows) |irow| {
for (0..self.ncols) |icol| {
const pos = self.get_idx(irow, icol);
var char: u8 = undefined;
if (irow == crow and icol == ccol) {
char = 'O';
} else {
switch (self.tiles.items[pos].obj) {
.wall => char = '#',
.start => char = 'S',
.end => char = 'E',
.empty => {
char = switch (smallest(self.tiles.items[pos].score)) {
18446744073709551615 => ' ',
else => '.',
};
},
}
}
std.debug.print("{c}", .{char});
}
std.debug.print("\n", .{});
}
}
fn flood(self: *Self, irow: usize, icol: usize, dir: dir_t, nrot: usize, dist: usize) void {
const idx = self.get_idx(irow, icol);
if (self.tiles.items[idx].obj == .wall) {
return;
}
const myScore = 1000 * nrot + dist;
//self.print_curr(irow, icol);
// already visited this field in this direction and it was better.
if (myScore > self.tiles.items[idx].score[@intFromEnum(dir)]) {
return;
}
// already visited this field in the opposite direction and it was better
const redScore = if (myScore > 2002) myScore - 2002 else 0;
if (redScore > self.tiles.items[idx].score[@mod(@intFromEnum(dir) + 2, 4)]) {
return;
}
self.tiles.items[idx].nrot = nrot;
self.tiles.items[idx].dist = dist;
self.tiles.items[idx].score[@intFromEnum(dir)] = myScore;
if (irow == self.end[0] and icol == self.end[1]) {
return;
}
switch (dir) {
.east => {
self.flood(irow, icol + 1, .east, nrot, dist + 1);
self.flood(irow - 1, icol, .north, nrot + 1, dist + 1);
self.flood(irow + 1, icol, .south, nrot + 1, dist + 1);
},
.west => {
self.flood(irow, icol - 1, .west, nrot, dist + 1);
self.flood(irow - 1, icol, .north, nrot + 1, dist + 1);
self.flood(irow + 1, icol, .south, nrot + 1, dist + 1);
},
.north => {
self.flood(irow - 1, icol, .north, nrot, dist + 1);
self.flood(irow, icol + 1, .east, nrot + 1, dist + 1);
self.flood(irow, icol - 1, .west, nrot + 1, dist + 1);
},
.south => {
self.flood(irow + 1, icol, .south, nrot, dist + 1);
self.flood(irow, icol + 1, .east, nrot + 1, dist + 1);
self.flood(irow, icol - 1, .west, nrot + 1, dist + 1);
},
}
}
pub fn solve(self: *Self) void {
self.flood(self.start[0], self.start[1], .east, 0, 0);
const idx_end = self.get_idx(self.end[0], self.end[1]);
self.score = smallest(self.tiles.items[idx_end].score);
}
fn score_works(prev_score: usize, my_score: usize) bool {
if ((prev_score >= 1 and my_score == prev_score - 1) or (prev_score >= 1001 and my_score == prev_score - 1001)) {
return true;
}
return false;
}
fn mark_path_step(self: *Self, irow: usize, icol: usize, prev_score: usize) void {
const idx = self.get_idx(irow, icol);
self.tiles.items[idx].used = true;
if (self.tiles.items[idx].obj == .start) {
return;
}
const my_score = self.tiles.items[idx].score;
//self.print();
//std.debug.print("({d},{d}) => {any}\n", .{ irow, icol, self.tiles.items[idx].score });
//std.debug.print("trying south {d} {d} {d}\n", .{ prev_score, my_score[0], self.tiles.items[self.get_idx(irow + 1, icol)].score[0] });
if (score_works(prev_score, my_score[0])) {
//std.debug.print("going south\n", .{});
self.mark_path_step(irow + 1, icol, my_score[0]);
}
//self.print();
//std.debug.print("({d},{d}) => {any}\n", .{ irow, icol, self.tiles.items[idx].score });
//std.debug.print("trying west {d} {d} {d} \n", .{ prev_score, my_score[1], self.tiles.items[self.get_idx(irow, icol - 1)].score[1] });
if (score_works(prev_score, my_score[1])) {
//std.debug.print("going west\n", .{});
self.mark_path_step(irow, icol - 1, my_score[1]);
}
//self.print();
//std.debug.print("({d},{d}) => {any}\n", .{ irow, icol, self.tiles.items[idx].score });
//std.debug.print("trying north {d} {d} {d}\n", .{ prev_score, my_score[2], self.tiles.items[self.get_idx(irow - 1, icol)].score[2] });
if (score_works(prev_score, my_score[2])) {
//std.debug.print("going north\n", .{});
self.mark_path_step(irow - 1, icol, my_score[2]);
}
//self.print();
//std.debug.print("({d},{d}) => {any}\n", .{ irow, icol, self.tiles.items[idx].score });
//std.debug.print("trying east {d} {d} {d}\n", .{ prev_score, my_score[3], self.tiles.items[self.get_idx(irow, icol + 1)].score[3] });
if (score_works(prev_score, my_score[3])) {
//std.debug.print("going east\n", .{});
self.mark_path_step(irow, icol + 1, my_score[3]);
}
}
pub fn mark_path(self: *Self) void {
const idx_end = self.get_idx(self.end[0], self.end[1]);
//std.debug.print("({d},{d}) => {any}\n", .{ self.end[0], self.end[1], self.tiles.items[idx_end].score });
self.tiles.items[idx_end].used = true;
if (self.tiles.items[idx_end].score[0] == self.score) {
self.mark_path_step(self.end[0] + 1, self.end[1], self.score);
}
if (self.tiles.items[idx_end].score[1] == self.score) {
self.mark_path_step(self.end[0], self.end[1] - 1, self.score);
}
if (self.tiles.items[idx_end].score[2] == self.score) {
self.mark_path_step(self.end[0], self.end[1] + 1, self.score);
}
if (self.tiles.items[idx_end].score[3] == self.score) {
self.mark_path_step(self.end[0] - 1, self.end[1], self.score);
}
}
pub fn count_best_tiles(self: Self) usize {
var cnt: usize = 0;
for (self.tiles.items) |tile| {
if (tile.used) {
cnt += 1;
}
}
return cnt;
}
};
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var maze = maze_t.init(allocator);
defer _ = maze.deinit();
try maze.read(input);
//maze.print();
maze.solve();
maze.mark_path();
//maze.print();
std.debug.print("Number of fields on best paths: {d}\n", .{maze.count_best_tiles()});
}