Ponder This Challenge - June 2023 - The temporal cheese maze

A super intelligent mouse is placed in a three dimensional "maze", consisting of a $k\times k\times k$ grid, where the mouse is placed at the beginning at $(1,1,1)$ at time $t=1$.

Every cell in the maze contains one unit of cheese. The catch: This is temporal cheese; it's phasing in and out, and is present only at certain times. If the mouse is at cell $(a,b,c)$ at time $t$ where the cheese is present in the cell, the mouse collects it. Afterwards, the cheese no longer appears in that cell!

At each time unit, the mouse can either stay in place, or move one step in exactly one direction. The maze has walls allowing only movement right, up, and forward on the X, Y, and Z axes, respectively. For example, if present at $(3,5,1)$ at $t=13$, the possible locations for the mouse at $t=14$ are

1. $(3,5,1)$ (waiting in place)
2. $(4,5,1)$ (moving right in the X axis)
3. $(3,6,1)$ (moving up in the Y axis)
4. $(3,5,2)$ (moving forward in the Z axis)

We denote the path taken by the mouse by a sequence of letters: 'W', 'R', 'U', and 'F', corresponding to options 1-4 above.

At time $n$, the mouse is removed from the maze and can no longer collect cheese. His goal: To maximize the cheese collected by then.

The phases of the cheese are determined by the following linear congruential generator:

$f(x) = (ax+c)\ mod\ m$

Where

a = $1103515245$
c = $12345$
m = $2^{31}$

The cheese is present at $(a,b,c)$ at time $t$ if and only if there is a value $0\le x < n/2$ such that $t=f(a\cdot b\cdot c + x)\ mod\ n$.

For example, when $n=20$ and $(a,b,c) = (3,5,1)$, the set of values of $t$ where the cheese appears is $\{1, 3, 4, 5, 6, 7, 8, 9, 10, 12\}$.

For $k=5$ and $n=20$, the maximum amount of cheese obtainable is 10 units, given by the following path:
FFRFWFWRRRUUUWWWUWW

Your goal: Find the maximum amount of cheese obtainable for $k=30$ and $n=100$. Supply your solution as two lines, one with the maximum number of cheese units and the other with the path itself.

A bonus "*" will be given for solving the same problem for $k=50$ and $n=200$, but this time allowing the mouse to move in more possible ways: left (L), down (D) and backwards (B) as well as wait (W), right (R), up (U) and forward (F), and allowing the mouse to collect the cheese more than once for the same cell, at each time where the cheese is present there.

Solution

• Click here to view the solution

  June 2023 Solution:

  The solution to the main problem is 87. For example:

  WWWWWFFWFFWFWWFFFWUUURUWFFFUUUURRFRRRUFFFFUUUFRFFFRFFFUURRRRFRRUUURRFUUURRRURUUFRRU RUFFUFUURRRUWRRW

  The solution to the bonus is 184 (everything from 179 up was accepted). For example:

  FFFFFFFFFFFFUUUUUUURURFRWRWFFFFLRFUWFURWRWUWUWRWFLWFWULWUWRLLLRWUWRLRWRRWLRRWFWU WFWUWURWURWFWFRRRRWUUWFFWFFWFUWFFRFRFFWFFUFLFFLFFLDLFLFLDDLFLDDDDBLDWLDBLDDLDLDLLWLRL RDLRLRDLRLDRLRLBRRDLRDRLLLRDRBRLLL

  One possible solution is to treat the maze as a 4-dimensional static grid (with the time t being the additional axis). Move in every axis can be in one direction only, so we can find a solution using dynamic programming techniques where for every grid cell we save the optimal value reachable from this grid cell, computed via the values of its neighbors.

  Tim Walters suggested a different route:

  “An entertaining way to solve this problem was to treat it as a shortest path problem, with movements from (a,b,c,t) -> (a',b',c',t+1) having weight 1 if there is cheese at the target node, and 1000 if there is none. A shortest path length of 13087 then represents 13 nodes without cheese, and 87 nodes with cheese. It's nice that the cheese times are symmetric in the ordering of a,b,and c, this is the times for (3, 5, 1) are the same as (1,3,5), and any paths through (3, 5,1) at time t correspond to symmetric paths through (1,3,5). This allows collapsing the node addresses to a canonical form, and significantly reduces computation time and memory space.”

  In its original phrasing, the bonus question allowed traversal in the LDB directions, without allowing the mouse to collect the cheese twice for the same cell. This made dynamic programming impossible to use, and rendered the problem much more difficult than intended (we do not know of a solution). The current phrasing of the bonus makes it rather simple.

Solvers

• *Lazar Ilic (1/6/2023 1:58 PM IDT)
• Paul Revenant (1/6/2023 5:42 PM IDT)
• *Joram Meron (1/6/2023 10:34 PM IDT)
• Bertram Felgenhauer (2/6/2023 4:21 AM IDT)
• *Vladimir Volevich (2/6/2023 10:24 AM IDT)
• Lorenz Reichel (2/6/2023 11:42 PM IDT)
• *Sanandan Swaminathan (3/6/2023 1:36 AM IDT)
• *Yan-Wu He (3/6/2023 6:22 PM IDT)
• *Gary M. Gerken (3/6/2023 11:57 PM IDT)
• Ralf Jonas (4/6/2023 2:58 PM IDT)
• *Alper Halbutogullari (4/6/2023 4:10 PM IDT)
• Julien Pradier (4/6/2023 7:11 PM IDT)
• *Bertram Felgenhauer (5/6/2023 12:26 PM IDT)
• Lorenzo Gianferrari Pini (5/6/2023 1:51 PM IDT)
• *Chris Shannon (7/6/2023 5:09 AM IDT)
• *Daniel Bitin (7/6/2023 12:51 PM IDT)
• *Evan Semet (8/6/2023 7:43 AM IDT)
• *Hok Leung Nip (8/6/2023 9:41 AM IDT)
• *Martin Thorne (8/6/2023 3:53 PM IDT)
• John Tromp (8/6/2023 5:07 PM IDT)
• *Fakih Karademir (9/6/2023 1:31 AM IDT)
• *Tim Walters (9/6/2023 4:33 AM IDT)
• *Harald Bögeholz (9/6/2023 9:46 AM IDT)
• *David Greer (10/6/2023 11:34 AM IDT)
• *Guy Daniel Hadas (10/6/2023 12:08 PM IDT)
• *Latchezar Christov (10/6/2023 3:38 PM IDT)
• *Asaf Zimmerman (11/6/2023 6:19 PM IDT)
• *Bert Dobbelaere (11/6/2023 8:10 PM IDT)
• *Diane Pham (12/6/2023 2:41 PM IDT)
• *Paul Shaw (12/6/2023 7:13 PM IDT)
• *Dominik Reichl (13/6/2023 12:33 PM IDT)
• *Luka Mushkudiani (14/6/2023 4:01 PM IDT)
• *D H Mayer (14/6/2023 7:26 PM IDT)
• *Christoph Baumgarten (14/6/2023 11:31 PM IDT)
• *Andreas Stiller (15/6/2023 6:39 PM IDT)
• *Daniel Chong Jyh Tar (15/6/2023 7:15 PM IDT)
• *Daniel Copeland & Isaac Lawrence (15/6/2023 11:41 PM IDT)
• *Phil Proudman (16/6/2023 12:12 PM IDT)
• *Rob Pratt (17/6/2023 8:32 PM IDT)
• Alex Fleischer (22/6/2023 12:35 PM IDT)
• *Todd Will (22/6/2023 8:03 PM IDT)
• *Philip Bui (23/6/2023 2:30 AM IDT)
• *James Heayes (23/6/2023 6:40 PM IDT)
• *David F.H. Dunkley (23/6/2023 6:41 PM IDT)
• *Guillaume Escamocher (23/6/2023 8:59 PM IDT)
• *Paolo Farinelli (24/6/2023 1:24 PM IDT)
• Dieter Beckerle (25/6/2023 6:11 PM IDT)
• *Marco Bellocchi (28/6/2023 7:42 PM IDT)
• Hakan Summakoğlu (28/6/2023 8:07 PM IDT)
• *Kang Jin Cho (29/6/2023 1:57 AM IDT)
• Nyles Heise (30/6/2023 12:18 AM IDT)
• *Hansraj Nahata (30/6/2023 2:59 AM IDT)
• *Li Li (1/7/2023 7:57 AM IDT)
• *Motty Porat (1/7/2023 11:23 PM IDT)
• *Lyes Belhoul (2/7/2023 1:26 PM IDT)
• *Nathan Salo (3/7/2023 11:36 PM IDT)
• Reiner Martin (4/7/2023 1:35 AM IDT)