Module day23

Source
Expand description

§A Long Walk

The longest path problem is NP-hard and requires an exhaustive search through all possible permutations. To speed things up we use several tricks to reduce the complexity.

§Compression

First we “compress” the maze into a much smaller simpler graph. For example the following maze converts into a undirected weighted graph.

    #.#####
    #....##    Start - A - B
    ##.#.## =>         |   |
    ##....#            C - D - End   (edge weights are 2)
    #####.#

Each actual input forms a graph of the same shape but with different edge weights that looks like:

    Start -  a - b - c - d - e
             |   |   |   |   | \
             f - A - B - C - D - g
             |   |   |   |   |   |
             h - E - F - G - H - k
             |   |   |   |   |   |
             m - K - M - N - P - n
             |   |   |   |   |   |
             p - Q - R - S - T - q
               \ |   |   |   |   |
                 r - s - t - u - v - End

§Conversion to grid

Next we convert this graph into a 6 x 6 square graph that can represented in an array. The start and end are moved to the corners and extra nodes added to the other corners.

    Start - b - c - d - e - e`
        |   |   |   |   |   |
        f - A - B - C - D - g
        |   |   |   |   |   |
        h - E - F - G - H - k
        |   |   |   |   |   |
        m - K - M - N - P - n
        |   |   |   |   |   |
        p - Q - R - S - T - q
        |   |   |   |   |   |
        p`- r - s - t - u - End

§Dynamic programming

For a 6x6 grid graph there are 1262816 total possible rook walks, given by OEIS A007764. However since we want the longest path it only makes sense to consider the paths that visit the most possible nodes, in this case 35 (we have to skip 1). There are only 10180 of these paths making it much faster.

A row by row dynamic programming approach from top to bottom finds these paths. For each row we calculate all possible next rows. Interestingly it turns out that there are only 76 possible different rows. Then at each y coordinate we deduplicate rows to find the maximum value. This is the most important optimisation as it means that each row is at most 76 elements instead of growing exponentially (76², 76³, …)

§Example paths

Using S to represents the start of a line segment and E to represent the end, the starting state looks like S..... and the end state .....S. One example:

   Start    S..... |
   Row 0    ..SS.E └─┐┌─┐
   Row 1    S..S.E ┌─┘|.|
   Row 2    ..SSE. └─┐|┌┘
   Row 3    SE...S ┌┐└┘└┐
   Row 4    S..... |└───┘
   Row 5    .....S └────┐
   End      .....S      |

Another example:

   Start    S..... |
   Row 0    .SSESE └┐┌┐┌┐
   Row 1    S.SESE ┌┘||||
   Row 2    ...SSE └─┘|||
   Row 3    S.E..S ┌─┐└┘|
   Row 4    S..... |.└──┘
   Row 5    .....S └────┐
   End      .....S      |

§Next row generation

To create the next row from a given row, there are 5 possibilites for each of the 6 columns.

§Leave a blank space, skipping over the column.

We do this at most once per row. For example:

    Previous .SSESE └┐┌┐┌┐
    Current  .....S .└┘└┘|
                    ^ Blank space

§Start a new (start, end) pair of lines.

All lines must eventually connect so we must create lines in pairs. For example:

    Previous .....S └────┐
    Current  S...ES ┌───┐|
                    ^   ^
                    New pair

§Continue a straight line down from the previous row.

The line stays the same kind (S or E).

    Previous .....S └────┐
    Current  S...ES ┌───┐|
                         ^ Continuation

§Move a previous downwards line to the left or right into a different column.

The line stays the same kind (S or E).

    Previous .....S └────┐
    Current  S..... ┌────┘
                    ^ Move

§Join two open segments from a previous row.

A restriction is that we can’t create closed cycles that don’t connect to the start or end, as this would skip several nodes. For example this is not allowed:

    Previous .....S |┌───┐
    Current  S..... |└───┘
                     ^ Closed cycles not allowed

We implement this by not joining any (S, E) pairs in that order. Joing the reverse order (E, S) is allowed.

Finally there are two special rules when joining two nested line segments. When joining (S, S) the next E convert to an S to maintain balance.

    Previous S..E ┌──┐
    Previous SSEE |┌┐|
    Current  ..SE └┘||

When joining (E, E) the previous S convert to an E to maintain balance.

    Previous S..E ┌──┐
    Previous SSEE |┌┐|
    Current  SE.. ||└┘

Structs§

Graph 🔒
Undirected weighted graph representing the compressed maze.
Input
Distilled two dimensional array of only weights.

Functions§

compress 🔒
Convert maze to undirected graph.
dfs 🔒
Modified depth first search that only allows rows that skip one node.
graph_to_grid 🔒
Convert graph to 6 x6 two dimensional array of weights.
parse
Simplify input for faster processing.
part1
The graph is directed so the only allowed steps are down or to the right. The maximum value for any cell is the maximum of either the cell to the left or above.
part2
Graph is undirected so we can also move up or to the right.

Type Aliases§

Row 🔒
We only use 6 elements but 8 is faster to hash.