advent-of-code

Solutions for Advent of Code.
git clone git://git.amin.space/advent-of-code.git
Log | Files | Refs | LICENSE

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 };