Module day23

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 optimization 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 possibilities 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. Joining 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.