Advanced Examples

"""Example 53: N-Queens by Backtracking with Pruning."""
 
# Backtracking (co-25) places queens column by column, checking safety
# against every PREVIOUSLY placed queen; the moment a placement is unsafe,
# it prunes -- never even exploring the rest of that doomed branch further.
 
 
def solve_n_queens(n: int) -> int:  # => returns the COUNT of distinct solutions
    solutions = [0]  # => a one-element list used as a mutable counter in the closure
    columns_used: set[int] = set()  # => which columns already have a queen
    diag1_used: set[int] = set()  # => which "row - col" diagonals already have a queen
    diag2_used: set[int] = set()  # => which "row + col" diagonals already have a queen
 
    def place(row: int) -> None:  # => tries placing a queen in every column of this row
        if row == n:  # => base case: every row has a safely placed queen
            solutions[0] += 1  # => one more complete, valid solution found
            return  # => backtracks to try other placements at the previous row
        for col in range(n):  # => tries every column in this row
            if (  # => opens the three-way safety check for this column
                col in columns_used  # => same column already has a queen
                or (row - col) in diag1_used  # => same "/" diagonal already has a queen
                or (row + col) in diag2_used  # => same "\" diagonal already has a queen
            ):  # => THE PRUNE: this column is attacked by an earlier queen
                continue  # => skip this column entirely -- never explore it further
            columns_used.add(col)  # => marks this column as occupied
            diag1_used.add(row - col)  # => marks this "/" diagonal as occupied
            diag2_used.add(row + col)  # => marks this "\" diagonal as occupied
            place(row + 1)  # => recurses to place the NEXT row's queen
            columns_used.remove(col)  # => THE BACKTRACK: undoes this choice
            diag1_used.remove(row - col)  # => frees this diagonal for other branches
            diag2_used.remove(row + col)  # => frees this diagonal too
 
    place(0)  # => starts placing from row 0
    return solutions[0]  # => the total count of valid N-queens solutions
 
 
known_counts: dict[int, int] = {  # => OEIS A000170: the known solution count per N
    4: 2,  # => N=4 has exactly 2 distinct solutions
    5: 10,  # => N=5 has exactly 10 distinct solutions
    6: 4,  # => N=6 has exactly 4 distinct solutions
    7: 40,  # => N=7 has exactly 40 distinct solutions
    8: 92,  # => N=8 has exactly 92 distinct solutions
}  # => closes the known-solution-count table
for (  # => opens the tuple-unpacking loop header
    n,  # => the board size N
    expected,  # => N's known correct solution count
) in known_counts.items():  # => verifies N=4..8, as the syllabus specifies
    found = solve_n_queens(n)  # => backtracking's own count
    print(f"N={n}: {found}")  # => Output: one "N=n: count" line per N
    assert found == expected  # => confirms against the well-known OEIS counts
print("ex-53 OK")  # => Output: ex-53 OK

N=4: 2
N=5: 10
N=6: 4
N=7: 40
N=8: 92
ex-53 OK

"""Example 53: pytest verification for N-Queens Backtracking."""
 
from example import solve_n_queens
 
 
def test_known_solution_counts_for_small_n() -> None:
    assert solve_n_queens(1) == 1  # => trivially one way to place a single queen
    assert solve_n_queens(4) == 2
    assert solve_n_queens(8) == 92
 
 
