FreeCampus Python

Choose an Algorithm That Fits

Recognize common algorithm patterns from the promised result, then adapt their state, stopping, ordering, tie, and no-result rules to a concrete task.
python-foundations problem-solving-algorithms algorithm-patterns searching
Open in Colab
  • Level: Python Foundations
  • Estimated time: 4–5 hours
  • You will learn: Select, trace, and adapt transform, filter, count, accumulation, search, selection, grouping, uniqueness, neighbor, and window patterns.
  • Practice in: Google Colab, JupyterLab, or a local editor

Open this lesson in Google Colab

You already know how for, if, lists, dictionaries, and sets behave. The new skill is choosing how those tools should work together when the solution has not been designed for you.

This lesson follows signals sent by lantern towers during a night festival. Keep six questions visible:

  1. What shape must the result have?
  2. What state must survive between input items?
  3. Does every item matter, or may the algorithm stop early?
  4. What result represents “nothing found”?
  5. Must input order be preserved?
  6. Which small boundary would expose a wrong adaptation?

1. Let the promised result suggest a pattern

Different requests need different result shapes:

Request Result shape State that usually persists Stop early?
Normalize every signal one output per input output collection no
Keep only active signals selected subset output collection no
Count red signals one integer counter no
Add energy readings one combined value running total no
Find the first alert one item or no result no result / found item yes
Choose the strongest tower one best item or no result running best usually no
Count each symbol key-to-count mapping frequency dictionary no
Group readings by tower key-to-values mapping group dictionary no
Keep first-seen symbols ordered collection result plus seen set no
Detect changes relationship per adjacent pair previous/current pair no
Find a sync sequence position or no result current window yes

The table is not a code generator. Words such as best, unique, and find still hide decisions. The contract must specify ties, order, eligibility, and a no-result value.

2. Transform when every input produces one output

Lantern symbols arrive in mixed case:

raw_symbols = ["r", "G", "b", "R"]
normalized = []

for symbol in raw_symbols:
    normalized.append(symbol.upper())

print(normalized)

The output is:

['R', 'G', 'B', 'R']

Trace the relationship:

Input position Input Output Output length
0 "r" "R" 1
1 "G" "G" 2
2 "b" "B" 3
3 "R" "R" 4

A transformation normally preserves the number and order of items while changing each value. A comprehension expresses the same contract compactly:

normalized = [symbol.upper() for symbol in raw_symbols]
assert normalized == ["R", "G", "B", "R"]
assert len(normalized) == len(raw_symbols)

This version accidentally filters while transforming:

incomplete = [symbol.upper() for symbol in raw_symbols if symbol != "b"]
assert incomplete == ["R", "G", "R"]

It is valid only if the contract says some inputs should disappear.

3. Filter when only matching inputs survive

Each reading contains an activation flag:

readings = [
    {"tower": "north", "energy": 4, "active": True},
    {"tower": "west", "energy": 9, "active": False},
    {"tower": "south", "energy": 6, "active": True},
]

Keep active records in encounter order:

active_readings = []

for reading in readings:
    if reading["active"]:
        active_readings.append(reading)

assert [reading["tower"] for reading in active_readings] == ["north", "south"]

Filtering asks a yes/no question for every item. The selected records do not need to be changed. A comprehension can remain readable when the predicate is short:

active_readings = [reading for reading in readings if reading["active"]]

Check empty behavior:

all_inactive = [
    {"tower": "east", "energy": 8, "active": False}
]

assert [reading for reading in all_inactive if reading["active"]] == []

An empty selected subset is not the same shape as None. The contract promised a list, so an empty list is the natural result.

4. Count matches with one explicit counter

Count red symbols without keeping the red symbols themselves:

symbols = "RGBRRY"
red_count = 0

for symbol in symbols:
    if symbol == "R":
        red_count += 1

assert red_count == 3

The counter starts at zero because no input has been processed. Each match adds one. Non-matches leave the state unchanged.

A useful invariant in plain language is:

After each iteration, red_count equals the number of R symbols in the processed prefix.

Do not confuse counting items with adding their values:

energy_readings = [4, 9, 6]
reading_count = len(energy_readings)
energy_total = sum(energy_readings)

assert reading_count == 3
assert energy_total == 19

5. Accumulate with an initial value that fits the operation

A running total begins at zero:

