1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
const std = @import("std");
const print = std.debug.print;
const assert = std.debug.assert;
const ArrayList = std.ArrayList;
const HashMap = std.HashMap;
const mem = std.mem;
const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace);
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
const Map = []const []const u8;
fn cnt_diff(lhs: []const u8, rhs: []const u8) i64 {
var cnt: i64 = 0;
for (lhs, rhs) |l, b| {
if (l != b) {
cnt += 1;
}
}
return cnt;
}
fn transpose(map: Map) Map {
var transposed = allocator.alloc([]u8, map[0].len) catch unreachable;
for (transposed) |*trow| {
trow.* = allocator.alloc(u8, map.len) catch unreachable;
}
for (map, 0..) |row, i| {
for (row, 0..) |c, j| {
transposed[j][i] = c;
}
}
return transposed;
}
fn check_eql(map: Map, i_: usize, j_: usize, tolerance_: i64) bool {
var i = i_;
var j = j_;
var tolerance = tolerance_;
while (i >= 0 and j < map.len) : ({
i = if (i > 0) i - 1 else break;
j += 1;
}) {
tolerance -= cnt_diff(map[i], map[j]);
if (tolerance < 0) {
return false;
}
}
return tolerance == 0;
}
fn evaluate(map: Map, tolerance: i64) u64 {
const h = map.len;
const w = map[0].len;
// per row
for (0..h - 1, 1..) |i, j| {
if (check_eql(map, i, j, tolerance)) {
return 100 * j;
}
}
// per column
const transposed = transpose(map);
for (0..w - 1, 1..) |i, j| {
if (check_eql(transposed, i, j, tolerance)) {
return j;
}
}
unreachable;
}
pub fn solve(maps: []const Map) void {
var part1: u64 = 0;
for (maps) |map| {
part1 += evaluate(map, 0);
}
print("{d}\n", .{part1});
var part2: u64 = 0;
for (maps) |map| {
part2 += evaluate(map, 1);
}
print("{d}\n", .{part2});
}
pub fn main() !void {
var splitMirros = mem.splitSequence(u8, fin, "\n\n");
var maps = ArrayList([]const []const u8).init(allocator);
while (splitMirros.next()) |mirror| {
var splitLines = mem.splitScalar(u8, mirror, '\n');
var map = ArrayList([]const u8).init(allocator);
while (splitLines.next()) |line| {
try map.append(line);
}
try maps.append(map.items);
}
solve(maps.items);
}
|
