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
|
const std = @import("std");
pub fn main() !void {
try std.fmt.format(std.io.getStdOut().writer(), "day 11 pt1: {}\n", .{try solve_pt1(std.heap.page_allocator, puzzle_input)});
try std.fmt.format(std.io.getStdOut().writer(), "day 11 pt2: {}\n", .{try solve_pt2(std.heap.page_allocator, puzzle_input)});
}
const Coord = struct {
x: usize,
y: usize,
};
inline fn get(grid: []const u8, width: usize, x: usize, y: usize) u8 {
return grid[y*(width+1) + x];
}
fn solve_pt1(a: std.mem.Allocator, input: []const u8) !u64 {
return solve(a, input, 2);
}
fn solve_pt2(a: std.mem.Allocator, input: []const u8) !u64 {
return solve(a, input, 1000000);
}
fn solve(a: std.mem.Allocator, input: []const u8, multiplier: usize) !u64 {
const width: usize = std.mem.indexOfScalar(u8, input, '\n') orelse return error.BadInput;
const height: usize = (input.len / width + 1) - 1;
// std.log.warn("width {} height {}", .{width, height});
const x_adjust = try a.alloc(usize, width);
defer a.free(x_adjust);
const y_adjust = try a.alloc(usize, height);
defer a.free(y_adjust);
var galaxies = std.ArrayList(Coord).init(a);
defer galaxies.deinit();
var x_adj: usize = 0;
for (0..width) |x| {
var allspace = true;
for (0..height) |y| {
const ch = get(input, width, x, y);
if (ch == '#') {
try galaxies.append(.{.x = x, .y = y});
allspace = false;
}
}
if (allspace) {
x_adj += (multiplier-1);
}
x_adjust[x] = x_adj;
}
var y_adj:usize = 0;
for (0..height) |y| {
var allspace = true;
for (0..width) |x| {
const ch = get(input, width, x, y);
if (ch == '#') {
allspace = false;
}
}
if (allspace) {
y_adj += (multiplier-1);
}
y_adjust[y] = y_adj;
}
for (galaxies.items) |*gal| {
const x = gal.x;
const y = gal.y;
gal.* = .{
.x = x + x_adjust[x],
.y = y + y_adjust[y],
};
}
var sum: usize = 0;
for (0..galaxies.items.len) |ix1| {
for (ix1..galaxies.items.len) |ix2| {
const g1 = galaxies.items[ix1];
const g2 = galaxies.items[ix2];
const x_diff = @max(g1.x, g2.x) - @min(g1.x, g2.x);
const y_diff = @max(g1.y, g2.y) - @min(g1.y, g2.y);
sum += x_diff + y_diff;
}
}
return sum;
}
test "pt1" {
try std.testing.expectEqual(@as(u64, 374), try solve_pt1(std.testing.allocator, test_input));
}
test "pt2" {
try std.testing.expectEqual(@as(u64, 1030), try solve(std.testing.allocator, test_input, 10));
}
test "pt2_2" {
try std.testing.expectEqual(@as(u64, 8410), try solve(std.testing.allocator, test_input, 100));
}
const test_input =
\\...#......
\\.......#..
\\#.........
\\..........
\\......#...
\\.#........
\\.........#
\\..........
\\.......#..
\\#...#.....
;
const puzzle_input = @embedFile("day11.in");
|