energy_readings = [4, 9, 6]
running_energy = 0

for energy in energy_readings:
    running_energy += energy

assert running_energy == 19

A trace shows why:

Energy Total before Total after
4 0 4
9 4 13
6 13 19

Joining text has a different practical pattern. Repeated += can work for small text, but collecting pieces and joining once makes the intended separator explicit:

symbols = ["R", "G", "B"]
message = "-".join(symbols)
assert message == "R-G-B"

An initial value must match the contract. Zero is suitable for addition, an empty list for collecting results, and None for “no candidate yet.” There is no universal initializer for every accumulation.

6. Search for a first match and stop deliberately

Find the first energy reading at or above an alert threshold:

def first_alert(energies, threshold):
    """Return the first alert value, or None when no value qualifies."""
    for energy in energies:
        if energy >= threshold:
            return energy
    return None

Run distinct cases:

assert first_alert([3, 8, 12, 7], 10) == 12
assert first_alert([10, 12], 10) == 10
assert first_alert([2, 4, 6], 10) is None
assert first_alert([], 10) is None

Returning immediately is correct because later matches cannot replace the first match. The return after the loop handles every no-match path.

Compare three related questions:

energies = [3, 8, 12, 7]

has_alert = any(energy >= 10 for energy in energies)
all_safe = all(energy < 15 for energy in energies)
first_value = first_alert(energies, 10)

assert has_alert is True
assert all_safe is True
assert first_value == 12

any promises a Boolean, all promises a Boolean, and first_alert promises a value or None. The request determines which shape is useful.

7. Select the best item with an explicit tie rule

A strongest-tower request cannot usually stop at the first strong reading. A later tower may be stronger.

def strongest_tower(readings):
    """Return the active tower with greatest energy, or None."""
    best = None

    for reading in readings:
        if not reading["active"]:
            continue
        if best is None or reading["energy"] > best["energy"]:
            best = reading

    return best

Trace the running best:

tower_readings = [
    {"tower": "north", "energy": 4, "active": True},
    {"tower": "west", "energy": 20, "active": False},
    {"tower": "south", "energy": 6, "active": True},
    {"tower": "east", "energy": 6, "active": True},
]

winner = strongest_tower(tower_readings)
assert winner["tower"] == "south"

west is ineligible. south replaces north. east ties south but does not replace it because the condition uses > rather than >=; the earlier active record wins.

After understanding the contract, a built-in can express part of it:

active = [reading for reading in tower_readings if reading["active"]]
winner = max(active, key=lambda reading: reading["energy"], default=None)
assert winner["tower"] == "south"

max keeps the first maximal item, but the filtering and no-result choice still come from your contract.

8. Build a frequency table for every distinct symbol

Counting only R needs one integer. Counting every symbol needs a mapping from symbol to count:

def symbol_frequencies(signal):
    """Return the occurrence count for every signal symbol."""
    frequencies = {}

    for symbol in signal:
        frequencies[symbol] = frequencies.get(symbol, 0) + 1

    return frequencies

Trace "ABACA":

Symbol Mapping before Mapping after
A {} {'A': 1}
B {'A': 1} {'A': 1, 'B': 1}
A {'A': 1, 'B': 1} {'A': 2, 'B': 1}
C {'A': 2, 'B': 1} {'A': 2, 'B': 1, 'C': 1}
A {'A': 2, 'B': 1, 'C': 1} {'A': 3, 'B': 1, 'C': 1}

Check ordinary and empty behavior:

assert symbol_frequencies("ABACA") == {"A": 3, "B": 1, "C": 1}
assert symbol_frequencies("") == {}

.get(symbol, 0) supplies the count before a symbol has appeared. The stored count then becomes state for later occurrences.

9. Group records when each key owns several values

Frequency counting stores one integer per key. Grouping stores a collection or other aggregate per key.

def energies_by_tower(readings):
    """Return active energy values grouped by tower name."""
    groups = {}

    for reading in readings:
        if not reading["active"]:
            continue
        tower = reading["tower"]
        groups.setdefault(tower, []).append(reading["energy"])

    return groups

Use repeated tower names:

repeated_readings = [
    {"tower": "north", "energy": 4, "active": True},
    {"tower": "south", "energy": 6, "active": True},
    {"tower": "north", "energy": 7, "active": True},
    {"tower": "south", "energy": 9, "active": False},
]

