← All solutions

Solved by 138 teams.

First solved after 14 minutes.

Shortest judge solution: 662 bytes.

Because there are only 4 directions, there are only 4! = 24 possible move orderings. We can track which orderings remain consistent with the rover’s moves. For each move in the sequence, determine which directions are valid from the current position. Then, filter out which orderings are inconsistent with the robot’s move. If there are no valid orderings, a cosmic ray must have hit. Increment the answer and reset the set of consistent orderings.

Alternatively, you can use dynamic programming. Let count(i, p) be the minimum number of cosmic ray flips for the rover to make the first i moves and currently have move order p, where p is a permutation of NEWS. The overall runtime is O(n).