Module day20

Race Condition

Examining the input shows that there is only a single path from start to finish with no branches. This simplifies checking for shortcuts as any empty space will be on the shortest path from start to end. The cheating rules allow us to “warp” up to n squares away to any empty space as measured by manhattan distance.

For part one this is a distance of 2. When checking surrounding squares we make 2 optimizations:

• Don’t check any squares only 1 away as we can always just move to these normally.
• Checking from point p => q is always the negative of q => p, e.g if p = 30, q = 50 then p => q = 20 and q => p = -20. This means we only ever need to check any pair once.
• Additionally we only need to check down and right. Previous rows and columns will already have checked points above and to the left when we reach an empty square.

      #         .
     ###       ...
    ##P## =>  ....#
     ###       ...
      #         #

For part two the distance is increased to 20 and the shape now resembles a wonky diamond. This shape ensures complete coverage without duplicating checks.

     #        .
    ###      ...
   ##P## => ..P##
    ###      ###
     #        #

Functions

• check 🔒
• parse
  Create a grid the same size as input with the time taken from start to any location.
• part1
• part2
  Searches for all cheats up to distance 20, parallelizing the work over multiple threads.
• worker 🔒