Python Algorithm Practice - Waterloo CCC Prep Part 2 🗺️

Welcome to Part 2! These exercises build toward CCC Question 5 problems - grid traversal, recursion, and graph exploration (DFS/BFS). We'll progress step-by-step from arrays to 2D grids to recursive exploration!

📖 Understanding 2D Arrays (Grids)

CCC Question 5 typically involves exploring a 2D grid (like a map or maze). Before we dive into complex algorithms, let's master the basics of working with grids!

Why Grids?

Grids represent maps, mazes, game boards, and more. Each cell can represent terrain, obstacles, or data. We need to navigate these efficiently!

Grid Example (4x4):
. . # .
. # . .
. . . #
# . . .

Where:
'.' = walkable
'#' = blocked

🎯 Key Concepts: 2D Arrays in Python

Creating a 2D Array:

# Method 1: List of lists
grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# Method 2: Programmatically
rows, cols = 3, 4
grid = [[0 for _ in range(cols)] for _ in range(rows)]

Accessing Elements:

grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# grid[row][col]
print(grid[0][0])  # 1 (top-left)
print(grid[1][2])  # 6 (middle row, right)
print(grid[2][1])  # 8 (bottom row, middle)

Traversing a 2D Array:

# Nested loops - visit every cell
for row in range(len(grid)):
    for col in range(len(grid[0])):
        print(f"Cell ({row},{col}) = {grid[row][col]}")

The Four Directions:

# Moving up, down, left, right
directions = [
    (-1, 0),  # up
    (1, 0),   # down
    (0, -1),  # left
    (0, 1)    # right
]

# To get neighbors of (row, col):
for dr, dc in directions:
    new_row = row + dr
    new_col = col + dc
    # Check if valid position before accessing!

Exercise 0: Warm Up - Grid Sum 🔢

Difficulty: Easy

Your Task: Write a function grid_sum(grid) that:

Takes a 2D list of integers
Returns the sum of all numbers in the grid

Hint: Use nested loops to visit each cell!

Examples:

grid1 = [
    [1, 2, 3],
    [4, 5, 6]
]
print(grid_sum(grid1))  # Output: 21

grid2 = [
    [10, -5],
    [3, 7],
    [2, -1]
]
print(grid_sum(grid2))  # Output: 16

Exercise 1: Find Maximum in Grid 🔍

Difficulty: Easy

Your Task: Write a function grid_maximum(grid) that:

Takes a 2D list of integers
Returns the largest number in the entire grid

Examples:

grid1 = [
    [3, 7, 2],
    [9, 1, 5],
    [4, 8, 6]
]
print(grid_maximum(grid1))  # Output: 9

grid2 = [
    [-5, -2],
    [-10, -1],
    [-3, -7]
]
print(grid_maximum(grid2))  # Output: -1

Exercise 2: Count Specific Value 📊

Difficulty: Easy

Your Task: Write a function count_value(grid, target) that:

Takes a 2D list and a target value
Returns how many times the target appears in the grid

Examples:

grid = [
    [1, 2, 1],
    [3, 1, 2],
    [1, 3, 1]
]
print(count_value(grid, 1))  # Output: 5
print(count_value(grid, 3))  # Output: 2
print(count_value(grid, 5))  # Output: 0

Exercise 3: Row and Column Sums 🧮

Difficulty: Medium

Your Task: Write a function sum_rows_and_cols(grid) that:

Takes a 2D list of integers
Returns a tuple: (list of row sums, list of column sums)

Examples:

grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print(sum_rows_and_cols(grid))
# Output: ([6, 15, 24], [12, 15, 18])
# Row sums: [1+2+3=6, 4+5+6=15, 7+8+9=24]
# Col sums: [1+4+7=12, 2+5+8=15, 3+6+9=18]

grid2 = [
    [1, 1],
    [2, 2],
    [3, 3]
]
print(sum_rows_and_cols(grid2))
# Output: ([2, 4, 6], [6, 6])

Exercise 4: Find Position 📍

Difficulty: Medium

Your Task: Write a function find_position(grid, target) that:

Takes a 2D list and a target value
Returns the position (row, col) of the FIRST occurrence
If not found, return None

Examples:

grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print(find_position(grid, 5))  # Output: (1, 1)
print(find_position(grid, 7))  # Output: (2, 0)
print(find_position(grid, 10)) # Output: None

Exercise 5: Check Neighbors 🧭

Difficulty: Medium

Your Task: Write a function count_neighbors(grid, row, col, value) that:

