Hands-on Practice with Control Structures

Advanced Practice

Let's finish with a few advanced exercises that combine multiple control structures and techniques.

Exercise 10: Improved Prime Number Generator (Sieve of Eratosthenes)

Implement the Sieve of Eratosthenes algorithm to find all prime numbers up to a given limit more efficiently.

def sieve_of_eratosthenes(limit):
    # Initialize all numbers as potential primes
    is_prime = [True] * (limit + 1)
    
    # 0 and 1 are not prime
    if limit >= 0:
        is_prime[0] = False
    if limit >= 1:
        is_prime[1] = False
    
    # Apply the sieve
    for number in range(2, int(limit**0.5) + 1):
        if is_prime[number]:
            # Mark all multiples of the current prime as non-prime
            for multiple in range(number*number, limit + 1, number):
                is_prime[multiple] = False
    
    # Collect the primes
    primes = [number for number, prime in enumerate(is_prime) if prime]
    
    return primes

# Compare performance with the naive approach
import time

limit = 10000

# Measure time for the naive approach
start_time = time.time()
naive_primes = find_primes(limit)
naive_time = time.time() - start_time
print(f"Naive approach found {len(naive_primes)} primes up to {limit}")
print(f"Time taken: {naive_time:.6f} seconds")

# Measure time for the sieve approach
start_time = time.time()
sieve_primes = sieve_of_eratosthenes(limit)
sieve_time = time.time() - start_time
print(f"Sieve approach found {len(sieve_primes)} primes up to {limit}")
print(f"Time taken: {sieve_time:.6f} seconds")

# Check that both methods found the same primes
print(f"Both methods found the same primes: {naive_primes == sieve_primes}")

# Calculate speedup
speedup = naive_time / sieve_time
print(f"The sieve approach was {speedup:.2f}x faster")

Discussion

The Sieve of Eratosthenes is a classic algorithm for finding all prime numbers up to a given limit. It's much more efficient than the naive approach of checking each number individually, especially for large limits.

The key insight is that instead of checking if each number is prime, we start with the assumption that all numbers are potentially prime, then systematically eliminate the non-primes. This approach leverages the fact that any multiple of a prime number cannot itself be prime.

This exercise demonstrates the power of efficient algorithms over brute-force approaches. It also shows how list comprehensions can be used to filter results based on a condition.

Exercise 11: Text Analyzer

Create a function that analyzes a text and returns statistics including word count, character count, average word length, and the most common words.

def analyze_text(text):
    if not text:
        return {
            "error": "Empty text provided"
        }
    
    # Split the text into words
    words = text.split()
    
    # Count the total characters (excluding spaces)
    char_count = sum(len(word) for word in words)
    
    # Count the frequency of each word (case insensitive)
    word_frequency = {}
    for word in words:
        # Remove punctuation and convert to lowercase
        clean_word = ''.join(char for char in word if char.isalnum()).lower()
        if clean_word:  # Skip empty strings after cleaning
            word_frequency[clean_word] = word_frequency.get(clean_word, 0) + 1
    
    # Find the most common words
    if word_frequency:
        max_frequency = max(word_frequency.values())
        most_common = [word for word, freq in word_frequency.items() 
                     if freq == max_frequency]
    else:
        most_common = []
    
    # Calculate average word length
    avg_word_length = char_count / len(words) if words else 0
    
    # Prepare and return the results
    return {
        "word_count": len(words),
        "character_count": char_count,
        "unique_words": len(word_frequency),
        "average_word_length": round(avg_word_length, 2),
        "most_common_words": most_common,
        "most_common_frequency": max_frequency if word_frequency else 0
    }

# Test the function
sample_text = """
Python is a high-level, general-purpose programming language. Its design philosophy 
emphasizes code readability with the use of significant indentation. Python is 
dynamically typed and garbage-collected. It supports multiple programming paradigms, 
including structured, object-oriented, and functional programming.
"""

analysis = analyze_text(sample_text)

