Module aoc::year2016::day22

source ·
Expand description

§Grid Computing

Part two is a decoy that can be solved in constant time with some analysis. Printing the actual node layout shows a structure similar to:

    O......G
    ........
    ..######
    ........
    .....-..
  • O is our destination
  • G is the data
  • # are large nodes that can’t be moved to neighbours, effectively acting as walls.
  • - is the empty node.

First we move the empty spot in front of the data:

    O>>>>>>G
    .^......
    .^######
    .^......
    .<<<<-..

Then we move the data into the empty spot.

    O.....G_
    ........
    ..######
    ........
    ........

Finally we move the data to the origin by repeating the same sequence of 5 moves. First moving the empty spot back around to in front of the data in 4 moves.

    O....^G_
    .....^<v
    ..######
    ........
    ........

Then moving the data another spot to the left.

    O....G_.
    ........
    ..######
    ........
    ........

To find the minimum number of steps we only need to find the (x, y) coordinates of the empty spot and the width of the wall, then add up the sequence of moves.

Structs§

Functions§

  • parse
  • part1
    Filter the used and available space in ascending order to find the viable pairs efficiently.
  • part2