aoc-2020-zig

main.zig (16941B)

const std = @import("std");
const aoc = @import("aoc");

const tile_width: u32 = 10;
const Tile = struct {
    id: u32,
    data: [tile_width * tile_width]u1,
    sides: [4][tile_width]u1, // NOTE: update these values when placed accordingly
    adj: [4]?usize,
    pos: aoc.Pos,
};
const Flip = enum { NONE, HOR, VERT };
const flips = [_]Flip{ Flip.NONE, Flip.HOR, Flip.VERT };

const seamonster = [_][]const u8{
    "                  # ",
    "#    ##    ##    ###",
    " #  #  #  #  #  #   ",
};

const dirs = [4]aoc.Pos{
    aoc.Pos{ .x = 0, .y = -1 },
    aoc.Pos{ .x = 1, .y = 0 },
    aoc.Pos{ .x = 0, .y = 1 },
    aoc.Pos{ .x = -1, .y = 0 },
};

fn printGrid(tiles: []Tile, grid: []?usize, grid_width: u32) void {
    var y: u32 = 0;
    while (y < grid_width * tile_width) : (y += 1) {
        var x: u32 = 0;
        if (y > 0 and y % tile_width == 0) aoc.debugfmt("\n", .{});
        while (x < grid_width * tile_width) : (x += 1) {
            if (x > 0 and x % tile_width == 0) aoc.debugfmt(" ", .{});
            var tile_index: ?usize = grid[@divFloor(y, tile_width) * grid_width + @divFloor(x, tile_width)];
            if (tile_index != null) {
                var tile = tiles[tile_index.?];
                var c: u8 = if (tile.data[(y % tile_width) * tile_width + (x % tile_width)] == 1) '#' else '.';
                aoc.debugfmt("{c}", .{c});
            } else {
                aoc.debugfmt("?", .{});
            }
        }
        aoc.debugfmt("\n", .{});
    }
    aoc.debugfmt("\n\n", .{});
}

fn printTile(data: []u1, width: u32) void {
    var y: u32 = 0;
    while (y < width) : (y += 1) {
        printTileSlice(data[y * width .. (y + 1) * width]);
        aoc.debugfmt("\n", .{});
    }
}

fn printTileSlice(slice: []const u1) void {
    var i: u32 = 0;
    while (i < slice.len) : (i += 1) {
        var c: u8 = if (slice[i] == 1) '#' else '.';
        aoc.debugfmt("{c}", .{c});
    }
}

fn couldMatch(side1: [tile_width]u1, side2: [tile_width]u1) bool {
    var side1_cpy = side1;
    if (std.mem.eql(u1, side1_cpy[0..], side2[0..])) return true;
    std.mem.reverse(u1, side1_cpy[0..]);
    if (std.mem.eql(u1, side1_cpy[0..], side2[0..])) return true;
    return false;
}

fn parseTiles(tiles: *std.ArrayList(Tile), input: []u8) !void {
    var tileit = std.mem.split(u8, input, "\n\n");
    while (tileit.next()) |tilestr| {
        if (tilestr.len <= 1) continue;
        var tile: Tile = undefined;
        var lineit = std.mem.tokenize(u8, tilestr, "\n");

        // read tile id
        var numstr = (try aoc.unwrap(lineit.next()))[5..9];
        tile.id = try std.fmt.parseInt(u32, numstr, 10);

        // read tile data
        var i: u32 = 0;
        var line: []const u8 = undefined;
        while (i < tile_width * tile_width) : (i += 1) {
            if (i % tile_width == 0) line = try aoc.unwrap(lineit.next());
            tile.data[i] = @boolToInt(line[i % tile_width] == '#');
        }

        // read side bits
        i = 0;
        while (i < 4) : (i += 1) {
            var sidebits: [tile_width]u1 = undefined;
            for (sidebits) |_, k| {
                sidebits[k] = switch (i) {
                    @enumToInt(aoc.Dir.Name.NORTH) => tile.data[k],
                    @enumToInt(aoc.Dir.Name.WEST) => tile.data[(tile_width - 1 - k) * tile_width],
                    @enumToInt(aoc.Dir.Name.EAST) => tile.data[tile_width - 1 + k * tile_width],
                    @enumToInt(aoc.Dir.Name.SOUTH) => tile.data[tile_width * tile_width - 1 - k],
                    else => unreachable,
                };
            }
            tile.sides[i] = sidebits;
        }

        // init misc data
        tile.adj = [_]?usize{ null, null, null, null };

        try tiles.append(tile);
    }
}

