Module aoc::year2017::day13

Packet Scanners

This problem is similar to Year 2016 Day 15. However the key difference is that we need to avoid the scanners, so the Chinese Remainder Theorem is not applicable.

Part one checks that we can calculate the period for each scanner which is 2 * (range - 1). For example a scanner with range 3 will be at the top position at time 0, 4, 8 and so on.

To avoid a brute force approach for part two we sieve possible values for each scanner sorted in ascending order of period. To combine the previous sieved values with the next scanner, we find the least common multiple of their ranges. Then we “stretch” the sieved values to cover the new range, by adding multiples of the factor between the previous range and the new lcm. Finally any values that would collide with the new scanner are filtered out.

Using the sample data:

   0: 3       1  2
   1: 2  =>   0  4
   4: 4       4  6
   6: 4       6  6

Starting value is [1]. First scanner:

• Lcm of 1 and 2 => 2
• Stretch [1] => [1+0 1+1] => [1 2]
• Filter [1 2] => [2]

Second scanner:

• Lcm of 2 and 4 => 4
• Stretch [2] => [2+0 2+2] => [2 4]
• Filter [2 4] => [2]

Third scanner:

• Lcm of 4 and 6 => 12
• Stretch [2] => [2+0 2+4 2+8] => [2 6 10]
• Filter [2 6 10] => [6 10]

Fourth scanner:

• Lcm of 12 and 6 => 12
• Stretch [6 10] => [6+0 10+0] => [6 10]
• Filter [6 10] => [10]

The lowest remaining value is our answer 10.

Functions

• parse
  Sorts scanners in ascending order of range.
• part1
  Leaving at time zero the packet will encounter each scanner at time depth.
• part2
  Sieves possible values at each scanner stage to reduce the number of possible values.

Type Aliases

• Input 🔒