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.


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.


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


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


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:
  elif row >= l:
  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:
  • 1
    \$\begingroup\$ Please include a brief summary of the challenge to be performed. Just including the link is insufficient. \$\endgroup\$ Oct 9, 2018 at 22:35
  • \$\begingroup\$ @200_success Is the last edit sufficient? \$\endgroup\$
    – T145
    Oct 9, 2018 at 23:06

1 Answer 1


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.

  • \$\begingroup\$ Quite right, which makes me a little concerned as to why this was accepted. I wouldn't have posted it otherwise. I'll leave it up unless commanded to delete it. \$\endgroup\$
    – T145
    Oct 10, 2018 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.