Coding Solution

Indiana - Episode 1 – CodinGame solution in Python

Mediumsimulationlookup table2D gridUpdated
Short answer

Read the grid of room types once, then each turn look up where Indy leaves the current room given its type and the side he entered from (TOP, LEFT or RIGHT). Exits are always DOWN, LEFT or RIGHT, so the next room is (x, y+1), (x-1, y) or (x+1, y), and you print those coordinates. A small table from (type, entry) to exit replaces any pathfinding.

The problem

The tunnel is a grid of W × H rooms (up to 20 × 20), each with a type from 0 to 13 describing which openings it connects. Indy starts at the top and falls through rooms; the layout is fixed in Episode 1 and guaranteed to lead him to the exit at the bottom.

Every turn you get Indy's current room x, y and the side through which he entered it. You must print the coordinates of the room he will be in at the next turn. The exit column is given but you do not need it, since the rooms already lead there.

Approach, step by step

  1. Store the grid as integersRead H lines of W space-separated numbers and index them grid[y][x]. Room types are plain ints here; negative (rotatable) types only appear in later episodes.
  2. Encode the 14 room types onceFor each type, list where Indy exits for each entry side: for example type 4 sends TOP to the left and RIGHT downward, type 5 sends TOP to the right and LEFT downward, and types 10 and 11 send TOP to the left and right respectively. Types 1, 3, 7, 8, 9, 12 and 13 always exit down for any valid entry, and types 2 and 6 move horizontally away from the entry side.
  3. Turn the exit into coordinatesDOWN means y+1, LEFT means x-1, RIGHT means x+1. Indy never moves up, so there is no y-1 case.
  4. Answer every turnRead the turn input inside an infinite loop and print 'x y'. There is no state to keep between turns because the input already tells you everything.

Complexity

TimeO(1) per turn
SpaceO(W·H)

Each turn is a single table lookup. The only memory is the grid itself.

Solution code

Indiana - Episode 1 – Python

Uses a chain of if/elif tests on the room type grouped by behaviour, which is compact because many types always exit down. A dictionary keyed by (type, entry) would make each rule explicit and is easier to reuse in Episode 2.

W, H = [int(i) for i in input().split()]
rooms = []
for i in range(H):
    rooms.append([int(i) for i in input().split()])
exit = int(input())

while 1:
    XI, YI, POS = input().split()
    XI, YI = int(XI), int(YI)

    if rooms[YI][XI] in (1, 3, 7, 8, 9, 12, 13):
        YI+=1
    elif rooms[YI][XI] in (2, 6): 
        XI+= 1 if POS == 'LEFT' else -1
    elif rooms[YI][XI] == 4:
        if POS == 'TOP':
            XI-=1
        else:
            YI+=1
    elif rooms[YI][XI] == 5:
        if POS == 'TOP':
            XI+=1
        else:
            YI+=1
    elif rooms[YI][XI] == 10:
        XI-=1
    elif rooms[YI][XI] == 11:
        XI+=1
        
    print("{} {}".format(XI, YI))
            

Common mistakes

Going further

Encoding the rooms as a dictionary, for example {(4, 'TOP'): 'LEFT', (4, 'RIGHT'): 'DOWN', ...}, is more than style: in Indiana Episode 2 and 3 you have to rotate rooms and simulate Indy and rocks several steps ahead, and every one of those simulations needs exactly the same 'type plus entry gives exit' function. Rotations also map neatly onto it, because rotating a room only changes its type number (2 and 3 swap, 4 and 5 swap, 6 to 9 cycle among themselves, as do 10 to 13). If you write the exit table and the rotation table cleanly now, Episode 2 becomes a search over rotations built on code you have already validated.

FAQ

Do I need the exit coordinate EX?

Not in Episode 1. The rooms are arranged so that following them leads to the exit, and you only predict the next room.

Can Indy enter a room from the bottom?

No. Entry is always TOP, LEFT or RIGHT and he never moves upward, which is why every exit is DOWN, LEFT or RIGHT.

What about type 0?

Type 0 is a solid block. Indy never enters it in a valid Episode 1 level, so it needs no rule.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome