const std = @import("std");
const Str = []const u8;
const path = "../data/day20/input.txt";
const max_rounds = 50;
const IMAGE_SIZE = 100;
const Pixels = std.DynamicBitSet;
const bitset_size = 512;
const BitSet = std.StaticBitSet(bitset_size);
const Image = struct {
    IEA: BitSet,
    lit: Pixels,
    size: usize,
    flippy: bool = false,
};
pub fn main() !void {
    var timer = try std.time.Timer.start();
    const ret = try second();
    const t = timer.lap() / 1000;
    try std.testing.expectEqual(@as(usize, 19156), ret);
    std.debug.print("Day 20b result: {d} \t\ttime: {d}µs\n", .{ ret, t });
}
pub fn second() !usize {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    const allocator = arena.allocator();
    var image = try parseInput(allocator);
    defer image.lit.deinit();
    var round: usize = 1;
    while (round <= max_rounds) : (round += 1) {
        const next_size = IMAGE_SIZE + round * 2; // 7, 9, 11...
        var next = try Pixels.initEmpty(allocator, (next_size * next_size));
        var row: usize = 0;
        while (row < next_size) : (row += 1) {
            var col: usize = 0;
            while (col < next_size) : (col += 1) {
                if (getValue(&image, row, col)) next.set(row * next_size + col);
            }
        }
        image.lit.deinit();
        image.lit = next;
        image.size = next_size;
        if (image.IEA.isSet(0) and !image.IEA.isSet(bitset_size - 1)) {
            image.flippy = !image.flippy;
        }
    }
    return image.lit.count();
}
const directions = [9][2]isize{
    // order is important!
    .{ 1, 1 },
    .{ 1, 0 },
    .{ 1, -1 },
    .{ 0, 1 },
    .{ 0, 0 },
    .{ 0, -1 },
    .{ -1, 1 },
    .{ -1, 0 },
    .{ -1, -1 },
};
fn getValue(image: *Image, row: usize, col: usize) bool {
    var index: u9 = 0;
    for (directions) |d, idx| {
        const r = @intCast(isize, row) - 1 + d[0];
        const c = @intCast(isize, col) - 1 + d[1];
        if (r < 0 or c < 0) { // upper of left
            if (image.flippy) index |= @as(u9, 1) <<| idx;
            continue;
        }
        if (r >= image.size or c >= image.size) { // bottom or right
            if (image.flippy) index |= @as(u9, 1) <<| idx;
            continue;
        }
        const rr = @intCast(usize, r);
        const cc = @intCast(usize, c);
        if (image.lit.isSet(rr * image.size + cc)) index |= @as(u9, 1) <<| idx;
    }
    std.debug.assert(index < bitset_size);
    return image.IEA.isSet(index);
}
fn parseInput(a: std.mem.Allocator) !Image {
    const input = @embedFile(path);
    var lines = std.mem.split(u8, input, "\n");
    var i: Image = undefined;
    i.IEA = BitSet.initEmpty();
    for (lines.next().?) |item, idx| {
        if (item == '#') i.IEA.set(idx);
    }
    _ = lines.next(); // drop empty line
    i.lit = try Pixels.initEmpty(a, IMAGE_SIZE * IMAGE_SIZE);
    var row: usize = 0;
    while (lines.next()) |line| : (row += 1) {
        for (line) |ch, col| {
            if (ch == '#') i.lit.set(IMAGE_SIZE * row + col);
        }
    }
    i.size = row - 1;
    return i;
}
fn printImage(image: *Image) void {
    std.debug.print("\n", .{});
    var row: usize = 0;
    while (row < image.size) : (row += 1) {
        var col: usize = 0;
        while (col < image.size) : (col += 1) {
            if (image.lit.isSet(row * image.size + col)) {
                std.debug.print("#", .{});
            } else {
                std.debug.print(".", .{});
            }
        }
        std.debug.print("\n", .{});
    }
}
test "day20b" {
    try std.testing.expectEqual(@as(usize, 19156), try second());
}

const Str = []const u8;

const PointType = isize;
const Point = [2]PointType;