def test_n_equals_two_and_three_have_no_solutions() -> None:
    assert solve_n_queens(2) == 0  # => too small a board to avoid all attacks
    assert solve_n_queens(3) == 0
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 54: Enumerate All Subsets by Backtracking -- Exactly 2^n of Them."""
 
# At each element, backtracking (co-25) branches into TWO choices: include
# it, or don't. n independent binary choices produce exactly 2^n leaves --
# no pruning needed here, since every combination of choices is valid.
 
 
def all_subsets(items: list[int]) -> list[list[int]]:  # => returns all 2^n subsets
    result: list[list[int]] = []  # => accumulates every complete subset found
    current: list[int] = []  # => the in-progress subset being built
 
    def backtrack(index: int) -> None:  # => decides item[index]'s fate: in or out
        if index == len(items):  # => base case: every item has been decided
            result.append(list(current))  # => records a COPY -- current keeps mutating
            return
        current.append(items[index])  # => CHOICE 1: include this item
        backtrack(index + 1)  # => explores every subset that includes it
        current.pop()  # => BACKTRACK: undoes that inclusion
        backtrack(index + 1)  # => CHOICE 2: explores every subset that excludes it
 
    backtrack(0)  # => starts deciding from the first item
    return result  # => every one of the 2^n possible subsets
 
 
items: list[int] = [1, 2, 3]  # => a small 3-element set
subsets = all_subsets(items)  # => all 8 subsets of {1, 2, 3}
print(len(subsets))  # => Output: 8
print(  # => opens the sorted-subsets print call
    sorted(subsets)  # => sorts for a deterministic, readable print order
)  # => Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
 
assert len(subsets) == 2 ** len(items)  # => confirms exactly 2^n subsets were generated
unique_subsets = {  # => opens the duplicate-detection set comprehension
    tuple(s)
    for s in subsets  # => converts each list subset to a hashable tuple
}  # => tuples are hashable, so a set catches duplicates
assert len(unique_subsets) == len(subsets)  # => confirms NO subset was generated twice
assert [] in subsets  # => confirms the empty subset is included
assert items in subsets  # => confirms the full set itself is included
print("ex-54 OK")  # => Output: ex-54 OK

8
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
ex-54 OK

"""Example 54: pytest verification for Backtracking Subsets."""
 
from example import all_subsets
 
 
def test_subset_count_is_two_to_the_n() -> None:
    for n in range(6):
        items = list(range(n))
        assert len(all_subsets(items)) == 2**n
 
 
def test_no_duplicate_subsets_are_generated() -> None:
    subsets = all_subsets([1, 2, 3, 4])
    unique = {tuple(s) for s in subsets}
    assert len(unique) == len(subsets)
 
 
def test_empty_input_yields_only_the_empty_subset() -> None:
    assert all_subsets([]) == [[]]
 
 
# => Run: pytest -- Output: 3 passed

3 passed

"""Example 55: Enumerate All Permutations by Backtracking -- Exactly n! of Them."""
 
# At each position, backtracking (co-25) tries every UNUSED item; n choices
# for the first slot, n-1 for the second, and so on -- the classic n!
# counting argument, realized directly as recursive choice-and-undo.
 
 
def all_permutations(  # => builds every ordering by choosing one UNUSED item at a time
    items: list[int],  # => the items to permute
) -> list[list[int]]:  # => returns all n! orderings
    result: list[list[int]] = []  # => accumulates every complete permutation
    current: list[int] = []  # => the in-progress permutation being built
    used: set[int] = set()  # => which items are already placed in `current`
 
    def backtrack() -> (
        None
    ):  # => fills the next position, then backtracks to try others
        if len(current) == len(items):  # => base case: every item has been placed
            result.append(list(current))  # => records a COPY of the completed ordering
            return
        for item in items:  # => tries every item as the NEXT position's value
            if item in used:  # => already placed earlier in this branch -- skip it
                continue  # => THE PRUNE: never reconsider an already-used item
            used.add(item)  # => marks item as placed
            current.append(item)  # => appends it to the in-progress ordering
            backtrack()  # => recurses to fill the remaining positions
            current.pop()  # => BACKTRACK: undoes the append
            used.remove(item)  # => frees item for other branches
 
    backtrack()  # => starts with an empty ordering
    return result  # => every one of the n! possible orderings
 
 
items: list[int] = [1, 2, 3]  # => a small 3-element set
perms = all_permutations(items)  # => all 6 permutations of [1, 2, 3]
print(len(perms))  # => Output: 6
print(  # => opens the sorted-permutations print call
    sorted(perms)  # => sorts for a deterministic, readable print order
)  # => Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
 
assert len(perms) == 6  # => 3! = 6, confirms the exact expected count
unique_perms = {tuple(p) for p in perms}  # => tuples are hashable, catching duplicates
assert len(unique_perms) == len(perms)  # => confirms every permutation is DISTINCT
for p in perms:  # => confirms every permutation is a valid rearrangement of items
    assert sorted(p) == sorted(items)  # => same multiset of elements, just reordered
print("ex-55 OK")  # => Output: ex-55 OK

6
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
ex-55 OK

"""Example 55: pytest verification for Backtracking Permutations."""
 
import math
 
from example import all_permutations
 
 
def test_permutation_count_is_n_factorial() -> None:
    for n in range(5):
        items = list(range(n))
        assert len(all_permutations(items)) == math.factorial(n)
 
 
def test_all_permutations_are_distinct() -> None:
    perms = all_permutations([1, 2, 3, 4])
    unique = {tuple(p) for p in perms}
    assert len(unique) == len(perms)
 
 
def test_empty_input_yields_one_empty_permutation() -> None:
    assert all_permutations([]) == [[]]
 
 
# => Run: pytest -- Output: 3 passed

3 passed

"""Example 56: Grid Word Search via Backtracking."""
 
# Backtracking (co-25) tries extending a partial match in all 4 directions
# from each cell, marking cells VISITED so the same letter isn't reused
# twice in one path -- and un-marking them on the way back out, so other
# starting cells can still use that same grid position.
 
 
def word_search(grid: list[list[str]], word: str) -> bool:  # => True if word is found
    rows, cols = len(grid), len(grid[0])  # => the grid's dimensions
    visited: set[tuple[int, int]] = set()  # => cells used in the CURRENT path attempt
 
    def backtrack(r: int, c: int, index: int) -> bool:  # => tries to match word[index:]
        if index == len(word):  # => base case: every character has been matched
            return True  # => the whole word was found along this path
        if (  # => opens the four-way out-of-bounds/reuse/mismatch check
            r < 0  # => off the top edge
            or r >= rows  # => off the bottom edge
            or c < 0  # => off the left edge
            or c >= cols  # => off the right edge
            or (r, c) in visited  # => this cell is already used in the current path
            or grid[r][c] != word[index]  # => this cell's letter doesn't match
        ):  # => out of bounds, already used, or the letter doesn't match
            return False  # => THE PRUNE: this path cannot possibly succeed
        visited.add((r, c))  # => marks this cell as used for the current path
        found = (  # => opens the 4-direction exploration
            backtrack(r + 1, c, index + 1)  # => try DOWN
            or backtrack(r - 1, c, index + 1)  # => try UP
            or backtrack(r, c + 1, index + 1)  # => try RIGHT
            or backtrack(r, c - 1, index + 1)  # => try LEFT
        )  # => tries all 4 directions -- `or` short-circuits on the first success
        visited.remove(  # => opens the un-mark-cell call
            (r, c)  # => the cell to free
        )  # => BACKTRACK: frees this cell for OTHER starting attempts
        return found  # => whether any of the 4 directions led to a full match
 
    for r in range(rows):  # => tries every cell as a possible STARTING point
        for c in range(cols):  # => and every column within that row
            if backtrack(r, c, 0):  # => a full match was found starting here
                return True  # => no need to try any other starting cell
    return False  # => no starting cell led to a complete match anywhere
 
 
grid: list[list[str]] = [  # => a 3x4 letter grid
    ["A", "B", "C", "E"],  # => row 0
    ["S", "F", "C", "S"],  # => row 1
    ["A", "D", "E", "E"],  # => row 2
]  # => closes the grid literal
print(word_search(grid, "ABCCED"))  # => Output: True -- A->B->C->C->E->D, a valid path
print(word_search(grid, "SEE"))  # => Output: True -- S->E->E, a valid path
print(word_search(grid, "ABCB"))  # => Output: False -- would need to reuse a cell
 
assert word_search(grid, "ABCCED") is True  # => confirms a genuinely findable word
assert word_search(grid, "SEE") is True  # => confirms another findable word
assert word_search(grid, "ABCB") is False  # => confirms reuse is correctly disallowed
assert word_search(grid, "ZZZ") is False  # => confirms a wholly absent word fails too
print("ex-56 OK")  # => Output: ex-56 OK

True
True
False
ex-56 OK

"""Example 56: pytest verification for Grid Word Search."""
 
from example import word_search
 
 
def test_finds_a_word_that_exists_along_a_valid_path() -> None:
    grid = [["A", "B"], ["C", "D"]]
    assert word_search(grid, "ABDC") is True  # => A -> B -> D -> C, all adjacent
 
 
def test_rejects_a_word_requiring_cell_reuse() -> None:
    grid = [["A", "A"]]
    assert word_search(grid, "AAA") is False  # => only 2 cells, word needs 3 A's
 
 
def test_single_cell_grid_matches_single_character_word() -> None:
    grid = [["X"]]
    assert word_search(grid, "X") is True
    assert word_search(grid, "Y") is False
 
 
# => Run: pytest -- Output: 3 passed

3 passed

"""Example 57: Solve Sudoku by Constraint Backtracking."""
 
# Backtracking (co-25) fills the FIRST empty cell with each candidate 1-9,
# checking the row/column/3x3-box constraints before committing -- an
# invalid candidate is pruned immediately, never explored further.
 
Board = list[list[int]]  # => a 9x9 grid; 0 marks an empty cell
 
 
def find_empty(board: Board) -> tuple[int, int] | None:  # => the first 0 cell, or None
    for r in range(9):  # => scans row by row
        for c in range(9):  # => and column by column within that row
            if board[r][c] == 0:  # => an unfilled cell
                return (r, c)  # => the next cell backtracking should try to fill
    return None  # => no empty cells remain -- the board is completely filled
 
 
def is_valid(board: Board, r: int, c: int, digit: int) -> bool:  # => the 3 Sudoku rules
    if digit in board[r]:  # => RULE 1: digit must not already be in this row
        return False  # => row conflict -- reject
    if digit in [board[i][c] for i in range(9)]:  # => RULE 2: nor in this column
        return False  # => column conflict -- reject
    box_r, box_c = 3 * (r // 3), 3 * (c // 3)  # => the top-left corner of this 3x3 box
    for i in range(box_r, box_r + 3):  # => RULE 3: nor anywhere in this 3x3 box
        for j in range(box_c, box_c + 3):  # => scans every cell of the 3x3 box
            if board[i][j] == digit:  # => the digit already appears in this box
                return False  # => box conflict -- reject
    return True  # => digit violates none of the three rules at this position
 
 
def solve_sudoku(board: Board) -> bool:  # => mutates board in place; True if solved
    empty = find_empty(board)  # => finds the next cell needing a digit
    if empty is None:  # => base case: no empty cells left -- solved!
        return True  # => nothing left to fill -- solved
    r, c = empty  # => the (row, col) to try filling next
    for digit in range(1, 10):  # => tries every candidate digit 1-9
        if is_valid(  # => opens the rule-check call
            board,  # => the current, partially-filled board
            r,  # => the row of the cell being tried
            c,  # => the column of the cell being tried
            digit,  # => the current board state and candidate digit
        ):  # => THE PRUNE: skip digits violating the rules
            board[r][c] = digit  # => commits this candidate
            if solve_sudoku(board):  # => recurses to fill the rest of the board
                return True  # => this whole branch led to a full solution
            board[r][c] = 0  # => BACKTRACK: this digit didn't lead anywhere -- undo it
    return False  # => no digit at (r, c) works -- an earlier choice must be wrong
 
 
puzzle: Board = [  # => a well-known easy Sudoku puzzle
    [5, 3, 0, 0, 7, 0, 0, 0, 0],  # => row 0
    [6, 0, 0, 1, 9, 5, 0, 0, 0],  # => row 1
    [0, 9, 8, 0, 0, 0, 0, 6, 0],  # => row 2
    [8, 0, 0, 0, 6, 0, 0, 0, 3],  # => row 3
    [4, 0, 0, 8, 0, 3, 0, 0, 1],  # => row 4
    [7, 0, 0, 0, 2, 0, 0, 0, 6],  # => row 5
    [0, 6, 0, 0, 0, 0, 2, 8, 0],  # => row 6
    [0, 0, 0, 4, 1, 9, 0, 0, 5],  # => row 7
    [0, 0, 0, 0, 8, 0, 0, 7, 9],  # => row 8
]  # => closes the puzzle literal -- 0 marks each empty cell
solved = solve_sudoku(  # => opens the solve call
    puzzle  # => mutated in place by the backtracking solver
)  # => mutates puzzle in place, returns whether it succeeded
print(solved)  # => Output: True
 
assert solved is True  # => confirms this puzzle was solvable
for r in range(9):  # => confirms every row is a permutation of 1-9
    assert sorted(puzzle[r]) == list(range(1, 10))  # => each row has every digit once
for c in range(9):  # => confirms every column is a permutation of 1-9
    assert sorted(  # => opens the column-values sort
        puzzle[i][c]  # => the value at row i, column c
        for i in range(9)  # => gathers column c's value from every row
    ) == list(range(1, 10))  # => each column has every digit once
for box_r in range(0, 9, 3):  # => confirms every 3x3 box is a permutation of 1-9
    for box_c in range(0, 9, 3):  # => scans every box's top-left corner
        box_values = [  # => opens the box-flattening comprehension
            puzzle[box_r + i][box_c + j]  # => the value at this box-relative cell
            for i in range(3)  # => 3 rows within the box
            for j in range(3)  # => one box's cells
        ]  # => flattens one 3x3 box into a flat list
        assert sorted(box_values) == list(
            range(1, 10)  # => the digits every box must contain exactly once
        )  # => each box has every digit once
print("ex-57 OK")  # => Output: ex-57 OK

True
ex-57 OK

"""Example 57: pytest verification for Sudoku Backtracking."""
 
from example import is_valid, solve_sudoku
 
 
def test_solves_a_known_easy_puzzle() -> None:
    puzzle = [
        [5, 3, 0, 0, 7, 0, 0, 0, 0],
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
        [0, 9, 8, 0, 0, 0, 0, 6, 0],
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
        [0, 0, 0, 0, 8, 0, 0, 7, 9],
    ]
    assert solve_sudoku(puzzle) is True
    assert puzzle[0] == [5, 3, 4, 6, 7, 8, 9, 1, 2]  # => the known solved first row
 
 
def test_is_valid_rejects_a_row_duplicate() -> None:
    board = [[0] * 9 for _ in range(9)]
    board[0][0] = 5
    assert is_valid(board, 0, 1, 5) is False  # => 5 already in row 0
    assert is_valid(board, 0, 1, 6) is True  # => 6 is not yet used anywhere relevant
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 58: 0/1 Knapsack -- Greedy by Value/Weight Ratio Diverges from DP-Optimal."""
 
