Ponder This

Welcome to our monthly puzzles.
You are cordially invited to match wits with some of the best minds in IBM Research.

November 2021 - Challenge

<< October December >>

We return to the maze from the October 2021 challenge (described again in detail in the appendix below), with some differences: Now columns can be moved up/down and rows left/right, but we can no longer move the row/column where the robotic mouse is situated. One slide moves the row/column exactly one cell.

Before and after performing a slide, the mouse can be moved to any cell reachable from its current location; it can also stay in its current place.

To denote slides we now use the following format: "U", "D", "L", "R" represent "Up", "Down", "Left", and "Right", so "U3" means "slide column number 3 one cell up" and "L6" means "slide row number 6 one cell left".

An example of the format for the move list:
[(3,5), "D2", "L4", (6,3), "R0", (7,7)]

  • Move the mouse from (0,0) to (3,5).
  • Slide column 2 down.
  • Slide row 4 left.
  • Move the mouse from (3,5) to (6,3).
  • Slide row 0 right.
  • Move the mouse from (6,3) to (7,7).

This set of move consists of 3 slides.

Note that
[(3,5), "D2", "L3"]
is illegal, since the mouse is in row 3 when the "L3" command is reached.

Your goal: Given the 15x15 maze
Find a sequence of moves for the mouse and row/column slides such that the mouse reaches the exit in at most 50 slides.

A bonus "*" will be given for solving the 10x10 maze
In at most 20 moves *without moving the mouse* except in the last move.

Appendix - description of the maze and the problem:
We are guiding a robotic mouse in a two dimensional maze. The mouse is situated in the upper-left corner of the maze, and must reach the lower-right corner. Unfortunately, there is no direct path in the maze between those two corners. However, we can slide the rows and columns of the maze: by sliding a row we move all the cells in the row one cell-length to the right, re-inserting the rightmost cell from the left. By sliding a column we do the same, sliding cells down and re-inserting the bottom cell from the top. We can also slide rows left and columns up.
We represent a maze by a hexadecimal string in the following manner: First, each cell in the maze is represented by a 4-digit binary string representing which passages are blocked (0) and which are open (1) for the directions "up", "right", "down" and "left". Every such 4-digit string can be converted to a single hexadecimal digit; this correspondence can be seen in the following illustration:

An nxm maze can be represented by a hexadecimal string of length n\cdot m where the first m digits give the upper row, the next m digits give the second row and so forth. For example, the string
represents the following maze:

We denote cells in the maze by (a,b) where a is the row number and b is the column number, both starting from 0. For example, if the mouse is in the second row from the top and the third column from the left, its location is (1,2). The mouse starts from (0,0) and for a nxm maze needs to reach (n-1, m-1).

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/10/2021 @ 12:00 PM EST
Solution: 04/12/2021 @ 12:00 PM EST
List Updated: 15/11/2021 @ 12:00 PM EST

People who answered correctly:

Guillaume Escamocher (31/10/2021 10:51 PM IDT)
*Lazar Ilic (31/10/2021 11:28 PM IDT)
Andreas Stiller (1/11/2021 2:57 AM IDT)
*Gary M. Gerken (1/11/2021 6:01 AM IDT)
*John Goh (1/11/2021 8:13 AM IDT)
*Phil Proudman (1/11/2021 11:41 AM IDT)
Daniel Chong Jyh Tar (1/11/2021 5:59 PM IDT)
*Alper Halbutogullari (1/11/2021 12:19 AM IDT)
*Bertram Felgenhauer (2/11/2021 5:14 AM IDT)
*Chris Shannon (2/11/2021 9:37 AM IDT)
*Harald Bögeholz (2/11/2021 12:58 PM IDT)
*Amos Guler (2/11/2021 12:18 PM IDT)
*Dieter Beckerle (2/11/2021 2:30 PM IDT)
*Paul Revenant (2/11/2021 3:06 PM IDT)
Stéphane Higueret (2/11/2021 3:31 PM IDT)
*Hakan Summakoğlu (3/11/2021 12:33 AM IDT)
*David McCullars (3/11/2021 1:52 AM IDT)
Graham Hemsley (3/11/2021 12:47 PM IDT)
*Tim Walters (3/11/2021 7:12 PM IDT)
*Dominik Reichl (3/11/2021 9:34 PM IDT)
*Andreas Stiller (4/11/2021 6:28 PM IDT)
*Erik Wünstel (3/11/2021 11:51 PM IDT)
*Vladimir Volevich (5/11/2021 7:39 PM IDT)
Liubing Yu (6/11/2021 1:41 AM IDT)
*Thomas Pircher (7/11/2021 7:43 PM IDT)
*Peter Moser (10/11/2021 12:38 PM IDT)
Vijay Nuthulapaty (11/11/2021 3:38 PM IDT)
*Mansi Pai (11/11/2021 6:52 PM IDT)
*Nyles Heise (12/11/2021 5:27 AM IDT)
*Latchezar Christov (12/11/2021 5:29 PM IDT)
*Motty Porat (13/11/2021 2:14 AM IDT)
*David Greer (13/11/2021 1:36 PM IDT)
*Lorenz Reichel (13/11/2021 5:30 PM IDT)
Fabio Michele Negroni (13/11/2021 7:32 PM IDT)
Marco Bellocchi (14/11/2021 1:09 PM IDT)
*Kang Jin Cho (14/11/2021 6:26 PM IDT)
*Clive Tong (15/11/2021 10:46 AM IDT)
Quentin Higueret (15/11/2021 11:36 AM IDT)
*Walter Schmidt (15/11/2021 4:18 PM IDT)
*Daniel Bitin (15/11/2021 11:59 PM IDT)