cf.completefrontend
FOUNDATIONS · FOUNDATION

Simulation

Follow the rules of a process step by step, exactly as described, and report the final state.

Time O(m)Space O(1)15 practice problemsStep-through picture

The idea

A simulation problem describes a process: a cursor moving on a canvas, a queue of print jobs, a game board changing each turn. You don't need a clever shortcut. You keep variables for the current state and apply the rules one step at a time, in the order the problem gives.

The hard part is being exact. Read the rules closely: what happens at the edges, what happens on a tie, and what order things happen in within one step. Most bugs in simulation code are a rule applied in the wrong order or a missed edge case.

The code here moves a cursor on a grid that is width cells wide and height cells tall. It starts at the top-left cell, follows the commands U, D, L, R, and ignores any move that would leave the grid.

An everyday example

Following a board game's rule book

In a board game you roll a die and move your token. If a square says "go back 3", you go back 3. If you would move past the last square, you stay where you are. You don't try to predict the end of the game; you just follow the rule book one turn at a time, and the final position is whatever the rules produce.

How the example maps to the code
In the exampleIn the code
Your token's squareThe state: x and y
One turnOne pass of the loop: one command
The rule bookThe moves table and the edge check
"You can't move past the edge"if (nextX >= 0 && nextX < width ...)

From the slow way to simulation

  1. It is tempting to look for a shortcut. Without edges, the final column would just be the number of R commands minus the number of L commands. But on a grid 3 wide, "RRRL" gives 3 minus 1 = 2 by that formula, while the real cursor ends at column 1, because the third R hits the edge and is ignored.
  2. The trouble is that whether a move counts depends on where the cursor is at that moment. So you can't skip ahead: you have to know the state after each command. First decide what "the state" is: the smallest set of variables that describes the situation completely. Here that is x and y.
  3. Next, turn the rules into data where you can. The moves table says what each letter does as a change [dx, dy], so the loop body doesn't need four if branches. Adding a new command later means adding one entry.
  4. Finally, make each step careful: work out nextX and nextY, check them against the rules, and only then commit them to x and y. Repeat for each command in order and return the state at the end. That loop is simulation.

How it works

  1. Decide which variables describe the whole state at one moment. Here: x and y.
  2. Write the rules as data where you can, like the moves table that maps each command to a change [dx, dy].
  3. Loop over the events in order. For each command, look up its change.
  4. Work out the next state (nextX, nextY) before changing anything.
  5. Check the rules, such as staying inside the grid, and only then update x and y.
  6. When the events run out, return the final state.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function simulateCursor(width, height, commands) {
  2. const moves = { U: [0, -1], D: [0, 1], L: [-1, 0], R: [1, 0] };
  3. let x = 0;
  4. let y = 0;
  5. for (const command of commands) {
  6. const [dx, dy] = moves[command];
  7. const nextX = x + dx;
  8. const nextY = y + dy;
  9. if (nextX >= 0 && nextX < width && nextY >= 0 && nextY < height) {
  10. x = nextX;
  11. y = nextY;
  12. }
  13. }
  14. return [x, y];
  15. }

How fast it is

TimeO(m)
Extra memoryO(1)

Each of the m commands does a fixed amount of work: one lookup, two additions, one check. Only x, y, and the small moves table are stored.

  • Best caseO(m)

    Any m commands, even if every move is blocked: each command still needs one lookup and one check. Only an empty commands string is O(1).

  • Average caseO(m)

    Any mix of commands: each costs the same small, fixed amount of work.

  • Worst caseO(m)

    Still one step per command. Simulations only get slow when m is huge, like a billion steps, or when one step touches many cells.

Common mistakes

  • Moving first and checking after, which leaves the state invalid when a move is blocked.
  • Mixing up rows and columns. Decide once that x is the column and y is the row, and write grid[y][x] everywhere.
  • Updating a grid in place when every cell should change at the same moment. Build the next grid separately.
  • Simulating a billion steps one by one. If the state repeats, find the cycle and skip ahead.

When to use it

Look for these clues in a problem:

  • The problem describes a process in detail: "each second", "each turn", "for each command".
  • The input size is small enough to run every step (for example, at most 10,000 commands).
  • The answer is the final state: a position, a board, a list of who finished when.
  • There are many special rules (edges, ties, order of events) to follow exactly.

Check yourself

Answer each one in your head first, then open it.

Why compute nextX and nextY before changing x and y?

So a blocked move never leaves the state outside the grid. Checking first means nothing needs to be undone.

Where does "LLLL" leave the cursor on a 3 by 3 grid?

At [0, 0]. Every L would move to column -1, which is off the grid, so all four are ignored.

Why does U use [0, -1] and not [0, 1]?

Row 0 is at the top, so moving up means a smaller row number. Screens and grids usually count rows downward.

If every cell of a grid must update based on its neighbors at the same moment, why can't you update in place?

Cells updated early would change the neighbors that later cells read, so later cells would see a mix of old and new values. Build the next grid separately, then replace the old one.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 15 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one promise: after handling the first t commands, x and y are exactly where the rules put the cursor after those t commands, and that cell is inside the grid. Before any command, the cursor is at (0, 0), the top-left cell, so the promise holds.

Each step keeps it. The code looks up the command's change, works out the candidate cell, and checks all four edges. If the candidate is inside, the rules say the cursor moves there, and it does. If not, the rules say it stays, and x and y are untouched. Either way, the new state is the one the rules give, and it is inside the grid.

The loop handles each command exactly once, in order, and then stops. When it ends, t equals the number of commands, so the promise says [x, y] is the final position the rules describe.