# Fractional knapsack's greedy-by-ratio is provably optimal WHEN items can be
# split. Forced to take items WHOLE (0/1, co-22), that same greedy heuristic
# can strand capacity that a globally-optimal DP (co-23) would have used
# better -- the greedy-choice property that makes fractional-knapsack work
# simply does not transfer to the 0/1 variant.
 
 
def greedy_knapsack_by_ratio(  # => sorts by value/weight ratio, then takes greedily
    weights: list[int],  # => each item's own weight
    values: list[int],  # => each item's own value
    capacity: int,  # => item weights/values + limit
) -> int:  # => O(n log n): sorts by ratio, then takes whole items greedily
    items = sorted(  # => opens the ratio-sort call
        zip(weights, values),  # => pairs each item's weight with its value
        key=lambda pair: pair[1] / pair[0],  # => sorts by value-per-weight ratio
        reverse=True,  # => best ratio first
    )  # => highest value-per-weight first
    total_value = 0  # => running greedy total
    remaining = capacity  # => how much capacity is still unused
    for w, v in items:  # => tries each item, best ratio first
        if w <= remaining:  # => it fits WHOLE -- take it (no fractions allowed)
            total_value += v  # => adds its full value
            remaining -= w  # => consumes its full weight
        # => else: SKIPPED ENTIRELY -- no partial credit, unlike fractional knapsack
    return total_value  # => greedy's answer -- NOT guaranteed optimal for 0/1
 
 
def knapsack_01_dp(  # => the same 2D DP as Example 51, guaranteed globally optimal
    weights: list[int],  # => each item's own weight
    values: list[int],  # => each item's own value
    capacity: int,  # => item weights/values + limit
) -> int:  # => O(n * capacity): the same DP as Example 51, the true optimum
    n = len(weights)  # => number of available items
    dp: list[list[int]] = [
        [0] * (capacity + 1)  # => one zero-filled row per item count
        for _ in range(n + 1)
    ]  # => table of zeros
    for i in range(1, n + 1):  # => considers items one at a time
        w, v = weights[i - 1], values[i - 1]  # => this item's own weight/value
        for c in range(capacity + 1):  # => every possible capacity, from 0 up
            dp[i][c] = dp[i - 1][c]  # => the SKIP option: value stays whatever it was
            if w <= c:  # => the TAKE option is only possible if it actually fits
                dp[i][c] = max(
                    dp[i][c],  # => the SKIP option's value
                    v + dp[i - 1][c - w],  # => the TAKE option's value
                )  # => best of skip vs take
    return dp[n][capacity]  # => the true optimal value, considering EVERY combination
 
 
weights: list[int] = [10, 20, 30]  # => a classic textbook counterexample
values: list[int] = [60, 100, 120]  # => ratios: 6.0, 5.0, 4.0 -- item 0 looks best
capacity = 50  # => the knapsack's weight limit
greedy_answer = greedy_knapsack_by_ratio(  # => opens the greedy call
    weights,  # => same weights as the DP call below
    values,  # => same values as the DP call below
    capacity,  # => same inputs as the DP, for a fair comparison
)  # => takes item 0 (ratio 6), then item 1 (ratio 5); item 2 no longer fits
optimal_answer = knapsack_01_dp(weights, values, capacity)  # => the TRUE optimum
print(greedy_answer)  # => Output: 160 -- items 0 and 1: weight 30, value 160
print(optimal_answer)  # => Output: 220 -- items 1 and 2: weight 50, value 220
 
assert greedy_answer == 160  # => confirms greedy's (suboptimal) answer
assert optimal_answer == 220  # => confirms DP's true optimum
assert (  # => opens the greedy-underperforms-DP check
    optimal_answer > greedy_answer
)  # => confirms the greedy heuristic genuinely underperforms DP here
print("ex-58 OK")  # => Output: ex-58 OK

160
220
ex-58 OK

"""Example 58: pytest verification for Greedy vs DP on 0/1 Knapsack."""
 
from example import greedy_knapsack_by_ratio, knapsack_01_dp
 
 
def test_dp_strictly_beats_ratio_greedy_on_the_classic_counterexample() -> None:
    weights, values, capacity = [10, 20, 30], [60, 100, 120], 50
    greedy = greedy_knapsack_by_ratio(weights, values, capacity)
    optimal = knapsack_01_dp(weights, values, capacity)
    assert greedy == 160
    assert optimal == 220
    assert optimal > greedy
 
 
