A robot surviving on top of a 3x3 platform

Question

A robot sits in the central square on top of a 3x3 platform. The robot can move up, down, left or right, but if it steps off the platform it will crash and die. You can preprogram the robot to make a sequence of moves, each in one of the four allowed directions. An evil captor can choose to execute your every move, or every second move (starting from second move) or every third move (starting from third move) and so on for any n-th move. So if the programmed move sequence is ABCDEFGH then the evil captor can choose to execute ABCDEFGH, or BDFH or CF or DH. What is the longest sequence of moves you can preprogram for your robot to stay alive no matter what the evil captor does?

Answer 1

I read the Wired article that was linked in the comments, and applied the ideas mentioned there to this problem, and my computer managed to find a solution that is

214 (now improved to 311 moves, see edit below)

moves long, and cannot find a solution of more moves. I do not know if this is an optimal solution.

My solution is:

UD RUDL UD DU DRUDLU DU UD RUDL UD LUDR UD LUDDUDRU DLUDUUDR UD LUDR UD RUDL UD DU DRUDLU DU UD RUDL LDUUDR UD LURD UD RUDL LDUUDR UD LURLRD RUDL UD DU DRUDLU DU UD RUDL UD RULRLD LUDDUDRU RL LDUUDR LR LUDDUDRU RL UD DU DRUDLLUURD RUDL UD LUDR DRLU UD LDRU DLUDUUDR RDLL

I've split it by hand into chunks that return the robot to the centre spot, so you can easily check that the robot stays inside the square. If you take every second move, you get:

DU LDUR DU UD ULDURD UD DU LDUR DU RDUL DU RDUUDULD URDUDDUL DU RDUL DU LDUR DU UD ULDURD UD DU LDUR RUDDUL DU RDLU DU LDUR RUDDUL DU RDL

and this is

the original sequence rotated by 180 degrees. This is because my computer program tried to find a multiplicative function $f:N\to Z_4$ where $Z_4$ is the cyclic group of 4 elements, i.e. $\{1, r, r^2, r^3\}$. These four elements represent the four directions U, R, D, L.
Multiplicative means that $f(a*b) = f(a)*f(b)$. This is a very nice property here. If you take the subsequence consisting of every $k$th element, then the multiplicative property gives you that $f(k*n)=f(k)*f(n)$, i.e. you get the original sequence multiplied by a constant $f(k)$ which in this context is the original sequence rotated by some amount. This works for every $k$, so as long as the original sequence stays within the bounds, then so does every $k$-subsequence.
Essentially the program only chooses which directions to use at the prime-numbered steps. All the other steps are determined through the multiplicative property. The program found 3200 solutions starting with the U move, or 1600 unique solutions and their mirror images.

Regarding possible optimality:

This is not necessarily optimal. It is the longest solution that has the multiplicative property. It turns out that it can be extended by letting go of the multiplicative property.
If I understand the 1-dimensional case in the linked article correctly, it was proven that if there is an infinitely long solution, then there is an infinitely long multiplicative one, so they only needed to prove multiplicative solutions were always finite in order to prove there were no infinitely long solutions. However, this does not rule out there being edge effects in the finite case that allow for longer non-multiplicative solutions.

EDIT:
I have now extended the above solution to

311 moves.

I did this by a depth first search, starting two moves before the end of the above solution. The new solution is:

UD RUDL UD DU DRUDLU DU UD RUDL UD LUDR UD LUDDUDRU DLUDUUDR UD LUDR UD RUDL UD DU DRUDLU DU UD RUDL LDUUDR UD LURD UD RUDL LDUUDR UD LURLRD RUDL UD DU DRUDLU DU UD RUDL UD RULRLD LUDDUDRU RL LDUUDR LR LUDDUDRU RL UD DU DRUDLLUURD RUDL UD LUDR DRLU UD LDRU DLUDUUDR RDUL DRUUDUDL UD DLUR RDLU DU UD RUDL LDUUDR UD LUDDUR RUDL UD ULDR UD DU ULRD URDL RUDULRDDLLRU UD DU LDUDRU DRLRUL DLUR URD

Since this no longer has the nice properties of the previous solution, for each of the $k$-subsequences we need to check that the robot stays within the bounds of the square. Here are the various subsequences:

