Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 63 ยท Ad Hoc and Implementation

Implementation Problems

Learn to solve implementation problems: careful simulation, state machines, string and grid handling, and building a solution from small, separately verified pieces.

Some contest problems need no clever algorithm at all. The statement describes a process, such as a robot walking on a grid, a text being reformatted or a game being played turn by turn, and your job is to reproduce it exactly. These are called implementation problems. They are usually the cheapest points in a contest, and also the ones most often lost to a misread rule or a small slip.

The skill being tested is discipline, not insight. You read the rules slowly, split the work into small functions, check each function on its own, and only then connect them. This lesson shows that workflow on three typical shapes: a simulation, a state machine over a string and a grid fill. If something goes wrong you can fall back on the debugging habits from earlier in this track.

A workflow that works

flowchart LR
  R["Read rules twice<br/>list every special case"] --> M["Model the state<br/>(what changes?)"]
  M --> P["Write small pure<br/>functions"]
  P --> T["Assert each piece<br/>on tiny cases"]
  T --> C["Combine and run<br/>the samples"]
  C --> S["Stress test against<br/>a naive version"]

Implementation workflow: understand the rules, name the state, build and verify pieces, then combine.

  1. Read the rules twice and list the special cases. "If the robot would leave the grid it stays in place" is one line in the statement and one if in the code. Highlight every "unless", "except" and "if there are several".
  2. Name the state. Decide exactly which variables describe the world at one moment: position, direction, a counter, a set of visited cells. Everything else is derived.
  3. Write a function per rule. One function turns left, one moves, one checks bounds. Short functions are easy to verify.
  4. Assert on tiny cases. An assert turn_left("N") == "W" costs five seconds and prevents ten minutes of confusion.
  5. Combine, then compare with the samples. If you can write a naive version, compare against it with stress tests.

Simulation: a robot on a grid

Problem: a robot starts at (0, 0) facing north on a grid of W columns and H rows. Commands are L (turn left), R (turn right) and F (move forward one cell). Moving outside the grid is ignored (the robot stays). Print the final position and direction.

The state is (x, y, direction). The directions form a cycle, which is easiest to store as an index into a list, so turning is addition modulo 4.

Python Robot simulation built from small verified pieces

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the asserts. If you only ever tested run on the final samples, a swapped L/R could look right on a symmetric sample. The small checks make errors visible exactly where they are.

State machines over text

A state machine reads input one symbol at a time and keeps a small piece of memory (the state) that decides what the next symbol means. Many string problems are secretly state machines: validating a format, tokenizing an expression, collapsing repeated characters, counting words.

Problem: given a string of letters, digits and spaces, split it into tokens. A token is either a maximal run of digits (a number) or a maximal run of letters (a word); spaces separate tokens and are ignored. The state is "what kind of token am I inside right now?".

Python A tokenizer written as a state machine

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The trick s + " " is a standard device: add a sentinel at the end so the last token is flushed by the same code that flushes all the others, instead of repeating the flush after the loop. The same idea works in many languages.

When the rules get more complicated, write a transition table. Each row says "in state X, on input Y, go to state Z and do W". Writing it down first turns a long tangle of if statements into a lookup you can check against the statement line by line.

Whenever a problem says "while", "until" or "repeat", ask what the loop invariant is: what is true at the start of every iteration. If you can state it in a sentence, the loop is probably right.

Grid handling: filling a spiral

Grid problems are implementation problems with a geometric twist. Problem: print an n by m matrix filled with 1, 2, 3, ... in a clockwise spiral starting at the top-left corner.

The standard approach walks one cell at a time, keeps a direction, and turns right whenever the next cell is outside the grid or already filled. There is no formula to remember; you just apply the rule.

Python Clockwise spiral fill

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This code passes the 1-row and 1-column cases without any special handling, because the rule "turn when blocked" covers them. Prefer rules that cover edge cases automatically over separate branches for each. More grid techniques, including direction arrays and border padding, are in Grid and Matrix Tricks.

Common implementation traps

  • Off-by-one in ranges. Decide whether coordinates are 0-based or 1-based once, and convert at the input boundary only.
  • Mutating while iterating. Do not remove from a list you are looping over. Build a new list or loop over a copy.
  • Aliasing. [[0] * m] * n creates n references to one row. Always use a comprehension: [[0] * m for _ in range(n)].
  • Order of updates. In simultaneous rules (every cell changes based on the old grid), compute into a new grid, then swap.
  • Ties. "Print the lexicographically smallest" or "the first such index" is a rule you must implement, so test it with equal candidates.
  • Misreading units. Minutes versus seconds, inclusive versus exclusive ends, 0-based indexes in the output.

Do not "fix" a sample mismatch by adjusting the code until the numbers match. Find which rule you misread. A hack that makes the sample pass will usually fail on hidden tests.

When the simulation is too long

If the statement asks for the state after 10^12 steps, a direct simulation will time out, but the state space is often small and the process repeats. That is the subject of Simulation and Cycle Detection. For counting problems, a formula may replace the loop; see Ad Hoc and Constructive Problems.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the main benefit of splitting an implementation problem into small functions?

    Small pure functions are easy to verify in isolation. When the combined program fails, you already know which pieces are trustworthy.
  2. 2. Why is [[0] * m] * n a bad way to make an n by m grid?

    The outer multiplication copies the reference to one inner list n times. Use a list comprehension to create independent rows.
  3. 3. In the tokenizer, why append a space to the input string?

    A sentinel at the end triggers a state change after the final character, so no duplicate flush code is needed after the loop.
  4. 4. A problem updates every cell of a grid at once using the previous values of its neighbours. What should you do?

    Updating in place lets later cells see already-updated neighbours, which breaks the 'simultaneous' rule.

Summary

  • Implementation problems test careful reading and clean code, not clever algorithms.
  • Read the rules twice, list the special cases and name the state before coding.
  • Write small functions, assert each one on tiny cases, then combine.
  • Many text problems are state machines; sentinels simplify the last step.
  • Prefer general rules (turn when blocked) over special-case branches.
  • Beware of aliasing, in-place updates and 0-based versus 1-based confusion.

Next: Ad Hoc and Constructive Problems