def test_both_agree_when_all_items_fit_anyway() -> None:
    weights, values, capacity = [1, 2, 3], [10, 20, 30], 100  # => everything fits
    assert greedy_knapsack_by_ratio(weights, values, capacity) == knapsack_01_dp(
        weights, values, capacity
    )
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 59: Least-Cost Path Through a Grid, via 2D DP."""
 
# dp[r][c] = cheapest cost to REACH (r, c), moving only right or down
# (co-24): it must have arrived from directly above or directly left,
# whichever was cheaper, plus this cell's own cost.
 
 
def min_cost_path(grid: list[list[int]]) -> int:  # => O(rows*cols) time and space
    rows, cols = len(grid), len(grid[0])  # => the grid's dimensions
    dp: list[list[int]] = [  # => opens the 2D table construction
        [0] * cols  # => one zero-filled row per grid row
        for _ in range(rows)  # => one fresh row of zeros per grid row
    ]  # => dp[r][c] = min cost to reach (r, c) from (0, 0)
    dp[0][0] = grid[0][0]  # => base case: reaching the start costs just its own cell
    for c in range(1, cols):  # => the FIRST row can only be reached by moving right
        dp[0][c] = (  # => opens the first-row assignment
            dp[0][c - 1] + grid[0][c]  # => running total plus this cell's own cost
        )  # => only one possible predecessor: the left
    for r in range(1, rows):  # => the FIRST column can only be reached by moving down
        dp[r][0] = dp[r - 1][0] + grid[r][0]  # => only one possible predecessor: above
    for r in range(1, rows):  # => fills the rest of the table, row by row
        for c in range(1, cols):  # => and column by column within each row
            dp[r][c] = grid[r][c] + min(  # => opens the cheaper-predecessor comparison
                dp[r - 1][c],  # => cost of arriving from directly above
                dp[r][c - 1],  # => cost via above vs cost via the left
            )  # => cheaper of "came from above" or "came from the left"
    return dp[rows - 1][  # => opens the final-cell lookup
        cols - 1  # => the destination's column index
    ]  # => the bottom-right cell: total cost of the best path
 
 
def min_cost_path_brute_force(grid: list[list[int]]) -> int:  # => O(2^(rows+cols))
    rows, cols = len(grid), len(grid[0])  # => the grid's dimensions
 
    def recurse(r: int, c: int) -> int:  # => explores EVERY right/down path, no memo
        if r == rows - 1 and c == cols - 1:  # => reached the destination
            return grid[r][c]  # => just this cell's own cost
        if r == rows - 1:  # => bottom row -- the ONLY option is moving right
            return grid[r][c] + recurse(
                r,  # => stays on the same, bottom row
                c + 1,  # => the only reachable neighbor from the bottom row
            )  # => this cell's cost plus moving right
        if c == cols - 1:  # => rightmost column -- the ONLY option is moving down
            return grid[r][c] + recurse(
                r + 1,  # => moves down a row
                c,  # => the only reachable neighbor from the rightmost column
            )  # => this cell's cost plus moving down
        return grid[r][c] + min(  # => opens the both-directions comparison
            recurse(r + 1, c),  # => cost of continuing downward
            recurse(r, c + 1),  # => cost via down vs cost via right
        )  # => tries BOTH directions, no reuse of overlapping subproblems
 
    return recurse(0, 0)  # => starts exploring from the top-left corner
 
 
grid: list[list[int]] = [  # => a small 3x3 cost grid
    [1, 3, 1],  # => row 0
    [1, 5, 1],  # => row 1
    [4, 2, 1],  # => row 2
]  # => closes the grid literal
fast_result = min_cost_path(grid)  # => O(rows*cols) DP answer
brute_result = min_cost_path_brute_force(grid)  # => exhaustive ground truth
print(fast_result)  # => Output: 7
print(brute_result)  # => Output: 7
 
assert fast_result == brute_result  # => confirms both approaches agree exactly
assert fast_result == 7  # => confirms the known-optimal path 1->3->1->1->1 sums to 7
print("ex-59 OK")  # => Output: ex-59 OK

7
7
ex-59 OK

"""Example 59: pytest verification for 2D DP Grid Paths."""
 
from example import min_cost_path, min_cost_path_brute_force
 
 
def test_matches_brute_force_enumeration_on_small_grids() -> None:
    grid = [[1, 2, 3], [4, 8, 2], [1, 5, 3]]
    assert min_cost_path(grid) == min_cost_path_brute_force(grid)
 
 
def test_single_row_grid_only_moves_right() -> None:
    grid = [[1, 2, 3, 4]]
    assert min_cost_path(grid) == 10  # => the only possible path
 
 
def test_single_cell_grid() -> None:
    assert min_cost_path([[5]]) == 5
 
 
# => Run: pytest -- Output: 3 passed

3 passed

"""Example 60: Longest Increasing Subsequence -- O(n^2) DP vs O(n log n) Patience."""
 
# dp[i] = length of the LIS ENDING at index i (co-23): look back at every
# earlier smaller element and extend its best LIS by one. The patience-
# sorting variant (co-27) instead maintains the smallest possible "tail"
# value for each achievable LIS length, using BINARY SEARCH to place each
# new element -- same final answer, but O(n log n) instead of O(n^2).
import bisect
 
 
def lis_length_dp(items: list[int]) -> int:  # => O(n^2): the straightforward DP
    if not items:  # => an empty sequence has LIS length 0
        return 0  # => nothing to extend
    dp: list[int] = [1] * len(  # => opens the seed-array construction
        items  # => one seed entry per element
    )  # => every element is, at minimum, its own LIS of 1
    for i in range(len(items)):  # => for each position...
        for j in range(i):  # => ...checks every EARLIER position
            if items[j] < items[i]:  # => items[i] could extend an increasing run from j
                dp[i] = max(  # => opens the best-so-far comparison
                    dp[i],
                    dp[j] + 1,  # => current best vs extending j's LIS by one
                )  # => extends j's best LIS by one, if better
    return max(dp)  # => the longest LIS ending anywhere
 
 
def lis_length_patience(  # => binary-search variant, same answer, faster asymptotically
    items: list[int],  # => the sequence to scan
) -> int:  # => O(n log n): binary-search variant
    tails: list[int] = []  # => tails[k] = smallest possible tail of a length-(k+1) LIS
    for x in items:  # => processes elements left to right, one at a time
        pos = bisect.bisect_left(  # => opens the insertion-point search
            tails,
            x,  # => where x would insert to keep tails sorted
        )  # => O(log n): where x would insert to keep tails sorted
        if pos == len(tails):  # => x is bigger than every current tail -- LIS GROWS
            tails.append(x)  # => extends the longest LIS found so far by one
        else:  # => x can replace an existing tail with a SMALLER one, same length
            tails[pos] = x  # => keeps future extensions as easy as possible
    return len(  # => opens the final-length lookup
        tails  # => tails' LENGTH, not its values, is the LIS length
    )  # => the final length -- tails' VALUES are not the actual sequence
 
 
sequence: list[int] = [  # => opens the classic LeetCode LIS example literal
    10,  # => index 0
    9,  # => index 1
    2,  # => index 2
    5,  # => index 3
    3,  # => index 4
    7,  # => index 5
    101,  # => index 6
    18,  # => index 7
]  # => the classic LeetCode LIS example
dp_answer = lis_length_dp(sequence)  # => O(n^2) DP result
patience_answer = lis_length_patience(sequence)  # => O(n log n) patience-sort result
print(dp_answer)  # => Output: 4
print(patience_answer)  # => Output: 4 -- e.g. [2, 3, 7, 101] or [2, 3, 7, 18]
 
assert dp_answer == patience_answer  # => confirms both approaches agree exactly
assert dp_answer == 4  # => confirms the known LIS length for this classic example
assert lis_length_dp([]) == 0  # => confirms the empty-sequence edge case
print("ex-60 OK")  # => Output: ex-60 OK

4
4
ex-60 OK

"""Example 60: pytest verification for Longest Increasing Subsequence."""
 
import random
 
from example import lis_length_dp, lis_length_patience
 
 
def test_both_approaches_agree_on_random_sequences() -> None:
    random.seed(71)
    for _ in range(20):
        seq = [random.randint(0, 30) for _ in range(15)]
        assert lis_length_dp(seq) == lis_length_patience(seq)
 
 
def test_strictly_increasing_input_has_lis_equal_to_its_own_length() -> None:
    seq = [1, 2, 3, 4, 5]
    assert lis_length_dp(seq) == 5
    assert lis_length_patience(seq) == 5
 
 
def test_strictly_decreasing_input_has_lis_of_one() -> None:
    seq = [5, 4, 3, 2, 1]
    assert lis_length_dp(seq) == 1
    assert lis_length_patience(seq) == 1
 
 
# => Run: pytest -- Output: 3 passed

3 passed

"""Example 61: Matrix-Chain Multiplication Order -- 2D Interval DP."""
 
# dp[i][j] = min scalar multiplications to multiply matrices i..j (co-24):
# try EVERY possible split point k, combining the cost of the two resulting
# sub-chains plus the cost of that final multiplication -- an interval DP,
# indexed by chain LENGTH rather than by a simple linear position.
INF = float("inf")  # => sentinel for "not yet computed / impossible"
 
 
def matrix_chain_min_cost(  # => tries every split point, keeps the cheapest for each interval
    dims: list[int],  # => n+1 dimension entries describing n matrices
) -> int:  # => dims has n+1 entries for n matrices; matrix i is dims[i-1] x dims[i]
    n = len(dims) - 1  # => number of matrices in the chain
    dp: list[list[float]] = [  # => opens the 2D table construction
        [0.0] * (n + 1)
        for _ in range(n + 1)  # => one fresh row of zeros per matrix index
    ]  # => dp[i][j] = min cost to multiply matrices i..j (1-indexed)
    for chain_len in range(2, n + 1):  # => builds by INCREASING chain length, 2 up to n
        for i in range(1, n - chain_len + 2):  # => every valid starting matrix index
            j = i + chain_len - 1  # => the ending matrix index for this chain length
            dp[i][j] = INF  # => starts as "no split tried yet"
            for k in range(i, j):  # => tries every possible SPLIT POINT k
                cost = (  # => opens the split-cost computation
                    dp[i][k]
                    + dp[k + 1][j]
                    + dims[i - 1] * dims[k] * dims[j]  # => split cost
                )  # => left sub-chain + right sub-chain + this final multiplication
                dp[i][j] = min(dp[i][j], cost)  # => keeps the cheapest split found
    return int(dp[1][n])  # => the minimum cost to multiply the ENTIRE chain
 
 
dims: list[int] = [  # => opens the classic CLRS dimension list
    30,  # => p0
    35,  # => p1
    15,  # => p2
    5,  # => p3
    10,  # => p4
    20,  # => p5
    25,  # => p6
]  # => the classic CLRS example: 6 matrices, dims p0..p6
min_cost = matrix_chain_min_cost(dims)  # => the minimum possible scalar-multiply count
print(min_cost)  # => Output: 15125
 
assert min_cost == 15125  # => confirms the well-known CLRS answer for this chain
assert matrix_chain_min_cost([10, 20]) == 0  # => a single matrix needs zero multiplies
assert matrix_chain_min_cost([10, 20, 30]) == 6000  # => two matrices: only one way
print("ex-61 OK")  # => Output: ex-61 OK

15125
ex-61 OK

"""Example 61: pytest verification for Matrix-Chain Multiplication Order."""
 
from example import matrix_chain_min_cost
 
 
def test_known_clrs_chain_example() -> None:
    dims = [30, 35, 15, 5, 10, 20, 25]
    assert matrix_chain_min_cost(dims) == 15125
 
 
def test_single_matrix_has_zero_cost() -> None:
    assert matrix_chain_min_cost([5, 10]) == 0
 
 
def test_two_matrices_have_exactly_one_possible_order() -> None:
    assert matrix_chain_min_cost([2, 3, 4]) == 24  # => 2*3*4, the only possible order
 
 
# => Run: pytest -- Output: 3 passed

3 passed

"""Example 62: Space-Optimized 0/1 Knapsack -- O(capacity) Instead of O(n * capacity)."""
 
# Each row of the knapsack's 2D table only ever reads the PREVIOUS row
# (co-24, co-05) -- so a single 1D array can replace the whole table, IF
# updated capacity DECREASING for each item. Iterating backward guarantees
# each cell still reads last item's value (not this item's, reused twice).
 
 
def knapsack_2d_full_table(  # => the full O(n*capacity) table, kept only for comparison
    weights: list[int],  # => each item's own weight
    values: list[int],  # => each item's own value
    capacity: int,  # => item weights/values + limit
) -> int:  # => O(n * capacity) TIME and SPACE -- the full table, for comparison
    n = len(weights)  # => number of available items
    dp: list[list[int]] = [
        [0] * (capacity + 1)  # => one zero-filled row per item count
        for _ in range(n + 1)
    ]  # => full 2D table
    for i in range(1, n + 1):  # => considers items one at a time
        w, v = weights[i - 1], values[i - 1]  # => this item's own weight/value
        for c in range(capacity + 1):  # => every possible capacity, from 0 up
            dp[i][c] = dp[i - 1][c]  # => the SKIP option: value stays whatever it was
            if w <= c:  # => the TAKE option is only possible if it actually fits
                dp[i][c] = max(
                    dp[i][c],  # => the SKIP option's value
                    v + dp[i - 1][c - w],  # => the TAKE option's value
                )  # => best of skip vs take
    return dp[n][capacity]  # => the best achievable value at full capacity
 
 
def knapsack_1d_space_optimized(  # => same recurrence, but reuses ONE row via reverse order
    weights: list[int],  # => each item's own weight
    values: list[int],  # => each item's own value
    capacity: int,  # => item weights/values + limit
) -> int:  # => O(n * capacity) TIME, but only O(capacity) SPACE
    dp: list[int] = [0] * (capacity + 1)  # => ONE row instead of n+1 rows
    for i in range(len(weights)):  # => processes each item once
        w, v = weights[i], values[i]  # => this item's own weight/value
        for c in range(
            capacity,  # => starts from full capacity
            w - 1,  # => stops just short of this item's own weight
            -1,  # => steps backward -- THE KEY TRICK
        ):  # => THE KEY TRICK: iterates capacity DOWNWARD, not upward
            dp[c] = max(
                dp[c],  # => the SKIP option's value, still last item's
                v + dp[c - w],  # => the TAKE option's value
            )  # => dp[c-w] here is still the PREVIOUS item's value (not yet overwritten)
    return dp[capacity]  # => same final answer, using far less memory
 
 
# => the same 4-item instance as Example 51, so the two answers can be compared directly
weights: list[int] = [2, 3, 4, 5]  # => the same instance as Example 51
values: list[int] = [3, 4, 5, 6]  # => their corresponding values
capacity = 5  # => the knapsack's weight limit
full_table_answer = knapsack_2d_full_table(  # => opens the full-table call
    weights,  # => same weights as the space-optimized call below
    values,  # => same values as the space-optimized call below
    capacity,  # => same inputs as the space-optimized version
)  # => O(n*cap) space
space_optimized_answer = knapsack_1d_space_optimized(  # => opens the 1D-DP call
    weights,  # => same weights as the full-table call above
    values,  # => same values as the full-table call above
    capacity,  # => same inputs as the full-table version
)  # => O(cap) space
print(full_table_answer)  # => Output: 7
print(space_optimized_answer)  # => Output: 7
 
# confirms the space-optimized 1D pass agrees exactly with the full 2D table
assert full_table_answer == space_optimized_answer  # => confirms IDENTICAL results
assert space_optimized_answer == 7  # => confirms it matches Example 51's known answer
print("ex-62 OK")  # => Output: ex-62 OK

7
7
ex-62 OK

"""Example 62: pytest verification for Space-Optimized Knapsack DP."""
 
import random
 
from example import knapsack_1d_space_optimized, knapsack_2d_full_table
 
 
def test_matches_the_full_table_on_random_instances() -> None:
    random.seed(81)
    for _ in range(15):
        n = random.randint(1, 8)
        weights = [random.randint(1, 10) for _ in range(n)]
        values = [random.randint(1, 20) for _ in range(n)]
        capacity = random.randint(1, 20)
        full = knapsack_2d_full_table(weights, values, capacity)
        optimized = knapsack_1d_space_optimized(weights, values, capacity)
        assert full == optimized
 
 
def test_zero_capacity_yields_zero_both_ways() -> None:
    assert knapsack_2d_full_table([1, 2], [10, 20], 0) == 0
    assert knapsack_1d_space_optimized([1, 2], [10, 20], 0) == 0
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 63: Dijkstra vs Bellman-Ford -- the Speed/Generality Trade, Measured."""
 
