//! This test solves first part of https://adventofcode.com/2021/day/23
const std = @import("std");
const math = std.math;
const Str = []const u8;
const Amphipod = enum {
A,
B,
C,
D,
};
const HALLWAY_LENGTH = 7;
const SIDEROOMS = 4;
const SIDEROOM_DEPTH = 2;
const PathType = u4;
const State = struct {
hallway: [HALLWAY_LENGTH]?Amphipod = .{null} ** HALLWAY_LENGTH,
rooms: [SIDEROOMS][SIDEROOM_DEPTH]?Amphipod,
pub fn print(self: @This()) []u8 {
const blank =
\\#############
\\#...........#
\\###.#.#.#.###
\\ #.#.#.#.#
\\ #########
;
var buffer: [100]u8 = undefined;
var mod: []u8 = buffer[0..blank.len];
std.mem.copy(u8, mod, blank);
for (self.hallway, 0..) |amp, idx| {
if (amp != null) {
const i: usize = switch (idx) {
0 => 14 + 1,
1 => 14 + 2,
2 => 14 + 4,
3 => 14 + 6,
4 => 14 + 8,
5 => 14 + 10,
6 => 14 + 11,
else => unreachable,
};
const a: u8 = switch (amp.?) {
.A => 'A',
.B => 'B',
.C => 'C',
.D => 'D',
};
mod[i] = a;
}
}
for (self.rooms, 0..) |room, rid| {
for (room, 0..) |amp, aid| {
if (amp != null) {
const a: u8 = switch (amp.?) {
.A => 'A',
.B => 'B',
.C => 'C',
.D => 'D',
};
mod[14 + 14 + rid * 2 + 3 + 14 * aid] = a;
}
}
}
return mod;
}
fn sideRoomDone(self: @This(), room: usize) bool {
std.debug.assert(room < SIDEROOMS);
for (self.rooms[room]) |amp| {
if (amp == null or amp != @as(Amphipod, @enumFromInt(room))) return false;
}
return true;
}
fn sideRoomFreeSpace(self: @This(), room: usize) ?u2 {
var ret: u2 = 0;
std.debug.assert(room < SIDEROOMS);
for (self.rooms[room]) |amp| {
if (amp == null) {
ret += 1;
} else if (amp != @as(Amphipod, @enumFromInt(room))) {
return null;
}
}
std.debug.assert(ret <= SIDEROOM_DEPTH);
return ret;
}
fn checkSideRoom(self: @This()) ?StateQueue {
for (self.rooms, 0..) |_, idx| {
const free = self.sideRoomFreeSpace(idx) orelse continue;
if (free == 0) continue;
// std.debug.print("FREE: {d}\n", .{free});
for (self.hallway, 0..) |amp, hwidx| {
if (amp == @as(Amphipod, @enumFromInt(idx))) {
const steps = (self.checkHWtoRoom(hwidx, idx) orelse continue) + free;
var ret: StateQueue = undefined;
ret.cost = (std.math.powi(usize, 10, @intFromEnum(amp.?)) catch unreachable) * steps;
ret.state = self;
ret.state.hallway[hwidx] = null;
ret.state.rooms[idx][free - 1] = amp;
return ret;
}
}
for (self.rooms, 0..) |other, oidx| {
if (idx == oidx) continue;
var pos: PathType = 0;
for (other) |amp| {
if (amp == null) {
pos += 1;
continue;
}
if (amp == @as(Amphipod, @enumFromInt(idx))) {
var steps: PathType = undefined;
if (idx < oidx) { // moving left
const hwidx = oidx + 2;
// std.debug.print("L->R from: {d} to: {d}\n", .{ hwidx, idx });
steps = (self.checkHWtoRoom(hwidx, idx) orelse break) + free + pos;
} else { // moving right
const hwidx = oidx + 1;
// std.debug.print("R->L from: {d} to: {d}\n", .{ hwidx, idx });
steps = (self.checkHWtoRoom(hwidx, idx) orelse break) + free + pos;
}
// we can move amp to his sideroom
var ret: StateQueue = undefined;
ret.cost = (std.math.powi(usize, 10, @intFromEnum(amp.?)) catch unreachable) * steps;
ret.state = self;
ret.state.rooms[oidx][pos] = null;
ret.state.rooms[idx][free - 1] = amp;
return ret;
}
// only first item can move, no need to check others
break;
}
}
}
return null;
}
fn checkHWtoRoom(self: @This(), from: usize, to: usize) ?PathType {
// #############
// #01.2.3.4.56#
// ###0#1#2#3###
// #0#1#2#3#
// #########
std.debug.assert(to < 4);
std.debug.assert(from < 8);
var steps: PathType = 0;
if (from -| to >= 2) {
var idx: usize = from -| 1;
while (idx >= to + 2) : (idx -= 1) {
// std.debug.print("LEFT from: {d} to: {d} step: {d}\n", .{ from, to, idx });
if (self.hallway[idx] == null) steps += 2 else return null;
}
} else {
var idx: usize = from + 1;
while (idx <= to + 1) : (idx += 1) {
// std.debug.print("RIGHT from: {d} to: {d} step: {d}\n", .{ from, to, idx });
if (self.hallway[idx] == null) steps += 2 else return null;
}
}
// room entrance point
if (from != 6 and from != 0) steps += 1;
return steps;
}
pub fn neighborFn(self: @This(), allocator: std.mem.Allocator) ![]StateQueue {
var ret = std.ArrayList(StateQueue).init(allocator);
// Amphipod can move to its final place, always a good move
if (self.checkSideRoom()) |item| {
try ret.append(item);
return ret.toOwnedSlice();
}
// we already checked the side rooms, so we only have to collect
// each rooms first item's possible hallway positions
for (self.rooms, 0..) |room, idx| {
// std.debug.print("ROOM->HW check {d} room\n", .{idx});
for (room, 0..) |amp, pos| {
if (amp == null) continue;
// do not move items in right room
// except: we should move away to let wrong placed amp out
if (amp == @as(Amphipod, @enumFromInt(idx))) {
var tainted: bool = false;
var next: PathType = @as(PathType, @intCast(pos)) + 1;
while (next < SIDEROOM_DEPTH) : (next += 1) {
if (room[next] != @as(Amphipod, @enumFromInt(idx))) tainted = true;
}
if (!tainted) break;
}
for (self.hallway, 0..) |hw, hwidx| {
if (hw == null) { // destination hallway spot is free
// std.debug.print("checking hallway spot {d} with amp {any}\n", .{hwidx, amp});
const steps = (self.checkHWtoRoom(hwidx, idx) orelse continue) + pos + 1;
var st: StateQueue = undefined;
st.cost = steps * try std.math.powi(usize, 10, @intFromEnum(amp.?));
st.state = self;
st.state.hallway[hwidx] = amp;
st.state.rooms[idx][pos] = null;
try ret.append(st);
}
}
// only first item can move
break;
}
}
return ret.toOwnedSlice();
}
};
fn parseInput(comptime input: Str) !State {
var lines = std.mem.split(u8, input, "\n");
var ret = State{ .rooms = undefined };
var line: usize = 0;
var counter: usize = 0;
while (lines.next()) |l| : (line += 1) {
if (line == 2 or line == 3) {
for (l, 0..) |ch, idx| {
if (idx == 3 or idx == 5 or idx == 7 or idx == 9) {
const amp: Amphipod = switch (ch) {
'A' => .A,
'B' => .B,
'C' => .C,
'D' => .D,
else => unreachable,
};
// std.debug.print("{d} {d}\n", .{counter%siderooms, counter/siderooms});
ret.rooms[counter % SIDEROOMS][counter / SIDEROOMS] = amp;
counter += 1;
}
}
}
}
return ret;
}
const PF = @import("pathfinder.zig");
const StateQueue = PF.Graph.Graph(State).QueueType;
test "Graph" {
const start_str =
\\#############
\\#...........#
\\###D#D#B#A###
\\ #B#C#A#C#
\\ #########
;
const goal_str =
\\#############
\\#...........#
\\###A#B#C#D###
\\ #A#B#C#D#
\\ #########
;
const start = try parseInput(start_str);
const goal = try parseInput(goal_str);
var graph = PF.Graph.Graph(State).init(std.testing.allocator);
defer graph.deinit();
const ret = try graph.dijkstra(start, goal);
try std.testing.expectEqual(@as(usize, 16244), ret);
}