fn matchTiles(tiles: *std.ArrayList(Tile)) void {
    // for each items's side, look for another item with a matching side
    for (tiles.items) |*tile, tile_index| {
        sides_loop: for (tile.sides) |_, i| {
            for (tiles.items) |*otile, otile_index| {
                if (tile_index == otile_index) continue;

                for (otile.sides) |_, oi| {
                    if (tile.adj[i] == null and otile.adj[oi] == null and couldMatch(tile.sides[i], otile.sides[oi])) {
                        tile.adj[i] = otile_index;
                        otile.adj[oi] = tile_index;
                        continue :sides_loop;
                    }
                }
            }
        }

        if (aoc.debug) {
            aoc.debugfmt("{}:\nSIDES ", .{tile.id});
            for (tile.sides) |side| {
                for (side) |b| {
                    var c: u8 = if (b == 1) '#' else '.';
                    aoc.debugfmt("{c}", .{c});
                }
                aoc.debugfmt(" ", .{});
            }
            aoc.debugfmt("\n", .{});
            for (tile.adj) |adj, i| {
                if (tile.adj[i] == null) {
                    aoc.debugfmt("null ", .{});
                } else {
                    var adjtile = tiles.items[adj.?];
                    aoc.debugfmt("{} ", .{adjtile.id});
                }
            }
            aoc.debugfmt("\n\n", .{});
        }
    }
}

fn checkSides(tiles: []Tile, grid: []?usize, grid_width: u32, p: aoc.Pos, adj: [4]?usize, sides: [4][10]u1) bool {
    var rot: u32 = 0;
    while (rot < 4) : (rot += 1) {
        const np = p.add(dirs[rot]);
        aoc.debugfmt("{}\n", .{@intToEnum(aoc.Dir.Name, @intCast(u2, rot))});
        aoc.debugfmt("{} {}\n", .{ np.x, np.y });

        if (np.x < 0 or np.x >= grid_width or np.y < 0 or np.y >= grid_width) {
            aoc.debugfmt("Side is null\n", .{});
            if (adj[rot] == null) {
                continue;
            } else {
                aoc.debugfmt("Side {} should be NULL!\n", .{@intToEnum(aoc.Dir.Name, @intCast(u2, rot))});
                return false;
            }
        }

        var ti: ?usize = grid[@intCast(u32, np.y * @intCast(i64, grid_width) + np.x)];
        if (ti == null) continue;

        var otherside = tiles[ti.?].sides[aoc.Dir.nextCW(rot, 2)];
        std.mem.reverse(u1, otherside[0..]);
        printTileSlice(otherside[0..]);
        aoc.debugfmt(" vs ", .{});
        printTileSlice(sides[rot][0..]);
        aoc.debugfmt("\n", .{});

        if (!std.mem.eql(u1, otherside[0..], sides[rot][0..])) return false;
    }
    return true;
}

fn rotateData(newdata: *[]u1, olddata: []u1, width: u32, rot: usize) void {
    for (olddata) |v, di| {
        const dy = @divFloor(di, width);
        const dx = di % width;
        var nx = dx;
        var ny = dy;
        switch (rot) {
            @enumToInt(aoc.Dir.Name.NORTH) => {},
            @enumToInt(aoc.Dir.Name.EAST) => {
                nx = width - 1 - dy;
                ny = dx;
            },
            @enumToInt(aoc.Dir.Name.SOUTH) => {
                nx = width - 1 - dx;
                ny = width - 1 - dy;
            },
            @enumToInt(aoc.Dir.Name.WEST) => {
                nx = dy;
                ny = width - 1 - dx;
            },
            else => {},
        }
        newdata.*[ny * width + nx] = v;
    }
}

fn flipData(data: []u1, width: u32, flip: Flip) void {
    switch (flip) {
        Flip.HOR => {
            var y: u32 = 0;
            while (y < width) : (y += 1) {
                std.mem.reverse(u1, data[y * width .. (y + 1) * width]);
            }
        },
        Flip.VERT => {
            var x: u32 = 0;
            while (x < width) : (x += 1) {
                var y: u32 = 0;
                while (y < width / 2) : (y += 1) {
                    std.mem.swap(u1, &data[x + y * width], &data[x + (width - 1 - y) * width]);
                }
            }
        },
        else => {},
    }
}