Takes a grid, a position (row, col), and a target value
Returns how many of the 4 adjacent cells (up, down, left, right) equal the target value
Be careful of boundaries!

Hint: Use the directions pattern from earlier!

Examples:

grid = [
    [1, 2, 1],
    [2, 5, 2],
    [1, 2, 1]
]

print(count_neighbors(grid, 1, 1, 2))  # Output: 4
# Center cell (5) has 4 neighbors that are all 2

print(count_neighbors(grid, 0, 0, 2))  # Output: 1
# Top-left (1) has only right neighbor = 2

print(count_neighbors(grid, 1, 1, 1))  # Output: 0
# Center cell has no neighbors = 1

Exercise 5.5: Grid Border Sum 🔲

Difficulty: Medium

Your Task: Write a function border_sum(grid) that:

Takes a 2D list of integers
Returns the sum of all cells on the border (edges) of the grid
Border cells are those in the first/last row OR first/last column

Hint: A cell is on the border if its row is 0 or last row, OR its column is 0 or last column. Be careful not to count corner cells twice!

Examples:

grid1 = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print(border_sum(grid1))  # Output: 40
# Border cells: 1,2,3,4,6,7,8,9 (not 5, it's in the center)
# Sum: 1+2+3+4+6+7+8+9 = 40

grid2 = [
    [1, 1, 1, 1],
    [1, 2, 2, 1],
    [1, 2, 2, 1],
    [1, 1, 1, 1]
]
print(border_sum(grid2))  # Output: 16
# Border is all the 1s (outer ring)

grid3 = [
    [5, 10],
    [15, 20]
]
print(border_sum(grid3))  # Output: 50
# All cells are on border in a 2x2 grid

Exercise 5.6: Transpose Grid (Flip Rows/Columns) 🔄

Difficulty: Hard

Your Task: Write a function transpose(grid) that:

