const std = @import("std");
const path = "../data/day23/input.txt";
const Energy = enum(u10) {
A = 1,
B = 10,
C = 100,
D = 1000,
};
const hallway_length = 11;
const siderooms = 4;
const sideroom_depth = 2;
const PositionType = u4;
const Amphipod = struct {
energy: Energy,
pos: [2]PositionType,
fn inPlace(self: @This()) bool {
switch (self.energy) {
.A => if (self.pos[1] != 2) return false,
.B => if (self.pos[1] != 4) return false,
.C => if (self.pos[1] != 6) return false,
.D => if (self.pos[1] != 8) return false,
}
return true;
}
};
const State = struct {
amps: [siderooms * sideroom_depth]Amphipod,
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.amps) |a| {
const ch: u8 = switch (a.energy) {
.A => 'A',
.B => 'B',
.C => 'C',
.D => 'D',
};
mod[14 + 14 * @intCast(usize, a.pos[0]) + @intCast(usize, a.pos[1]) + 1] = ch;
}
return mod;
}
fn done(self: @This()) bool {
// every amp in the proper side room
for (self.amps) |a| {
if (!a.inPlace()) return false;
}
return true;
}
fn checkSideRoom(self: @This()) ?StateQueue {
amp: for (self.amps) |a, idx| {
// skip if already in place
if (a.inPlace()) continue;
// set destination sideroom
const dest: PositionType = switch (a.energy) {
.A => 2,
.B => 4,
.C => 6,
.D => 8,
};
var counter: PositionType = 0; // items in destination
for (self.amps) |other, oidx| {
if (idx == oidx) continue;
if (other.pos[1] == dest) {
if (other.energy == a.energy) counter += 1 else continue :amp;
}
}
std.debug.assert(counter < sideroom_depth);
const steps = self.checkPath(a.pos, .{ sideroom_depth - counter, dest }) orelse continue;
var ret: StateQueue = undefined;
ret.state = self;
ret.state.amps[idx].pos = .{ sideroom_depth - counter, dest };
ret.energy = @enumToInt(a.energy) * steps;
return ret;
}
return null;
}
fn checkPath(self: @This(), from: [2]PositionType, to: [2]PositionType) ?usize {
var steps: usize = 0;
var row = from[0];
var col = from[1];
while (true) : (steps += 1) {
// check if row/col occupied or not
if (steps != 0) {
for (self.amps) |a| {
if (a.pos[0] == row and a.pos[1] == col) {
return null;
}
}
}
// reached destination, return
if (row == to[0] and col == to[1]) {
break;
}
// come out of current sideroom
if (row != 0 and col != to[1]) {
row -= 1;
continue;
}
// hallway
if (row == 0 and col != to[1]) {
if (col > to[1]) col -= 1 else col += 1;
continue;
}
row += 1;
}
return steps;
}
fn getValidStates(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();
}
for ([_]PositionType{ 2, 4, 6, 8 }) |col| {
if (self.sideRoomDone(col)) {
continue;
}
var row: PositionType = 1;
while (row <= sideroom_depth) : (row += 1) {
var first_amp_pos: ?[2]PositionType = null;
var idx: ?usize = null;
// find the first item in the sideroom
for (self.amps) |a, i| {
if (a.pos[0] == row and a.pos[1] == col) {
first_amp_pos = .{ row, col };
idx = i;
break;
}
}
if (first_amp_pos != null) {
var hw: PositionType = 0;
while (hw < hallway_length) : (hw += 1) {
// skip sideroom entry point, they are forbidden
if (hw == 2 or hw == 4 or hw == 6 or hw == 8) {
continue;
}
if (self.checkPath(first_amp_pos.?, .{ 0, hw })) |steps| {
var next: StateQueue = undefined;
next.state = self;
next.state.amps[idx.?].pos = .{ 0, hw };
next.energy = steps * @enumToInt(next.state.amps[idx.?].energy);
try ret.append(next);
}
}
}
}
}
return ret.toOwnedSlice();
}
fn sideRoomDone(self: @This(), col: usize) bool {
const goodType: Energy = switch (col) {
2 => .A,
4 => .B,
6 => .C,
8 => .D,
else => unreachable,
};
for (self.amps) |a| {
if (a.pos[1] == col and a.energy != goodType) {
return false;
}
}
return true;
}
};
const StateQueue = struct {
state: State,
energy: usize,
};
pub fn main() !void {
var timer = try std.time.Timer.start();
const ret = try first();
const t = timer.lap() / 1000;
try std.testing.expectEqual(@as(usize, 16244), ret);
std.debug.print("Day 23a result: {d} \t\ttime: {d}µs\n", .{ ret, t });
}
fn lessThan(context: void, a: StateQueue, b: StateQueue) std.math.Order {
_ = context;
if (a.energy == b.energy) {
return .eq;
} else if (a.energy < b.energy) {
return .lt;
} else if (a.energy > b.energy) {
return .gt;
} else unreachable;
}
pub fn first() !usize {
const allocator = std.testing.allocator;
var queue = std.PriorityQueue(StateQueue, void, lessThan).init(allocator, {});
defer queue.deinit();
var visited = std.AutoHashMap(State, void).init(allocator);
defer visited.deinit();
var init_state: StateQueue = undefined;
init_state.state = try parseInput();
init_state.energy = 0;
// HACK
// init_state.state.amps[2].pos = .{0,3};
// init_state.energy += 40;
// init_state.state.amps[1].pos = .{1,6};
// init_state.energy += 400;
// init_state.state.amps[5].pos = .{0,5};
// init_state.energy += 3000;
// init_state.state.amps[2].pos = .{2,4};
// init_state.energy += 30;
// init_state.state.amps[0].pos = .{1,4};
// init_state.energy += 40;
// init_state.state.amps[3].pos = .{0,7};
// init_state.energy += 2000;
// init_state.state.amps[7].pos = .{0,9};
// init_state.energy += 3;
try queue.add(init_state);
while (queue.count() > 0) {
// var steps: usize = 0;
// while (steps < 1) : (steps += 1) {
const curr = queue.remove();
// std.debug.print("{d}\n{s}\n", .{curr.energy, curr.state.print()});
// std.debug.print("{d} ", .{curr.energy});
// skip if already checked
if (visited.contains(curr.state)) continue;
try visited.put(curr.state, {});
// Amphipods are in place, return energy
if (curr.state.done()) return curr.energy;
var possible_states = try curr.state.getValidStates(allocator);
defer allocator.free(possible_states);
for (possible_states) |*sq| {
// std.debug.print("{d}\n{s}\n", .{sq.energy, sq.state.print()});
// do not queue if already visited
// if (visited.contains(sq.state)) continue;
// XXX: this makes 3x slower :-)
// update energy if it is lower than the current in queue
// var qit = queue.iterator();
// while (qit.next()) |queue_item| {
// if (std.meta.eql(queue_item.state, sq.state)) {
// // if queued energy is lower than current then skip state
// if (queue_item.energy <= sq.energy + curr.energy) continue :states;
// // else remove the current, so we can add the new value
// _ = queue.removeIndex(qit.count);
// }
// }
// add to the queue if not already there
sq.energy += curr.energy;
try queue.add(sq.*);
}
}
unreachable;
}
fn parseInput() !State {
const input = @embedFile(path);
var lines = std.mem.split(u8, input, "\n");
var ret: State = undefined;
var line: usize = 0;
var counter: usize = 0;
while (lines.next()) |l| : (line += 1) {
if (line == 2 or line == 3) {
for (l) |ch, idx| {
if (idx == 3 or idx == 5 or idx == 7 or idx == 9) {
var a: Amphipod = undefined;
a.energy = switch (ch) {
'A' => .A,
'B' => .B,
'C' => .C,
'D' => .D,
else => unreachable,
};
a.pos = .{ @intCast(PositionType, line - 1), @intCast(PositionType, idx - 1) };
ret.amps[counter] = a;
counter += 1;
}
}
}
}
return ret;
}
test "day23a" {
try std.testing.expectEqual(@as(usize, 16244), try first());
}