# On the SAME non-negative-weight graph, both algorithms agree on distances
# (co-19, co-20) -- but Dijkstra's heap-driven O((V+E) log V) does far fewer
# edge relaxations than Bellman-Ford's O(V*E) brute-force repetition.
# Bellman-Ford's payoff for that extra work is GENERALITY: it also handles
# negative edges, which would silently break Dijkstra's greedy assumption.
import heapq  # => the min-heap priority queue used to pick the closest unfinished node
import random  # => generates the random weighted graph both algorithms share
 
 
def dijkstra_counted(  # => heap-driven: only relaxes edges from the CLOSEST unfinished node
    graph: dict[int, list[tuple[int, int]]],  # => node -> list of (neighbor, weight)
    start: int,  # => adjacency list + source node
) -> tuple[dict[int, float], int]:  # => (distances, relaxation attempts)
    distances: dict[int, float] = {  # => opens the initial all-infinity distance map
        node: float("inf")  # => every node starts unreachable, by default
        for node in graph  # => every node starts unreachable
    }  # => all unreached
    distances[start] = 0  # => the source reaches itself at cost 0
    heap: list[tuple[float, int]] = [  # => opens the initial single-entry heap
        (0, start)  # => the only known reachable node at distance 0
    ]  # => (distance, node), ordered by distance
    visited: set[int] = set()  # => nodes whose shortest distance is already finalized
    relaxations = 0  # => counts every edge examined, across the whole run
    while heap:  # => keeps going until every reachable node is finalized
        dist, node = heapq.heappop(heap)  # => pops the CLOSEST unfinished node
        if (  # => opens the stale-entry check
            node in visited  # => True if this node's distance is already final
        ):  # => a stale heap entry -- already finalized via a shorter path
            continue  # => skip it, no work to redo
        visited.add(node)  # => this node's shortest distance is now final
        for neighbor, weight in graph[node]:  # => only relaxes THIS node's own edges
            relaxations += 1  # => one relaxation ATTEMPT per edge examined
            new_dist = dist + weight  # => the candidate distance via this node
            if (  # => opens the strictly-shorter-path check
                new_dist < distances[neighbor]  # => True if this route just beat it
            ):  # => a strictly shorter path was just found
                distances[neighbor] = new_dist  # => records the improved distance
                heapq.heappush(  # => the heap may end up holding stale entries too
                    heap,  # => the shared candidate-node priority queue
                    (new_dist, neighbor),  # => queues it for future expansion
                )  # => queues it for future expansion
    return distances, relaxations  # => the final shortest distances + total work done
 
 
def bellman_ford_counted(  # => brute-force: relaxes EVERY edge, EVERY round, no early exit
    n: int,  # => the number of nodes, labeled 0..n-1
    edges: list[tuple[int, int, int]],  # => (from, to, weight) triples
    start: int,  # => node count, edge list, source
) -> tuple[list[float], int]:  # => (distances, relaxation attempts)
    dist: list[float] = [float("inf")] * n  # => all nodes start unreached
    dist[start] = 0  # => the source reaches itself at cost 0
    relaxations = 0  # => counts every edge examined, across ALL n-1 rounds
    for _ in range(n - 1):  # => O(V) full rounds, EVEN once nothing more can improve
        for u, v, w in edges:  # => O(E) edges examined, every single round
            relaxations += 1  # => one relaxation attempt, whether or not it improves
            if (  # => opens the strictly-shorter-path check
                dist[u] + w < dist[v]  # => True if this edge just beat the known cost
            ):  # => a strictly shorter path via edge (u, v) was found
                dist[v] = dist[u] + w  # => records the improved distance
    return dist, relaxations  # => the final shortest distances + total work done
 
 
random.seed(91)  # => fixed seed -> reproducible graph structure
n = 40  # => 40 nodes, labeled 0..39
edge_list: list[tuple[int, int, int]] = [  # => a moderately dense random graph
    (u, v, random.randint(1, 20))  # => a random non-negative weight per candidate edge
    for u in range(n)  # => every possible source node
    for v in range(n)  # => every possible destination node
    if u != v  # => random weight
][:300]  # => 300 non-negative-weight edges
 
adjacency: dict[
    int, list[tuple[int, int]]  # => node -> list of (neighbor, weight)
] = {  # => opens the empty adjacency-map build
    i: []  # => this node starts with no outgoing edges yet
    for i in range(n)  # => every node starts with an empty edge list
}  # => empty adjacency lists
for u, v, w in edge_list:  # => builds Dijkstra's adjacency-list representation
    adjacency[u].append((v, w))  # => one directed edge per entry
 
dijkstra_distances, dijkstra_relaxations = dijkstra_counted(  # => opens the heap run
    adjacency,  # => the adjacency-list graph both algorithms will process
    0,  # => the same graph and source Bellman-Ford will also use
)  # => heap-driven run
bellman_distances, bellman_relaxations = bellman_ford_counted(  # => opens the brute run
    n,  # => the same node count as the graph above
    edge_list,  # => the same edges, in flat-list form for Bellman-Ford
    0,  # => the same graph and source Dijkstra already used
)  # => brute-force run
 
print(dijkstra_relaxations < bellman_relaxations)  # => Output: True
matches = all(  # => opens the pairwise distance-agreement check
    abs(dijkstra_distances[i] - bellman_distances[i])  # => this node's distance gap
    < 1e-9  # => allows for floating-point rounding only
    for i in range(n)  # => near-equal
)  # => both algorithms must AGREE, since edges here are all non-negative
print(matches)  # => Output: True
 
assert (  # => opens the Dijkstra-does-less-work check
    dijkstra_relaxations < bellman_relaxations  # => True only if Dijkstra truly won
)  # => confirms Dijkstra does meaningfully LESS work on this same graph
assert matches  # => confirms both agree exactly when weights are non-negative
print("ex-63 OK")  # => Output: ex-63 OK

True
True
ex-63 OK

"""Example 63: pytest verification for the Dijkstra vs Bellman-Ford Trade."""
 
import random
 
from example import bellman_ford_counted, dijkstra_counted
 
 
def test_both_algorithms_agree_on_a_small_graph() -> None:
    edges = [(0, 1, 4), (0, 2, 1), (1, 3, 1), (2, 1, 2), (2, 3, 5)]
    adjacency: dict[int, list[tuple[int, int]]] = {i: [] for i in range(4)}
    for u, v, w in edges:
        adjacency[u].append((v, w))
    dijkstra_distances, _ = dijkstra_counted(adjacency, 0)
    bellman_distances, _ = bellman_ford_counted(4, edges, 0)
    for i in range(4):
        assert abs(dijkstra_distances[i] - bellman_distances[i]) < 1e-9
 
 
