Y6LR3BWYWC2E3HAB45T5VFBUCWJLRTWIVYOETYUHLBA3UDSGKB2AC
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 PathType = u4;
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;
for (self.hallway) |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) |room, rid| {
for (room) |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;
}
}
// every amp in the proper side room
for (self.amps) |a| {
if (!a.inPlace()) return false;
// check if hallway is empty
for (self.hallway) |item| {
if (item != null) return false;
}
// every room is done
for (self.rooms) |_, idx| {
if (!self.sideRoomDone(idx)) return false;
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 != @intToEnum(Amphipod, room)) {
return null;
}
}
std.debug.assert(ret <= sideroom_depth);
return ret;
}
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;
for (self.hallway) |amp, hwidx| {
if (amp == @intToEnum(Amphipod, idx)) {
const steps = (self.checkHWtoRoom(hwidx, idx) orelse continue) + free;
var ret: StateQueue = undefined;
ret.energy = (std.math.powi(usize, 10, @enumToInt(amp.?)) catch unreachable) * steps;
ret.state = self;
ret.state.hallway[hwidx] = null;
ret.state.rooms[idx][free - 1] = amp;
return ret;
std.debug.assert(counter < sideroom_depth);
const steps = self.checkPath(a.pos, .{ sideroom_depth - counter, dest }) orelse continue;
var pos: PathType = 0;
for (other) |amp| {
if (amp == null) {
pos += 1;
continue;
}
if (amp == @intToEnum(Amphipod, 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.energy = (std.math.powi(usize, 10, @enumToInt(amp.?)) catch unreachable) * steps;
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;
ret.state = self;
ret.state.rooms[oidx][pos] = null;
ret.state.rooms[idx][free - 1] = amp;
// hallway
if (row == 0 and col != to[1]) {
if (col > to[1]) col -= 1 else col += 1;
continue;
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;
for ([_]PositionType{ 2, 4, 6, 8 }) |col| {
if (self.sideRoomDone(col)) {
continue;
}
// we already checked the side rooms, so we only have to collect
// each rooms first item's possible hallway positions
for (self.rooms) |room, idx| {
// std.debug.print("ROOM->HW check {d} room\n", .{idx});
for (room) |amp, pos| {
if (amp == null) continue;
var row: PositionType = 1;
while (row <= sideroom_depth) : (row += 1) {
var first_amp_pos: ?[2]PositionType = null;
var idx: ?usize = null;
// do not move items in right room
// except: we should move away to let wrong placed amp out
if (amp == @intToEnum(Amphipod, idx)) {
var tainted: bool = false;
// 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;
var next: PathType = @intCast(PathType, pos) + 1;
while (next < sideroom_depth) : (next += 1) {
if (room[next] != @intToEnum(Amphipod, idx)) tainted = true;
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;
}
for (self.hallway) |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.energy = steps * try std.math.powi(usize, 10, @enumToInt(amp.?));
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);
st.state = self;
st.state.hallway[hwidx] = amp;
st.state.rooms[idx][pos] = null;
}
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;
// 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;
if (curr.state.done()) return curr.energy;
if (curr.state.done()) {
// var bt: StateQueue = curr;
// while (backtrack.contains(bt)) {
// std.debug.print("{d}\n{s}\n", .{bt.energy, bt.state.print()});
// bt = backtrack.get(bt).?;
// }
return curr.energy;
}
// 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
test "checkHWtoRoom" {
const room = [sideroom_depth]?Amphipod{ null, null };
const st = State{
.hallway = [_]?Amphipod{ null, null, null, null, null, null, null },
.rooms = .{ room, room, room, room },
};
try std.testing.expectEqual(@as(PathType, 5), st.checkHWtoRoom(5, 1).?);
try std.testing.expectEqual(@as(PathType, 6), st.checkHWtoRoom(6, 1).?);
try std.testing.expectEqual(@as(PathType, 2), st.checkHWtoRoom(6, 3).?);
try std.testing.expectEqual(@as(PathType, 1), st.checkHWtoRoom(1, 0).?);
try std.testing.expectEqual(@as(PathType, 2), st.checkHWtoRoom(0, 0).?);
try std.testing.expectEqual(@as(PathType, 8), st.checkHWtoRoom(0, 3).?);
try std.testing.expectEqual(@as(PathType, 6), st.checkHWtoRoom(0, 2).?);
}