{"header":{"message":"Add solution for day23b","description":null,"timestamp":"2022-02-23T14:17:08.835346275Z","authors":[{}]},"hash":"TYIMCQZ4CP2JSZVNXULIFZOMTENG3NDCUSH2XJQBJQVF3UPNYS7AC","authors":[{"login":"voroskoi","key":"Guf8VYJNUiWAqxwLxDSKxmvvtY65ht2zK2q4h6VhxrcZ"}],"deps":{"hashes":[["TYIMCQZ4CP2JSZVNXULIFZOMTENG3NDCUSH2XJQBJQVF3UPNYS7AC","Add solution for day23b"],["AA",null],["ISKIMCRTCM4ZY34QENDO4AN7ZAKRRBPFLA5MYHXH2K6Q2WKJDZNQC","Add build files and solution for day1"]],"deps":["ISKIMCRTCM4ZY34QENDO4AN7ZAKRRBPFLA5MYHXH2K6Q2WKJDZNQC"],"known":[]},"hunks":[{"FileAdd":{"meta":{"basename":"day23b.zig","metadata":0},"context":[{"change":2,"pos":15}],"contents":[{"Add":"const std = @import(\"std\");"},{"Add":"const math = std.math;"},{"Add":""},{"Add":"const path = \"../data/day23/input2.txt\";"},{"Add":""},{"Add":"const Amphipod = enum {"},{"Add":" A,"},{"Add":" B,"},{"Add":" C,"},{"Add":" D,"},{"Add":"};"},{"Add":""},{"Add":"const hallway_length = 7;"},{"Add":"const siderooms = 4;"},{"Add":"const sideroom_depth = 4;"},{"Add":""},{"Add":"const PathType = u4;"},{"Add":""},{"Add":"const State = struct {"},{"Add":" hallway: [hallway_length]?Amphipod,"},{"Add":" rooms: [siderooms][sideroom_depth]?Amphipod,"},{"Add":" fn print(self: @This()) []u8 {"},{"Add":" const blank ="},{"Add":" \\\\#############"},{"Add":" \\\\#...........#"},{"Add":" \\\\###.#.#.#.###"},{"Add":" \\\\ #.#.#.#.#"},{"Add":" \\\\ #.#.#.#.#"},{"Add":" \\\\ #.#.#.#.#"},{"Add":" \\\\ #########"},{"Add":" ;"},{"Add":" var buffer: [100]u8 = undefined;"},{"Add":" var mod: []u8 = buffer[0..blank.len];"},{"Add":" std.mem.copy(u8, mod, blank);"},{"Add":" for (self.hallway) |amp, idx| {"},{"Add":" if (amp != null) {"},{"Add":" const i: usize = switch (idx) {"},{"Add":" 0 => 14 + 1,"},{"Add":" 1 => 14 + 2,"},{"Add":" 2 => 14 + 4,"},{"Add":" 3 => 14 + 6,"},{"Add":" 4 => 14 + 8,"},{"Add":" 5 => 14 + 10,"},{"Add":" 6 => 14 + 11,"},{"Add":" else => unreachable,"},{"Add":" };"},{"Add":" const a: u8 = switch (amp.?) {"},{"Add":" .A => 'A',"},{"Add":" .B => 'B',"},{"Add":" .C => 'C',"},{"Add":" .D => 'D',"},{"Add":" };"},{"Add":" mod[i] = a;"},{"Add":" }"},{"Add":" }"},{"Add":" for (self.rooms) |room, rid| {"},{"Add":" for (room) |amp, aid| {"},{"Add":" if (amp != null) {"},{"Add":" const a: u8 = switch (amp.?) {"},{"Add":" .A => 'A',"},{"Add":" .B => 'B',"},{"Add":" .C => 'C',"},{"Add":" .D => 'D',"},{"Add":" };"},{"Add":" mod[14 + 14 + rid * 2 + 3 + 14 * aid] = a;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" return mod;"},{"Add":" }"},{"Add":" fn sideRoomDone(self: @This(), room: usize) bool {"},{"Add":" std.debug.assert(room < siderooms);"},{"Add":" for (self.rooms[room]) |amp| {"},{"Add":" // https://github.com/ziglang/zig/issues/6059"},{"Add":" if (amp == null) {"},{"Add":" return false;"},{"Add":" } else if (amp != @intToEnum(Amphipod, room)) return false;"},{"Add":" }"},{"Add":" return true;"},{"Add":" }"},{"Add":" fn done(self: @This()) bool {"},{"Add":" // check if hallway is empty"},{"Add":" for (self.hallway) |item| {"},{"Add":" if (item != null) return false;"},{"Add":" }"},{"Add":""},{"Add":" // every room is done"},{"Add":" for (self.rooms) |_, idx| {"},{"Add":" if (!self.sideRoomDone(idx)) return false;"},{"Add":" }"},{"Add":" return true;"},{"Add":" }"},{"Add":" fn sideRoomFreeSpace(self: @This(), room: usize) ?u3 {"},{"Add":" var ret: u3 = 0;"},{"Add":""},{"Add":" std.debug.assert(room < siderooms);"},{"Add":" for (self.rooms[room]) |amp| {"},{"Add":" if (amp == null) {"},{"Add":" ret += 1;"},{"Add":" } else if (amp != @intToEnum(Amphipod, room)) {"},{"Add":" return null;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" std.debug.assert(ret <= sideroom_depth);"},{"Add":" return ret;"},{"Add":" }"},{"Add":" fn checkSideRoom(self: @This()) ?StateQueue {"},{"Add":" for (self.rooms) |_, idx| {"},{"Add":" const free = self.sideRoomFreeSpace(idx) orelse continue;"},{"Add":" if (free == 0) continue;"},{"Add":""},{"Add":" // std.debug.print(\"FREE: {d}\\n\", .{free});"},{"Add":""},{"Add":" for (self.hallway) |amp, hwidx| {"},{"Add":" if (amp == @intToEnum(Amphipod, idx)) {"},{"Add":" const steps = (self.checkHWtoRoom(hwidx, idx) orelse continue) + free;"},{"Add":""},{"Add":" var ret: StateQueue = undefined;"},{"Add":""},{"Add":" ret.energy = (std.math.powi(usize, 10, @enumToInt(amp.?)) catch unreachable) * steps;"},{"Add":""},{"Add":" ret.state = self;"},{"Add":" ret.state.hallway[hwidx] = null;"},{"Add":" ret.state.rooms[idx][free - 1] = amp;"},{"Add":""},{"Add":" return ret;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" for (self.rooms) |other, oidx| {"},{"Add":" if (idx == oidx) continue;"},{"Add":""},{"Add":" var pos: PathType = 0;"},{"Add":" for (other) |amp| {"},{"Add":" if (amp == null) {"},{"Add":" pos += 1;"},{"Add":" continue;"},{"Add":" }"},{"Add":" if (amp == @intToEnum(Amphipod, idx)) {"},{"Add":" var steps: PathType = undefined;"},{"Add":" if (idx < oidx) { // moving left"},{"Add":" const hwidx = oidx + 2;"},{"Add":" // std.debug.print(\"L->R from: {d} to: {d}\\n\", .{ hwidx, idx });"},{"Add":" steps = (self.checkHWtoRoom(hwidx, idx) orelse break) + free + pos;"},{"Add":" } else { // moving right"},{"Add":" const hwidx = oidx + 1;"},{"Add":" // std.debug.print(\"R->L from: {d} to: {d}\\n\", .{ hwidx, idx });"},{"Add":" steps = (self.checkHWtoRoom(hwidx, idx) orelse break) + free + pos;"},{"Add":" }"},{"Add":""},{"Add":" // we can move amp to his sideroom"},{"Add":" var ret: StateQueue = undefined;"},{"Add":""},{"Add":" ret.energy = (std.math.powi(usize, 10, @enumToInt(amp.?)) catch unreachable) * steps;"},{"Add":""},{"Add":" ret.state = self;"},{"Add":" ret.state.rooms[oidx][pos] = null;"},{"Add":" ret.state.rooms[idx][free - 1] = amp;"},{"Add":""},{"Add":" return ret;"},{"Add":" }"},{"Add":" // only first item can move, no need to check others"},{"Add":" break;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" return null;"},{"Add":" }"},{"Add":" fn checkHWtoRoom(self: @This(), from: usize, to: usize) ?PathType {"},{"Add":" // #############"},{"Add":" // #01.2.3.4.56#"},{"Add":" // ###0#1#2#3###"},{"Add":" // #0#1#2#3#"},{"Add":" // #########"},{"Add":""},{"Add":" std.debug.assert(to < 4);"},{"Add":" std.debug.assert(from < 8);"},{"Add":""},{"Add":" var steps: PathType = 0;"},{"Add":" if (from -| to >= 2) {"},{"Add":" var idx: usize = from -| 1;"},{"Add":" while (idx >= to + 2) : (idx -= 1) {"},{"Add":" // std.debug.print(\"LEFT from: {d} to: {d} step: {d}\\n\", .{ from, to, idx });"},{"Add":" if (self.hallway[idx] == null) steps += 2 else return null;"},{"Add":" }"},{"Add":" } else {"},{"Add":" var idx: usize = from + 1;"},{"Add":" while (idx <= to + 1) : (idx += 1) {"},{"Add":" // std.debug.print(\"RIGHT from: {d} to: {d} step: {d}\\n\", .{ from, to, idx });"},{"Add":" if (self.hallway[idx] == null) steps += 2 else return null;"},{"Add":" }"},{"Add":" }"},{"Add":" // room entrance point"},{"Add":" if (from != 6 and from != 0) steps += 1;"},{"Add":""},{"Add":" return steps;"},{"Add":" }"},{"Add":" fn getValidStates(self: @This(), allocator: std.mem.Allocator) ![]StateQueue {"},{"Add":" var ret = std.ArrayList(StateQueue).init(allocator);"},{"Add":""},{"Add":" // Amphipod can move to its final place, always a good move"},{"Add":" if (self.checkSideRoom()) |item| {"},{"Add":" try ret.append(item);"},{"Add":" return ret.toOwnedSlice();"},{"Add":" }"},{"Add":""},{"Add":" // we already checked the side rooms, so we only have to collect"},{"Add":" // each rooms first item's possible hallway positions"},{"Add":" for (self.rooms) |room, idx| {"},{"Add":" // std.debug.print(\"ROOM->HW check {d} room\\n\", .{idx});"},{"Add":" for (room) |amp, pos| {"},{"Add":" if (amp == null) continue;"},{"Add":""},{"Add":" // do not move items in right room"},{"Add":" // except: we should move away to let wrong placed amp out"},{"Add":" if (amp == @intToEnum(Amphipod, idx)) {"},{"Add":" var tainted: bool = false;"},{"Add":""},{"Add":" var next: PathType = @intCast(PathType, pos) + 1;"},{"Add":" while (next < sideroom_depth) : (next += 1) {"},{"Add":" if (room[next] != @intToEnum(Amphipod, idx)) tainted = true;"},{"Add":" }"},{"Add":" if (!tainted) break;"},{"Add":" }"},{"Add":""},{"Add":" for (self.hallway) |hw, hwidx| {"},{"Add":" if (hw == null) { // destination hallway spot is free"},{"Add":" // std.debug.print(\"checking hallway spot {d} with amp {any}\\n\", .{hwidx, amp});"},{"Add":" const steps = (self.checkHWtoRoom(hwidx, idx) orelse continue) + pos + 1;"},{"Add":""},{"Add":" var st: StateQueue = undefined;"},{"Add":""},{"Add":" st.energy = steps * try std.math.powi(usize, 10, @enumToInt(amp.?));"},{"Add":""},{"Add":" st.state = self;"},{"Add":" st.state.hallway[hwidx] = amp;"},{"Add":" st.state.rooms[idx][pos] = null;"},{"Add":""},{"Add":" try ret.append(st);"},{"Add":" }"},{"Add":" }"},{"Add":" // only first item can move"},{"Add":" break;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" return ret.toOwnedSlice();"},{"Add":" }"},{"Add":"};"},{"Add":""},{"Add":"const StateQueue = struct {"},{"Add":" state: State,"},{"Add":" energy: usize,"},{"Add":"};"},{"Add":""},{"Add":"pub fn main() !void {"},{"Add":" var timer = try std.time.Timer.start();"},{"Add":" const ret = try second();"},{"Add":" const t = timer.lap() / 1000;"},{"Add":""},{"Add":" try std.testing.expectEqual(@as(usize, 43226), ret);"},{"Add":""},{"Add":" std.debug.print(\"Day 23b result: {d} \\t\\ttime: {d}µs\\n\", .{ ret, t });"},{"Add":"}"},{"Add":""},{"Add":"fn lessThan(context: void, a: StateQueue, b: StateQueue) std.math.Order {"},{"Add":" _ = context;"},{"Add":" if (a.energy == b.energy) {"},{"Add":" return .eq;"},{"Add":" } else if (a.energy < b.energy) {"},{"Add":" return .lt;"},{"Add":" } else if (a.energy > b.energy) {"},{"Add":" return .gt;"},{"Add":" } else unreachable;"},{"Add":"}"},{"Add":""},{"Add":"pub fn second() !usize {"},{"Add":" const allocator = std.testing.allocator;"},{"Add":""},{"Add":" var queue = std.PriorityQueue(StateQueue, void, lessThan).init(allocator, {});"},{"Add":" defer queue.deinit();"},{"Add":""},{"Add":" var visited = std.AutoHashMap(State, void).init(allocator);"},{"Add":" defer visited.deinit();"},{"Add":""},{"Add":" // var backtrack = std.AutoHashMap(StateQueue, StateQueue).init(allocator);"},{"Add":" // defer backtrack.deinit();"},{"Add":""},{"Add":" var init_state: StateQueue = undefined;"},{"Add":" init_state.state = try parseInput();"},{"Add":" init_state.energy = 0;"},{"Add":""},{"Add":" try queue.add(init_state);"},{"Add":""},{"Add":" while (queue.count() > 0) {"},{"Add":" // var steps: usize = 0;"},{"Add":" // while (steps < 1) : (steps += 1) {"},{"Add":" const curr = queue.remove();"},{"Add":""},{"Add":" // std.debug.print(\"{d}\\n{s}\\n\", .{ curr.energy, curr.state.print() });"},{"Add":" // std.debug.print(\"{d} \", .{curr.energy});"},{"Add":""},{"Add":" // skip if already checked"},{"Add":" if (visited.contains(curr.state)) continue;"},{"Add":" try visited.put(curr.state, {});"},{"Add":""},{"Add":" // Amphipods are in place, return energy"},{"Add":" if (curr.state.done()) {"},{"Add":" // var bt: StateQueue = curr;"},{"Add":" // while (backtrack.contains(bt)) {"},{"Add":" // std.debug.print(\"{d}\\n{s}\\n\", .{bt.energy, bt.state.print()});"},{"Add":" // bt = backtrack.get(bt).?;"},{"Add":" // }"},{"Add":" return curr.energy;"},{"Add":" }"},{"Add":""},{"Add":" var possible_states = try curr.state.getValidStates(allocator);"},{"Add":" defer allocator.free(possible_states);"},{"Add":""},{"Add":" for (possible_states) |*sq| {"},{"Add":" sq.energy += curr.energy;"},{"Add":" // std.debug.print(\"{d}\\n{s}\\n\", .{ sq.energy, sq.state.print() });"},{"Add":" try queue.add(sq.*);"},{"Add":" // try backtrack.put(sq.*, curr);"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" unreachable;"},{"Add":"}"},{"Add":""},{"Add":"fn parseInput() !State {"},{"Add":" const input = @embedFile(path);"},{"Add":" var lines = std.mem.split(u8, input, \"\\n\");"},{"Add":""},{"Add":" var ret: State = undefined;"},{"Add":""},{"Add":" var line: usize = 0;"},{"Add":" var counter: usize = 0;"},{"Add":" while (lines.next()) |l| : (line += 1) {"},{"Add":" if (line == 2 or line == 3 or line == 4 or line == 5) {"},{"Add":" for (l) |ch, idx| {"},{"Add":" if (idx == 3 or idx == 5 or idx == 7 or idx == 9) {"},{"Add":" const amp: Amphipod = switch (ch) {"},{"Add":" 'A' => .A,"},{"Add":" 'B' => .B,"},{"Add":" 'C' => .C,"},{"Add":" 'D' => .D,"},{"Add":" else => unreachable,"},{"Add":" };"},{"Add":" // std.debug.print(\"{d} {d}\\n\", .{counter%siderooms, counter/siderooms});"},{"Add":" ret.rooms[counter % siderooms][counter / siderooms] = amp;"},{"Add":" counter += 1;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" return ret;"},{"Add":"}"},{"Add":""},{"Add":"test \"day23b\" {"},{"Add":" try std.testing.expectEqual(@as(usize, 43226), try second());"},{"Add":"}"}]}}],"owner":"voroskoi","repo":"aoc2021-zig","token":"LW3sGeJDEhRXO55wTK6uP52b2Ui3NbLJCpDvDsxp4Ac=","login":null}

…

Dependencies

Change contents