Simulation

The category

Some problems do not need an insight. They describe a process — a machine, a game, a set of movement rules — and ask what state it ends in. The solution is to carry out the process. These are simulation problems, and they are a large share of entry-level contest problems.

The difficulty is never conceptual. It is that the statement has five rules and your code implements four of them, or implements the fifth slightly differently. Simulation problems are lost to misreading, not to algorithms.

The core discipline

Translate the statement into code one rule at a time, in the order the statement gives them, and keep the names the statement uses.

A worked example

A robot starts at position 0 on a number line facing right. You are given a string of commands: F moves one step forward, B moves one step backward, and R reverses its facing direction. Print the final position.

The statement gives three rules. The code has three cases.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String commands = in.readLine().trim();

        int pos = 0;
        int facing = 1;          // +1 is right, -1 is left

        for (int i = 0; i < commands.length(); i++) {
            char c = commands.charAt(i);
            if (c == 'F') {
                pos += facing;
            } else if (c == 'B') {
                pos -= facing;
            } else if (c == 'R') {
                facing = -facing;
            }
        }

        System.out.println(pos);
    }
}

Encoding the direction as +1 or -1 is the small design decision that makes this clean. “Forward” becomes pos += facing regardless of which way the robot faces, so there is no separate case for each direction.

// right, down, left, up — turning clockwise is (dir + 1) % 4
int[] dr = {0, 1, 0, -1};
int[] dc = {1, 0, -1, 0};

int r = 0, c = 0, dir = 0;
r += dr[dir];
c += dc[dir];

Grid simulation

Most simulation problems are on a grid. The pattern is a position, a direction, and a bounds check.

A robot walks forward on an R × C grid. If the next cell is off the grid or blocked, it turns right instead of moving. Report its position after K steps.

int r = 0, c = 0, dir = 0;
int[] dr = {0, 1, 0, -1};
int[] dc = {1, 0, -1, 0};

for (int step = 0; step < k; step++) {
    int nr = r + dr[dir];
    int nc = c + dc[dir];

    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] == '#') {
        dir = (dir + 1) % 4;
    } else {
        r = nr;
        c = nc;
    }
}

Computing the candidate position into nr and nc before committing is the important habit. It lets you test the move for legality without having to undo it.

if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] == '#')

When the step count is huge

If the problem says K ≤ 10⁹ steps, you cannot simulate each one. That is the constraint telling you the state must repeat.

A finite amount of state means the process eventually cycles. Find the cycle, then skip ahead with arithmetic.

Map<String, Integer> firstSeen = new HashMap<>();
int step = 0;
while (step < k) {
    String state = encode(r, c, dir);
    if (firstSeen.containsKey(state)) {
        int cycleStart = firstSeen.get(state);
        int cycleLen = step - cycleStart;
        int remaining = (k - step) % cycleLen;
        for (int i = 0; i < remaining; i++) advance();
        break;
    }
    firstSeen.put(state, step);
    advance();
    step++;
}

The state must include everything that affects the future — for the walking robot, that is position and facing direction. Leaving out the direction produces a wrong cycle length, and the answer will be wrong only on large inputs, which is a hard bug to find later.

The checklist

Next