Takes a 2D list (doesn't have to be square)
Returns a NEW grid where rows become columns and columns become rows
This is called "transposing" the matrix

Hint: If the original grid is rows × cols, the transposed grid will be cols × rows. Element at grid[i][j] moves to transposed[j][i].

Visual Example:

Original (3×2):        Transposed (2×3):
[1, 2]                 [1, 3, 5]
[3, 4]        →        [2, 4, 6]
[5, 6]

Examples:

grid1 = [
    [1, 2, 3],
    [4, 5, 6]
]
print(transpose(grid1))
# Output:
# [
#     [1, 4],
#     [2, 5],
#     [3, 6]
# ]

grid2 = [
    [1, 2],
    [3, 4],
    [5, 6]
]
print(transpose(grid2))
# Output:
# [
#     [1, 3, 5],
#     [2, 4, 6]
# ]

grid3 = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print(transpose(grid3))
# Output:
# [
#     [1, 4, 7],
#     [2, 5, 8],
#     [3, 6, 9]
# ]
# Notice: diagonals stay in place, everything else swaps!

🔄 Understanding Recursion

Recursion = A function that calls itself to solve smaller versions of the same problem.

The Three Rules of Recursion:

Base Case - When to STOP recursing (prevents infinite loops!)
Recursive Case - How to break the problem into smaller pieces
Progress - Each recursive call must get closer to the base case

Classic Example: Factorial

def factorial(n):
    # Base case: 0! = 1
    if n == 0:
        return 1
    
    # Recursive case: n! = n × (n-1)!
    return n * factorial(n - 1)

# factorial(5) = 5 × factorial(4)
#              = 5 × 4 × factorial(3)
#              = 5 × 4 × 3 × factorial(2)
#              = 5 × 4 × 3 × 2 × factorial(1)
#              = 5 × 4 × 3 × 2 × 1 × factorial(0)
#              = 5 × 4 × 3 × 2 × 1 × 1 = 120

Visual Thinking:

factorial(3)
├─ 3 * factorial(2)
│  ├─ 2 * factorial(1)
│  │  ├─ 1 * factorial(0)
│  │  │  └─ 1 (base case!)
│  │  └─ 1 * 1 = 1
│  └─ 2 * 1 = 2
└─ 3 * 2 = 6

Exercise 6: Simple Recursion - Countdown 🚀

Difficulty: Easy-Medium

Your Task: Write a recursive function countdown(n) that:

Takes a positive integer n
Prints numbers from n down to 1
Uses recursion (NO loops allowed!)

Hint:

def countdown(n):
    # Base case: when to stop?
    
    # Print current number
    
    # Recursive case: countdown from n-1

Examples:

countdown(5)
# Output:
# 5
# 4
# 3
# 2
# 1

countdown(3)
# Output:
# 3
# 2
# 1

Exercise 7: Recursive Sum 🔢

Difficulty: Medium

Your Task: Write a recursive function recursive_sum(numbers, index) that:

Takes a list of numbers and starting index
Returns the sum of all elements from that index to the end
Uses recursion (NO loops!)

Hint:

def recursive_sum(numbers, index):
    # Base case: reached end of list?
    
    # Recursive case: current element + sum of rest

Examples:

print(recursive_sum([1, 2, 3, 4, 5], 0))  # Output: 15
print(recursive_sum([1, 2, 3, 4, 5], 2))  # Output: 12 (3+4+5)
print(recursive_sum([10, 20, 30], 1))     # Output: 50 (20+30)

🌊 Understanding DFS (Depth-First Search)

Now that we understand recursion and grids, we can combine them with Depth-First Search (DFS)!

What is DFS?

Explore as far as possible down one path before backtracking
Perfect for: finding all connected cells, exploring mazes, flood fill
Implementation: Use recursion (or a stack)

How DFS Works:

Starting at S, explore neighbors:

S 1 2     DFS visits: S→1→3→4→2→5
. 3 .     (goes deep before wide)
. 4 5

DFS on a Grid - The Pattern:

def dfs(grid, row, col, visited):
    # Base cases (when to STOP):
    # 1. Out of bounds?
    if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
        return
    
    # 2. Already visited?
    if (row, col) in visited:
        return
    
    # 3. Is this cell valid? (depends on problem)
    if grid[row][col] == 0:  # Example: 0 is blocked
        return
    
    # Mark as visited
    visited.add((row, col))
    
    # Recursive case: explore all 4 neighbors
    dfs(grid, row - 1, col, visited)  # up
    dfs(grid, row + 1, col, visited)  # down
    dfs(grid, row, col - 1, visited)  # left
    dfs(grid, row, col + 1, visited)  # right

Key Insight: DFS explores COMPLETELY down one direction before trying another. It's like exploring a maze by always taking the first available path until you hit a dead end, then backtracking.

Exercise 8: Flood Fill 🎨

Difficulty: Medium-Hard

Your Task: Write a recursive function flood_fill(grid, row, col, new_color) that:

Starts at position (row, col)
Changes that cell and ALL connected cells of the same color to new_color
Connected = adjacent horizontally or vertically (not diagonal)
Returns the modified grid

Hint: This is like painting in MS Paint! The fill spreads to all connected cells of the same color.

Algorithm:

1. Store original color at starting position
2. If current cell is out of bounds OR not original color: return
3. Change current cell to new_color
4. Recursively fill all 4 neighbors

Examples:

grid = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]

result = flood_fill(grid, 0, 0, 2)
# Output:
# [2, 2, 2],
# [2, 0, 2],
# [2, 2, 2]
# All connected 1s became 2s

grid2 = [
    [1, 1, 0],
    [1, 0, 0],
    [0, 0, 1]
]

result2 = flood_fill(grid2, 0, 0, 5)
# Output:
# [5, 5, 0],
# [5, 0, 0],
# [0, 0, 1]
# Only top-left connected 1s became 5

Exercise 9: Count Connected Components 🏝️

Difficulty: Hard

Your Task: Write a function count_regions(grid, target) that:

Takes a grid and a target value
Counts how many separate regions of that target value exist
A region = connected cells (horizontally/vertically) with the same value

Hint: Use DFS! For each unvisited target cell, run DFS to mark the entire region, then increment your counter.

Examples:

grid1 = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 1]
]
print(count_regions(grid1, 1))  # Output: 3
# Three separate groups of 1s

grid2 = [
    [2, 2, 3],
    [2, 3, 3],
    [3, 3, 3]
]
print(count_regions(grid2, 3))  # Output: 1
# All 3s are connected

print(count_regions(grid2, 2))  # Output: 1
# All 2s are connected

📚 Model Problem: Count Islands (EXAMPLE)

Let's solve a complete DFS grid problem together!

Problem: Given a 2D grid of 1s (land) and 0s (water), count the number of islands. An island is formed by connecting adjacent lands horizontally or vertically (not diagonally).

Example:

grid = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 1],
    [0, 0, 0, 0]
]
# Output: 3 islands
# Island 1: top-left connected 1s
# Island 2: single 1 on right
# Island 3: bottom-right connected 1s

Step 1: Understand the Problem

