From Solution to Clean Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# Without helper: Reader must understand merge logic to understand sort
def sort_array(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = sort_array(arr[:mid])
    right = sort_array(arr[mid:])
    
    # Now reader must parse 15 lines of merge logic
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
# With helper: Merge is abstracted, sort is instantly clear
def sort_array(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = sort_array(arr[:mid])
    right = sort_array(arr[mid:])
    return merge_sorted_arrays(left, right)  # Intent is clear

1
2
3
4
5
6
7
8
9
10
11
12

# Each helper can be tested independently
def test_merge_sorted_arrays():
    assert merge_sorted_arrays([1, 3], [2, 4]) == [1, 2, 3, 4]
    assert merge_sorted_arrays([], [1, 2]) == [1, 2]
    assert merge_sorted_arrays([1], []) == [1]
    assert merge_sorted_arrays([], []) == []
 
def test_partition():
    arr = [3, 1, 4, 1, 5, 9, 2, 6]
    pivot_idx = partition(arr, 0, len(arr))
    assert all(arr[i] <= arr[pivot_idx] for i in range(pivot_idx))
    assert all(arr[i] >= arr[pivot_idx] for i in range(pivot_idx, len(arr)))

1
2
3
4
5
6
7
8
9

# The 'merge' operation is conceptually distinct from 'sort'
# Clear inputs: two sorted arrays
# Clear output: one merged sorted array
# → Strong extraction signal
 
# The 'partition' operation is conceptually distinct from 'quicksort'
# Clear input: array and range
# Clear output: pivot position
# → Strong extraction signal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# Before: Repeated pattern in graph algorithm
for neighbor in graph[current]:
    if neighbor not in visited:
        visited.add(neighbor)
        stack.append(neighbor)
 
# ... later in the same function ...
 
for neighbor in graph[node]:
    if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)
 
# After: Extracted helper
def add_unvisited_neighbors(neighbors, visited, collection):
    for neighbor in neighbors:
        if neighbor not in visited:
            visited.add(neighbor)
            collection.append(neighbor)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# Before: Nested validation logic
def process_graph(graph, start, end):
    for node in graph:
        for neighbor in graph[node]:
            if neighbor not in graph:
                # Multiple lines handling invalid edge
                if strict_mode:
                    raise ValueError(f"Invalid edge to {neighbor}")
                else:
                    graph[neighbor] = []
    # ... actual processing
 
# After: Extracted validation
def validate_and_fix_graph(graph: dict, strict_mode: bool) -> None:
    """Ensure all edge targets exist as nodes."""
    for node in graph:
        for neighbor in graph[node]:
            if neighbor not in graph:
                if strict_mode:
                    raise ValueError(f"Invalid edge to {neighbor}")
                graph[neighbor] = []
 
def process_graph(graph, start, end):
    validate_and_fix_graph(graph, strict_mode=False)
    # ... actual processing (now cleaner)

1
2
3
4
5
6
7
8
9
10
11
12

# Before: Complex inline condition
if i > 0 and j > 0 and grid[i-1][j-1] == target and visited[i-1][j-1] == False:
    process_diagonal()
 
# After: Named predicate
def can_move_diagonal(grid, visited, i, j, target):
    return (i > 0 and j > 0 and 
            grid[i-1][j-1] == target and 
            not visited[i-1][j-1])
 
if can_move_diagonal(grid, visited, i, j, target):
    process_diagonal()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# Over-extraction: The cure is worse than the disease
 
# Bad: Function is trivial and name adds nothing
def increment_counter(counter):
    return counter + 1
 
# Bad: Requires reading implementation to understand
def do_step(arr, i, j, k, visited, result):
    # Complex logic that isn't encapsulated by name
    pass
 
# Bad: Too many parameters indicate wrong boundary
def process_node(graph, node, visited, distances, predecessors, 
                 priority_queue, target, max_depth):
    # This probably shouldn't be extracted
    pass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# Merge Sort decomposition
def merge_sort(arr: list[int]) -> list[int]:
    """Sort array using divide-and-conquer."""
    if is_base_case(arr):
        return arr
    
    left_half, right_half = divide(arr)
    sorted_left = merge_sort(left_half)
    sorted_right = merge_sort(right_half)
    
    return merge(sorted_left, sorted_right)
 
def is_base_case(arr: list[int]) -> bool:
    return len(arr) <= 1
 
def divide(arr: list[int]) -> tuple[list[int], list[int]]:
    mid = len(arr) // 2
    return arr[:mid], arr[mid:]
 
def merge(left: list[int], right: list[int]) -> list[int]:
    """Merge two sorted arrays into one sorted array."""
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# Dijkstra's algorithm decomposition
def dijkstra(graph: dict, source: int, target: int) -> tuple[int, list[int]]:
    """Find shortest path from source to target."""
    distances, predecessors = initialize_structures(graph, source)
    priority_queue = [(0, source)]
    
    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        
        if should_skip(current_node, current_dist, distances):
            continue
        
        if current_node == target:
            return current_dist, reconstruct_path(predecessors, source, target)
        
        relax_edges(graph, current_node, current_dist, distances, 
                   predecessors, priority_queue)
    
    return float('inf'), []
 
def initialize_structures(graph: dict, source: int):
    distances = {node: float('inf') for node in graph}
    distances[source] = 0
    predecessors = {source: None}
    return distances, predecessors
 
def should_skip(node, distance, distances):
    return distance > distances[node]
 
def relax_edges(graph, node, node_dist, distances, predecessors, pq):
    for neighbor, weight in graph[node]:
        new_dist = node_dist + weight
        if new_dist < distances[neighbor]:
            distances[neighbor] = new_dist
            predecessors[neighbor] = node
            heapq.heappush(pq, (new_dist, neighbor))
 
def reconstruct_path(predecessors, source, target):
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = predecessors.get(current)
    return path[::-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# Longest Common Subsequence decomposition
def longest_common_subsequence(text1: str, text2: str) -> str:
    """Find the longest common subsequence of two strings."""
    dp_table = build_lcs_table(text1, text2)
    return extract_lcs(dp_table, text1, text2)
 
def build_lcs_table(text1: str, text2: str) -> list[list[int]]:
    """Build DP table where dp[i][j] = LCS length of text1[:i] and text2[:j]."""
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp
 
def extract_lcs(dp: list[list[int]], text1: str, text2: str) -> str:
    """Reconstruct the LCS from the DP table."""
    i, j = len(text1), len(text2)
    lcs_chars = []
    
    while i > 0 and j > 0:
        if text1[i-1] == text2[j-1]:
            lcs_chars.append(text1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] >= dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    return ''.join(reversed(lcs_chars))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

# N-Queens decomposition
def solve_n_queens(n: int) -> list[list[str]]:
    """Find all solutions to the N-Queens puzzle."""
    solutions = []
    board = create_empty_board(n)
    
    def backtrack(row: int):
        if is_complete(row, n):
            solutions.append(format_board(board))
            return
        
        for col in range(n):
            if is_safe_placement(board, row, col):
                place_queen(board, row, col)
                backtrack(row + 1)
                remove_queen(board, row, col)
    
    backtrack(0)
    return solutions
 
def create_empty_board(n: int) -> list[list[str]]:
    return [['.' for _ in range(n)] for _ in range(n)]
 
def is_complete(row: int, n: int) -> bool:
    return row == n
 
def is_safe_placement(board: list[list[str]], row: int, col: int) -> bool:
    n = len(board)
    # Check column
    for i in range(row):
        if board[i][col] == 'Q':
            return False
    # Check upper-left diagonal
    for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
        if board[i][j] == 'Q':
            return False
    # Check upper-right diagonal
    for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
        if board[i][j] == 'Q':
            return False
    return True
 
def place_queen(board: list[list[str]], row: int, col: int):
    board[row][col] = 'Q'
 
def remove_queen(board: list[list[str]], row: int, col: int):
    board[row][col] = '.'
 
def format_board(board: list[list[str]]) -> list[str]:
    return [''.join(row) for row in board]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Bad: Does two things
def validate_and_process(data):
    if not is_valid(data):
        raise ValueError("Invalid data")
    return transform(data)
 
# Good: Separate concerns
def validate(data):
    if not is_valid(data):
        raise ValueError("Invalid data")
 
def process(data):
    return transform(data)
 
# Caller combines as needed
validate(data)
result = process(data)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# Impure: Modifies external state
total = 0
def add_to_total(value):
    global total
    total += value
    return total
 
# Pure: No side effects, predictable output
def compute_sum(values):
    return sum(values)
 
# Impure: Mutates input
def sort_in_place(arr):
    arr.sort()
 
# Pure: Returns new sorted array
def sorted_copy(arr):
    return sorted(arr)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# Bad: Too many parameters
def find_path(graph, start, end, visited, distances, predecessors, max_depth, 
              allow_cycles, weight_threshold):
    pass
 
# Better: Group related parameters
@dataclass
class SearchConfig:
    max_depth: int
    allow_cycles: bool
    weight_threshold: float
 
@dataclass
class SearchState:
    visited: set
    distances: dict
    predecessors: dict
 
def find_path(graph: dict, start: int, end: int, 
              config: SearchConfig, state: SearchState):
    pass
 
# Or: Split into more focused functions
def find_shortest_path(graph, start, end): pass
def find_path_with_constraints(graph, start, end, max_depth): pass

1
2
3
4
5
6
7
8
9
10

# Bad: Vague or misleading names
def check(data): pass      # Check what?
def do_stuff(arr): pass    # What stuff?
def helper1(x): pass       # Unhelpful
 
# Good: Intent is clear from name
def is_valid_binary_tree(node): pass
def find_minimum_spanning_tree(graph): pass
def partition_around_pivot(arr, start, end): pass
def compute_prefix_sum(values): pass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

def count_islands(grid: list[list[str]]) -> int:
    """Count number of connected island regions in grid."""
    if not grid or not grid[0]:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    
    # Inner function: Uses grid, rows, cols, visited from enclosing scope
    def flood_fill(start_row: int, start_col: int) -> None:
        """Mark all connected land cells as visited."""
        stack = [(start_row, start_col)]
        
        while stack:
            row, col = stack.pop()
            
            if (row < 0 or row >= rows or 
                col < 0 or col >= cols or
                visited[row][col] or 
                grid[row][col] != '1'):
                continue
            
            visited[row][col] = True
            
            # Add all four neighbors
            stack.extend([
                (row + 1, col),
                (row - 1, col),
                (row, col + 1),
                (row, col - 1)
            ])
    
    # Main algorithm
    island_count = 0
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == '1' and not visited[row][col]:
                flood_fill(row, col)
                island_count += 1
    
    return island_count

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

def generate_permutations(elements: list) -> list[list]:
    """Generate all permutations of elements."""
    result = []
    used = [False] * len(elements)
    current_permutation = []
    
    def backtrack():
        # Base case: permutation complete
        if len(current_permutation) == len(elements):
            result.append(current_permutation.copy())
            return
        
        # Try each unused element
        for i in range(len(elements)):
            if used[i]:
                continue
            
            # Make choice
            used[i] = True
            current_permutation.append(elements[i])
            
            # Recurse
            backtrack()
            
            # Undo choice
            current_permutation.pop()
            used[i] = False
    
    backtrack()
    return result
 
# Without inner function, we'd need:
# def backtrack(elements, used, current, result)
# Called as: backtrack(elements, used, current, result)
# Much more verbose and error-prone

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def solve(grid):
    import heapq
    if not grid: return -1
    m, n = len(grid), len(grid[0])
    if grid[0][0] == -1 or grid[m-1][n-1] == -1: return -1
    d = [[float('inf')] * n for _ in range(m)]
    d[0][0] = grid[0][0]
    pq = [(d[0][0], 0, 0)]
    while pq:
        dist, r, c = heapq.heappop(pq)
        if dist > d[r][c]: continue
        if r == m - 1 and c == n - 1: return dist
        for dr, dc in [(0,1),(1,0),(0,-1),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != -1:
                nd = dist + grid[nr][nc]
                if nd < d[nr][nc]:
                    d[nr][nc] = nd
                    heapq.heappush(pq, (nd, nr, nc))
    return -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

import heapq
from typing import Optional
 
# Type aliases for clarity
Grid = list[list[int]]
Position = tuple[int, int]
 
BLOCKED = -1
DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # Right, Down, Left, Up
 
 
def find_shortest_path_cost(grid: Grid) -> int:
    """
    Find minimum cost path from top-left to bottom-right of weighted grid.
    
    Grid values:
    - Positive integers: traversal cost of that cell
    - -1: blocked cell (impassable)
    
    Returns minimum total cost, or -1 if no path exists.
    
    Algorithm: Dijkstra's shortest path adapted for grids.
    Time: O(mn log(mn))  Space: O(mn)
    """
    if not is_valid_grid(grid):
        return -1
    
    rows, cols = len(grid), len(grid[0])
    start = (0, 0)
    end = (rows - 1, cols - 1)
    
    if is_blocked(grid, start) or is_blocked(grid, end):
        return -1
    
    distances = initialize_distances(rows, cols)
    distances[0][0] = grid[0][0]
    
    priority_queue = [(distances[0][0], start)]
    
    while priority_queue:
        current_cost, position = heapq.heappop(priority_queue)
        
        if should_skip_position(current_cost, position, distances):
            continue
        
        if position == end:
            return current_cost
        
        process_neighbors(grid, position, current_cost, distances, priority_queue)
    
    return -1  # No path found
 
 
def is_valid_grid(grid: Grid) -> bool:
    """Check if grid is non-empty and rectangular."""
    return bool(grid and grid[0])
 
 
def is_blocked(grid: Grid, position: Position) -> bool:
    """Check if position is a blocked cell."""
    row, col = position
    return grid[row][col] == BLOCKED
 
 
def initialize_distances(rows: int, cols: int) -> list[list[float]]:
    """Create distance matrix initialized to infinity."""
    return [[float('inf')] * cols for _ in range(rows)]
 
 
def should_skip_position(cost: int, position: Position, 
                         distances: list[list[float]]) -> bool:
    """Check if we've already found a better path to this position."""
    row, col = position
    return cost > distances[row][col]
 
 
def process_neighbors(grid: Grid, position: Position, current_cost: int,
                     distances: list[list[float]], 
                     priority_queue: list) -> None:
    """Explore and potentially update all valid neighbors."""
    rows, cols = len(grid), len(grid[0])
    row, col = position
    
    for delta_row, delta_col in DIRECTIONS:
        neighbor = (row + delta_row, col + delta_col)
        
        if is_valid_position(neighbor, rows, cols, grid):
            update_distance_if_better(
                grid, neighbor, current_cost, distances, priority_queue
            )
 
 
def is_valid_position(position: Position, rows: int, cols: int, 
                      grid: Grid) -> bool:
    """Check if position is within bounds and not blocked."""
    row, col = position
    return (0 <= row < rows and 
            0 <= col < cols and 
            grid[row][col] != BLOCKED)
 
 
def update_distance_if_better(grid: Grid, position: Position, 
                               current_cost: int,
                               distances: list[list[float]],
                               priority_queue: list) -> None:
    """Update distance to position if current path is better."""
    row, col = position
    new_cost = current_cost + grid[row][col]
    
    if new_cost < distances[row][col]:
        distances[row][col] = new_cost
        heapq.heappush(priority_queue, (new_cost, position))