Algorithms · 26
Simulation and Brute Force
Do exactly what the story says, step by step, and try every candidate without skipping one.
The first step in algorithms is not being clever.
The robot in the example below lives in a corridor of cells 1 to n.
It moves one cell per command, L (left) or R (right), and stays put when a wall is in the way.
The program prints every starting cell from which the robot ends on cell goal, and then how many there are.
n, goal = map(int, input().split())moves = input().strip()count = 0for start in range(1, n + 1): # 모두 해 보기: 출발 칸 후보 n개 pos = start # 후보마다 처음부터 다시 for m in moves: # 그대로 따라 하기: 명령 하나에 한 걸음 if m == "L" and pos > 1: pos -= 1 elif m == "R" and pos < n: pos += 1 if pos == goal: print(start) count += 1print(count)const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, goal] = lines[0].split(" ").map(Number);const moves = lines[1].trim();let count = 0;for (let start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 let pos = start; // 후보마다 처음부터 다시 for (const m of moves) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m === "L" && pos > 1) pos--; else if (m === "R" && pos < n) pos++; } if (pos === goal) { console.log(start); count++; }}console.log(count);import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, goal] = lines[0].split(" ").map(Number);const moves: string = lines[1].trim();let count: number = 0;for (let start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 let pos: number = start; // 후보마다 처음부터 다시 for (const m of moves) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m === "L" && pos > 1) pos--; else if (m === "R" && pos < n) pos++; } if (pos === goal) { console.log(start); count++; }}console.log(count);import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), goal = sc.nextInt(); String moves = sc.next(); int count = 0; for (int start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 int pos = start; // 후보마다 처음부터 다시 for (char m : moves.toCharArray()) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m == 'L' && pos > 1) pos--; else if (m == 'R' && pos < n) pos++; } if (pos == goal) { System.out.println(start); count++; } } System.out.println(count); }}using System; class Program{ static void Main() { string[] first = Console.ReadLine().Split(' '); int n = int.Parse(first[0]), goal = int.Parse(first[1]); string moves = Console.ReadLine().Trim(); int count = 0; for (int start = 1; start <= n; start++) // 모두 해 보기: 출발 칸 후보 n개 { int pos = start; // 후보마다 처음부터 다시 foreach (char m in moves) // 그대로 따라 하기: 명령 하나에 한 걸음 { if (m == 'L' && pos > 1) pos--; else if (m == 'R' && pos < n) pos++; } if (pos == goal) { Console.WriteLine(start); count++; } } Console.WriteLine(count); }}#include <iostream>#include <string> int main() { int n, goal, count = 0; std::string moves; std::cin >> n >> goal >> moves; for (int start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 int pos = start; // 후보마다 처음부터 다시 for (char m : moves) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m == 'L' && pos > 1) pos--; else if (m == 'R' && pos < n) pos++; } if (pos == goal) { std::cout << start << '\n'; count++; } } std::cout << count << '\n';}#include <stdio.h> int main(void) { int n, goal, count = 0; char moves[1001]; scanf("%d %d %1000s", &n, &goal, moves); for (int start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 int pos = start; // 후보마다 처음부터 다시 for (int i = 0; moves[i] != '\0'; i++) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (moves[i] == 'L' && pos > 1) pos--; else if (moves[i] == 'R' && pos < n) pos++; } if (pos == goal) { printf("%d\n", start); count++; } } printf("%d\n", count); return 0;}first = Console.ReadNumbers();n = first[0];goal = first[1];moves = Console.ReadLine().Trim();count = 0;for (start = 1; start <= n; start++){ pos = start; // 후보마다 처음부터 다시 foreach (m in moves) { if (m == "L" && pos > 1) { pos -= 1; } else if (m == "R" && pos < n) { pos += 1; } } if (pos == goal) { Console.WriteLine(start); count += 1; }}Console.WriteLine(count);6 3 LLLRR
1 2 3 4 4
Key points
- Simulation turns the story into code in the same order.
Keep the current state in variables (here the robot's positionpos) and update it by the rules at each step.
Because of the walls, a formula such as "rights minus lefts" does not give the answer, so actually walking is the surest way. - Brute force (exhaustive search) tries every candidate that could be an answer and keeps the ones that pass.
Here the candidates are the starting cells 1 to n.
If no candidate is skipped, no answer is missed. - Reset the state for each candidate.
That is whypos = startsits inside the outer loop. - Before writing it, count the steps: number of candidates × steps per candidate.
For this example that is n × number of commands.
Choosing two out of n gives n × (n − 1) ÷ 2 pairs (19,900 for n = 200), deciding in-or-out n times gives 2ⁿ cases (about a million for n = 20), and the orders of a line of n things number n!
(about 3.6 million for n = 10). - Here one step is carrying out one command once (one lap of the inner loop).
Measured on our judge with this example: 10 million steps (10,000 cells × 1,000 commands) finished within a second in all eight languages.
At 100 million steps (10,000 cells × 10,000 commands), C, C++, Java and C# finished within a second and JavaScript and TypeScript in about a second, but Python went over its 4-second limit.
Craykon finished 40 million steps, but at 50 million it stopped with "Took too long". - If the step count is comfortable, brute force is enough.
Look for something faster only when it is too large, and even then keep the slow solution to check the fast one on small inputs.
How each language writes it
| Python | Reset with pos = start inside for start in range(1, n + 1):, and read the commands one character at a time with for m in moves:.itertools.combinations(nums, 2) makes the pairs and itertools.permutations(nums) makes every order |
|---|---|
| JavaScript | let pos = start; inside for (let start = 1; start <= n; start++), commands with for (const m of moves).To choose two, start the inner loop at let j = i + 1 |
| TypeScript | Same as JavaScript |
| Java | Put int pos = start; inside the outer loop; commands with for (char m : moves.toCharArray()).Compare characters with single quotes ( m == 'L') |
| C# | Put int pos = start; inside the outer loop; commands with foreach (char m in moves).A character is 'L' |
| C++ | Commands with for (char m : moves), a character is 'L'.For every order, sort a vector and repeat std::next_permutation(v.begin(), v.end()) until it returns false |
| C | Commands with for (int i = 0; moves[i] != '\0'; i++) — loop by index up to the terminating '\0'.A character is 'L' |
| Craykon | pos = start; inside for (start = 1; start <= n; start++), commands with foreach (m in moves).One run has a limit on the number of steps; beyond it the program stops with "Took too long (an endless loop?)" |
Common mistakes
Not resetting for each candidate
let sum = 0;
for (let x = 10; x <= 12; x++) {
for (const d of String(x)) sum += Number(d);
console.log(x, sum);
}→ 10 1, 11 3, 12 6 — the digit sums should be 1, 2, 3, but the previous candidate's sum is still there and keeps growing
Move let sum = 0; inside the outer loop so every candidate starts from 0.
Counting the same pair twice
int nums[] = {1, 2, 3, 4}, count = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (nums[i] + nums[j] == 4) count++;
printf("%d\n", count);→ 3 — only one pair, (1, 3), adds up to 4, but the reversed (3, 1) and 2 paired with itself, (2, 2), were counted too
Start the inner loop at j = i + 1.
Each pair is then seen once and nothing is paired with itself, so it prints 1.
Updating cells while still reading their neighbours
cells = list("O..")
for i in range(3):
left = i > 0 and cells[i - 1] == "O"
right = i < 2 and cells[i + 1] == "O"
cells[i] = "O" if cells[i] == "." and left != right else "."
print("".join(cells))→ ... — the answer is .O.. The rule is "a lit cell goes dark, and a dark cell lights up when exactly one neighbour is lit" (left != right means "exactly one"), and every cell must change at the same time. But cell 0 was switched off first, so when cell 1 looked at its neighbour it was already dark
Write the next state into a new list and swap it in once it is complete.
Start with after = [], collect with after.append(...), and set cells = after after the loop.
Then it prints .O..
How languages differ
Make a habit of counting the steps from the input sizes in the problem first.
If the count is comfortable, the simplest solution is the best one.
When a simulation gives a wrong answer, walk through a small input by hand, one step at a time, and compare with the variables.
Look first at the edges, such as the walls, for a position that is off by one.
Make a habit of counting the steps from the input sizes in the problem first.
If the count is comfortable, the simplest solution is the best one.
When a simulation gives a wrong answer, walk through a small input by hand, one step at a time, and compare with the variables.
Look first at the edges, such as the walls, for a position that is off by one.