Input: 2D grid of 1s and 0s
Output: Count of separate island groups
Key insight: Connected 1s = one island

Step 2: Work Through Example by Hand

[1, 1, 0, 0]
[1, 0, 0, 1]
[0, 0, 1, 1]
[0, 0, 0, 0]

Start at (0,0): It's a 1!
- Mark it as visited
- Check neighbors: (0,1) is also 1, (1,0) is also 1
- Keep exploring until all connected 1s are found
- Island count = 1

Continue scanning...
Find unvisited 1 at (1,3): Island count = 2
Find unvisited 1 at (2,2): Island count = 3

Step 3: Identify the Pattern

This uses DFS recursion:

Scan the grid for unvisited land (1)
When found, start a DFS to mark all connected land
Increment island counter
Repeat until grid is fully scanned

Step 4: Plan the Algorithm

1. Create a visited array to track explored cells
2. Initialize island_count = 0
3. For each cell in grid:
   - If it's land (1) and not visited:
     - Run DFS to mark entire island
     - Increment island_count
4. Return island_count

DFS function (recursive):
- Mark current cell as visited
- For each of 4 neighbors:
  - If neighbor is valid, land, and unvisited:
    - Recursively call DFS on neighbor

Step 5: Write the Code

def count_islands(grid):
    if not grid:
        return 0
    
    rows = len(grid)
    cols = len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    island_count = 0
    
    def dfs(row, col):
        # Base case: out of bounds or not land or already visited
        if (row < 0 or row >= rows or 
            col < 0 or col >= cols or 
            grid[row][col] == 0 or 
            visited[row][col]):
            return
        
        # Mark as visited
        visited[row][col] = True
        
        # Explore all 4 directions
        dfs(row - 1, col)  # up
        dfs(row + 1, col)  # down
        dfs(row, col - 1)  # left
        dfs(row, col + 1)  # right
    
    # Scan entire grid
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 1 and not visited[row][col]:
                dfs(row, col)  # Explore entire island
                island_count += 1
    
    return island_count

Step 6: Test It

grid1 = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 1]
]
print(count_islands(grid1))  # Output: 3

grid2 = [
    [1, 1, 1],
    [0, 1, 0],
    [1, 1, 1]
]
print(count_islands(grid2))  # Output: 1 (all connected!)

Exercise 10: Maze Path Finder 🗺️

Difficulty: Hard

Your Task: Write a recursive function has_path(maze, row, col, visited) that:

Takes a maze grid (0=wall, 1=path), current position, and visited set
Returns True if you can reach the bottom-right corner from (row, col)
Returns False if no path exists
You can only move on 1s (paths), not 0s (walls)
You can move up, down, left, or right

Hint:

Base case: reached bottom-right? Return True!
Base case: out of bounds, wall, or already visited? Return False!
Recursive case: Try all 4 directions, return True if ANY path works

Examples:

maze1 = [
    [1, 0, 1],
    [1, 1, 1],
    [0, 0, 1]
]
visited = set()
print(has_path(maze1, 0, 0, visited))  # Output: True
# Path exists: (0,0)→(1,0)→(1,1)→(1,2)→(2,2)

maze2 = [
    [1, 0, 1],
    [0, 0, 1],
    [0, 0, 1]
]
visited = set()
print(has_path(maze2, 0, 0, visited))  # Output: False
# No path - blocked by walls

🌊 Understanding BFS (Breadth-First Search)

BFS is different from DFS - instead of going deep, it explores level by level!

What is BFS?

Explore all neighbors at the current distance before moving farther
Perfect for: finding shortest paths, level-order traversal
Implementation: Use a queue (collections.deque)

How BFS Works:

Starting at S, explore neighbors:

S 1 2     BFS visits: S→1→3→2→4→5
. 3 .     (level by level, like ripples)
. 4 5

BFS vs DFS:

DFS: Goes deep first (recursion/stack) → Good for exploring ALL paths
BFS: Goes wide first (queue) → Good for SHORTEST path

BFS on a Grid - The Pattern:

from collections import deque

def bfs(grid, start_row, start_col):
    rows, cols = len(grid), len(grid[0])
    
    # Queue stores: (row, col, distance)
    queue = deque([(start_row, start_col, 0)])
    visited = {(start_row, start_col)}
    
    while queue:
        row, col, dist = queue.popleft()  # Process closest cells first
        
        # Do something with current cell
        print(f"Visiting ({row}, {col}) at distance {dist}")
        
        # Explore all 4 neighbors
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            new_row, new_col = row + dr, col + dc
            
            # Check if valid and unvisited
            if (0 <= new_row < rows and 
                0 <= new_col < cols and
                grid[new_row][new_col] != 0 and  # Example: 0 is blocked
                (new_row, new_col) not in visited):
                
                visited.add((new_row, new_col))
                queue.append((new_row, new_col, dist + 1))