const IMAGE_SIZE = 100;

const Pixels = std.AutoHashMap(Point, void);

const Pixels = std.DynamicBitSet;

    size: isize,

    size: usize,

    const allocator = std.testing.allocator;

    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    const allocator = arena.allocator();

    var round: isize = 1;

    var round: usize = 1;

        var next = Pixels.init(allocator);

        const next_size = IMAGE_SIZE + round * 2; // 7, 9, 11...

        // printImage(&image, round);

        var next = try Pixels.initEmpty(allocator, (next_size * next_size));

        var row: isize = -round;
        while (row < @intCast(isize, image.size) + round) : (row += 1) {
            var col: isize = -round;
            while (col < @intCast(isize, image.size) + round) : (col += 1) {
                const p = Point{ row, col };
                if (getValue(&image, p, round)) try next.put(p, {});

        var row: usize = 0;
        while (row < next_size) : (row += 1) {
            var col: usize = 0;
            while (col < next_size) : (col += 1) {
                if (getValue(&image, row, col)) next.set(row * next_size + col);

        // std.debug.print("lit: {d}\n", .{next.count()});

        image.size = next_size;

fn getValue(image: *Image, pt: Point, round: isize) bool {

fn getValue(image: *Image, row: usize, col: usize) bool {

        const p: Point = .{ pt[0] + d[0], pt[1] + d[1] };

        const r = @intCast(isize, row) - 1 + d[0];
        const c = @intCast(isize, col) - 1 + d[1];

        if (image.flippy and
            (p[0] < -round + 1 or p[0] >= image.size + round - 1 or
            p[1] < -round + 1 or p[1] >= image.size + round - 1))
        {
            index |= @as(u9, 1) <<| idx;

        if (r < 0 or c < 0) { // upper of left
            if (image.flippy) index |= @as(u9, 1) <<| idx;
            continue;
        }
        if (r >= image.size or c >= image.size) { // bottom or right
            if (image.flippy) index |= @as(u9, 1) <<| idx;

        if (image.lit.contains(p)) index |= @as(u9, 1) <<| idx;

        const rr = @intCast(usize, r);
        const cc = @intCast(usize, c);
        if (image.lit.isSet(rr * image.size + cc)) index |= @as(u9, 1) <<| idx;

    // std.debug.print("{d} {any}\n", .{index, image.IEA.isSet(index)});

    i.lit = Pixels.init(a);

    i.lit = try Pixels.initEmpty(a, IMAGE_SIZE * IMAGE_SIZE);

    var row: isize = 0;

    var row: usize = 0;

            if (ch == '#') try i.lit.put(.{ row, @intCast(isize, col) }, {});

            if (ch == '#') i.lit.set(IMAGE_SIZE * row + col);

fn printImage(image: *Image, round: isize) void {

fn printImage(image: *Image) void {

    var row: isize = -round;
    while (row < @intCast(isize, image.size) + round) : (row += 1) {
        var col: isize = -round;
        while (col < @intCast(isize, image.size) + round) : (col += 1) {
            const p = Point{ row, col };
            if (image.lit.contains(p)) {

    var row: usize = 0;
    while (row < image.size) : (row += 1) {
        var col: usize = 0;
        while (col < image.size) : (col += 1) {
            if (image.lit.isSet(row * image.size + col)) {

TODO: Day23 fails when built with `-Drelease-fast`, so using `-Drelease-safe` for
now.

TODO:
 - figure out how to avoid checking all scanner, beacon and rotation against the

TODO: Figure out how to avoid checking all scanner, beacon and rotation against the

else?

else? (Sort of done, but I am not satisfied with the result, especially the
hard coded magic numbers.)

The image enhancement algorithm string converted to a `std.StaticBitSet`. I use
a `u9` for generating the index with bitmasking. This works fine.

### Day 20b first solution: day20b_hashmap.zig ~1.6 seconds

### Final version

I have replaced `std.AutoHashMap` with `std.DynamicBitSet` as each pixes is
either lit or not. This makes the code much faster.
First part is ~3792 us, second part is 190 ms.