Unit 7 — Simulation & Ad Hoc

Slide 1 of 26

A contest robot receives a long list of commands, but walls, edges, and earlier commands change what later commands do. Instead of guessing a shortcut, we FOLLOW THE RULES exactly: model the changing state, apply every step in order, and check the edges that can stop or redirect a step. We build it as a short ladder of executable demos (each with a Notice), then a full stdin solver.
- Turn a list of rules into code that carries out every step in order.
- Choose a state (a few variables, a list or a grid) that makes the rules easy to apply.
- Guard the edges by clamping values and checking bounds and walls.
- Make sure every simulation loop is certain to stop.
Lesson 1 — Model the State, Apply Every Rule in Order

First pull the starting state out of the input.

tokens = "18 7 3 5 -25 40".split()
capacity = int(tokens[0])
charge = int(tokens[1])
ticks = int(tokens[2])
print("capacity", capacity, "start charge", charge, "ticks", ticks)

Output

capacity 18 start charge 7 ticks 3

Parsing names the pieces of state (capacity, charge, number of ticks) before any rule runs.

Apply ONE rule, respecting a cap.

capacity = 10
charge = 8
change = 5
charge = charge + change
if charge > capacity:
    charge = capacity
print(charge)

Output

Adding 5 would reach 13, but the cap clamps it to 10.

Apply the rules in ORDER over a sequence, clamping after each step.

capacity = 15
charge = 6
changes = [7, 4, -30, 12]
for change in changes:
    charge = charge + change
    if charge > capacity:
        charge = capacity
    elif charge < 0:
        charge = 0
    print("after", change, "->", charge)

Output

after 7 -> 13
after 4 -> 15
after -30 -> 0
after 12 -> 12

Each change updates the running charge, clamped to [0, capacity] — the state carries forward.

Put it together: the battery program reads capacity charge ticks then the ticks changes from stdin and prints the final charge.

Try it

import sys

data = sys.stdin.read()
tokens = data.split()
capacity = int(tokens[0])
charge = int(tokens[1])
ticks = int(tokens[2])
for tick in range(ticks):
    change = int(tokens[tick + 3])
    charge = charge + change
    if charge > capacity:
        charge = capacity
    elif charge < 0:
        charge = 0
print(str(charge))

Run the full solver from this unit folder:
```
python assets/l1.py < assets/l1/1.in
```
Apply each tick's change to charge, clamping to [0, capacity]; print the final charge.

Complexity: O(ticks) — one pass over the changes.
Lesson 2 — Edges & Provable Termination

Ad-hoc loops must handle boundaries and be guaranteed to STOP. First, clamp a position to the grid edges.

position = 0
size = 5
for step in [-1, -1, 3, 9]:
    position = position + step
    if position < 0:
        position = 0
    elif position >= size:
        position = size - 1
    print(position)

Output

A step past either end is clamped, so position stays a valid index.

A robot on a grid moves only when the next square is in bounds AND not a wall (-1). This is one full simulation over a command string.

data = '3 4 1 0 5 2 3 4 6 -1 8 6 7 1 4 9 DDRRRU'
tokens = data.split()
rows = int(tokens[0])
columns = int(tokens[1])
robot_row = int(tokens[2])
robot_column = int(tokens[3])
token_position = 4
grid = []
for row in range(rows):
    current_row = []
    for column in range(columns):
        current_row.append(int(tokens[token_position]))
        token_position = token_position + 1
    grid.append(current_row)
commands = tokens[token_position]

for command in commands:
    next_row = robot_row
    next_column = robot_column
    if command == "U":
        next_row = next_row - 1
    elif command == "D":
        next_row = next_row + 1
    elif command == "L":
        next_column = next_column - 1
    elif command == "R":
        next_column = next_column + 1
    if next_row >= 0 and next_row < rows and next_column >= 0 and next_column < columns:
        if grid[next_row][next_column] != -1:
            robot_row = next_row
            robot_column = next_column
print(str(grid[robot_row][robot_column]))

Output

The bounds check (0 <= next < size) and the wall check (grid[next] != -1) together keep the robot on legal squares; blocked moves are skipped.
Make a loop PROVABLY stop: track states already seen in a LIST (using in) so a repeat ends the loop — no set needed.

state = 1
seen = []
steps = 0
while state not in seen:
    seen.append(state)
    state = (state * 2) % 7
    steps = steps + 1
print("repeat after", steps, "steps")

Output

repeat after 3 steps

Each new state is appended to seen; when a state recurs, state not in seen is false and the loop stops. (A plain step cap works too.)

Put it together: the event-walk program reads N then N points jump pairs and follows the jumps, summing points, until it lands beyond the list.

Try it

import sys

data = sys.stdin.read()
tokens = data.split()
event_count = int(tokens[0])
points = []
jumps = []
for event in range(event_count):
    points.append(int(tokens[1 + event * 2]))
    jumps.append(int(tokens[2 + event * 2]))

score = 0
event_index = 0
while event_index < event_count:
    score = score + points[event_index]
    event_index = event_index + jumps[event_index]
print(str(score))

Run the full solver from this unit folder:
```
python assets/l2.py < assets/l2/1.in
```
Add the current event's points, then jump ahead by its jump count; the walk stops when the index passes the end.

Complexity: O(N) — the index only increases, so the walk terminates.
A Simulation Checklist

(1) Name the state; (2) apply rules in the given order; (3) clamp/guard every edge; (4) make the loop provably stop (an increasing index, a step cap, or a repeat check). Correct and careful beats clever.
- Name the pieces of state first, then apply each rule in the order the problem gives.
- Clamp after every step so a value stays inside its limits, such as [0, capacity].
- A move happens only when the next square is in bounds AND not a wall.
- A loop surely stops when its index only increases, it has a step cap, or it checks for a repeated state.
- Trace a few steps by hand and compare them with the sample.
You can now simulate a contest process carefully and correctly.

Unit 7 — Simulation & Ad Hoc

Lesson 1 — Model the State, Apply Every Rule in Order

Lesson 2 — Edges & Provable Termination

A Simulation Checklist