problem4.py

problem = "problem4"
student_name = "Abudi Alshamam"
student_numer = "N1212353"

# Part A

def make_change(coin_vals, change):
    # Initialize a table to store the minimum coins needed for each amount
    dp = [float('inf')] * (change + 1)
    dp[0] = 0  # Base case: 0 coins are needed to make change for 0

    # Fill the table iteratively
    for amount in range(1, change + 1):
        for coin in coin_vals:
            if coin <= amount:
                dp[amount] = min(dp[amount], dp[amount - coin] + 1)

    return dp[change] if dp[change] != float('inf') else -1  # Return -1 if no solution exists

# Part B

def make_change2(coin_vals, change):
    # Initialize a table to store the minimum coins needed for each amount
    dp = [float('inf')] * (change + 1)
    dp[0] = 0  # Base case: 0 coins are needed to make change for 0

    # Initialize a table to store the last coin used for each amount
    last_coin = [-1] * (change + 1)

    # Fill the table iteratively
    for amount in range(1, change + 1):
        for coin in coin_vals:
            if coin <= amount and dp[amount - coin] + 1 < dp[amount]:
                dp[amount] = dp[amount - coin] + 1
                last_coin[amount] = coin

    # If no solution exists, return an empty list
    if dp[change] == float('inf'):
        return []

    # Backtrack to find the coins used
    result = []
    while change > 0:
        result.append(last_coin[change])
        change -= last_coin[change]

    return result

# Part C

def word_break(dictionary, string_to_segment):
    n = len(string_to_segment)
    dp = [False] * (n + 1)
    dp[0] = True

    # To store the words used for segmentation
    backtrack = [-1] * (n + 1)

    # Fill the dp table
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and string_to_segment[j:i] in dictionary:
                dp[i] = True
                backtrack[i] = j
                break

    # If the string cannot be segmented
    if not dp[n]:
        print("Cannot be segmented.")
        return

    # Backtrack to find the words used
    result = []
    idx = n
    while idx > 0:
        prev_idx = backtrack[idx]
        result.append(string_to_segment[prev_idx:idx])
        idx = prev_idx

    result.reverse()
    print(f"can be segmented into: {' '.join(f'\"{word}\"' for word in result)}")

# Example usage
# ["coffee", "parrot", "a", "m", "can", "crate", "walk", "mmjop", "fe"]
# "canmawalkaacanmmjopmafea"
# "canmawallkaacanmmjopmafea"


# print(make_change([1, 2, 5], 11))
# print(make_change2([1, 2, 5], 11))

# word_break(["coffee", "parrot", "a", "m", "can", "crate", "walk", "mmjop", "fe"], "canmawalkaacanmmjopmafea")