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());
}