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