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.

\$\endgroup\$
2
11
\$\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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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