13
$\begingroup$

A robot is placed on an empty infinite grid. Each turn it can move in one of four directions: left (L), up (U), right (R) or down (D). It cannot move to a cell that it already visited. Also, it cannot repeat triplets of consecutive moves. For example, if it has moved RRDLD, then it cannot go RRD or RDL or DLD as that would repeat an existing triplet of moves. Similarly, it cannot do U or RU or RL as that would revisit a cell. What is the longest path that it can take following these constraints?

Bonus: What is the furthest Euclidean distance away from its starting point that it can reach?

$\endgroup$
6
  • 1
    $\begingroup$ My interpretation is that it doesn't matter how far away the robot ends up, you just want the longest sequence of moves, is that right? $\endgroup$
    – hexomino
    Sep 27, 2022 at 14:13
  • $\begingroup$ That is correct. Furthest distance would also be interesting. Let's add it as a bonus :) $\endgroup$ Sep 27, 2022 at 14:14
  • $\begingroup$ are intersecting triplets (RRRR or RDRDR) allowed? $\endgroup$
    – Magma
    Oct 2, 2022 at 0:21
  • $\begingroup$ @Magma RRRR is disallowed because it contains RRR twice and also revisits the starting cell, and RDRDR is disallowed because it contains RDR twice. $\endgroup$
    – RobPratt
    Oct 2, 2022 at 2:21
  • $\begingroup$ @RobPratt RRRR does not revisit the starting cell since it moves in the same direction four times. The R is not a turn, but a step in the rightwards direction (or East if you prefer). $\endgroup$ Oct 3, 2022 at 11:50

1 Answer 1

13
$\begingroup$

The largest number of moves is

35

There are many such moves sequences, for example this:

LLLURRRURULUURDRUUULLDLULDDDLDRRDLL
Picture of LLLURRRURULUURDRUUULLDLULDDDLDRRDLL

I used a computer for this, but here is a handwavey argument for why this is optimal.

This is very close to being a De Bruijn sequence. The difference is that we are not stringing together all possible $4^3$ triplets of moves, but are restricted to using only the $4\cdot 3\cdot 3=36$ triplets where a move is not immediately followed by its reverse.
If there were no further restriction on revisiting squares, we could string together these $36$ triplets to get a $38$ move sequence. Here is one example:
LLLURRRURULUURDRUUULLDLULDDRDDDLDRRD(LL)
It can be proved that the last two moves will always be equal to the first two, so it is really a cycle. Note also that this $36$-move cycle contains every move exactly $9$ times. Performing that cycle will therefore bring the robot back to its starting position on the $36$th move.
So if you follow such a cycle and cannot revisit any squares, then you cannot do better than $35$ moves.

The above is not quite a proof, as it assumes that the optimal sequence is actually simply a part of such a cycle. I do believe however that it is essentially always the case that the three unused triplets can be appended or inserted to make a complete cycle. In the solution the missing triplets were DDR, DRD, RDD and they can be inserted by replacing DD by DDRDD resulting in the cycle I show above.

A solution to the bonus question:

LLLULLDLUULDDDLDRDLL
Picture of LLLULLDLUULDDDLDRDLL
This ends up $(9,3)$ away from the start, a distance of $\sqrt{90}$.

I have no argument for why this must be optimal, though my computer program exhaustively tried all possibilities and found nothing better.

$\endgroup$
1
  • 2
    $\begingroup$ That is correct! Brilliant work as always. I like the connection to the De Bruijn sequence. $\endgroup$ Sep 27, 2022 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.