def test_dijkstra_does_fewer_relaxations_on_a_larger_random_graph() -> None:
    random.seed(2)
    n = 25
    edges = [
        (u, v, random.randint(1, 15)) for u in range(n) for v in range(n) if u != v
    ][:150]
    adjacency: dict[int, list[tuple[int, int]]] = {i: [] for i in range(n)}
    for u, v, w in edges:
        adjacency[u].append((v, w))
    _, dijkstra_relax = dijkstra_counted(adjacency, 0)
    _, bellman_relax = bellman_ford_counted(n, edges, 0)
    assert dijkstra_relax < bellman_relax
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 64: A* Search -- Same Cost as Dijkstra, Fewer Nodes Expanded."""
 
# A* (co-19) is Dijkstra plus a HEURISTIC: it orders the frontier by g+h
# (cost-so-far plus estimated cost-to-goal) instead of g alone. An ADMISSIBLE
# heuristic (never overestimates -- Manhattan distance on a 4-directional
# grid) guarantees A* still finds the OPTIMAL path, while expanding fewer
# nodes than Dijkstra, which has no sense of "which direction is promising."
import heapq  # => the min-heap priority queue both searches use to pick a frontier cell
 
Cell = tuple[int, int]  # => a grid position (row, col)
 
 
def neighbors(cell: Cell, rows: int, cols: int) -> list[Cell]:  # => 4-directional moves
    r, c = cell  # => the cell's own row/column
    candidates = [  # => opens the four-direction candidate list
        (r + 1, c),  # => down
        (r - 1, c),  # => up
        (r, c + 1),  # => right
        (r, c - 1),  # => left
    ]  # => down/up/right/left
    return [  # => opens the in-bounds filter
        (nr, nc)  # => a candidate cell that survives the bounds check
        for nr, nc in candidates  # => checks every one of the 4 candidate moves
        if 0 <= nr < rows and 0 <= nc < cols  # => in-bounds only
    ]  # => stays within the grid's bounds
 
 
def manhattan(
    a: Cell,  # => the first cell being measured
    b: Cell,  # => the two cells to measure between
) -> int:  # => the ADMISSIBLE heuristic: never overestimates
    return abs(a[0] - b[0]) + abs(  # => row distance plus (opens) column distance
        a[1] - b[1]  # => the absolute column distance
    )  # => a lower bound on any grid path's cost
 
 
def dijkstra_grid(  # => baseline: orders the frontier by cost-so-far (g) alone
    rows: int,  # => the grid's row count
    cols: int,  # => the grid's column count
    start: Cell,  # => the search's origin cell
    goal: Cell,  # => grid size, start cell, goal cell
) -> tuple[int, int]:  # => (path cost, nodes expanded)
    dist: dict[Cell, int] = {start: 0}  # => cost-so-far to reach each visited cell
    heap: list[tuple[int, Cell]] = [(0, start)]  # => (g, cell) -- ordered by g alone
    expanded = 0  # => counts FINALIZED node expansions
    visited: set[Cell] = set()  # => cells whose shortest cost is already finalized
    while heap:  # => keeps going until the goal is reached or the heap is empty
        g, cell = heapq.heappop(heap)  # => pops the cheapest-so-far unfinished cell
        if cell in visited:  # => a stale heap entry -- already finalized more cheaply
            continue  # => skip it, no work to redo
        visited.add(cell)  # => this cell's shortest cost is now final
        expanded += 1  # => one more node finalized
        if cell == goal:  # => reached the goal -- its distance is now final
            return g, expanded  # => the optimal cost, plus how much work it took
        for nxt in neighbors(cell, rows, cols):  # => tries every 4-directional neighbor
            new_g = g + 1  # => every grid step costs 1
            if new_g < dist.get(
                nxt,  # => this neighbor's cell key
                float("inf"),  # => treats an unvisited neighbor as infinitely far
            ):  # => a strictly cheaper path was found
                dist[nxt] = new_g  # => records the improved cost
                heapq.heappush(heap, (new_g, nxt))  # => queues it, ordered by g alone
    return -1, expanded  # => unreachable (never happens on a full grid)
 
 
def a_star_grid(  # => same search, but orders the frontier by g+h (estimated total cost)
    rows: int,  # => the grid's row count
    cols: int,  # => the grid's column count
    start: Cell,  # => the search's origin cell
    goal: Cell,  # => grid size, start cell, goal cell
) -> tuple[int, int]:  # => (path cost, nodes expanded)
    g_score: dict[Cell, int] = {start: 0}  # => cost-so-far to reach each visited cell
    heap: list[tuple[int, Cell]] = [
        (manhattan(start, goal), start)  # => f = h at the start, since g is 0
    ]  # => (f = g+h, cell) -- ordered by the ESTIMATED total cost
    expanded = 0  # => counts FINALIZED node expansions
    visited: set[Cell] = set()  # => cells whose shortest cost is already finalized
    while heap:  # => keeps going until the goal is reached or the heap is empty
        _, cell = heapq.heappop(heap)  # => pops the most-promising unfinished cell
        if cell in visited:  # => a stale heap entry -- already finalized more cheaply
            continue  # => skip it, no work to redo
        visited.add(cell)  # => this cell's shortest cost is now final
        expanded += 1  # => one more node finalized
        if cell == goal:  # => reached the goal -- its cost is now final and OPTIMAL
            return g_score[
                cell  # => the goal's own finalized cost-so-far
            ], expanded  # => the optimal cost, plus how much work it took
        for nxt in neighbors(cell, rows, cols):  # => tries every 4-directional neighbor
            new_g = g_score[cell] + 1  # => every grid step costs 1
            if new_g < g_score.get(
                nxt,  # => this neighbor's cell key
                float("inf"),  # => treats an unvisited neighbor as infinitely far
            ):  # => a strictly cheaper path was found
                g_score[nxt] = new_g  # => records the improved cost-so-far
                heapq.heappush(  # => the heap may end up holding stale entries too
                    heap, (new_g + manhattan(nxt, goal), nxt)
                )  # => f = g + h steers the search TOWARD the goal
    return -1, expanded  # => unreachable (never happens on a full grid)
 
 
# A goal near the CENTER of a large grid (not a far corner) is what actually
# lets the heuristic discriminate: Dijkstra, blind to direction, must expand
# every cell within Manhattan-distance-6 of start -- including cells pointing
# entirely AWAY from goal. A*'s heuristic confines expansion to the much
# smaller rectangle of cells that could plausibly lie on a shortest path.
rows, cols = 30, 30  # => a large grid -- plenty of room for goal-irrelevant cells
start, goal = (15, 15), (18, 18)  # => goal is near the center, not a far corner
dijkstra_cost, dijkstra_expanded = dijkstra_grid(  # => opens the baseline run
    rows,  # => the grid's row count
    cols,  # => the grid's column count
    start,  # => the search's origin cell
    goal,  # => the same grid, start, and goal as A* will use
)  # => baseline run
a_star_cost, a_star_expanded = a_star_grid(  # => opens the heuristic-guided run
    rows,  # => the same row count as Dijkstra's run above
    cols,  # => the same column count as Dijkstra's run above
    start,  # => the same origin cell as Dijkstra's run above
    goal,  # => the same grid, start, and goal Dijkstra already used
)  # => heuristic-guided run
print(dijkstra_cost == a_star_cost)  # => Output: True
print(a_star_expanded < dijkstra_expanded)  # => Output: True
 
assert dijkstra_cost == a_star_cost  # => confirms BOTH found the same optimal cost
assert dijkstra_cost == 6  # => the Manhattan distance from (15,15) to (18,18): 3+3
assert (  # => opens the A*-expands-fewer-nodes check
    a_star_expanded < dijkstra_expanded
)  # => confirms A*'s heuristic genuinely reduces expansions
print("ex-64 OK")  # => Output: ex-64 OK

True
True
ex-64 OK

"""Example 64: pytest verification for A* Search."""
 
from example import a_star_grid, dijkstra_grid
 
 
def test_a_star_matches_dijkstra_cost_but_expands_fewer_nodes() -> None:
    rows, cols = 30, 30
    start, goal = (10, 10), (13, 12)
    d_cost, d_expanded = dijkstra_grid(rows, cols, start, goal)
    a_cost, a_expanded = a_star_grid(rows, cols, start, goal)
    assert d_cost == a_cost  # => same optimal cost
    assert a_expanded < d_expanded  # => A* explores meaningfully less
 
 
def test_adjacent_start_and_goal_cost_one() -> None:
    d_cost, _ = dijkstra_grid(5, 5, (0, 0), (0, 1))
    a_cost, _ = a_star_grid(5, 5, (0, 0), (0, 1))
    assert d_cost == a_cost == 1
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 65: Critical Path via DP over a Topological Order."""
 
