9
\$\begingroup\$

Universal Command Sequence

Definition

An \$n\$-maze is a \$n\times n\$ chessboard which has "walls" on some edges, and a "king" on the board that can move to the 4 adjacent cells, which cannot pass through any walls. Starting from any cell the king should be able to reach every cell on the board.

A command sequence is an array consisting of 4 distinct types of element (for example [1,2,3,4,1,4,2,3,1,...]). Each type of element means a direction of the movement of the king. A command sequence can be "applied to" a maze, if the king can traverse every cell on the board by following the command sequence. For example a command sequence [up,right,down] can be applied to a 2-maze that has no walls and the king is placed at the botton-left cell. If the king is going to pass through a wall or go outside the board, the command will be skipped.

Challenge

For a given positive integer \$n\$, output a command sequence that can be applied to any \$n\$-maze. The existence of this sequence can be proved mathematically.See 1998 All-Russian Math Olympiad, Grade level 9, Day 1, Problem 4.

Input

A positive integer n. You can assume that n>1.

Output

An array consisting of 4 distince types of elements.

Python 3 validator

Try it online. Test your generated sequence here. Usage tips can be found in the footer.

This is . Shortest code wins.

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ Sandbox link: codegolf.meta.stackexchange.com/questions/2140/… \$\endgroup\$ Commented Jan 14, 2022 at 7:21
  • \$\begingroup\$ Related: Shortest universal maze exit string: sequence to go from any variable start to any variable exit in any 3x3 maze. This challenge will be quite a bit harder I assume, since it's not a hard-coded 3x3 maze but \$N\times N\$ based on the input \$N\$ instead. (The 'variable start to exit' versus 'visit all cells' shouldn't make a̶n̶y̶?̶ too much difference.) \$\endgroup\$ Commented Jan 14, 2022 at 8:34

1 Answer 1

Reset to default
12
\$\begingroup\$

Pyth, 7 bytes

s^S4^5*

We could construct a universal sequence of length \$2^{2n(n-1)} ⋅ n^2 ⋅ (2n^2 - 2) < 5^{n^2}\$. Start with the empty sequence; then for each of the at most \$2^{2n(n-1)}\$ mazes and \$n^2\$ possible starts, imagine following all the previously appended commands to get a new location, and append \$2n^2 - 2\$ more commands representing a complete traversal of that maze from that new location.

But, since we know we could construct it, we don’t have to actually do it. Instead, just concatenate all length \$5^{n^2}\$ sequences of \$1, 2, 3, 4\$. Since we just proved at least one of those sequences is universal, so is their concatenation.

Improve this answer
\$\endgroup\$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.