-
Notifications
You must be signed in to change notification settings - Fork 1
/
day13.c3
149 lines (141 loc) · 3.78 KB
/
day13.c3
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/*
* Advent of Code 2023 day 13
*/
import std::io;
import std::time;
import std::math;
fn void main()
{
io::printn("Advent of code, day 13.");
@pool()
{
// Simple benchmarking with Clock, "mark" returns the last duration and resets the clock
Clock c = clock::now();
io::printfn("* Sum part 1: %d - completed in %s", solve_part(1), c.mark());
io::printfn("* Sum part 2: %d - completed in %s", solve_part(2), c.mark());
};
}
fn bool check(int[] lines, int candidate)
{
int len = lines.len;
// What is the range we're checking up and down?
int max_check = math::min(len - candidate - 2, candidate);
for (int i = 0; i < max_check; i++)
{
// If the lines don't match that's an error.
if (lines[i + candidate + 2] != lines[candidate - i - 1]) return false;
}
return true;
}
// Doing the check but requiring a smudge!
fn bool check_smudge(int[] lines, int candidate)
{
int len = lines.len;
// Again, what's the max span to check.
int max_check = math::min(len - candidate - 2, candidate);
// Auto init to false
bool smudge;
for (int i = 0; i < max_check; i++)
{
// Let's pick the bit diff
int diff = lines[i + candidate + 2] ^ lines[candidate - i - 1];
switch
{
case diff == 0:
// If the diff is zero then then match, all's well.
continue;
case !smudge && diff.popcount() == 1:
// If they only mismatch on 1 bit and there is no smudge detected,
// we now have a smudge. Horray!
smudge = true;
continue;
default:
// Too big a diff or smudge already found -> failed
return false;
}
}
// Only return true if we found a smudge!
return smudge;
}
fault SolveFault
{
NO_SOLVE
}
fn int! solve(int[] lines)
{
int len = lines.len;
// Work through all lines.
for (int i = 0; i < len - 1; i++)
{
// If two consequent lines match, we might have detected a mirror.
if (lines[i] == lines[i + 1] && check(lines, i)) return i + 1;
}
return SolveFault.NO_SOLVE?;
}
// Let's solve requiring exactly 1 smudge.
fn int! solve_smudged(int[] lines)
{
int len = lines.len;
for (int i = 0; i < len - 1; i++)
{
// Create the bit diff
int diff = lines[i] ^ lines[i + 1];
switch
{
case diff == 0:
// If the diff is zero, we want to check assuming the smudge comes later.
if (check_smudge(lines, i)) return i + 1;
case diff.popcount() == 1:
// If the diff is 1 bit, then we want to check assuming no smudge
if (check(lines, i)) return i + 1;
default:
// Anything else just look again.
continue;
}
}
// Return that the solve failed.
return SolveFault.NO_SOLVE?;
}
fn long solve_part(int part)
{
File f = file::open("day13.txt", "rb")!!;
defer (void)f.close();
long sum;
while OUTER: (true)
{
// Keep two variants of the map, where one is turned 90 degrees,
// so that both can be solved with the same algorithm.
int[32] vertical;
int[32] horizontal;
int lines = 0;
int width;
while (try line = io::treadline(&f))
{
// Empty line -> we're done reading.
if (line.len == 0) break;
// Update width
width = line.len;
foreach (i, c : line)
{
if (c != '#') continue;
// Pack into bits, we assume width and height <= 32
horizontal[lines] |= 1 << i;
vertical[i] |= 1 << lines;
}
lines++;
}
// If we got zero lines, that's because we reached EOF reading nothing.
if (!lines) break;
// Solve first with the horizontal stack, multiplying by 100. If that
// result was instead SolveFault.NO_SOLVE, then ?? makes the code
// try the vertical stack instead. We finally use !! because we know one of them should work!
if (part == 1)
{
sum += (solve(horizontal[:lines]) * 100 ?? solve(vertical[:width]))!!;
continue;
}
// This is the same as above, but using solve_smudged.
sum += (solve_smudged(horizontal[:lines]) * 100 ?? solve_smudged(vertical[:width]))!!;
}
return sum;
}