Key Insight: BFS guarantees you find the SHORTEST path because it explores cells in order of increasing distance!

🎓 Challenge: Shortest Path Length (BFS)

Difficulty: Very Hard (CCC Q5 Level)

Your Task: Write a function shortest_path_length(maze) that:

Takes a maze grid (0=wall, 1=path)
Finds the shortest path from top-left (0,0) to bottom-right
Returns the LENGTH of that shortest path (number of cells)
Returns -1 if no path exists
Uses BFS (not recursion!) with a queue

BFS Algorithm Template:

from collections import deque

def shortest_path_length(maze):
    rows, cols = len(maze), len(maze[0])
    
    # BFS uses a queue: (row, col, distance)
    queue = deque([(0, 0, 1)])  # Start at (0,0) with distance 1
    visited = {(0, 0)}
    
    while queue:
        row, col, dist = queue.popleft()
        
        # Check if reached destination
        if row == rows - 1 and col == cols - 1:
            return dist
        
        # Explore all 4 neighbors
        for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
            new_row, new_col = row + dr, col + dc
            
            # Check if valid and unvisited
            if (0 <= new_row < rows and 
                0 <= new_col < cols and
                maze[new_row][new_col] == 1 and
                (new_row, new_col) not in visited):
                
                visited.add((new_row, new_col))
                queue.append((new_row, new_col, dist + 1))
    
    return -1  # No path found

Examples:

maze1 = [
    [1, 1, 0],
    [0, 1, 0],
    [0, 1, 1]
]
print(shortest_path_length(maze1))  # Output: 5
# Path: (0,0)→(0,1)→(1,1)→(2,1)→(2,2) = 5 cells

maze2 = [
    [1, 0, 1],
    [1, 1, 1],
    [0, 0, 1]
]
print(shortest_path_length(maze2))  # Output: 5
# Multiple paths exist, shortest is length 5

maze3 = [
    [1, 0],
    [0, 1]
]
print(shortest_path_length(maze3))  # Output: -1
# No path exists

📝 CCC Question 5 Success Tips

Draw it out - Visualize the grid on paper, trace your algorithm by hand
Check boundaries - Always validate row/col before accessing grid cells
Track visited cells - Use a set or separate boolean grid to avoid infinite recursion
Understand recursion deeply - Every recursive call should make progress toward base case
BFS for shortest path - Use BFS when you need the minimum steps/distance
DFS for exploration - Use DFS when you need to visit all reachable cells
Test small grids first - 2x2 or 3x3 grids before trying 10x10
Separate concerns - Write helper functions for checking validity, getting neighbors, etc.

Remember: Grid problems are just 2D array manipulation + recursion/BFS. Master each piece, then combine them! 🚀

DFS & BFS — Grid Traversal

Python Algorithm Practice - Waterloo CCC Prep Part 2 🗺️

📖 Understanding 2D Arrays (Grids)

Why Grids?

🎯 Key Concepts: 2D Arrays in Python

Exercise 0: Warm Up - Grid Sum 🔢

Exercise 1: Find Maximum in Grid 🔍

Exercise 2: Count Specific Value 📊

Exercise 3: Row and Column Sums 🧮

Exercise 4: Find Position 📍

Exercise 5: Check Neighbors 🧭

Exercise 5.5: Grid Border Sum 🔲

Exercise 5.6: Transpose Grid (Flip Rows/Columns) 🔄

🔄 Understanding Recursion

Exercise 6: Simple Recursion - Countdown 🚀

Exercise 7: Recursive Sum 🔢

🌊 Understanding DFS (Depth-First Search)

Exercise 8: Flood Fill 🎨

Exercise 9: Count Connected Components 🏝️

📚 Model Problem: Count Islands (EXAMPLE)

Step 1: Understand the Problem

Step 2: Work Through Example by Hand

Step 3: Identify the Pattern

Step 4: Plan the Algorithm

Step 5: Write the Code

Step 6: Test It

Exercise 10: Maze Path Finder 🗺️

🌊 Understanding BFS (Breadth-First Search)

🎓 Challenge: Shortest Path Length (BFS)

📝 CCC Question 5 Success Tips