# Tilt Game

• You are given a `board` of the game Tilt (see figure), a `start` position and an `end` position inside the board. To move the ball, your possible moves are:

• Tilt right
• Tilt up
• Tilt down
• Tilt left

When you tilt, the ball doesn't stop till it reaches the farthest possible point in the board in the direction you're tilting. For example, if you're in (0,0) and you tilt up, the final position will be (3, 0) at the end of the move.

Design the game (data structures, etc.) and implement function `play(board, start, end)` that returns a list of moves to reach `end` from `start`. In the example, one of the possible plays are (UP, RIGHT, DOWN, LEFT, UP). If not possible return `[]`. It is given absolute freedom on the implementation details (board, etc.). The only thing that matters is the list of moves.

Follow-up: can you implement `play()` in a way that returns the play with minimum number of moves?

• @StefanPochmann can you solve it?

• Too much freedom for my liking, I demand the board data in nice format, not as a piece of paper :stuck_out_tongue_closed_eyes:

• @StefanPochmann I know... the interview question is vague on purpose to see if you can come up with a data structure to hold the board on the spot. You can use any data structure you see fit. For example, I would do a matrix where `1` indicates an obstacle.

• @agave Gonna be a pretty large matrix, since the lines are pretty thin compared to the size of the board.

• Ok it could mean an obstacle to let's say the north. And 2, 4, 8 meaning obstacles to the east, south and west. And `or`-ing them together.

• @StefanPochmann what do you mean? Can you give an example?

• @agave Your example board would have `obstacles[0][0] = 14` (because of obstacles to the east=2, south=4 and west=8, and 2+4+8=14).

• @StefanPochmann Gotcha. Pretty smart choice.

• Oops, what was I thinking, making such random choices. Of course I want east=1, north=2, west=4, and south=8. And positions being complex numbers. So that my BFS goes like

``````prev = {}
queue = [start]
while queue:
pos = queue.pop()
for dir in range(4):
p = pos
while not obstacle[p] & (1<<dir):
p += 1j**dir
if p not in prev:
queue.push(p)
prev[p] = pos, 'RULD'[dir]
``````

• @StefanPochmann said in Tilt Game:

Oops, what was I thinking, making such random choices. Of course I want east=1, north=2, west=4, and south=8. And positions being complex numbers. So that my BFS goes like

``````prev = {}
queue = [start]
while queue:
pos = queue.pop()
for dir in range(4):
p = pos
while not obstacle[p] & (1<<dir):
p += 1j**dir
if p not in prev:
queue.push(p)
``````

You mean append here, right?

``````        prev[p] = pos, 'RULD'[dir]
``````

• @agave No, that's intentional. That's not supposed to be working Python code, but pseudo code with a strong Python flavor. Otherwise `append` and `pop` would both work on the end of the queue list and thus this wouldn't be BFS.

(Oh wow, I did find a use for strike-through text after all.)

• Just to clarify, with @StefanPochmann's method, the board would be represented (in bit notation) as

``````0110, 1010, 1010, 0010, 0011
0100, 0100, 0011, 1100, 0001
0101, 1101, 1101, 0110, 0001
1101, 1111, 1111, 1100, 1001
``````

So we actually need a matrix of `m * n` integers (well, nibbles, actually) to store the board.

• @agave I think that this problem was discussed some months ago.