assert energies_by_tower(repeated_readings) == {
    "north": [4, 7],
    "south": [6],
}

Choose the stored value from the output contract:

  • counts per tower → integer;
  • energy values per tower → list;
  • energy total per tower → running numeric total;
  • latest reading per tower → one record.

All use a dictionary, but they are different algorithms because their updates and output shapes differ.

10. Remove duplicates without losing first-seen order

A set can remove duplicates, but a set result does not promise encounter order. When order matters, keep both a membership structure and an output structure:

def unique_in_order(values):
    """Return first occurrences in their original order."""
    seen = set()
    result = []

    for value in values:
        if value not in seen:
            seen.add(value)
            result.append(value)

    return result

Check cases that expose the contract:

assert unique_in_order(["R", "G", "R", "B"]) == ["R", "G", "B"]
assert unique_in_order([]) == []
assert unique_in_order(["R", "R", "R"]) == ["R"]
assert unique_in_order(["B", "R", "B"]) == ["B", "R"]

These structures have different jobs:

  • seen answers “has this value appeared?”;
  • result preserves “in what order did new values appear?”

Returning list(set(values)) does not express the order promise, even when one small run happens to look right.

Checkpoint: selection, frequencies, grouping, and uniqueness

11. Compare neighbors without losing an endpoint

Some questions concern relationships between adjacent values: Did energy rise? Where did the symbol change? How many equal pairs occur?

An index-based scan names both positions:

def rising_steps(values):
    """Return indexes where a value is greater than its predecessor."""
    rises = []

    for index in range(1, len(values)):
        if values[index] > values[index - 1]:
            rises.append(index)

    return rises

Check the first comparable index and small inputs:

assert rising_steps([3, 5, 4, 8]) == [1, 3]
assert rising_steps([]) == []
assert rising_steps([7]) == []
assert rising_steps([7, 7]) == []

Starting at 1 is deliberate: index 0 has no predecessor. A paired traversal can express the values rather than indexes:

values = [3, 5, 4, 8]
pairs = list(zip(values, values[1:]))
assert pairs == [(3, 5), (5, 4), (4, 8)]

Use indexes when the position itself is part of the result. Use paired values when only the relationship matters.

12. Scan a fixed-size window for a local pattern

A synchronization marker is the first consecutive window whose symbols are all distinct. Return the 1-based end position of that window:

def first_sync_end(signal, width):
    """Return the 1-based end of the first distinct window, or None."""
    if width <= 0:
        return None

    for end in range(width, len(signal) + 1):
        window = signal[end - width : end]
        if len(set(window)) == width:
            return end

    return None

Trace "AABCDEF" with width 4:

end Slice indexes Window Distinct?
4 0:4 AABC no
5 1:5 ABCD yes

The function returns 5, meaning that five input symbols have been processed when the marker ends. It does not return the zero-based start index 1.

Check boundaries:

assert first_sync_end("AABCDEF", 4) == 5
assert first_sync_end("Z", 1) == 1
assert first_sync_end("ABCD", 4) == 4
assert first_sync_end("AAAA", 2) is None
assert first_sync_end("ABC", 4) is None
assert first_sync_end("ABC", 0) is None

Writing the slice and returned-position meanings beside the trace prevents a common off-by-one error.

13. Combine patterns only when the contract connects them

Suppose the task is: “From active readings, return normalized tower names.” A filter followed by a transform directly matches the words:

active_names = [
    reading["tower"].upper()
    for reading in readings
    if reading["active"]
]

assert active_names == ["NORTH", "SOUTH"]

A longer sequence may be clearer as named stages:

active = [reading for reading in readings if reading["active"]]
energies = [reading["energy"] for reading in active]
total = sum(energies)

assert total == 10

One loop can combine filter, transform, and accumulate:

total = 0
for reading in readings:
    if reading["active"]:
        total += reading["energy"]

assert total == 10

Neither version is automatically superior. The staged form exposes reusable intermediate results. The combined form avoids building intermediate lists. Use the contract, scale, and clarity—not a slogan that fewer loops are always better.

14. Built-ins express patterns but do not decide the contract

Python provides concise operations:

values = [4, 9, 6]

assert sum(values) == 19
assert min(values) == 4
assert max(values) == 9
assert any(value > 8 for value in values) is True
assert all(value > 0 for value in values) is True
assert sorted(values) == [4, 6, 9]

