const math = std.math;

const Energy = enum(u10) {
    A = 1,
    B = 10,
    C = 100,
    D = 1000,

const Amphipod = enum {
    A,
    B,
    C,
    D,

const hallway_length = 11;

const hallway_length = 7;

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 PathType = u4;

    amps: [siderooms * sideroom_depth]Amphipod,

    hallway: [hallway_length]?Amphipod,
    rooms: [siderooms][sideroom_depth]?Amphipod,

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

    }
    fn sideRoomDone(self: @This(), room: usize) bool {
        std.debug.assert(room < siderooms);
        for (self.rooms[room]) |amp| {
            // https://github.com/ziglang/zig/issues/6059
            if (amp == null) {
                return false;
            } else if (amp != @intToEnum(Amphipod, room)) return false;
        }
        return true;

        // 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;
    }

        amp: for (self.amps) |a, idx| {
            // skip if already in place
            if (a.inPlace()) continue;

        for (self.rooms) |_, idx| {
            const free = self.sideRoomFreeSpace(idx) orelse continue;
            if (free == 0) continue;

            // set destination sideroom
            const dest: PositionType = switch (a.energy) {
                .A => 2,
                .B => 4,
                .C => 6,
                .D => 8,
            };

            // std.debug.print("FREE: {d}\n", .{free});

            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;

            for (self.rooms) |other, oidx| {
                if (idx == oidx) continue;

            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;

        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;

                        return ret;

                    // only first item can move, no need to check others
                    break;

        }

            // reached destination, return
            if (row == to[0] and col == to[1]) {
                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#
        //   #########

            // come out of current sideroom
            if (row != 0 and col != to[1]) {
                row -= 1;
                continue;
            }

        std.debug.assert(to < 4);
        std.debug.assert(from < 8);

            // 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;

            row += 1;

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

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

                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;

                            try ret.append(next);
                        }

                        try ret.append(st);

                // only first item can move
                break;

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

    // var backtrack = std.AutoHashMap(StateQueue, StateQueue).init(allocator);
    // defer backtrack.deinit();

    // 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;

        // std.debug.print("{d}\n{s}\n", .{curr.energy, curr.state.print()});

        // std.debug.print("{d}\n{s}\n", .{ curr.energy, curr.state.print() });

        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

            // std.debug.print("{d}\n{s}\n", .{ sq.energy, sq.state.print() });

            // try backtrack.put(sq.*, curr);

                    var a: Amphipod = undefined;
                    a.energy = switch (ch) {

                    const amp: Amphipod = switch (ch) {

                    a.pos = .{ @intCast(PositionType, line - 1), @intCast(PositionType, idx - 1) };
                    ret.amps[counter] = a;

                    // std.debug.print("{d} {d}\n", .{counter%siderooms, counter/siderooms});
                    ret.rooms[counter % siderooms][counter / siderooms] = amp;

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).?);
}