NAQ 2018 Problem D Froggie Successful attempt at the ICPC North America Qualifier 2018 Problem D "Froggie." Any advice and all topical comments on code optimization and performance enhancement is appreciated!

Problem Summary


  You are recreating the classic ‘Frogger’ video game.
  
  Each level consists of a road with multiple lanes, with cars traveling in both directions. Cars within each lane are evenly-spaced and move at the same speed and in the same direction. Lane directions alternate, with the top lane moving left to right.
  
  ‘Froggie’ starts below the bottom lane and she travels across the road from the bottom to the top. At each time step, Froggie hops one space in one of four directions: up, down, left, or right. The goal of the game is to get Froggie across the road and above the top lane without her getting hit by a car.
  
  Goal
  
  Given a description of the road, car positions and speeds, and Froggie’s starting positions and moves, determine her outcome after the simulation. There are two possible outcomes: safely exiting the top lane or getting squished.
  
  In order to better plan her travel, Froggie may move left or right before entering the road. Once Froggie has entered the road she may only exit through the top of the road. That is, Froggie’s path never exits the left, right, or bottom lane boundaries.
  
  Input
  
  Each input describes one simulation. The first line of input contains two integers separated by a space: \$L\$ and \$W\$. The number of lanes is given by \$L\$ (\$1≤L≤10\$), while \$W\$ (\$3≤W≤20\$) defines the width (in number of cells) of the grid.
  
  This is followed by \$L\$ lines each describing the car configuration for a lane (from top to bottom). Each line contains three integers: \$O\$, the starting offset of the first car; \$I\$, the interval between cars; and \$S\$, the speed of the cars. The bounds are \$0≤O&lt;I≤W\$ and \$0≤S≤W\$. All offsets should be computed based on the direction of lane movement.
  
  The final line of input starts with a single integer, \$P\$ (\$0≤P≤W−1\$) followed by a space and then a string of \$M\$ characters (\$1≤M≤L⋅W\$) from the set \$\{U,D,L,R\}\$. \$P\$ defines the starting position of Froggie, starting from the left. The string of characters defines the sequence of moves (up, down, left, right) that Froggie makes during the simulation.
  
  Output
  
  If Froggie successfully crosses the road (exiting the road from the top lane), output “safe”. If Froggie is hit by a car, or does not end above the road, output “squish”.


froggie.py

l, w = map(int, input().split())
cars = []
for i in range(l):
  cars.append(list(map(int, input().split())))
  if i % 2 != 0:
    cars[-1][0] = w - cars[-1][0] - 1
pos, moves = input().split()
pos = (l, int(pos))

dirs = { 'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1) }
for i, c in enumerate(moves):
  pos = list(map(sum, zip(pos, dirs[c])))
  row = pos[0]
  if row == -1:
    print('safe')
    exit(0)
  elif row &gt;= l:
    continue
  car = cars[row]
  diff = car[0] + car[2] * (i + 1) if row % 2 == 0 else car[0] - car[2] * (i + 1)
  if (diff - pos[1]) % car[1] == 0:
    print('squish')
    exit(0)
print('squish')
The code in the post does not solve the problem. Consider the following input:

1 6
0 3 3
1 UU


The code in the post prints "safe", but in fact the frog is squished, since the cars have speed 3 and separation 3, meaning that a car crosses every square in the lane on every time step, and so the lane is impassable.