June 2023 - Challenge
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
- (3,5,1) (waiting in place)
- (4,5,1) (moving right in the X axis)
- (3,6,1) (moving up in the Y axis)
- (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\ mWhere
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
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.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
31/05/2023 @ 15:30 PM EST
Solution:
05/07/2023 @ 12:00 PM EST
List Updated:
05/07/2023 @ 13:35 PM EST
People who answered correctly:
*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)