2: DU LDUR DU UD ULDURD UD DU LDUR DU RDUL DU RDUUDULD URDUDDUL DU RDUL DU LDUR DU UD ULDURD UD DU LDUR RUDDUL DU RDLU DU LDUR RUDDUL DU RDLRUULD LR DU UD ULDURD UD RULD LR DU LDRLUURD LUDUDDUR RL LR R
3: RL DRLU RL LR LDRLUR LR RL DRLU RL URLD RL URLLRLDR LURLRRLD RL URLD RL DRLU RL LR LDRLUR URDL DRLU RL URLD RL URDL ULDR LUDDRRUL U
4: UD RUDL UD DU DRUDLU DU UD RUDL UD LUDR UD LUDDUDRU DLUDUUDR UD LUDR UD RUDL UD DU DRUDLU DU UD RL R
5: DU LDUR DU UD ULDURD UD DU LDUR DU RDUL DU RDUUDULD URDUDDUL DU RDUL DU LDUR DR
6: LR ULRD LR RL RULRDL RL LR ULRD LR DLRU LR DLRRLRUL RDLRLLRU DRL
7: UD RUDL UD DU DRUDLU DU UD RUDL UD LUDR UD LUDDUDUURD LR
8: DU LDUR DU UD ULDURD UD DU LDUR DU RDUL DU RDUUDL
9: DU LDUR DU UD ULDURD UD DU LDUR DU UD ULDURL
10: UD RUDL UD DU DRUDLU DU UD RUDL UD LUDR R
11: DU LDUR DU UD ULDURD UD DU LDUR DLRR
12: RL DRLU RL LR LDRLUR LR RL DRLU R
13: UD RUDL UD DU DRUDLU DU UD ULD
14: DU LDUR DU UD ULDURD UD DU DR
15: LR ULRD LR RL RULRDL RL LR
16: UD RUDL UD DU DRUDLU DU L
17: DU LDUR DU UD ULDURD UL
18: UD RUDL UD DU DRUDLU L
19: UD RUDL UD DU DRUDLL
20: DU LDUR DU UD ULDUR
21: RL DRLU RL LR LDUD
22: UD RUDL UD DU DRLR
23: DU LDUR DU UD ULD
24: LR ULRD LR RL RU
25: UD RUDL UD DU DR
26: DU LDUR DU UD L
27: LR ULRD LR ULR
28: UD RUDL UD DU R
29: DU LDUR DU UD
30: RL DRLU RL LR
31: UD RUDL UD DR
32: DU LDUR DU U
33: LR ULRD LR R
34: UD RUDL UD L
35: DU LDUR DU
36: DU LDUR DU
37: UD RUDL UD
38: DU LDUR DL
39: RL DRLU U
40: UD RUDL U
41: DU LDUR R
42: LR ULRD D
43: UD RUDL L
44: DU LDUR R
45: UD RUDL
46: UD RUDL
47: DU LDUR
48: RL DRLU
49: UD RUDD
50: DU LDUR
51: LR ULRL
52: UD RUD
53: DU LDU
54: RL DRL
55: UD RUD
56: DU LDU
57: RL DRL
58: UD RUD
59: DU LDU
60: LR ULR
61: UD RUD
62: DU LDR
63: DU LD
64: UD RU
65: DU LD
66: RL DR
67: UD RU
68: DU LD
69: LR UL
70: UD RU
71: DU UD
72: UD RU
73: UD DU
74: DU LD
75: RL DR
76: UD RL
77: DU LR
78: LR U
79: LR R
80: DU L
81: UD U
82: UD R
83: DU L
84: RL D
85: UD R
86: DU L
87: LR U
88: UD R
89: RL D
90: DU L
91: UD U
92: DU L
93: RL D
94: UD R
95: DU L
96: LR U
97: LR D
98: DU D
99: UD R
100: UD R
101: DU U
102: RL L
103: UD U
104: DU
105: LR
106: UD
107: RL
108: LR
109: RU
110: DU
111: RL
112: UD
113: DL
114: LR
115: UD
116: DU
117: DU
118: UD
119: DU
120: RL
121: UD
122: DU
123: LR
124: UD
125: DU
126: UD
127: UR
128: DU
129: RL
130: UD
131: DL
132: LR
133: UD
134: DU
135: RL
136: UD
137: LR
138: RL
139: LU
140: DU
141: LR
142: UD
143: DL
144: DU
145: UD
146: DU
147: RD
148: UD
149: RU
150: LR
151: LR
152: DL
153: UL
154: UR
155: DR

