PyPro: Challenge 3

This challenge is due on Saturday, October 10th, 2024, at 8pm.

These exercises offer a diverse array of tasks that assess your comprehension of fundamental Python concepts such as loops, data types, string manipulations, list comprehensions, and higher-order functions.

Here is the given text in proper markdown format with numbered questions:

PyPro Challenges

1. Perfect Numbers Calculation
   By definition, a natural number is called a perfect number if its value is equal to the sum of its divisors. For example, 6 and 28 are perfect numbers:

   1 + 2 + 3 = 6
   1 + 2 + 4 + 7 + 14 = 28
   

   Write a function calc_perfect_numbers(max_exclusive) that calculates all perfect numbers up to a maximum value, such as 10,000.

2. Prime Numbers Calculation
   Write a function calc_primes_up_to(max_value) to compute all prime numbers up to a given value. A prime number is a natural number greater than 1 that is only divisible by 1 and itself. The Sieve of Eratosthenes is a useful algorithm for this task.
   Test your algorithm with the following values:

   Input	Result
   15	[2, 3, 5, 7, 11, 13]
   25	[2, 3, 5, 7, 11, 13, 17, 19, 23]
   50	[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31…]

3. Twin, Cousin, and Sexy Prime Numbers
   Compute all pairs of prime numbers with a distance of 2 (twin), 4 (cousin), and 6 (sexy) up to an upper bound n.
   For example, for limit=50, the expected results are:

   • Twins: {3: 5, 5: 7, 11: 13, 17: 19, 29: 31, 41: 43}

   • Cousins: {3: 7, 7: 11, 13: 17, 19: 23, 37: 41, 43: 47}

   • Sexy: {5: 11, 7: 13, 11: 17, 13: 19, 17: 23, 23: 29, 31: 37, 37: 43, 41: 47, 47: 53}

4. Sum of Digits (Recursive)
   Write a recursive function calc_sum_of_digits(value) that calculates the sum of the digits of a given number.
   Examples:

   Input	Number of Digits	Cross Sum
   1234	4	1 + 2 + 3 + 4 = 10
   1234567	7	1 + 2 + 3 + … 7 = 28

5. Convert to Binary (Recursive)
   Write a function to_binary(n) that recursively converts the given positive integer into its binary string representation (without using int(x, base)).
   Examples:

   Input	Result
   5	“101”
   7	“111”
   22	“10110”
   42	“101010”
   256	“100000000”

6. Letter Permutations
   Write a function calc_permutations(text) that calculates all possible permutations of the characters in the given string. Handle duplicate letters but avoid using Python’s itertools.permutations().
   Examples:

   Input	Result
   “a”	“a”
   “aa”	“aa”
   “aB”	“aB”, “Ba”
   “aBC”	“aBC”, “BaC”, “aCB”, “CaB”, “CBa”, “BCa”
   “aaC”	“aaC”, “aCa”, “Caa”

7. Join Strings with Delimiter
   Write a function join(values, delimiter) that joins a list of strings with the given delimiter and returns it as a single string. Implement this without using Python’s built-in join() function.
   Example:

   • Input: ["hello", "world", "message"], " +++ "

   • Result: "hello +++ world +++ message"

8. Pascal’s Triangle
   Write a function pascal(n) that computes Pascal’s triangle as nested lists. Each line is generated from the previous one, with sums of adjacent numbers and a 1 at the beginning and end.
   Example for n=5:

   [1]
   [1, 1]
   [1, 2, 1]
   [1, 3, 3, 1]
   [1, 4, 6, 4, 1]
   

9. Contains All Values
   Write a function contains_all(values, search_values) that checks if all search values are present in the given list. Do not use Python’s all() function.
   Examples:

   Input	Search Values	Result
   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]	[7, 2]	True
   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]	[5, 11]	False

10. Optimized Insertion Sort
    Rewrite the insertion sort algorithm to perform the sorting in one pass by finding the correct insertion point and swapping elements. Write an optimized version of insertion_sort(values).
    Example:

    • Input: [7, 2, 5, 1, 6, 8, 9, 4, 3]

    • Result: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Here are the problems with the corresponding Wikipedia links for reference:

---

11. Sudoku Solver
    Write a function solve_sudoku(board) that solves a given 9x9 Sudoku puzzle using backtracking. The puzzle is represented as a 2D list with ‘0’ indicating empty cells. The function should modify the board in-place and return True if the puzzle is solved, otherwise False.
    Sudoku - Wikipedia
    Example Input:

    board = [
        [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]
    ]
    

    Example Output:

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

12. N-Queens Problem
    Write a function solve_n_queens(n) to find all possible solutions for the n-queens problem. The function should return all distinct solutions as a list of lists, where each list represents the position of queens on the board. The board should be represented as a list of strings, where ‘Q’ and ‘.’ indicate a queen and an empty space, respectively.
    N-Queens - Wikipedia
    Example Input:
    n = 4
    Example Output:

    [
        [".Q..",
         "...Q",
         "Q...",
         "..Q."],
    
        ["..Q.",
         "Q...",
         "...Q",
         ".Q.."]
    ]
    

13. Knapsack Problem (Dynamic Programming)
    Implement a function knapsack(weights, values, capacity) that solves the 0/1 Knapsack problem using dynamic programming. Given a list of weights and corresponding values of n items, determine the maximum value that can be obtained by selecting items with a total weight not exceeding a given capacity.
    Knapsack Problem - Wikipedia
    Example Input:

    weights = [2, 3, 4, 5]
    values = [3, 4, 5, 6]
    capacity = 5
    

    Example Output:
    7 (items with weights 2 and 3 are selected, values are 3 and 4)

14. Travelling Salesman Problem (TSP)
    Write a function tsp(graph) to solve the Travelling Salesman Problem (TSP) using dynamic programming with bit masking. Given a graph represented as an adjacency matrix, find the shortest possible route that visits each city exactly once and returns to the origin city.
    Travelling Salesman Problem - Wikipedia
    Example Input:

    graph = [
        [0, 10, 15, 20],
        [10, 0, 35, 25],
        [15, 35, 0, 30],
        [20, 25, 30, 0]
    ]
    

    Example Output:
    80 (minimum cost path: 0 → 1 → 3 → 2 → 0)

15. Word Break Problem (Dynamic Programming)
    Given a string s and a dictionary of words dict, write a function word_break(s, dict) to determine if s can be segmented into a space-separated sequence of one or more dictionary words. Return all such possible sentences.
    Word Break Problem - Wikipedia
    Example Input:

    s = "catsanddog"
    dict = ["cat", "cats", "and", "sand", "dog"]
    

    Example Output:

    ["cats and dog", "cat sand dog"]
    

    Example Input:

    s = "pineapplepenapple"
    dict = ["apple", "pen", "applepen", "pine", "pineapple"]
    

    Example Output:

    ["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]