day_06.zig (6630B)
1 const std = @import("std"); 2 const debug = std.debug; 3 const fmt = std.fmt; 4 const mem = std.mem; 5 const math = std.math; 6 7 pub fn main() !void { 8 var allocator = &std.heap.DirectAllocator.init().allocator; 9 10 var result1 = try biggest_finite_area(allocator, coordinates); 11 debug.assert(result1 == 2342); 12 debug.warn("06-1: {}\n", result1); 13 14 var result2 = try safe_area(coordinates, 10000); 15 debug.assert(result2 == 43302); 16 debug.warn("06-2: {}\n", result2); 17 } 18 19 fn safe_area(coords: []const V2, distance_threshold: usize) !u32 { 20 var max = point(0, 0); 21 for (coords) |c| { 22 //V2.print(c); 23 if (c.x > max.x) { 24 max.x = c.x; 25 } 26 if (c.y > max.y) { 27 max.y = c.y; 28 } 29 } 30 31 const field_stride = max.x + 1; 32 const field_size: usize = field_stride * (max.y + 1); 33 34 var area: u32 = 0; 35 var cell_i: usize = 0; 36 while (cell_i < field_size) : (cell_i += 1) { 37 var distance_sum: usize = 0; 38 for (coords) |coord, coord_i| { 39 var dist = try manhattan_distance(point_from_index(cell_i, field_stride), coord); 40 distance_sum += dist; 41 if (distance_sum >= distance_threshold) { 42 break; 43 } 44 } 45 if (distance_sum < distance_threshold) { 46 area += 1; 47 } 48 } 49 50 return area; 51 } 52 53 test "safe area" { 54 const test_threshold: usize = 32; 55 debug.assert(16 == try safe_area(test_coords, test_threshold)); 56 } 57 58 fn biggest_finite_area(allocator: *mem.Allocator, coords: []const V2) !u32 { 59 var max = point(0, 0); 60 for (coords) |c| { 61 //V2.print(c); 62 if (c.x > max.x) { 63 max.x = c.x; 64 } 65 if (c.y > max.y) { 66 max.y = c.y; 67 } 68 } 69 70 var field_stride = max.x + 1; 71 var field = try allocator.alloc(isize, field_stride * (max.y + 1)); 72 defer allocator.free(field); 73 74 for (field) |*cell, cell_i| { 75 cell.* = -1; 76 var closest_distance = field.len * 1000; 77 78 for (coords) |coord, coord_i| { 79 var dist = try manhattan_distance(point_from_index(cell_i, field_stride), coord); 80 if (dist < closest_distance) { 81 closest_distance = dist; 82 cell.* = @intCast(isize, coord_i); 83 } else if (dist == closest_distance) { 84 // when a cell of the field contains -1, this represents a tie 85 cell.* = -1; 86 } 87 } 88 } 89 90 var coord_counts = try allocator.alloc(isize, coords.len); 91 defer allocator.free(coord_counts); 92 for (coord_counts) |*count| { 93 count.* = 0; 94 } 95 96 for (field) |cell, cell_i| { 97 if (cell < 0) { 98 continue; 99 } 100 101 var current_cell = point_from_index(cell_i, field_stride); 102 103 if (current_cell.x == 0 104 or current_cell.y == 0 105 or current_cell.x >= max.x 106 or current_cell.y >= max.y) { 107 // when a coord_count contains -1, this means that the area of that 108 // coord is infinite 109 coord_counts[@intCast(usize, cell)] = -1; 110 } else { 111 if (coord_counts[@intCast(usize, cell)] != -1) { 112 coord_counts[@intCast(usize, cell)] += 1; 113 } 114 } 115 } 116 117 var max_area: isize = 0; 118 var max_coord: usize = 0; 119 for (coord_counts) |count, coord_i| { 120 //debug.warn("[{}]: {}\n", coord_i, count); 121 if (count > max_area) { 122 max_area = count; 123 max_coord = coord_i; 124 } 125 } 126 debug.assert(max_area >= 0); 127 128 return @intCast(u32, max_area); 129 } 130 131 test "biggest finite area" { 132 var allocator = &std.heap.DirectAllocator.init().allocator; 133 debug.assert(17 == try biggest_finite_area(allocator, test_coords)); 134 } 135 136 fn point_from_index(i: usize, stride: usize) V2 { 137 var x: u32 = @intCast(u32, i % stride); 138 var y: u32 = @intCast(u32, @divTrunc(i, stride)); 139 return V2 { 140 .x = x, 141 .y = y 142 }; 143 } 144 145 // 0 1 2 3 4 146 // 5 6 7 8 9 147 // 10 11 12 13 14 148 test "point from index" { 149 debug.assert(0 == point_from_index(0, 5).x); 150 debug.assert(0 == point_from_index(0, 5).y); 151 152 debug.assert(1 == point_from_index(6, 5).x); 153 debug.assert(1 == point_from_index(6, 5).y); 154 155 debug.assert(2 == point_from_index(7, 5).x); 156 debug.assert(1 == point_from_index(7, 5).y); 157 158 debug.assert(4 == point_from_index(14, 5).x); 159 debug.assert(2 == point_from_index(14, 5).y); 160 } 161 162 fn manhattan_distance(p1: V2, p2: V2) !u32 { 163 var x_dist = (try math.absInt(@intCast(i32, p1.x) - @intCast(i32, p2.x))); 164 var y_dist = (try math.absInt(@intCast(i32, p1.y) - @intCast(i32, p2.y))); 165 return @intCast(u32, x_dist + y_dist); 166 } 167 168 test "manhattan" { 169 debug.assert(5 == try manhattan_distance(point(1, 1), point(3, 4))); 170 debug.assert(5 == try manhattan_distance(point(3, 4), point(1, 1))); 171 debug.assert(0 == try manhattan_distance(point(13, 14), point(13, 14))); 172 } 173 174 const V2 = struct { 175 x: u32, 176 y: u32, 177 178 fn print(self: V2) void { 179 debug.warn("({}, {})\n", self.x, self.y); 180 } 181 }; 182 183 inline fn point(x: u32, y: u32) V2 { 184 return V2 { 185 .x = x, 186 .y = y, 187 }; 188 } 189 190 const test_coords = []const V2 { 191 point(1, 1), 192 point(1, 6), 193 point(8, 3), 194 point(3, 4), 195 point(5, 5), 196 point(8, 9), 197 }; 198 199 const coordinates = comptime block: { 200 break :block []V2{ 201 point(67, 191), 202 point(215, 237), 203 point(130, 233), 204 point(244, 61), 205 point(93, 93), 206 point(145, 351), 207 point(254, 146), 208 point(260, 278), 209 point(177, 117), 210 point(89, 291), 211 point(313, 108), 212 point(145, 161), 213 point(143, 304), 214 point(329, 139), 215 point(153, 357), 216 point(217, 156), 217 point(139, 247), 218 point(304, 63), 219 point(202, 344), 220 point(140, 302), 221 point(233, 127), 222 point(260, 251), 223 point(235, 46), 224 point(357, 336), 225 point(302, 284), 226 point(313, 260), 227 point(135, 40), 228 point(95, 57), 229 point(227, 202), 230 point(277, 126), 231 point(163, 99), 232 point(232, 271), 233 point(130, 158), 234 point(72, 289), 235 point(89, 66), 236 point(94, 111), 237 point(210, 184), 238 point(139, 58), 239 point(99, 272), 240 point(322, 148), 241 point(209, 111), 242 point(170, 244), 243 point(230, 348), 244 point(112, 200), 245 point(287, 55), 246 point(320, 270), 247 point(53, 219), 248 point(42, 52), 249 point(313, 205), 250 point(166, 259), 251 }; 252 };