advent-of-code

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

day_07.zig (10915B)


      1 const std = @import("std");
      2 const debug = std.debug;
      3 const mem = std.mem;
      4 
      5 pub fn main() !void {
      6     var allocator = &std.heap.DirectAllocator.init().allocator;
      7 
      8     const result1 = try step_dependency_order(allocator, dependency_hierarchy);
      9     defer allocator.free(result1);
     10     debug.warn("07-1: {}\n", result1);
     11 
     12     const result2 = try step_completion_time(allocator, dependency_hierarchy, 5, 60);
     13     debug.warn("07-2: {}\n", result2);
     14 }
     15 
     16 fn step_completion_time(allocator: *mem.Allocator, rules: []const Rule, num_workers: u32, base_step_time: u32) !u32 {
     17     const step_range = set_of_all_steps(rules);
     18     const largest_letter = step_range[step_range.len - 1];
     19 
     20     var workers = try allocator.alloc(Worker, num_workers);
     21     defer allocator.free(workers);
     22     for (workers) |*w| {
     23         w.step = Worker.idle;
     24         w.seconds_worked = 0;
     25     }
     26 
     27     var completed_steps = try allocator.alloc(u8, step_range.len);
     28     defer allocator.free(completed_steps);
     29     var num_steps_completed: usize = 0;
     30 
     31     var current_second: u32 = 0;
     32     while (num_steps_completed < completed_steps.len) : (current_second += 1) {
     33         //debug.warn("{}: ", current_second);
     34         //for (workers) |w| {
     35         //    debug.warn("{c} ", w.step);
     36         //}
     37         //debug.warn("{}\n", completed_steps);
     38 
     39         for (workers) |*w| {
     40             // do work for this second
     41             if (w.step != Worker.idle) {
     42                 w.seconds_worked += 1;
     43                 debug.assert(w.seconds_worked <= step_time(w.step, base_step_time));
     44 
     45                 // check for completed steps
     46                 if (w.seconds_worked == step_time(w.step, base_step_time)) {
     47                     completed_steps[num_steps_completed] = w.step;
     48                     num_steps_completed += 1;
     49                     w.step = Worker.idle;
     50                     w.seconds_worked = 0;
     51                 }
     52             }
     53         }
     54 
     55         const awaiting_steps = try available_steps(allocator, completed_steps[0..num_steps_completed], workers, step_range, rules);
     56         defer allocator.free(awaiting_steps);
     57         var num_awaiting_steps_taken: u32 = 0;
     58 
     59         for (workers) |*w| {
     60             if (w.step == Worker.idle) {
     61                 if (num_awaiting_steps_taken < awaiting_steps.len) {
     62                     w.step = awaiting_steps[num_awaiting_steps_taken];
     63                     num_awaiting_steps_taken += 1;
     64                 }
     65             }
     66         }
     67     }
     68 
     69     return current_second - 1;
     70 }
     71 
     72 test "step completion time" {
     73     var allocator = &std.heap.DirectAllocator.init().allocator;
     74     debug.assert(15 == try step_completion_time(allocator, test_hierarchy, 2, 0));
     75 }
     76 
     77 fn available_steps(allocator: *mem.Allocator, completed_steps: []u8, workers: []Worker, step_range: []const u8, rules: []const Rule) ![]const u8 {
     78     var steps_to_return = std.ArrayList(u8).init(allocator);
     79 
     80     if (completed_steps.len == step_range.len - 1) {
     81         // We've reached the end. There's only one uncompleted step.
     82         for (step_range) |s| {
     83             var step_is_done = false;
     84             for (completed_steps) |done| {
     85                 if (done == s) {
     86                     step_is_done = true;
     87                 }
     88             }
     89             if (!step_is_done) {
     90                 try steps_to_return.append(s);
     91                 return steps_to_return.toSliceConst();
     92             }
     93         }
     94     }
     95 
     96     debug.assert(rules.len < 1000);
     97     var relevant_rules_array = []bool{true} ** 1000;
     98     var relevant_rules = relevant_rules_array[0..rules.len];
     99 
    100     // cull irrelevant rules
    101     for (completed_steps) |s| {
    102         for (rules) |r, i| {
    103             if (r.p == s) {
    104                 relevant_rules[i] = false;
    105             }
    106         }
    107     }
    108 
    109     // Make sure we didn't cull rules inconsistently
    110     for (completed_steps) |s| {
    111         for (rules) |r, i| {
    112             if (relevant_rules[i]) {
    113                 debug.assert(r.p != s);
    114                 debug.assert(r.c != s);
    115             }
    116         }
    117     }
    118 
    119     // an available step is one that:
    120     //    - exists in the rules as a parent
    121     //    - does not exist in the rules as a child
    122     //    - is not the current step of any worker
    123     for(step_range) |step| {
    124         var step_exists_as_parent: bool = false;
    125         var step_exists_as_child: bool = false;
    126         var step_is_being_worked_on: bool = false;
    127 
    128         for (rules) |r, i| {
    129             if (relevant_rules[i]) {
    130                 if (step == r.p) {
    131                     step_exists_as_parent = true;
    132                 } else if (step == r.c) {
    133                     step_exists_as_child = true;
    134                 }
    135             }
    136         }
    137 
    138         for (workers) |w| {
    139             if (w.step == step) {
    140                 step_is_being_worked_on = true;
    141             }
    142         }
    143 
    144         if (step_exists_as_parent and !step_exists_as_child and !step_is_being_worked_on) {
    145             try steps_to_return.append(step);
    146         }
    147     }
    148 
    149     return steps_to_return.toSliceConst();
    150 }
    151 
    152 const Worker = struct {
    153     step: u8,
    154     seconds_worked: u32,
    155     const idle: u8 = '.';
    156 };
    157 
    158 fn step_time(step: u8, base_step_time: u32) u32 {
    159     debug.assert(step >= 'A');
    160     debug.assert(step <= 'Z');
    161     const step_alphabet_number = step - 'A' + 1;
    162     return step_alphabet_number + base_step_time;
    163 }
    164 
    165 test "step time" {
    166     debug.assert(61 == step_time('A', 60));
    167     debug.assert(86 == step_time('Z', 60));
    168     debug.assert(1 == step_time('A', 0));
    169     debug.assert(26 == step_time('Z', 0));
    170 }
    171 
    172 fn step_dependency_order(allocator: *mem.Allocator, rules: []const Rule) ![]const u8 {
    173     const step_range = set_of_all_steps(rules);
    174     const largest_letter = step_range[step_range.len - 1];
    175 
    176     var steps = try allocator.alloc(u8, step_range.len);
    177     for (steps) |*s, i| {
    178         s.* = next_step(steps[0..i], step_range, rules);
    179     }
    180 
    181     return steps;
    182 }
    183 
    184 test "step dependency order" {
    185     var allocator = &std.heap.DirectAllocator.init().allocator;
    186     debug.assert(mem.eql(u8, "CABDFE", try step_dependency_order(allocator, test_hierarchy)));
    187 }
    188 
    189 fn next_step(done_steps: []u8, step_range: []const u8, rules: []const Rule) u8 {
    190     if (done_steps.len == step_range.len - 1) {
    191         // We've reached the end. There's only one undone step.
    192         for (step_range) |s| {
    193             var step_is_done = false;
    194             for (done_steps) |done| {
    195                 if (done == s) {
    196                     step_is_done = true;
    197                 }
    198             }
    199             if (!step_is_done) {
    200                 return s;
    201             }
    202         }
    203     }
    204 
    205     debug.assert(rules.len < 1000);
    206     var relevant_rules_array = []bool{true} ** 1000;
    207     var relevant_rules = relevant_rules_array[0..rules.len];
    208 
    209     // cull irrelevant rules
    210     for (done_steps) |s| {
    211         for (rules) |r, i| {
    212             if (r.p == s) {
    213                 relevant_rules[i] = false;
    214             }
    215         }
    216     }
    217 
    218     // Make sure we didn't cull rules inconsistently
    219     for (done_steps) |s| {
    220         for (rules) |r, i| {
    221             if (relevant_rules[i]) {
    222                 debug.assert(r.p != s);
    223                 debug.assert(r.c != s);
    224             }
    225         }
    226     }
    227 
    228     {
    229         // the next step is the first one alphabetically that:
    230         //    - exists in the rules as a parent
    231         //    - does not exist in the rules as a child
    232         var step: u8 = step_range[0];
    233         while (step <= step_range[step_range.len - 1]) : (step += 1) {
    234             var step_exists_as_parent: bool = false;
    235             var step_exists_as_child: bool = false;
    236             for (rules) |r, i| {
    237                 if (relevant_rules[i]) {
    238                     if (step == r.p) {
    239                         step_exists_as_parent = true;
    240                     } else if (step == r.c) {
    241                         step_exists_as_child = true;
    242                     }
    243                 }
    244             }
    245             if (step_exists_as_parent and !step_exists_as_child) {
    246                 return step;
    247             }
    248         }
    249     }
    250     unreachable;
    251 }
    252 
    253 fn set_of_all_steps(rules: []const Rule) []const u8 {
    254     // This assumes no letters in the alphabetical range are skipped
    255     const letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    256     var largest_letter: u8 = 'A';
    257     for (rules) |r| {
    258         if (r.p > largest_letter) {
    259             largest_letter = r.p;
    260         }
    261         if (r.c > largest_letter) {
    262             largest_letter = r.c;
    263         }
    264     }
    265     var num_letters = largest_letter - 'A' + 1;
    266     var step_range = letters[0..num_letters];
    267     debug.assert(step_range.len <= 26);
    268     return step_range;
    269 }
    270 
    271 const Rule = struct {
    272     p: u8,
    273     c: u8,
    274 };
    275 
    276 inline fn rule(parent: u8, child: u8) Rule {
    277     return Rule {
    278         .p = parent,
    279         .c = child,
    280     };
    281 }
    282 
    283 const test_hierarchy = []const Rule {
    284     rule('C', 'A'),
    285     rule('C', 'F'),
    286     rule('A', 'B'),
    287     rule('A', 'D'),
    288     rule('B', 'E'),
    289     rule('D', 'E'),
    290     rule('F', 'E'),
    291 };
    292 
    293 const dependency_hierarchy = []const Rule {
    294     rule('X', 'C'),
    295     rule('C', 'G'),
    296     rule('F', 'G'),
    297     rule('U', 'Y'),
    298     rule('O', 'S'),
    299     rule('D', 'N'),
    300     rule('M', 'H'),
    301     rule('J', 'Q'),
    302     rule('G', 'R'),
    303     rule('I', 'N'),
    304     rule('R', 'K'),
    305     rule('A', 'Z'),
    306     rule('Y', 'L'),
    307     rule('H', 'P'),
    308     rule('K', 'S'),
    309     rule('Z', 'P'),
    310     rule('T', 'S'),
    311     rule('N', 'P'),
    312     rule('E', 'S'),
    313     rule('S', 'W'),
    314     rule('W', 'V'),
    315     rule('L', 'V'),
    316     rule('P', 'B'),
    317     rule('Q', 'V'),
    318     rule('B', 'V'),
    319     rule('P', 'Q'),
    320     rule('S', 'V'),
    321     rule('C', 'Q'),
    322     rule('I', 'H'),
    323     rule('A', 'E'),
    324     rule('H', 'Q'),
    325     rule('G', 'V'),
    326     rule('N', 'L'),
    327     rule('R', 'Q'),
    328     rule('W', 'L'),
    329     rule('X', 'L'),
    330     rule('X', 'J'),
    331     rule('W', 'P'),
    332     rule('U', 'B'),
    333     rule('P', 'V'),
    334     rule('O', 'P'),
    335     rule('W', 'Q'),
    336     rule('S', 'Q'),
    337     rule('U', 'Z'),
    338     rule('Z', 'T'),
    339     rule('M', 'T'),
    340     rule('A', 'P'),
    341     rule('Z', 'B'),
    342     rule('N', 'S'),
    343     rule('H', 'N'),
    344     rule('J', 'E'),
    345     rule('M', 'J'),
    346     rule('R', 'A'),
    347     rule('A', 'Y'),
    348     rule('F', 'V'),
    349     rule('L', 'P'),
    350     rule('K', 'L'),
    351     rule('F', 'P'),
    352     rule('G', 'L'),
    353     rule('I', 'Q'),
    354     rule('C', 'L'),
    355     rule('I', 'Y'),
    356     rule('G', 'B'),
    357     rule('H', 'L'),
    358     rule('X', 'U'),
    359     rule('I', 'K'),
    360     rule('R', 'N'),
    361     rule('I', 'L'),
    362     rule('M', 'I'),
    363     rule('K', 'V'),
    364     rule('G', 'E'),
    365     rule('F', 'B'),
    366     rule('O', 'Y'),
    367     rule('Y', 'Q'),
    368     rule('F', 'K'),
    369     rule('N', 'W'),
    370     rule('O', 'R'),
    371     rule('N', 'E'),
    372     rule('M', 'V'),
    373     rule('H', 'T'),
    374     rule('Y', 'T'),
    375     rule('F', 'J'),
    376     rule('F', 'O'),
    377     rule('W', 'B'),
    378     rule('T', 'E'),
    379     rule('T', 'P'),
    380     rule('F', 'M'),
    381     rule('U', 'I'),
    382     rule('H', 'S'),
    383     rule('S', 'P'),
    384     rule('T', 'W'),
    385     rule('A', 'N'),
    386     rule('O', 'N'),
    387     rule('L', 'B'),
    388     rule('U', 'K'),
    389     rule('Z', 'W'),
    390     rule('X', 'D'),
    391     rule('Z', 'L'),
    392     rule('I', 'T'),
    393     rule('O', 'W'),
    394     rule('I', 'B'),
    395 };