Indiana - Episode 1 – CodinGame solution in Python
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
- 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.
- 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.
- 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.
- 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
O(1) per turnO(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
- Confusing the entry side with the direction of travelPOS is the side Indy came in from, not where he is going. Entering type 2 from the LEFT means he moves RIGHT, so x+1.
- Mixing up types 4 and 5They are mirror images. In type 4 the TOP opening leads LEFT and the RIGHT opening leads DOWN; in type 5 TOP leads RIGHT and LEFT leads DOWN. Swapping them fails as soon as a test uses one.
- Reading rows as strings of single digitsTypes 10 to 13 have two digits, so splitting a row character by character breaks. Split on spaces.
- Trying to pathfindEpisode 1 needs no search: the route is fixed and you only predict one step. BFS or recursion adds bugs without adding anything.
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.