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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
|
const std = @import("std");
pub fn main() !void {
try std.fmt.format(std.io.getStdOut().writer(), "day 10 pt1: {}\n", .{try solve_pt1(std.heap.page_allocator, puzzle_input)});
}
const Direction = enum { north, east, south, west,
fn opp(self: Direction) Direction {
return switch (self) {
.north => .south,
.east => .west,
.south => .north,
.west => .east,
};
}
};
const Cell = enum(u8) {
NS = '|',
WE = '-',
NE = 'L',
NW = 'J',
SW = '7',
SE = 'F',
Ground = '.',
Start = 'S',
_,
fn next(self: Cell, whence: Direction) ?Direction {
// return switch (self) {
// .NS => switch (whence) {
// .north => .South,
// .south => .North,
// else => null,
// },
// else => null,
// };
// std.log.warn("whence {} cell {}", .{whence, self});
return switch (whence) {
.north => switch (self) {
.NS => .south,
.NE => .east,
.NW => .west,
else => null,
},
.east => switch (self) {
.WE => .west,
.NE => .north,
.SE => .south,
else => null,
},
.south => switch (self) {
.NS => .north,
.SW => .west,
.SE => .east,
else => null,
},
.west => switch (self) {
.WE => .east,
.NW => .north,
.SW => .south,
else => null,
},
};
}
};
const Coord = struct {
x: i64,
y: i64,
fn move(self: Coord, dir: Direction) Coord {
return switch (dir) {
.north => .{ .x = self.x, .y = self.y - 1 },
.south => .{ .x = self.x, .y = self.y + 1 },
.east => .{ .x = self.x + 1, .y = self.y },
.west => .{ .x = self.x - 1, .y = self.y },
};
}
};
const Path = struct {
grid: *const Grid,
current: Coord,
// Doesn't include .current
trail: std.ArrayList(Coord),
// direction we travelled to get to .current
whence: Direction,
};
const Grid = struct {
data: []const u8,
width: usize,
height: usize,
fn parse(input: []const u8) !Grid {
return .{
.data = input,
.width = std.mem.indexOfScalar(u8, input, '\n') orelse return error.Foo,
.height = std.mem.count(u8, input, "\n") + 1,
};
}
fn get(self: Grid, c: Coord) ?Cell {
if (c.x < 0) return null;
if (c.y < 0) return null;
if (c.x >= self.width) return null;
if (c.y >= self.height) return null;
return @enumFromInt(self.data[@intCast(c.x + (c.y * (@as(i64, @intCast(self.width)) + 1)))]); // skip the newline
}
fn findStart(self: Grid) ?Coord {
for (0..self.width) |x| {
for (0..self.height) |y| {
const coord: Coord = .{ .x = @intCast(x), .y = @intCast(y) };
//std.log.warn("checking {any} for start", .{coord});
if (self.get(coord) == .Start) {
return coord;
}
}
}
return null;
}
};
fn solve_pt1(a: std.mem.Allocator, input: []const u8) !u64 {
// read the Grid
// find the start pos
// setup 4 Paths on each NESW from S and follow them through, one of them
// will link up back to S.
// half the trail length gives the answer.
const grid = try Grid.parse(input);
// std.log.warn("grid width {} height {}", .{ grid.width, grid.height });
const start: Coord = grid.findStart() orelse return error.NoStart;
const loop: Path = lp1: for (std.enums.values(Direction)) |dir| {
const st = start.move(dir);
// std.log.warn("st {any}", .{st});
_ = grid.get(st) orelse continue :lp1;
var trail = std.ArrayList(Coord).init(a);
defer trail.deinit();
try trail.append(start);
var path: Path = .{
.current = st,
.grid = &grid,
.trail = trail,
.whence = dir.opp(),
};
while (true) {
const cell: Cell = grid.get(path.current) orelse {
// std.log.warn("out of bounds", .{});
continue :lp1;
}; // out of bounds
if (cell == .Start) break :lp1 Path{
.current = path.current,
.grid = path.grid,
.trail = try trail.clone(),
.whence = path.whence,
}; // we found it yay
const dirn = cell.next(path.whence) orelse {
// std.log.warn("pipe mismatch", .{});
continue :lp1;
}; // pipes don't match up
const newpos = path.current.move(dirn);
path.whence = dirn.opp();
try trail.append(path.current);
path.current = newpos;
}
} else {
return error.NoLoop;
};
defer loop.trail.deinit();
// std.log.warn("loop {any}", .{loop});
return loop.trail.items.len / 2;
}
test "pt1_1" {
try std.testing.expectEqual(@as(u64, 4), try solve_pt1(std.testing.allocator, test_input1));
}
const test_input1 =
\\.....
\\.S-7.
\\.|.|.
\\.L-J.
\\.....
;
const puzzle_input = @embedFile("day10.in");
|