Going deeper

3 more ideas

Why compute the next state first

The code works out nextX and nextY and checks them before touching x and y. If it moved first and checked after, a blocked move would leave the cursor outside the grid, and you would need extra code to undo it. Computing the next state, checking it, then committing it keeps the state valid after every step.

When the board changes all at once

Some simulations update many cells in one step, like a grid where each cell's next value depends on its neighbors. If you update cells one by one in place, later cells read neighbors that already changed. Build the next state in a new grid (or mark changes with special values), then swap it in when the step is done.

Cost

A simulation does a fixed amount of work per step, so its time is the number of steps times the work per step. Here that is O(m) for m commands, with O(1) extra space. If a problem asks for the state after a billion steps, a plain simulation is too slow; look for a repeating cycle or a formula instead.

Work it by hand

Every step in a table, with why

Move a cursor on a grid 4 cells wide and 2 cells tall. Two moves try to leave the grid, one at the bottom and one on the right.

width = 4, height = 2, commands = "DRDRRRUL"

StepcommandnextX, nextYInside?x, y afterWhat happensWhy
1D0, 1yes0, 1Move downRow 1 is the bottom row, still inside a grid 2 tall.
2R1, 1yes1, 1Move rightColumn 1 is inside a grid 4 wide.
3D1, 2no1, 1Blocked: staynextY = 2 is not less than height, so the move is ignored and the state doesn't change.
4R2, 1yes2, 1Move rightThe blocked move left nothing to undo, so this command starts from the correct cell.
5R3, 1yes3, 1Move rightColumn 3 is the last column.
6R4, 1no3, 1Blocked: staynextX = 4 equals width, which is off the grid.
7U3, 0yes3, 0Move upU lowers y, because row 0 is the top row.
8L2, 0yes2, 0Move leftThe last command. The loop ends after it.

It returns [2, 0]. A formula that counts letters would say column 4 - 1 = 3 and row 2 - 1 = 1, both wrong, because it can't know which moves were blocked.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
SimulationO(m)O(1)The rules depend on the current state, such as blocked moves at edges, and the number of steps is manageable.
Counting letters with a formulaO(m)O(1)Only when no rule depends on the state, such as an infinite grid with no edges. Then the column is the count of R minus the count of L.
Simulate until a state repeats, then skip cyclesO(s)O(s)The step count is huge but the number of different states s is small, so the process must repeat soon.

Extra memory: O(1): x, y, the candidate cell, and the 4-entry moves table. Simulations that keep a grid use space for the grid, O(width × height).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Simulation and the other approaches, on a scale where each line up is 10 times more steps.
  • Simulation, Counting letters with a formula, Simulate until a state repeats, then skip cycles O(m)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Simulation101,0001 million
Counting letters with a formula101,0001 million
Simulate until a state repeats, then skip cycles101,0001 million

Inputs that need care

5 tricky inputs
An empty command string: ""
The loop runs zero times and the function returns the starting cell, [0, 0].
A grid one cell big: width = 1, height = 1
Every move points off the grid, so every command is ignored and the answer is [0, 0].
An unknown letter, such as "Rx" or lowercase "r"
moves[command] is undefined, and const [dx, dy] = undefined throws a TypeError. Decide the rule: skip unknown commands with if (!moves[command]) continue;, or report an error.
A grid with no cells: width = 0
The code still returns [0, 0], a cell that doesn't exist, because the starting cell is never checked. Validate the size first if it can be zero.
A billion commands that repeat the same pattern
A plain simulation would take a billion steps. Instead, record each state you've seen with the step number; when one repeats, you've found a cycle, and you can skip whole cycles at once.

Variations and follow-ups

Twists interviewers add

Everything changes at once

In grids where each cell's next value depends on its neighbors, like a game-of-life board, updating cells in place makes later cells read already-updated neighbors. Build the next state in a second grid, then swap the two. This is called double buffering.

Wrapping around the edges

Some boards wrap: leaving on the right brings you back on the left. Replace the edge check with x = (x + dx + width) % width, which also handles moving left from column 0.

Jumping between events

If events happen at specific times, like timers firing at 30 ms and 450 ms, don't step through every millisecond. Keep the upcoming events in a priority queue and jump straight to the next one. Test fake clocks work this way.

Finding a cycle to skip ahead

When asked for the state after a huge number of steps, store each state in a Map with the step at which it appeared. Once a state repeats, the steps between are a cycle, and the remainder after dividing by the cycle length tells you where you'll end.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from the wording: "each turn", "for each command", "after every second", or a long list of rules with edge cases. If the limits are small enough to run every step, simulation is expected.
  • Before coding, say what the state is and write the rules as data: "the state is x and y; moves maps each letter to [dx, dy]". This shows you've planned, and it shortens the code.
  • Test the edges by hand: a move off each of the four sides, a move from a corner, and an empty command list. Most simulation bugs are in an edge rule or in mixing up rows and columns.
  • The usual follow-up is "what if there are 10^9 steps?". The answer: look for a repeating state and skip whole cycles, or find a formula for the parts that don't depend on the state.

Where frontend code uses it

The same idea in real UI code
  • Moving keyboard focus around a grid of cells (a calendar, a spreadsheet, an emoji picker) with arrow keys, stopping at the edges.
  • Testing timers and animations by stepping a fake clock forward and checking the state after each tick.
  • Replaying a list of recorded user events against a store to reproduce a bug.
  • Running a reducer over a list of actions to get the final state, which is what Redux does when you replay its history.

Related algorithms