Here is the computer program that I used to find the first solution.

 using System;
 namespace test
 {
    class PseRobot
    {
       static int[] moves = new int[215];
       static int[] dirsx = { 0, 1, 0, -1 };
       static int[] dirsy = { 1, 0, -1, 0 };

       static void Main()
       {
          for (int i = 0; i < moves.Length; i++) moves[i] = -1;
          moves[1] = 0;

          Search(1, 0, 0);
       }

       static void Search(int ix, int x, int y)
       {
          if (ix >= moves.Length)
          {
             for(int i=1; i<moves.Length; i++)
             {
                Console.Write("URDL"[moves[i]]);
             }
             Console.WriteLine();
             return;
          }
          if (moves[ix] >= 0)
          {
             int newx = x + dirsx[moves[ix]];
             int newy = y + dirsy[moves[ix]];
             if (Math.Abs(newx) <= 1 && Math.Abs(newy) <= 1)
             {
                Search(ix + 1, newx, newy);
             }
          }
          else
          {
             for (int d = 0; d < 4; d++)
             {
                int newx = x + dirsx[d];
                int newy = y + dirsy[d];
                if (Math.Abs(newx) <= 1 && Math.Abs(newy) <= 1)
                {
                   // mark all multiples that you can already know
                   for (int f = 1, ix2=ix; ix2 < moves.Length; f++, ix2+=ix)
                   {
                      if (moves[f] >= 0) moves[ix2] = (moves[f] + d) % 4;
                   }
                   Search(ix + 1, newx, newy);
                   // unmark all multiples
                   for (int ix2 = ix; ix2 < moves.Length; ix2 += ix)
                   {
                      moves[ix2] = -1;
                   }
                }
             }
          }
       }
    }
 }

Answer 2

I wrote a straightforward depth-first-search program, and found a sequence of length

129

namely

ULDUDRUDULDDURURLLDUDRLURLDDURDLURLURLDRULRDDRLLRLUUDRULRRLDDUURDLULRRLDRLLRLRDLURLURDLURLDDRUURLDDUULRLRRLDRDLUDUUDUDDRUULLDRUDL

This took about five minutes to find. I don't see any obvious pattern to extend this indefinitely. I'll leave the program running, and see what shows up.

Here's the program:

translate = {
        (0, 1): "R",
        (1, 0): "U",
        (0, -1): "L",
        (-1, 0): "D",
        }