# The critical path (longest path through a DAG) combines two ideas
# (co-18, co-24): process tasks in TOPOLOGICAL order (co-18) so every
# predecessor is already finalized, then DP: earliest_finish[task] =
# duration[task] + the LATEST of its predecessors' earliest_finish times.
from collections import deque  # => O(1) popleft, unlike a plain list
 
 
def topological_order(graph: dict[str, list[str]]) -> list[str]:  # => Kahn's algorithm
    in_degree: dict[str, int] = {  # => opens the initial all-zero in-degree map
        node: 0  # => this node's predecessor count, before any edges are counted
        for node in graph  # => every node starts with zero known predecessors
    }  # => how many predecessors each node has
    for node in graph:  # => scans every node's outgoing edges
        for neighbor in graph[node]:  # => each edge node->neighbor
            in_degree[neighbor] += 1  # => neighbor gains one more predecessor
    queue: deque[str] = deque(  # => opens the initial ready-queue construction
        [node for node in graph if in_degree[node] == 0]  # => the zero-in-degree nodes
    )  # => sources first
    order: list[str] = []  # => accumulates the topological order as it's discovered
    while queue:  # => processes nodes in the order their in-degree hits zero
        node = queue.popleft()  # => the next node with all predecessors already emitted
        order.append(node)  # => records it as next in topological order
        for neighbor in graph[node]:  # => this node no longer blocks its successors
            in_degree[neighbor] -= 1  # => one fewer unresolved predecessor for neighbor
            if (  # => opens the last-predecessor check
                in_degree[neighbor] == 0  # => True once every predecessor has emitted
            ):  # => neighbor's LAST predecessor was just emitted
                queue.append(neighbor)  # => neighbor is now safe to process too
    return order  # => a valid topological order (assumes a DAG -- no cycle check here)
 
 
def critical_path_length(  # => DP over a topological order: the true project length
    graph: dict[str, list[str]],  # => the task-dependency DAG
    durations: dict[str, int],  # => task graph + each task's duration
) -> tuple[int, dict[str, int]]:  # => (total project length, earliest_finish per task)
    order = topological_order(  # => opens the topological-order call
        graph  # => the same task dependency graph
    )  # => process every predecessor before its successors
    predecessors: dict[  # => opens the reversed-edge map's type annotation
        str, list[str]  # => task name -> list of tasks that must finish first
    ] = {  # => opens the reversed-edge map construction
        node: []  # => this task starts with no known predecessors yet
        for node in graph  # => one empty predecessor list per task
    }  # => reverse the edges -- who must finish before each task
    for u in graph:  # => scans every node's outgoing edges
        for v in graph[u]:  # => each edge u->v
            predecessors[v].append(u)  # => u is a predecessor of v
 
    earliest_finish: dict[  # => opens the DP table's type annotation
        str, int  # => task name -> earliest completion time
    ] = {}  # => DP table: task -> earliest completion time
    for (  # => opens the topo-order iteration
        task  # => the current task, in topological order
    ) in order:  # => processes in topo order -- every predecessor is already known
        latest_predecessor_finish = max(  # => opens the slowest-predecessor lookup
            (  # => opens the predecessor-finish-times generator
                earliest_finish[p] for p in predecessors[task]
            ),  # => every predecessor's own finish time
            default=0,  # => 0 if no predecessors
        )  # => 0 if this task has no predecessors -- it can start immediately
        earliest_finish[task] = (  # => opens the DP-table assignment
            durations[task]  # => this task's own duration
            + latest_predecessor_finish  # => own duration plus the slowest wait
        )  # => this task's own duration, stacked on top of its slowest predecessor
 
    total_length = max(earliest_finish.values())  # => the whole PROJECT'S critical path
    return (  # => opens the result tuple
        total_length,  # => the overall project length
        earliest_finish,  # => every task's own earliest-finish time
    )  # => project length and every task's finish time
 
 
graph: dict[str, list[str]] = {  # => a small hand-computable project schedule
    "design": ["build_a", "build_b"],  # => design must finish before either build
    "build_a": ["test"],  # => build_a must finish before test
    "build_b": ["test"],  # => build_b must finish before test
    "test": [],  # => the final task, with no successors
}  # => closes the graph literal
durations: dict[str, int] = {  # => how long each task takes, in days
    "design": 3,  # => 3 days
    "build_a": 5,  # => 5 days -- the SLOWER of the two parallel builds
    "build_b": 2,  # => 2 days
    "test": 4,  # => 4 days
}  # => closes the durations literal
total_length, finish_times = critical_path_length(graph, durations)  # => runs the DP
print(total_length)  # => Output: 12
print(finish_times["test"])  # => Output: 12
 
assert (  # => opens the known-critical-path-length check
    total_length == 12  # => confirms the DP computed the known critical-path length
)  # => design(3) -> build_a(5, the SLOWER branch) -> test(4) = 12
assert finish_times["design"] == 3  # => no predecessors -- finishes at its own duration
assert finish_times["build_b"] == 5  # => 3 (design) + 2 (build_b) = 5, NOT critical
assert finish_times["build_a"] == 8  # => 3 (design) + 5 (build_a) = 8, the SLOWER path
print("ex-65 OK")  # => Output: ex-65 OK

12
12
ex-65 OK

"""Example 65: pytest verification for Critical Path DP."""
 
from example import critical_path_length
 
 
def test_matches_a_hand_computed_schedule() -> None:
    graph: dict[str, list[str]] = {
        "design": ["build_a", "build_b"],
        "build_a": ["test"],
        "build_b": ["test"],
        "test": [],
    }
    durations: dict[str, int] = {"design": 3, "build_a": 5, "build_b": 2, "test": 4}
    total, finishes = critical_path_length(graph, durations)
    assert total == 12
    assert finishes["build_a"] == 8
 
 
def test_single_chain_sums_durations_exactly() -> None:
    graph: dict[str, list[str]] = {"a": ["b"], "b": ["c"], "c": []}
    durations: dict[str, int] = {"a": 1, "b": 2, "c": 3}
    total, _ = critical_path_length(graph, durations)
    assert total == 6  # => a single chain: no branching, just a straight sum
 
 
def test_task_with_no_predecessors_starts_at_time_zero() -> None:
    graph: dict[str, list[str]] = {"solo": []}
    durations: dict[str, int] = {"solo": 7}
    total, finishes = critical_path_length(graph, durations)
    assert total == 7
    assert finishes["solo"] == 7
 
 
# => Run: pytest -- Output: 3 passed

3 passed

"""Example 66: Strongly Connected Components via Kosaraju's Two-Pass DFS."""
 
# Kosaraju's algorithm (co-17, co-18) is a clever two-pass trick: DFS the
# ORIGINAL graph, recording finish order (like Example 36's topo sort);
# then DFS the TRANSPOSED graph (every edge reversed), processing nodes in
# REVERSE finish order -- each tree that DFS grows is exactly one SCC.
 
 
def transpose(graph: dict[str, list[str]]) -> dict[str, list[str]]:  # => reverses edges
    reversed_graph: dict[str, list[str]] = {
        node: [] for node in graph
    }  # => same nodes, no edges yet
    for u in graph:  # => scans every node's outgoing edges
        for v in graph[u]:  # => each original edge u->v
            reversed_graph[v].append(u)  # => flips u->v into v->u
    return reversed_graph  # => same nodes, every edge direction reversed
 
 
def dfs_finish_order(  # => PASS 1: records DFS finish order over the ORIGINAL graph
    graph: dict[str, list[str]],  # => the original adjacency-list graph
) -> list[str]:  # => same idea as Ex. 36
    visited: set[str] = set()  # => nodes already fully explored
    finish_order: list[str] = []  # => nodes in the order their DFS subtree COMPLETES
 
    def recurse(node: str) -> None:  # => explores node's subtree before recording it
        visited.add(node)  # => marks node as being explored
        for neighbor in graph.get(node, []):  # => tries every outgoing edge
            if neighbor not in visited:  # => only recurse into UNEXPLORED neighbors
                recurse(neighbor)  # => fully explores that neighbor's subtree first
        finish_order.append(node)  # => appended only after all descendants finish
 
    for node in graph:  # => ensures every node gets visited, even disconnected ones
        if node not in visited:  # => starts a fresh DFS from any unvisited node
            recurse(node)  # => explores that node's entire reachable subtree
    return finish_order  # => PASS 1's output: nodes ordered by DFS finish time
 
 
def strongly_connected_components(  # => the two-pass Kosaraju driver
    graph: dict[str, list[str]],  # => the original adjacency-list graph
) -> list[list[str]]:  # => Kosaraju's algorithm, O(V+E)
    finish_order = dfs_finish_order(graph)  # => PASS 1: DFS the original graph
    reversed_graph = transpose(graph)  # => build the transposed graph once
    visited: set[str] = set()  # => nodes already assigned to a component
    components: list[list[str]] = []  # => each entry is one full SCC
 
    def recurse(node: str, component: list[str]) -> None:  # => grows one component
        visited.add(node)  # => marks node as assigned
        component.append(node)  # => this node belongs to the CURRENT component
        for neighbor in reversed_graph.get(node, []):  # => tries every REVERSED edge
            if neighbor not in visited:  # => only recurse into UNASSIGNED neighbors
                recurse(neighbor, component)  # => grows the same component further
 
    for node in reversed(  # => opens the reverse-finish-order iteration
        finish_order  # => PASS 1's output, walked back to front
    ):  # => PASS 2: REVERSE finish order, on the reversed graph
        if node not in visited:  # => this node starts a BRAND NEW component
            component: list[str] = []  # => a fresh SCC, seeded by this unvisited node
            recurse(node, component)  # => the ENTIRE reachable set here is one SCC
            components.append(component)  # => records the completed component
    return components  # => every node's SCC, as a list of node lists
 
 