fn manipulateAndPlace(allocator: std.mem.Allocator, tiles: []Tile, grid: []?usize, grid_width: u32, p: aoc.Pos, tile_index: usize) !void {
    var tile = &tiles[tile_index];

    for (dirs) |_, rot| {
        for (flips) |flip| {
            // apply manipulation to only sides first for checking
            var sides = tile.sides;
            var tmp_sides = tile.sides;
            var adj = tile.adj;
            var tmp_adj = tile.adj;
            switch (flip) {
                Flip.HOR => {
                    std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.NORTH)][0..]);
                    std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.SOUTH)][0..]);
                    tmp_sides[@enumToInt(aoc.Dir.Name.WEST)] = sides[@enumToInt(aoc.Dir.Name.EAST)];
                    tmp_sides[@enumToInt(aoc.Dir.Name.EAST)] = sides[@enumToInt(aoc.Dir.Name.WEST)];
                    std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.EAST)][0..]);
                    std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.WEST)][0..]);
                    std.mem.swap(?usize, &adj[@enumToInt(aoc.Dir.Name.EAST)], &adj[@enumToInt(aoc.Dir.Name.WEST)]);
                },
                Flip.VERT => {
                    std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.WEST)][0..]);
                    std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.EAST)][0..]);
                    tmp_sides[@enumToInt(aoc.Dir.Name.NORTH)] = sides[@enumToInt(aoc.Dir.Name.SOUTH)];
                    tmp_sides[@enumToInt(aoc.Dir.Name.SOUTH)] = sides[@enumToInt(aoc.Dir.Name.NORTH)];
                    std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.NORTH)][0..]);
                    std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.SOUTH)][0..]);
                    std.mem.swap(?usize, &adj[@enumToInt(aoc.Dir.Name.NORTH)], &adj[@enumToInt(aoc.Dir.Name.SOUTH)]);
                },
                else => {},
            }
            sides = tmp_sides;

            for (dirs) |_, i| {
                tmp_sides[i] = sides[aoc.Dir.nextCCW(i, rot)];
                tmp_adj[i] = adj[aoc.Dir.nextCCW(i, rot)];
            }

            aoc.debugfmt("\nROT: {}\n", .{rot});
            aoc.debugfmt("FLIP: {}\n", .{flip});
            aoc.debugfmt("SIDES: \n", .{});
            for (tmp_sides) |side| {
                printTileSlice(side[0..]);
                aoc.debugfmt("\n", .{});
            }
            const valid = checkSides(tiles, grid, grid_width, p, tmp_adj, tmp_sides);

            // now apply manipulations to image data
            if (valid) {
                // for (tile.sides) |side| {
                //     printTileSlice(side[0..]);
                //     aoc.debugfmt("\n", .{});
                // }
                aoc.debugfmt("{} {} {}\n", .{ tile.id, flip, rot });
                printTile(tile.data[0..], tile_width);
                aoc.debugfmt("\n", .{});
                tile.sides = tmp_sides;
                tile.pos = p;
                tile.adj = tmp_adj;
                grid[@intCast(u32, p.y * @intCast(i64, grid_width) + p.x)] = tile_index;

                flipData(tile.data[0..], tile_width, flip);

                var newdata = try allocator.alloc(u1, tile_width * tile_width);
                defer allocator.free(newdata);

                rotateData(&newdata, tile.data[0..], tile_width, rot);
                std.mem.copy(u1, tile.data[0..], newdata);
                return;
            }
        }
    }
    return aoc.Error.InvalidInput;
}

fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
    _ = args;

    var tiles = std.ArrayList(Tile).init(allocator);
    defer tiles.deinit();

    try parseTiles(&tiles, input);

    matchTiles(&tiles);

    var answer: u64 = 1;
    for (tiles.items) |tile| {
        var unknown: u32 = 0;
        for (tile.adj) |v| {
            unknown += @boolToInt(v == null);
        }
        if (unknown == 2) answer *= tile.id;
    }

    return try std.fmt.allocPrint(allocator, "{}", .{answer});
}

fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
    _ = args;

    var tiles = std.ArrayList(Tile).init(allocator);
    defer tiles.deinit();

    try parseTiles(&tiles, input);

    matchTiles(&tiles);

    var grid = try allocator.alloc(?usize, tiles.items.len);
    std.mem.set(?usize, grid, null);
    defer allocator.free(grid);
    var grid_width = @intCast(u32, std.math.sqrt(tiles.items.len));

    var left = std.ArrayList(usize).init(allocator);
    defer left.deinit();

    for (tiles.items) |_, tile_index| {
        try left.append(tile_index);
    }

    // add a corner as first item to add onto
    for (tiles.items) |tile, tile_index| {
        var unknown: u32 = 0;
        for (tile.adj) |v| {
            unknown += @boolToInt(v == null);
        }
        if (unknown == 2) {
            try manipulateAndPlace(allocator, tiles.items, grid, grid_width, aoc.Pos{ .x = 0, .y = 0 }, tile_index);
            _ = left.swapRemove(tile_index);
            break;
        }
    }

    // find adjacents and manipulate until they fit
    next_tile: while (left.items.len > 0) {
        if (aoc.debug) printGrid(tiles.items, grid, grid_width);

        for (grid) |_, gi| {
            aoc.debugfmt("POS {}\n", .{gi});
            const tile_index: ?usize = grid[gi] orelse continue;
            aoc.debugfmt("POS {} YES\n", .{gi});

            var placed = &tiles.items[tile_index.?];
            for (placed.adj) |want, dir| {
                if (want == null) continue;
                // aoc.debugfmt("LOOKING FOR {}\n", .{want.?});
                // for (left.items) |item| {
                //     aoc.debugfmt("> {}\n", .{item});
                // }
                if (std.mem.indexOfScalar(usize, left.items, want.?)) |left_index| {
                    const new_index = left.items[left_index];
                    const new_tile = tiles.items[new_index];
                    var npos = placed.pos.add(dirs[dir]);
                    aoc.debugfmt("TRYING TO PLACE {} NEW AT: {} {}\n", .{ new_tile.id, npos.x, npos.y });

                    try manipulateAndPlace(allocator, tiles.items, grid, grid_width, npos, new_index);

                    _ = left.swapRemove(left_index);
                    continue :next_tile;
                }
            }
        }
        return aoc.Error.InvalidInput;
    }

    if (aoc.debug) printGrid(tiles.items, grid, grid_width);

    // convert grid to image
    var image = try allocator.alloc(u1, grid.len * (tile_width - 2) * (tile_width - 2));
    defer allocator.free(image);

    const image_width = grid_width * (tile_width - 2);
    var y: u32 = 0;
    while (y < grid_width) : (y += 1) {
        var x: u32 = 0;
        while (x < grid_width) : (x += 1) {
            var tile = tiles.items[grid[y * grid_width + x].?];
            var doff = (y * grid_width * (tile_width - 2) + x) * (tile_width - 2);
            var dy: u32 = 1;
            while (dy < tile_width - 1) : (dy += 1) {
                var dx: u32 = 1;
                while (dx < tile_width - 1) : (dx += 1) {
                    image[doff + (dy - 1) * image_width + (dx - 1)] = tile.data[dy * tile_width + dx];
                }
            }
        }
    }

    y = 0;
    while (y < grid_width * (tile_width - 2)) : (y += 1) {
        printTileSlice(image[y * grid_width * (tile_width - 2) .. (y + 1) * grid_width * (tile_width - 2)]);
        aoc.debugfmt("\n", .{});
    }

    // rotate image till we find a sea monster
    var image_copy = try allocator.dupe(u1, image);
    defer allocator.free(image_copy);

    var rot: usize = 0;
    while (rot < 4) : (rot += 1) {
        for (flips) |flip| {
            flipData(image, image_width, flip);
            rotateData(&image_copy, image, image_width, rot);

            y = 0;
            var count: u32 = 0;
            while (y < image_width - seamonster.len) : (y += 1) {
                var x: u32 = 0;
                check_next: while (x < image_width - seamonster[0].len) : (x += 1) {
                    var sy: u32 = 0;
                    while (sy < seamonster.len) : (sy += 1) {
                        var sx: u32 = 0;
                        while (sx < seamonster[0].len) : (sx += 1) {
                            if (seamonster[sy][sx] == '#' and image_copy[(y + sy) * image_width + (x + sx)] != 1)
                                continue :check_next;
                        }
                    }
                    count += 1;
                }
            }

            if (count > 0) {
                var image_count = std.mem.count(u1, image_copy, ([_]u1{1})[0..]);
                var seamonster_count: usize = 0;
                var sy: u32 = 0;
                while (sy < seamonster.len) : (sy += 1) {
                    seamonster_count += std.mem.count(u8, seamonster[sy], "#");
                }
                const answer = image_count - count * seamonster_count;
                return try std.fmt.allocPrint(allocator, "{}", .{answer});
            }
        }
    }

    return null;
}

pub const main = aoc.main(part1, part2, .{ "54755174472007", "1692" });