print("Text Analysis Results:")
print(f"Word count: {analysis['word_count']}")
print(f"Character count: {analysis['character_count']}")
print(f"Unique words: {analysis['unique_words']}")
print(f"Average word length: {analysis['average_word_length']} characters")
print(f"Most common word(s): {', '.join(analysis['most_common_words'])}")
print(f"Most common word frequency: {analysis['most_common_frequency']}")

Discussion

This exercise combines various control structures, dictionary operations, and string manipulation techniques. The solution demonstrates how to process text data and extract meaningful statistics using loops and conditionals.

The solution uses a dictionary to track word frequencies, which is a common technique in text analysis. It also demonstrates the use of list comprehensions for transforming and filtering data.

For a more advanced version, consider implementing additional features like:

• Sentence count and average sentence length
• Filtering out common "stop words" like "the", "and", "is"
• Calculating the readability score using formulas like Flesch-Kincaid

Exercise 12: Tic-Tac-Toe Game

Create a simple two-player Tic-Tac-Toe game that allows players to take turns marking positions on a 3x3 grid.

def tic_tac_toe():
    # Initialize the board
    board = [' ' for _ in range(9)]  # 3x3 board as a flat list
    
    def print_board():
        """Print the current state of the board."""
        print("\n")
        print(f" {board[0]} | {board[1]} | {board[2]} ")
        print("---+---+---")
        print(f" {board[3]} | {board[4]} | {board[5]} ")
        print("---+---+---")
        print(f" {board[6]} | {board[7]} | {board[8]} ")
        print("\n")
    
    def is_winner(player):
        """Check if the given player has won."""
        # Check rows
        for i in range(0, 9, 3):
            if board[i] == board[i+1] == board[i+2] == player:
                return True
        
        # Check columns
        for i in range(3):
            if board[i] == board[i+3] == board[i+6] == player:
                return True
        
        # Check diagonals
        if board[0] == board[4] == board[8] == player:
            return True
        if board[2] == board[4] == board[6] == player:
            return True
        
        return False
    
    def is_board_full():
        """Check if the board is full (tie game)."""
        return ' ' not in board
    
    # Game loop
    current_player = 'X'
    
    print("Welcome to Tic-Tac-Toe!")
    print("Enter positions as numbers 1-9 (left to right, top to bottom)")
    
    while True:
        print_board()
        
        # Get player move
        position = input(f"Player {current_player}, enter your move (1-9): ")
        
        # Validate input
        if not position.isdigit() or not 1 <= int(position) <= 9:
            print("Invalid input! Please enter a number between 1 and 9.")
            continue
        
        position = int(position) - 1  # Convert to 0-based index
        
        # Check if the position is already taken
        if board[position] != ' ':
            print("That position is already taken! Try again.")
            continue
        
        # Make the move
        board[position] = current_player
        
        # Check for a win
        if is_winner(current_player):
            print_board()
            print(f"Player {current_player} wins!")
            break
        
        # Check for a tie
        if is_board_full():
            print_board()
            print("It's a tie!")
            break
        
        # Switch player
        current_player = 'O' if current_player == 'X' else 'X'
    
    # Ask if they want to play again
    play_again = input("Would you like to play again? (yes/no): ")
    if play_again.lower() in ('yes', 'y'):
        tic_tac_toe()  # Recursive call to play again
    else:
        print("Thanks for playing! Goodbye!")

# Uncomment to play the game
# tic_tac_toe()

Discussion

This implementation of Tic-Tac-Toe combines multiple control structures and techniques we've learned:

• A while loop for the main game loop
• Nested functions for organizing code
• Conditionals for validating moves and checking win conditions
• List comprehensions for initializing the board

The game demonstrates how to create an interactive program that maintains state (the board) and responds to user input. It also shows how to validate input and handle invalid cases gracefully.

For a more advanced version, consider adding features like:

• A computer player with simple AI
• Scoring to track wins across multiple games
• The ability to choose who goes first