Module aoc::year2018::day15

Beverage Bandits

This problem is notoriously tricky due to the finicky rules that must be followed precisely and that not all inputs trigger all edge cases. However from a performance aspect most of the time is consumed finding the nearest target whenever a unit needs to move.

For each move we perform two BFS. The first search from the current unit finds the nearest target in reading order. The second reverse search from the target to the current unit finds the correct direction to move.

Since the cave dimensions are 32 x 32 we use a fixed sized array of bitmasks stored in u32 to execute each BFS efficiently. Each step we expand the frontier using the bitwise logic applied to each row:

   (previous | (current << 1) | current | (current >> 1) | next) & !walls

We represent the goal using bits and stop searching once that intersects with the frontier. First example:

• Goblin’s turn.
• We should choose the first target square in reading order (to the right of the nearest elf)
• There are two equal shortest paths to that square, so we should choose the first step in reading order (up).

    Map        Walls      In Range
    #######    1111111    0000000
    #E    #    1000001    0110000
    # E   #    1000001    0111000
    #    G#    1000001    0010000
    #######    1111111    0000000

    Forward BFS frontier                        Intersection
    0000000    0000000    0000000    0000000    0000000
    0000000    0000000    0000010    0000110    0000000
    0000000 => 0000010 => 0000110 => 0001110 => 0001000 <= Choose first target square
    0000010    0000110    0001110    0011110    0010000    in reading order
    0000000    0000000    0000000    0000000    0000000

    Reverse BFS frontier             Intersection
    0000000    0000000    0000000    0000000
    0000000    0001000    0011100    0000000
    0001000 => 0011100 => 0111110 => 0000010 <= Choose first step
    0000000    0001000    0011100    0000100    in reading order
    0000000    0000000    0000000    0000000

Choosing the first intersection in reading order the Goblin correctly moves upwards. Second example:

• Elf’s turn.
• There are two equal shortest paths.
• We should choose the first unit in reading order (left).

    Map             Walls           In Range
    ###########    11111111111    00000000000
    #G..#....G#    10001000001    01100000110
    ###..E#####    11100011111    00000000000
    ###########    11111111111    00000000000

    Forward BFS frontier                                                       Intersection
    00000000000    00000000000    00000000000    00000000000    00000000000    00000000000
    00000000000    00000100000    00000110000    00010111000    00110111100    00100000100
    00000100000 => 00001100000 => 00011100000 => 00011100000 => 00011100000 => 00000000000
    00000000000    00000000000    00000000000    00000000000    00000000000    00000000000

    Reverse BFS frontier                                        Intersection
    00000000000    00000000000    00000000000    00000000000    00000000000
    00100000000    01110000000    01110000000    01110000000    00000000000
    00000000000 => 00000000000 => 00010000000 => 00011000000 => 00001000000
    00000000000    00000000000    00000000000    00000000000    00000000000

Choosing the first intersection in reading order the Elf correctly moves left.

Structs

• Input
• Shared 🔒
  Shared between threads for part two.
• Unit 🔒

Enums

• Kind 🔒

Constants

• READING_ORDER 🔒

Functions

• attack 🔒
  Search for weakest neighboring enemy. Equal health ties are broken in reading order.
• double_bfs 🔒
  Performs two BFS searches. The first search from the current unit finds the nearest target in reading order. The second reverse search from the target to the current unit, finds the correct direction to move.
• expand 🔒
  Use bitwise logic to expand the frontier. Returns a boolean indicating if the frontier actually expanded.
• fight 🔒
  Careful implementation of the game rules.
• intersect 🔒
  Check if we have reached a target, returning the first target in reading order.
• parse
  Parse the input into a bitmask for the cave walls and a list of point coordinates for each Elf and Goblin.
• part1
  Simulate a full fight until only Goblins remain.
• part2
  Find the lowest attack power where no Elf dies. We can short circuit any fight once a single Elf is killed. Since each fight is independent we can parallelize the search over multiple threads.
• set_bit 🔒
  Convenience function to set a single bit from a point’s location.
• worker 🔒