graph: dict[str, list[str]] = {  # => a known digraph with two clear SCCs
    "a": ["b"],  # => a points to b
    "b": ["c"],  # => b points to c
    "c": ["a", "d"],  # => a->b->c->a is a cycle: {a, b, c} form one SCC
    "d": ["e"],  # => d points to e
    "e": ["d"],  # => d->e->d is a cycle: {d, e} form another SCC
}  # => closes the graph literal
components = strongly_connected_components(graph)  # => Kosaraju's SCC decomposition
component_sets = [set(c) for c in components]  # => order-independent comparison
print(len(components))  # => Output: 2
 
assert len(components) == 2  # => confirms exactly two SCCs were found
assert {"a", "b", "c"} in component_sets  # => confirms the first cycle is one SCC
assert {"d", "e"} in component_sets  # => confirms the second cycle is another SCC
print("ex-66 OK")  # => Output: ex-66 OK

2
ex-66 OK

"""Example 66: pytest verification for Kosaraju's SCC Algorithm."""
 
from example import strongly_connected_components
 
 
def test_two_disjoint_cycles_form_two_components() -> None:
    graph: dict[str, list[str]] = {
        "a": ["b"],
        "b": ["c"],
        "c": ["a", "d"],
        "d": ["e"],
        "e": ["d"],
    }
    components = strongly_connected_components(graph)
    sets = [set(c) for c in components]
    assert len(components) == 2
    assert {"a", "b", "c"} in sets
    assert {"d", "e"} in sets
 
 
def test_a_dag_has_every_node_as_its_own_singleton_component() -> None:
    graph: dict[str, list[str]] = {"x": ["y"], "y": ["z"], "z": []}
    components = strongly_connected_components(graph)
    assert len(components) == 3  # => no cycles at all -- every node is its own SCC
 
 
def test_a_fully_cyclic_graph_is_one_single_component() -> None:
    graph: dict[str, list[str]] = {"p": ["q"], "q": ["r"], "r": ["p"]}
    components = strongly_connected_components(graph)
    assert len(components) == 1
    assert set(components[0]) == {"p", "q", "r"}
 
 
# => Run: pytest -- Output: 3 passed

3 passed

"""Example 67: Segment Tree vs Fenwick Tree -- Same Prefix-Sum Answers, Different Cost."""
 
# Both structures answer prefix-sum + point-update in O(log n) (co-14,
# co-15) -- but a Fenwick tree needs only O(n) space and a handful of lines
# (Example 30), while a segment tree needs O(4n) space and more code, in
# exchange for handling queries a Fenwick tree CAN'T (like range-min).
 
 
class FenwickTree:  # => identical to Example 30's implementation
    def __init__(self, n: int) -> None:  # => allocates the flat backing array
        self.n = n  # => the number of elements tracked
        self.tree: list[int] = [0] * (n + 1)  # => O(n) space -- a single flat array
 
    def update(self, i: int, delta: int) -> None:  # => applies delta at index i
        i += 1  # => converts to Fenwick's 1-indexed internal scheme
        while i <= self.n:  # => climbs through every ancestor this index touches
            self.tree[i] += delta  # => applies the delta at this ancestor node
            i += i & (  # => opens the lowest-set-bit isolation
                -i  # => isolates the lowest set bit
            )  # => THE FENWICK TRICK: jumps to the next responsible ancestor
 
    def prefix_sum(self, i: int) -> int:  # => sum of elements [0..i], inclusive
        i += 1  # => converts to Fenwick's 1-indexed internal scheme
        total = 0  # => running prefix sum
        while i > 0:  # => walks DOWN through the ancestors that cover this prefix
            total += self.tree[i]  # => accumulates this ancestor's contribution
            i -= i & (-i)  # => THE FENWICK TRICK: jumps to the next covering ancestor
        return total  # => the completed prefix sum
 
 
class SegmentTreeSum:  # => a sum-tracking segment tree -- more code, more memory
    def __init__(self, n: int) -> None:  # => allocates the recursive tree array
        self.n = n  # => the number of elements tracked
        self.tree: list[int] = [0] * (  # => opens the flat backing array's size
            4 * n  # => 4x n is enough slack for any recursive segment-tree layout
        )  # => O(4n) space -- 4x a Fenwick tree's array
 
    def update(  # => public entry point for a point update
        self,  # => the segment-tree instance being updated
        i: int,  # => the index being updated
        delta: int,  # => the amount to add at that index
    ) -> None:  # => public entry point for a point update
        self._update(  # => opens the recursive-descent call
            1,  # => starts at the root node
            0,  # => the root's own range: lower bound
            self.n - 1,  # => the root's own range: upper bound, covering everything
            i,  # => the target index being updated
            delta,  # => starts at the root, covering the full range
        )  # => starts the recursive descent at the root
 
    def _update(  # => recurses down, then merges back up on the way out
        self,  # => the segment-tree instance being mutated
        node: int,  # => the current tree node's index
        lo: int,  # => this node's range: lower bound
        hi: int,  # => this node's range: upper bound
        i: int,  # => the target index being updated
        delta: int,  # => the amount to add at that index
    ) -> None:  # => recursive descent
        if lo == hi:  # => reached the LEAF representing index i
            self.tree[node] += delta  # => applies the delta directly
            return  # => nothing more to do at a leaf
        mid = (lo + hi) // 2  # => splits this node's range in half
        if i <= mid:  # => index i lives in the LEFT half
            self._update(2 * node, lo, mid, i, delta)  # => recurse into the left child
        else:  # => index i lives in the RIGHT half
            self._update(  # => recurses into the right child instead
                2 * node + 1,  # => the right child's index
                mid + 1,  # => the right child's own range: lower bound
                hi,  # => recurse into the right child
                i,  # => the target index being updated
                delta,  # => the amount being added at that index
            )  # => recurse into the right child
        self.tree[node] = (  # => opens the parent re-merge
            self.tree[2 * node]  # => the left child's own subtree sum
            + self.tree[2 * node + 1]  # => plus the right child's own subtree sum
        )  # => re-merge from children
 
    def prefix_sum(self, i: int) -> int:  # => needs its OWN range-query traversal
        return self._query(1, 0, self.n - 1, 0, i)  # => queries the range [0, i]
 
    def _query(  # => three-way split: no overlap, full overlap, or partial (recurse)
        self,  # => the segment-tree instance being queried
        node: int,  # => the current tree node's index
        node_lo: int,  # => this node's own range: lower bound
        node_hi: int,  # => this node's own range: upper bound
        lo: int,  # => the query range's lower bound
        hi: int,  # => the query range's upper bound
    ) -> int:  # => range sum
        if (  # => opens the no-overlap check
            hi < node_lo or node_hi < lo  # => True if the two ranges never touch
        ):  # => this node's range is ENTIRELY outside [lo, hi]
            return 0  # => contributes nothing
        if (  # => opens the full-overlap check
            lo <= node_lo and node_hi <= hi  # => True if fully nested inside
        ):  # => this node's range is ENTIRELY inside [lo, hi]
            return self.tree[
                node  # => this node's precomputed sum, valid for its whole range
            ]  # => its precomputed sum answers this subrange exactly
        mid = (node_lo + node_hi) // 2  # => a PARTIAL overlap -- must split and recurse
        return self._query(  # => opens the left-subrange recursive call
            2 * node,  # => the left child's index
            node_lo,  # => the left child's own range: lower bound
            mid,  # => the left child's own range: upper bound
            lo,  # => the query range's lower bound
            hi,  # => the left child's own subrange query
        ) + self._query(  # => left contribution
            2 * node + 1,  # => the right child's index
            mid + 1,  # => the right child's own range: lower bound
            node_hi,  # => the right child's own range: upper bound
            lo,  # => the same query range's lower bound
            hi,  # => plus the right contribution
        )  # => closes the two-subquery sum
 
 
n = 12  # => 12 elements, both starting at zero
fenwick = FenwickTree(n)  # => the Fenwick-tree instance under test
segment_tree = SegmentTreeSum(n)  # => the segment-tree instance under test
updates: list[tuple[int, int]] = [  # => opens the shared update sequence
    (0, 5),  # => index 0, +5
    (3, 2),  # => index 3, +2
    (7, -1),  # => index 7, -1
    (11, 8),  # => index 11, +8
    (5, 4),  # => index 5, +4
]  # => the SAME sequence of point updates, applied to BOTH structures
for idx, delta in updates:  # => applies every update to both structures identically
    fenwick.update(idx, delta)  # => O(log n): a handful of pointer-arithmetic hops
    segment_tree.update(idx, delta)  # => O(log n): a recursive tree descent
 
queries: list[int] = [0, 3, 7, 11]  # => a spread of prefix-sum queries to compare
fenwick_answers = [fenwick.prefix_sum(i) for i in queries]  # => Fenwick's own answers
segment_answers = [  # => opens the segment-tree answer collection
    segment_tree.prefix_sum(i)  # => this query's answer from the segment tree
    for i in queries  # => the same queries as Fenwick's answers above
]  # => segment tree's own answers
print(fenwick_answers)  # => Output: [5, 7, 10, 18]
print(segment_answers)  # => Output: [5, 7, 10, 18]
 
assert (  # => opens the both-structures-agree check
    fenwick_answers == segment_answers  # => both structures agree on every query
)  # => confirms IDENTICAL answers from two structurally different approaches
assert len(fenwick.tree) == n + 1  # => confirms Fenwick's O(n) space usage
assert len(segment_tree.tree) == 4 * n  # => confirms segment tree's larger O(4n) space
print("ex-67 OK")  # => Output: ex-67 OK