Before choosing one, identify the promised result:

  • sum accumulates numeric values;
  • min and max select one extreme value;
  • any and all return Booleans and may stop early;
  • sorted returns a complete ordered list.

A built-in cannot infer eligibility or a product-specific tie rule. Provide those decisions explicitly:

best_active = max(
    (reading for reading in readings if reading["active"]),
    key=lambda reading: reading["energy"],
    default=None,
)

assert best_active["tower"] == "south"

This is concise only after the generator expression, key, and default are understood. A direct loop is preferable when it better exposes the current learning goal or complex tie behavior.

15. Repair patterns chosen from one keyword

“Find all red signals”

A first-match search is wrong because all matching values must appear in the result.

red_positions = [
    index
    for index, symbol in enumerate("RGBRRY")
    if symbol == "R"
]

assert red_positions == [0, 3, 4]

“Return unique signals”

The word unique is ambiguous. It might mean distinct values in first-seen order:

assert unique_in_order("ABACA") == ["A", "B", "C"]

Or it might mean values that occur exactly once:

frequencies = symbol_frequencies("ABACA")
once_only = [symbol for symbol in "ABACA" if frequencies[symbol] == 1]
assert once_only == ["B", "C"]

“Choose the best reading”

Define eligibility, comparison direction, tie rule, no-result behavior, returned shape, and whether every item must be inspected. Only then choose running-best, max, sorting, or another strategy.

Checkpoint: neighbors, windows, combinations, and built-ins

16. Lab: decode the lantern relay

Use this signal and reading sequence:

relay_signal = "RRGYBGRY"
relay_energy = [2, 5, 3, 8, 1, 4, 7, 2]

Implement these contracts:

def count_symbols(signal):
    """Return a frequency dictionary for signal."""
    pass


def first_energy_at_least(values, threshold):
    """Return the first qualifying energy value, or None."""
    pass


def rising_energy_positions(values):
    """Return indexes whose values are greater than their predecessors."""
    pass


def first_distinct_window_end(signal, width):
    """Return the 1-based end of the first distinct window, or None."""
    pass

Use these progressive checks:

assert count_symbols("") == {}
assert count_symbols("RRGYBGRY") == {"R": 3, "G": 2, "Y": 2, "B": 1}

assert first_energy_at_least([], 6) is None
assert first_energy_at_least(relay_energy, 6) == 8

assert rising_energy_positions([]) == []
assert rising_energy_positions([5]) == []
assert rising_energy_positions(relay_energy) == [1, 3, 5, 6]

assert first_distinct_window_end("AAAA", 2) is None
assert first_distinct_window_end("RRGYBGRY", 4) == 5

For each function, record:

  • promised result shape;
  • persistent state;
  • stopping rule;
  • empty/no-result value;
  • order requirement; and
  • one boundary that could expose a mistake.
Hint: solve the window on paper

For width four, list candidate windows in order. RRGY repeats R; the next window, RGYB, contains four distinct symbols and ends after five processed symbols.

Show the window evidence

The width-four windows begin RRGY, RGYB, GYBG, YBGR, and BGRY. RGYB is the first all-distinct window and ends after position 5, which agrees with the supplied assertion.

17. Name the state and stopping rule

Complete this table for your lab before checking the summary:

Function State Stops early? No-result/empty output
count_symbols
first_energy_at_least
rising_energy_positions
first_distinct_window_end
Compare the pattern choices
  • count_symbols: frequency dictionary; no early stop; {} for empty input.
  • first_energy_at_least: no persistent collection, only current value; stops on a match; None for no match.
  • rising_energy_positions: result list plus adjacent values/index; examines all pairs; [] for fewer than two values.
  • first_distinct_window_end: current candidate window/end position; stops on a match; None for invalid width or no matching window.

Key points

  • Start from the promised result shape, then choose state, update, stopping, order, tie, and no-result behavior.
  • Transform, filter, count, accumulate, search, select, group, deduplicate, compare neighbors, and scan windows answer different questions.
  • Built-ins express familiar algorithms but cannot decide product rules.
  • Several clear passes can be better than one overloaded pass; one combined pass can be better when intermediate collections add no value.
  • A pattern is only a starting structure. Acceptance examples determine whether its adaptation is correct.

References

Back to top