const std = @import("std");
const PATH = "input/day20.txt";
const Str = []const u8;
const TileData = [10][10]bool;
const Tile = struct {
id: u16,
data: TileData,
// rotating left
fn rotate(self: *@This()) void {
var rotated: TileData = undefined;
for (self.data) |line, row| {
for (line) |item, col| {
rotated[self.data.len - 1 - col][row] = item;
}
}
self.data = rotated;
}
fn flip(self: *@This(), axis: u1) void {
var flipped: TileData = undefined;
switch (axis) {
0 => return,
1 => {
// horizontal flip
for (self.data) |slice, row| {
flipped[self.data.len - 1 - row] = slice;
}
},
}
self.data = flipped;
}
};
const Image = struct {
tiles: []Tile,
size: u8 = undefined,
visited: std.AutoHashMap(u16, void),
current_tile: [2]u8 = .{ 0, 0 },
order: std.ArrayList(usize),
fn checkLeft(self: @This(), candidate: Tile) bool {
// left column is always good
if (self.current_tile[1] == 0) return true;
// last item's right side should be equal to candidate left side
for (candidate.data) |_, row| {
if (self.tiles[self.order.items[self.order.items.len - 1]]
.data[row][candidate.data.len - 1] != candidate.data[row][0]) return false;
}
return true;
}
fn checkUpper(self: @This(), candidate: Tile) bool {
// top row is always good
if (self.current_tile[0] == 0) return true;
// index of the upper element in self.order
const upper = (self.current_tile[0] - 1) * self.size + self.current_tile[1];
// compare upper last line with candidate's first line
return std.mem.eql(
bool,
&self.tiles[self.order.items[upper]].data[candidate.data.len - 1],
&candidate.data[0],
);
}
fn solve(self: *@This()) bool {
// all item in place
if (self.current_tile[0] == self.size) {
return true;
}
var idx: usize = 0;
while (idx < self.tiles.len) : (idx += 1) {
const candidate = self.tiles[idx];
if (self.visited.contains(candidate.id)) {
// next 8 item has the same id, skip them!
// while adds one more, so it is 7 here
idx += 7;
continue;
}
if (!self.checkUpper(candidate)) continue;
if (!self.checkLeft(candidate)) continue;
self.order.append(idx) catch unreachable;
self.visited.put(candidate.id, {}) catch unreachable;
// move current_tile forward
const old_tile = self.current_tile;
if (self.current_tile[1] != self.size - 1) {
self.current_tile[1] += 1;
} else {
self.current_tile[0] += 1;
self.current_tile[1] = 0;
}
if (self.solve()) {
return true;
} else {
// restore items
_ = self.order.pop();
_ = self.visited.remove(candidate.id);
self.current_tile = old_tile;
}
}
return false;
}
fn bigImage(self: @This()) [8 * SIZE][8 * SIZE]bool {
var ret: [8 * SIZE][8 * SIZE]bool = undefined;
for (self.order.items) |oidx, i| {
const start_row = i / SIZE * 8;
const start_col = i % SIZE * 8;
// std.debug.print("idx: {d} srow: {d} scol: {d}\n", .{oidx, start_row, start_col});
for (self.tiles[oidx].data) |line, row| {
if (row == 0 or row == 9) continue;
for (line[1..9]) |item, col| {
ret[start_row + row - 1][start_col + col] = item;
}
}
}
return ret;
}
};
fn bigRotate(big: [8 * SIZE][8 * SIZE]bool) [8 * SIZE][8 * SIZE]bool {
var rotated: [8 * SIZE][8 * SIZE]bool = undefined;
for (big) |line, row| {
for (line) |item, col| {
rotated[big.len - 1 - col][row] = item;
}
}
return rotated;
}
fn bigFlip(big: [8 * SIZE][8 * SIZE]bool, axis: u1) [8 * SIZE][8 * SIZE]bool {
var flipped: [8 * SIZE][8 * SIZE]bool = undefined;
switch (axis) {
0 => return big,
1 => {
// horizontal flip
for (big) |slice, row| {
flipped[big.len - 1 - row] = slice;
}
},
}
return flipped;
}
pub fn first(allocator: ?std.mem.Allocator) anyerror!usize {
var image = Image{
.tiles = undefined,
.visited = std.AutoHashMap(u16, void).init(allocator.?),
.order = std.ArrayList(usize).init(allocator.?),
};
image.tiles = try parseInput(allocator.?, @embedFile(PATH));
defer {
allocator.?.free(image.tiles);
image.visited.deinit();
image.order.deinit();
}
image.size = @intCast(u8, std.math.sqrt(image.tiles.len / 8));
if (!image.solve()) unreachable;
var mul: usize = 1;
for ([_]usize{
0,
image.size - 1,
image.size * image.size - image.size,
image.size * image.size - 1,
}) |order_no| {
mul *= image.tiles[image.order.items[order_no]].id;
}
return mul;
}
const SIZE = 12;
pub fn second(allocator: ?std.mem.Allocator) anyerror!usize {
var image = Image{
.tiles = undefined,
.visited = std.AutoHashMap(u16, void).init(allocator.?),
.order = std.ArrayList(usize).init(allocator.?),
};
image.tiles = try parseInput(allocator.?, @embedFile(PATH));
defer {
allocator.?.free(image.tiles);
image.visited.deinit();
image.order.deinit();
}
image.size = @intCast(u8, std.math.sqrt(image.tiles.len / 8));
if (!image.solve()) unreachable;
var big = image.bigImage();
var monsters: usize = 0;
var habitat: usize = 0;
for ([_]u1{ 0, 1 }) |flip| {
big = bigFlip(big, flip);
for ([_]u2{ 0, 1, 2, 3 }) |rotate| {
big = bigRotate(big);
// Monster search...
for (big) |line, row| {
ears: for (line) |item, col| {
if (flip == 0 and rotate == 0 and item == true) habitat += 1;
// ear is on .{-1, 18}
if (col < 18) continue;
// after ear we move one right
if (col >= big.len - 1) continue;
// after ear we move two down
if (row >= big.len - 2) continue;
if (item == true) {
const tailRow = row + 1;
const tailCol = col - 18;
for (monster_offsets) |diff| {
if (big[tailRow + diff[0]][tailCol + diff[1]] != true) continue :ears;
}
monsters += 1;
}
}
}
if (monsters > 0) return habitat - monsters * 15;
}
}
unreachable;
}
// O
// X ## ## ###
// # # # # # #
//
// check for ears (marked with O first), then move .{1, -18} to tail (marked with X)
// and try these positions...
// zig fmt: off
const monster_offsets = [_][2]u8{
.{ 0, 0 }, .{ 0, 5 }, .{ 0, 6 }, .{ 0, 11 }, .{ 0, 12 }, .{ 0, 17 }, .{ 0, 18 }, .{ 0, 19 },
.{ 1, 1 }, .{ 1, 4 }, .{ 1, 7 }, .{ 1, 10 }, .{ 1, 13 }, .{ 1, 16 } };
// zig fmt: on
fn parseInput(allocator: std.mem.Allocator, input: Str) anyerror![]Tile {
var ret = std.ArrayList(Tile).init(allocator);
var lines = std.mem.split(u8, input, "\n");
var t: Tile = undefined;
var l_no: usize = 0;
while (lines.next()) |line| {
if (line.len == 0) {
try flipRotate(&ret, &t);
l_no = 0;
t = undefined;
continue;
}
switch (line[0]) {
'T' => {
t.id = try std.fmt.parseUnsigned(u16, line[5..9], 10);
},
'.', '#' => {
for (line) |ch, idx| {
switch (ch) {
'.' => t.data[l_no][idx] = false,
'#' => t.data[l_no][idx] = true,
else => unreachable,
}
}
l_no += 1;
},
else => unreachable,
}
}
// add the last item...
try flipRotate(&ret, &t);
return ret.toOwnedSlice();
}
fn flipRotate(ret: *std.ArrayList(Tile), t: *Tile) !void {
for ([_]u1{ 0, 1 }) |flip| {
t.flip(flip);
for ([_]u2{ 0, 1, 2, 3 }) |_| {
t.rotate();
try ret.append(t.*);
}
}
}
test "day20a" {
try std.testing.expectEqual(@as(usize, 83775126454273), try first(std.testing.allocator));
}
test "day20b" {
try std.testing.expectEqual(@as(usize, 1993), try second(std.testing.allocator));
}
const test_input =
\\Tile 2311:
\\..##.#..#.
\\##..#.....
\\#...##..#.
\\####.#...#
\\##.##.###.
\\##...#.###
\\.#.#.#..##
\\..#....#..
\\###...#.#.
\\..###..###
\\
\\Tile 1951:
\\#.##...##.
\\#.####...#
\\.....#..##
\\#...######
\\.##.#....#
\\.###.#####
\\###.##.##.
\\.###....#.
\\..#.#..#.#
\\#...##.#..
\\
\\Tile 1171:
\\####...##.
\\#..##.#..#
\\##.#..#.#.
\\.###.####.
\\..###.####
\\.##....##.
\\.#...####.
\\#.##.####.
\\####..#...
\\.....##...
\\
\\Tile 1427:
\\###.##.#..
\\.#..#.##..
\\.#.##.#..#
\\#.#.#.##.#
\\....#...##
\\...##..##.
\\...#.#####
\\.#.####.#.
\\..#..###.#
\\..##.#..#.
\\
\\Tile 1489:
\\##.#.#....
\\..##...#..
\\.##..##...
\\..#...#...
\\#####...#.
\\#..#.#.#.#
\\...#.#.#..
\\##.#...##.
\\..##.##.##
\\###.##.#..
\\
\\Tile 2473:
\\#....####.
\\#..#.##...
\\#.##..#...
\\######.#.#
\\.#...#.#.#
\\.#########
\\.###.#..#.
\\########.#
\\##...##.#.
\\..###.#.#.
\\
\\Tile 2971:
\\..#.#....#
\\#...###...
\\#.#.###...
\\##.##..#..
\\.#####..##
\\.#..####.#
\\#..#.#..#.
\\..####.###
\\..#.#.###.
\\...#.#.#.#
\\
\\Tile 2729:
\\...#.#.#.#
\\####.#....
\\..#.#.....
\\....#..#.#
\\.##..##.#.
\\.#.####...
\\####.#.#..
\\##.####...
\\##..#.##..
\\#.##...##.
\\
\\Tile 3079:
\\#.#.#####.
\\.#..######
\\..#.......
\\######....
\\####.#..#.
\\.#...#.##.
\\#.#####.##
\\..#.###...
\\..#.......
\\..#.###...
;