c = [0]
v = [(1, 0), (0, -1), (-1, 0), (0, 1)]
m = 0
while c:
    succeed = True
    for div in range(1, len(c)):
        up = 0
        right = 0
        for off in range(len(c)//div):
            up += v[c[off*div+div-1]][0]
            right += v[c[off*div+div-1]][1]
            if up < -1 or up > 1 or right < -1 or right > 1:
                succeed = False
                break
        if not succeed:
            break
    if succeed:
        if len(c) > m:
            m = len(c)
            print(m, ''.join(translate[v[i]] for i in c))
        c.append(0)
    else:
        while c[-1] == 3:
            c.pop()
        c[-1] += 1

Answer 3

Partial:

It's at least

28

using

I just wrote a program to enumerate them; it's still running. I would hope to find an analytical solution but I figured it would be best to generate some examples first. Obviously any rotations or reflections of this also work. Note that if you are enumerating them, you can reduce the work by quite a lot if you assume the first two commands will be (say) either UR or UD. Any UL strings will have a reflection in UR, and any strings that don't start with U will have a rotation that starts with U.

Edited with better solution. I also changed the pruning a bit - all strings start with U and all strings have L before they have R. I think this eliminates all rotations and reflections. Even without rotations and reflections, there are millions of solutions of this length and the number at each length seems to still be growing steadily.

Note that

When you are trying to go from length P-1 to length P where P is prime, you always at least double the number of candidates (in reality, it's closer to tripling). This is because when you extend a solution of length P-1, it is only now not a solution if it falls off in the "execute every instruction" case. In all other captor strategies, the new instruction is not executed. No matter where the robot is, there will be either 2, 3, or 4 valid instructions that will keep it on the board.

So far I've only seen three lengths which reduce the number of candidates - 12, 18 and 24. This makes sense, since they have several divisors.

Answer 4

I have a minor correction to Jaap Scherphuis's answer; swapping two pairs of moves makes it valid again. (I don't have enough reputation to comment.)

Edit: Also, how do I put a large block of text in a scrollable box?

Jaap's 311 move solution fails for n=149 and n=154, both of which result in the sequence UU. By swapping moves 149 and 151, and swapping moves 308 and 309, we have a valid 311 move solution. I have been unable to find a longer one so far.
Revised 311 move solution (modified moves are marked with an asterisk):
1 UD RUDL UD DU DRUDLU DU UD RUDL UD LUDR UD LUDDUDRU DLUDUUDR UD LUDR UD RUDL UD DU DRUDLU DU UD RUDL LDUUDR UD LURD UD RUDL LDUUDR UD LURLRD RUDL UD DU DRUDLU DU UD RUDL UD RULRLD LUDDUDRU D*LU*DUUDR LR LUDDUDRU RL UD DU DRUDLLUURD RUDL UD LUDR DRLU UD LDRU DLUDUUDR RDUL DRUUDUDL UD DLUR RDLU DU UD RUDL LDUUDR UD LUDDUR RUDL UD ULDR UD DU ULRD URDL RUDULRDDLLRU UD DU LDUDRU DRLRUL DLUR* U*RD 2 DU LDUR DU UD ULDURD UD DU LDUR DU RDUL DU RDUUDULD URDUDDUL DU RDUL DU LDUR DU UD ULDURD UD DU LDUR RUDDUL DU RDLU DU LDUR RUDDUL DU RDLRUULD LR DU UD ULDURD UD RULD LR DU LDRLUURD LUDUDDUR RL LR* R 3 RL DRLU RL LR LDRLUR LR RL DRLU RL URLD RL URLLRLDR LURLRRLD RL URLD RL DRLU RL LR LDRLUR URDL DRLU RL URLD RL URDL ULDR LUDDRRUL U* 4 UD RUDL UD DU DRUDLU DU UD RUDL UD LUDR UD LUDDUDRU DLUDUUDR UD LUDR UD RUDL UD DU DRUDLU DU UD RL R* 5 DU LDUR DU UD ULDURD UD DU LDUR DU RDUL DU RDUUDULD URDUDDUL DU RDUL DU LDUR DR 6 LR ULRD LR RL RULRDL RL LR ULRD LR DLRU LR DLRRLRUL RDLRLLRU DRL 7 UD RUDL UD DU DRUDLU DU UD RUDL UD LUDR UD LUDDUDUURD LR* 8 DU LDUR DU UD ULDURD UD DU LDUR DU RDUL DU RDUUDL 9 DU LDUR DU UD ULDURD UD DU LDUR DU UD ULDURL 10 UD RUDL UD DU DRUDLU DU UD RUDL UD LUDR R 11 DU LDUR DU UD ULDURD UD DU LDUR DLRR* 12 RL DRLU RL LR LDRLUR LR RL DRLU R 13 UD RUDL UD DU DRUDLU DU UD ULD 14 DU LDUR DU UD ULDURD UD DU DR* 15 LR ULRD LR RL RULRDL RL LR 16 UD RUDL UD DU DRUDLU DU L 17 DU LDUR DU UD ULDURD UL 18 UD RUDL UD DU DRUDLU L 19 UD RUDL UD DU DRUDLL 20 DU LDUR DU UD ULDUR 21 RL DRLU RL LR LDUD 22 UD RUDL UD DU DRLR* 23 DU LDUR DU UD ULD 24 LR ULRD LR RL RU 25 UD RUDL UD DU DR 26 DU LDUR DU UD L 27 LR ULRD LR ULR 28 UD RUDL UD DU R* 29 DU LDUR DU UD 30 RL DRLU RL LR 31 UD RUDL UD DR 32 DU LDUR DU U 33 LR ULRD LR R 34 UD RUDL UD L 35 DU LDUR DU 36 DU LDUR DU 37 UD RUDL UD 38 DU LDUR DL 39 RL DRLU U 40 UD RUDL U 41 DU LDUR R 42 LR ULRD D 43 UD RUDL L 44 DU LDUR R* 45 UD RUDL 46 UD RUDL 47 DU LDUR 48 RL DRLU 49 UD RUDD 50 DU LDUR 51 LR ULRL 52 UD RUD 53 DU LDU 54 RL DRL 55 UD RUD 56 DU LDU 57 RL DRL 58 UD RUD 59 DU LDU 60 LR ULR 61 UD RUD 62 DU LDR 63 DU LD 64 UD RU 65 DU LD 66 RL DR 67 UD RU 68 DU LD 69 LR UL 70 UD RU 71 DU UD 72 UD RU 73 UD DU 74 DU LD 75 RL DR 76 UD RL 77 DU LR* 78 LR U 79 LR R 80 DU L 81 UD U 82 UD R 83 DU L 84 RL D 85 UD R 86 DU L 87 LR U 88 UD R 89 RL D 90 DU L 91 UD U 92 DU L 93 RL D 94 UD R 95 DU L 96 LR U 97 LR D 98 DU D 99 UD R 100 UD R 101 DU U 102 RL L 103 UD U* 104 DU 105 LR 106 UD 107 RL 108 LR 109 RU 110 DU 111 RL 112 UD 113 DL 114 LR 115 UD 116 DU 117 DU 118 UD 119 DU 120 RL 121 UD 122 DU 123 LR 124 UD 125 DU 126 UD 127 UR 128 DU 129 RL 130 UD 131 DL 132 LR 133 UD 134 DU 135 RL 136 UD 137 LR 138 RL 139 LU 140 DU 141 LR 142 UD 143 DL 144 DU 145 UD 146 DU 147 RD 148 UD 149 D*U 150 LR 151 U*R 152 DL 153 UL 154 UR* 155 DR

I have also been searching for a sequence independently:

Like others, I have been using a depth-first search. However, to limit the search space, if both L and R are valid moves I only consider L, and if both U and D are valid moves I only consider U. This quickly gave me a 174 move solution:
UD LR LURLDR LDRLUUDURLDR LR RL URDDUDUULLRLDR URLLRRDL ULRRLD RL LUDUDDUR LDRLUR URDL DRLU ULDR ULRD URDL RL DU LURD DRUDLLUURRDL LR LR RDUULD RUDULLDDRRLU RDUUDL ULRD LDRU DRLRUL LR DLUDRU DU UD DLUUDDRRUD
I then allowed 1 exception to that rule, which yielded a 183 move solution (exception at move 7):
UD LUDR RL LR LDRLUR LURLDR LURLRRDL UD RULD UD LURRLD RUDL UD RUDL UD LURRDDLU DU LDRU LR UD LUDDUDRLRLRRUUDL UD DU LR UD DU ULDDRU LURD LUDR UD ULDDUR LURRDDUUDL URDULD LDRU RL LDUUDUDDRLRRUL LURD UD DU LUDDUDUR LR DU LURD L
With 2 exceptions, a 239 move solution (exceptions at moves 19 and 47):
UD LR LURLRRDDUL URDL RL DRLU RL DU LDUDUUDR ULDURRDL LR DLUDRRLU RDLU URDDUULLRD RUDDUDLU LR LDRLRLUR DU LURD LUDR UD DU ULDDRU ULDDUUDR UD UD DLUUDUDDUDUUDR UD RUDL LDRU DU UD LR URDDLU DLUR RUDDUULLDR LDRLRU UD DU UD UD LUDR UD LURLDDRU DU LDUDRRLU DU DLRLUDRRLU DRUL LDUR ULRLRRDDUULRD
With 3 exceptions, a 245 move solution (exceptions at moves 5, 11, and 25):
ULDR RUDL UD RDLRLU LDRU UD LR RUDL LURD LR LURLRD LDUURRDL ULRD LURRLRDDUL DU LUDDRU ULRD LR LDRRUUDULLRD UD RL LR URDL RUDL LURRDDUL LDUR DU LR RULLDDRU ULRRLD LR LURLRD ULRRLD DU URDDLU RUDL ULRD URDUDL LR RDUL LR ULDURD DU URLD ULDDUR RUDL UD LUDURRDL UD LDRU LR UD LURRDULLRLDR RDLU UD UD ULDR DU R
I also performed exhaustive searches starting with certain sequences of moves. I believe the longest solution that starts with UDULRR is 219:
UD ULRRLRDL RL LR DU DU LR ULRD URDL DU RDLU DRUDLLUDRRUL DU UD RUDL LR RUDDLU DLRRUDLU ULDDUURD DRUDLU LURLRD LR LURRDDUL RL UD DU LR LR RL RL LDRRUULD DLRU URLLRD DRLU DU URDDUDUL ULDR LR RL DU RULLRD LR RULD RDLLRU LR LDUUDR RL UD LR RL DU URDL ULDR LUDDUR RL RL LDUUDURD R
...and the longest solution starting with ULDDRRLUUD is 254:
ULDDRRLU UD RUDULD ULDURD UD DU DRLU RL LR LDRLUR UD DLRRLU RL DRLRUL URLD RL LR LURLDR DU RL URDDUL UD ULDUDR LDRLUR URLLRRDL DLRRUUDL LR LR RL DRUL UD LR DU DLRU URDL LR ULRD RUDDUDLU URDL RULLRD URLLDUDDRRUL LDRRUL RUDULD LR DLUDRRUL LR RULD ULDUDR DU URDL ULRD UD RULRLRDL LURLDDUUDR UD LDUURLDR DU UD DU URDL


Answer 5

 LDRRULRULLDR
  D R L U L R
   R  L  L  R

leaves robots 1, 2 and 3 where they started.

Answer 6

EDIT : I found a better solution for

17 steps

Omitting the older solution as that is no more valid