Tilt Game


  • 1

    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. 0_1467839299859_FullSizeRender-min.jpg

    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?


  • 0

    @StefanPochmann can you solve it?


  • 0

    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:


  • 0

    @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.


  • 0

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


  • 0

    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.


  • 0

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


  • 0

    @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).


  • 0

    @StefanPochmann Gotcha. Pretty smart choice.


  • 0

    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]
    

  • 0

    @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]
    

  • 0

    @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.)


  • 0

    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.


  • 0

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


  • 0

    @elmirap Link?


  • 0

    @agave unfortunately cannot provide now but I am sure that we talked about modified BFS


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.