Exhaustive search

These problems can be solved by exhaustively generating candidate solutions and keeping those that satisfy the problem’s requirements, e.g. the best solution. The search may stop early, e.g. if only the first solution is needed. This approach is also called brute-force search, or generate and test.

In a linear search, the candidates are the items in a given collection: list, string, set, etc. Candidates are ‘generated’ by iterating through the collection. The search may require an additional collection to keep information about the items already processed.

  1. Hot Hike (10 LOC): Given the air temperatures over several days, find the lowest n that minimises the temperature on days n and n+2.

  2. Pea Soup and Pancakes (15 LOC): Given a list of restaurants and their menus, find the first one that serves pea soup and pancakes.

  3. Saving Princess Peach (7 LOC): Find all obstacles that Super Mario missed.

  4. ICPC Awards (8 LOC): Given a list of university teams, find the first team of each university.

  5. Amalgamated Artichokes (11 LOC): Given the fluctuation of stock prices over time, find the start and end of the largest price drop. Use the math library functions sin and cos to compute the prices.

Combinations

In these problems, each candidate is a combination of digits, letters or other items. Generating all combinations may require nested loops.

  1. Heir’s Dilemma (14 LOC): Count how many 6-digit PINs, within a given range, have distinct digits and are divisible by each of their digits.

Backtracking

This technique incrementally builds a candidate. As soon as the partial candidate cannot lead to a solution, the algorithm tries a different one. Backtracking is usually implemented recursively.

  1. Boggle (48 LOC): Given a list of words, find all that occur in a 4x4 grid of letters.