day_10.zig (15824B)
1 const std = @import("std"); 2 const debug = std.debug; 3 const mem = std.mem; 4 5 const debug_logging: bool = false; 6 7 pub fn main() !void { 8 var allocator = &std.heap.DirectAllocator.init().allocator; 9 10 debug.warn("10-1:"); 11 try printMessage(allocator, input_lights); 12 13 const result2 = try getTimeOfSmallestBoundingArea(allocator, input_lights); 14 debug.warn("10-2: {}\n", result2); 15 } 16 17 fn printMessage(allocator: *mem.Allocator, lights: []const Light) !void { 18 var message_time = try getTimeOfSmallestBoundingArea(allocator, lights); 19 var lights_prime = try getLightsAtTime(allocator, lights, message_time); 20 printLights(lights_prime); 21 } 22 23 test "print message" { 24 var allocator = debug.global_allocator; 25 try printMessage(allocator, test_lights); 26 } 27 28 fn printLights(lights: []const Light) void { 29 var bound = getBoundingArea(lights); 30 31 debug.warn("\n"); 32 var cursor = bound.nw; 33 while (cursor.y <= bound.se.y) : (cursor.y += 1) { 34 cursor.x = bound.nw.x; 35 while (cursor.x <= bound.se.x) : (cursor.x += 1) { 36 var light_is_here: bool = false; 37 for (lights) |l| { 38 if (V2.equal(l.p, cursor)) { 39 light_is_here = true; 40 debug.warn("#"); 41 break; 42 } 43 } 44 if (!light_is_here) { 45 debug.warn("."); 46 } 47 } 48 debug.warn("\n"); 49 } 50 debug.warn("\n"); 51 } 52 53 /// Caller responsible for freeing returned buffer 54 fn getLightsAtTime(allocator: *mem.Allocator, lights: []const Light, time: u64) ![]Light { 55 var lights_prime = try allocator.alloc(Light, lights.len); 56 mem.copy(Light, lights_prime, lights); 57 58 for (lights_prime) |*l| { 59 l.p = V2.add(l.p, V2.scale(l.v, @intCast(i64, time))); 60 } 61 62 return lights_prime; 63 } 64 65 fn getTimeOfSmallestBoundingArea(allocator: *mem.Allocator, lights: []const Light) !u64 { 66 var time: u64 = 0; 67 var area = getBoundingArea(lights).area(); 68 var last_area: isize = 0; 69 70 while (true) { 71 last_area = area; 72 time += 1; 73 74 var lights_prime = try getLightsAtTime(allocator, lights, time); 75 defer allocator.free(lights_prime); 76 77 area = getBoundingArea(lights_prime).area(); 78 if (area > last_area) { 79 break; 80 } 81 } 82 83 return time - 1; 84 } 85 86 test "get time of smallest bounding area" { 87 var allocator = debug.global_allocator; 88 debug.assert(3 == try getTimeOfSmallestBoundingArea(allocator, test_lights)); 89 } 90 91 fn getBoundingArea(lights: []const Light) Rect { 92 var min = V2.init(@maxValue(i64), @maxValue(i64)); 93 var max = V2.init(@minValue(i64), @minValue(i64)); 94 95 for (lights) |l| { 96 if (l.p.x < min.x) { 97 min.x = l.p.x; 98 } else if (l.p.x > max.x) { 99 max.x = l.p.x; 100 } 101 if (l.p.y < min.y) { 102 min.y = l.p.y; 103 } else if (l.p.y > max.y) { 104 max.y = l.p.y; 105 } 106 } 107 108 debug.assert(min.x < max.x); 109 debug.assert(min.y < max.y); 110 111 var area = Rect { 112 .nw = min, 113 .se = max, 114 }; 115 return area; 116 } 117 118 test "get bounding area" { 119 debug.assert(352 == getBoundingArea(test_lights).area()); 120 } 121 122 const Light = struct { 123 p: V2, 124 v: V2, 125 }; 126 127 const Rect = struct { 128 nw: V2, 129 se: V2, 130 131 pub fn area(self: Rect) isize { 132 var xdim = self.se.x - self.nw.x + 1; 133 var ydim = self.se.y - self.nw.y + 1; 134 return xdim * ydim; 135 } 136 }; 137 138 const V2 = struct { 139 x: i64, 140 y: i64, 141 142 pub fn init(_x: i64, _y: i64) V2 { 143 return V2 { 144 .x = _x, 145 .y = _y, 146 }; 147 } 148 149 pub fn equal(self: V2, other: V2) bool { 150 return (self.x == other.x and self.y == other.y); 151 } 152 153 pub fn add(vec1: V2, vec2: V2) V2 { 154 return V2.init(vec1.x + vec2.x, vec1.y + vec2.y); 155 } 156 157 pub fn scale(self: V2, scalar: i64) V2 { 158 return V2.init(self.x * scalar, self.y * scalar); 159 } 160 161 pub fn print(v: V2) void { 162 logDebug("({}, {})\n", v.x, v.y); 163 } 164 }; 165 166 test "v2 add" { 167 debug.assert(V2.equal(V2.init(1, 3), V2.add(V2.init(0, 0), V2.init(1, 3)))); 168 debug.assert(V2.equal(V2.init(299, 11), V2.add(V2.init(-23, 14), V2.init(322, -3)))); 169 } 170 171 test "v2 scale" { 172 debug.assert(V2.equal(V2.init(0, 0), V2.init(0, 0).scale(100))); 173 debug.assert(V2.equal(V2.init(-2400, 3000), V2.init(-24, 30).scale(100))); 174 debug.assert(V2.equal(V2.init(-1, 1), V2.init(1, -1).scale(-1))); 175 } 176 177 fn logDebug(comptime format_str: []const u8, args: ...) void { 178 if (debug_logging) { 179 debug.warn(format_str, args); 180 } 181 } 182 183 inline fn light(px: i64, py: i64, vx: i64, vy: i64) Light { 184 return Light { 185 .p = V2.init(px, py), 186 .v = V2.init(vx, vy), 187 }; 188 } 189 190 const test_lights = []Light { 191 light( 9, 1, 0, 2), 192 light( 7, 0, -1, 0), 193 light( 3, -2, -1, 1), 194 light( 6, 10, -2, -1), 195 light( 2, -4, 2, 2), 196 light(-6, 10, 2, -2), 197 light( 1, 8, 1, -1), 198 light( 1, 7, 1, 0), 199 light(-3, 11, 1, -2), 200 light( 7, 6, -1, -1), 201 light(-2, 3, 1, 0), 202 light(-4, 3, 2, 0), 203 light(10, -3, -1, 1), 204 light( 5, 11, 1, -2), 205 light( 4, 7, 0, -1), 206 light( 8, -2, 0, 1), 207 light(15, 0, -2, 0), 208 light( 1, 6, 1, 0), 209 light( 8, 9, 0, -1), 210 light( 3, 3, -1, 1), 211 light( 0, 5, 0, -1), 212 light(-2, 2, 2, 0), 213 light( 5, -2, 1, 2), 214 light( 1, 4, 2, 1), 215 light(-2, 7, 2, -2), 216 light( 3, 6, -1, -1), 217 light( 5, 0, 1, 0), 218 light(-6, 0, 2, 0), 219 light( 5, 9, 1, -2), 220 light(14, 7, -2, 0), 221 light(-3, 6, 2, -1), 222 }; 223 224 const input_lights = []Light { 225 light( 31766, -52454, -3, 5), 226 light(-52374, -41935, 5, 4), 227 light( 31758, -31427, -3, 3), 228 light(-41862, 31671, 4, -3), 229 light( 10747, -41934, -1, 4), 230 light( 21267, 42181, -2, -4), 231 light( 52759, -20913, -5, 2), 232 light( 31734, 52701, -3, -5), 233 light(-41823, 31669, 4, -3), 234 light(-52346, 42184, 5, -4), 235 light(-20801, -52451, 2, 5), 236 light( 31760, -20904, -3, 2), 237 light(-31356, -10397, 3, 1), 238 light(-41823, -41934, 4, 4), 239 light( 10724, -10389, -1, 1), 240 light(-31344, -31427, 3, 3), 241 light(-41826, 42186, 4, -4), 242 light(-52393, 42186, 5, -4), 243 light( 42281, 52698, -4, -5), 244 light( 10700, -10398, -1, 1), 245 light( 21259, 31667, -2, -3), 246 light( 21215, 31662, -2, -3), 247 light(-10294, 10635, 1, -1), 248 light( 31734, -10392, -3, 1), 249 light( 52764, 52698, -5, -5), 250 light(-52394, 21148, 5, -2), 251 light(-20809, -31428, 2, 3), 252 light(-52333, 31666, 5, -3), 253 light( 31787, -20913, -3, 2), 254 light( 52776, -10391, -5, 1), 255 light(-52393, -52449, 5, 5), 256 light( 31768, 52701, -3, -5), 257 light( 31734, 21155, -3, -2), 258 light(-41847, -52455, 4, 5), 259 light( 21220, 21147, -2, -2), 260 light( 42273, 10640, -4, -1), 261 light( 10753, 52696, -1, -5), 262 light(-10309, -10389, 1, 1), 263 light( 42241, 21149, -4, -2), 264 light( 52806, 52701, -5, -5), 265 light(-20801, 31670, 2, -3), 266 light( 10720, 21152, -1, -2), 267 light( 31737, 42181, -3, -4), 268 light(-31332, -20913, 3, 2), 269 light(-10321, 52695, 1, -5), 270 light(-10294, 31664, 1, -3), 271 light(-10331, -41943, 1, 4), 272 light( 52788, -10397, -5, 1), 273 light( 52766, -31428, -5, 3), 274 light(-31332, -52458, 3, 5), 275 light(-31356, -20909, 3, 2), 276 light(-10329, -52453, 1, 5), 277 light(-31346, -31419, 3, 3), 278 light( 31787, 10638, -3, -1), 279 light( 10736, 21152, -1, -2), 280 light( 21255, -31419, -2, 3), 281 light(-31308, 31669, 3, -3), 282 light(-52386, 42186, 5, -4), 283 light(-10314, -20912, 1, 2), 284 light( 31766, -41938, -3, 4), 285 light( 42273, 21149, -4, -2), 286 light( 21255, -31419, -2, 3), 287 light(-41860, -41934, 4, 4), 288 light(-20817, -31421, 2, 3), 289 light( 21231, 52695, -2, -5), 290 light(-20793, 21151, 2, -2), 291 light( 42274, 31671, -4, -3), 292 light(-31353, 10636, 3, -1), 293 light( 21235, -41937, -2, 4), 294 light( 21251, -52452, -2, 5), 295 light( 42289, -20905, -4, 2), 296 light( 52766, 31666, -5, -3), 297 light(-52357, 52701, 5, -5), 298 light(-52386, -41935, 5, 4), 299 light( 42260, -20913, -4, 2), 300 light(-20836, 42180, 2, -4), 301 light(-52386, 31670, 5, -3), 302 light( 10757, -10390, -1, 1), 303 light( 10752, 42183, -1, -4), 304 light(-52381, 10633, 5, -1), 305 light(-31332, 31667, 3, -3), 306 light( 21237, 52701, -2, -5), 307 light( 10731, -41934, -1, 4), 308 light( 31787, -31425, -3, 3), 309 light( 52757, -41943, -5, 4), 310 light(-52374, 52698, 5, -5), 311 light(-52338, -52456, 5, 5), 312 light(-20844, 42178, 2, -4), 313 light(-20825, -52456, 2, 5), 314 light(-52367, -10389, 5, 1), 315 light( 10744, 52697, -1, -5), 316 light( 10704, -52457, -1, 5), 317 light( 31766, 42186, -3, -4), 318 light( 52761, -10390, -5, 1), 319 light( 31777, -20904, -3, 2), 320 light(-41818, -41938, 4, 4), 321 light(-52370, 10637, 5, -1), 322 light( 21267, 10639, -2, -1), 323 light(-52382, -10394, 5, 1), 324 light(-52370, 42180, 5, -4), 325 light( 21223, -31428, -2, 3), 326 light(-20845, -20913, 2, 2), 327 light( 52812, 21148, -5, -2), 328 light( 42241, -41935, -4, 4), 329 light( 52814, 52696, -5, -5), 330 light(-31316, -10398, 3, 1), 331 light( 52776, 10636, -5, -1), 332 light(-41823, 21148, 4, -2), 333 light( 52788, -10391, -5, 1), 334 light(-52370, 42186, 5, -4), 335 light( 10721, 52701, -1, -5), 336 light( 10744, 42185, -1, -4), 337 light( 21219, -41939, -2, 4), 338 light(-52378, -52451, 5, 5), 339 light( 31758, -20911, -3, 2), 340 light(-31332, 52697, 3, -5), 341 light(-10329, 31671, 1, -3), 342 light(-31308, 42179, 3, -4), 343 light( 31726, -20911, -3, 2), 344 light( 42275, 52701, -4, -5), 345 light(-20829, 21149, 2, -2), 346 light( 10706, 52696, -1, -5), 347 light(-31312, 52701, 3, -5), 348 light(-31364, -10397, 3, 1), 349 light(-41855, 42179, 4, -4), 350 light(-41823, 31665, 4, -3), 351 light(-31362, -10389, 3, 1), 352 light( 42273, -20912, -4, 2), 353 light( 10700, -52453, -1, 5), 354 light( 52788, 21149, -5, -2), 355 light(-10324, -31424, 1, 3), 356 light(-31356, -31423, 3, 3), 357 light( 10725, 52701, -1, -5), 358 light(-52343, 42186, 5, -4), 359 light(-31324, -31425, 3, 3), 360 light( 52799, -31419, -5, 3), 361 light( 10716, -52458, -1, 5), 362 light(-20849, 10638, 2, -1), 363 light(-52378, -20905, 5, 2), 364 light( 52764, -10391, -5, 1), 365 light( 31726, 10635, -3, -1), 366 light( 31750, -20907, -3, 2), 367 light(-31344, 10636, 3, -1), 368 light(-41839, -10397, 4, 1), 369 light(-52333, 52701, 5, -5), 370 light( 52780, -41939, -5, 4), 371 light( 42242, 10641, -4, -1), 372 light( 10728, -20909, -1, 2), 373 light( 52780, -41943, -5, 4), 374 light( 31766, -41939, -3, 4), 375 light(-20846, -41934, 2, 4), 376 light(-31303, 10640, 3, -1), 377 light( 42282, -41934, -4, 4), 378 light( 52780, -20907, -5, 2), 379 light( 31726, -20908, -3, 2), 380 light(-10310, 31666, 1, -3), 381 light(-31316, -41940, 3, 4), 382 light(-20801, 10635, 2, -1), 383 light(-41859, -10396, 4, 1), 384 light( 31750, 31669, -3, -3), 385 light(-52370, 21151, 5, -2), 386 light(-31312, -52449, 3, 5), 387 light(-20821, -10389, 2, 1), 388 light( 10744, 42179, -1, -4), 389 light( 31766, -20909, -3, 2), 390 light(-41870, 52692, 4, -5), 391 light(-52366, 31671, 5, -3), 392 light(-31364, -41938, 3, 4), 393 light(-31324, 52700, 3, -5), 394 light( 42289, -52449, -4, 5), 395 light(-10298, 21156, 1, -2), 396 light( 21212, 31662, -2, -3), 397 light( 10696, -20907, -1, 2), 398 light( 52776, 52699, -5, -5), 399 light( 42261, 52697, -4, -5), 400 light( 21235, -20905, -2, 2), 401 light(-52334, 42181, 5, -4), 402 light( 52777, -31428, -5, 3), 403 light( 10716, 31665, -1, -3), 404 light( 52817, -41943, -5, 4), 405 light( 52798, -41934, -5, 4), 406 light(-52338, 52696, 5, -5), 407 light(-52338, 42178, 5, -4), 408 light( 31787, 42186, -3, -4), 409 light(-31356, -52454, 3, 5), 410 light( 21259, 31667, -2, -3), 411 light(-20807, 10641, 2, -1), 412 light(-31319, 10641, 3, -1), 413 light( 31746, 31667, -3, -3), 414 light(-31324, 31671, 3, -3), 415 light(-10278, -10398, 1, 1), 416 light(-10286, 42181, 1, -4), 417 light( 42257, -10390, -4, 1), 418 light(-52354, 10641, 5, -1), 419 light(-20845, -31423, 2, 3), 420 light( 21220, -31424, -2, 3), 421 light( 21230, -20904, -2, 2), 422 light(-52392, -41934, 5, 4), 423 light(-20793, 52694, 2, -5), 424 light( 10744, -41941, -1, 4), 425 light( 31758, 42185, -3, -4), 426 light(-20788, 21149, 2, -2), 427 light(-52346, -31428, 5, 3), 428 light( 31729, -20908, -3, 2), 429 light( 52804, -20909, -5, 2), 430 light(-20841, 52697, 2, -5), 431 light(-20820, -41934, 2, 4), 432 light(-20829, -41936, 2, 4), 433 light(-52375, 10632, 5, -1), 434 light(-41874, 42184, 4, -4), 435 light( 52756, 52700, -5, -5), 436 light( 42265, 42184, -4, -4), 437 light(-31364, 31668, 3, -3), 438 light(-10310, 42178, 1, -4), 439 light( 10716, -52454, -1, 5), 440 light( 31774, -41937, -3, 4), 441 light(-52389, 10638, 5, -1), 442 light( 31747, 52692, -3, -5), 443 light(-31316, -52457, 3, 5), 444 light( 52760, -31423, -5, 3), 445 light(-31305, 21151, 3, -2), 446 light( 10736, -31421, -1, 3), 447 light(-10326, 10634, 1, -1), 448 light(-41847, -20905, 4, 2), 449 light(-10286, 31666, 1, -3), 450 light( 31787, -20906, -3, 2), 451 light( 42290, -31419, -4, 3), 452 light( 21223, -10394, -2, 1), 453 light(-31306, -10394, 3, 1), 454 light(-20801, 21149, 2, -2), 455 light( 31753, -52449, -3, 5), 456 light( 31787, 21151, -3, -2), 457 light(-10314, 10634, 1, -1), 458 light( 42284, 21156, -4, -2), 459 light( 21235, 10632, -2, -1), 460 light( 21228, 31671, -2, -3), 461 light(-20825, 21147, 2, -2), 462 light( 31758, 21153, -3, -2), 463 light(-31305, -20909, 3, 2), 464 light( 42241, 42184, -4, -4), 465 light(-20801, 31663, 2, -3), 466 light( 52796, -52453, -5, 5), 467 light(-10334, -31423, 1, 3), 468 light( 52764, -31425, -5, 3), 469 light( 10720, -10393, -1, 1), 470 light(-20844, -31422, 2, 3), 471 light( 10704, 10635, -1, -1), 472 light( 42250, 52696, -4, -5), 473 light(-10273, 52695, 1, -5), 474 light( 10698, 31662, -1, -3), 475 light(-10278, 10638, 1, -1), 476 light( 21211, 52693, -2, -5), 477 light( 42298, -31424, -4, 3), 478 light(-10326, 52701, 1, -5), 479 light( 31760, 31671, -3, -3), 480 light( 10752, 10641, -1, -1), 481 light(-10313, -10398, 1, 1), 482 light(-31311, 31671, 3, -3), 483 light( 42273, -31422, -4, 3), 484 light( 10720, 42184, -1, -4), 485 light(-20845, 31670, 2, -3), 486 light(-31347, 10641, 3, -1), 487 light(-10332, 52692, 1, -5), 488 light(-31332, -31419, 3, 3), 489 light( 42293, 21156, -4, -2), 490 light(-31353, 10632, 3, -1), 491 light(-31316, 52699, 3, -5), 492 light(-31364, 21149, 3, -2), 493 light(-10278, 21156, 1, -2), 494 light( 42302, -31427, -4, 3), 495 light( 21219, -41942, -2, 4), 496 light( 31731, 52701, -3, -5), 497 light( 42241, -20909, -4, 2), 498 light(-31344, -10397, 3, 1), 499 light( 42277, -20904, -4, 2), 500 light(-10274, -41939, 1, 4), 501 light( 31782, -52450, -3, 5), 502 light(-41876, 31667, 4, -3), 503 light( 10749, -20904, -1, 2), 504 light( 21224, -20911, -2, 2), 505 light( 31734, 31662, -3, -3), 506 light( 21231, 10635, -2, -1), 507 light(-52389, -31419, 5, 3), 508 light( 31734, -41937, -3, 4), 509 light( 42257, -20905, -4, 2), 510 light( 42297, 52697, -4, -5), 511 light( 52805, 21156, -5, -2), 512 light( 10709, -20910, -1, 2), 513 light(-52370, -31420, 5, 3), 514 light(-10326, 21152, 1, -2), 515 };