Making connections

Weekly Challenge 285

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: No Connection

Task

You are given a list of routes, @routes.

Write a script to find the destination with no further outgoing connection.

My solution

This is pretty straight forward so doesn't need too much explanation. I compute two lists, origins has the first values from the routes list while destinations has the second value.

I then use list comprehension to find destinations that are not in the origins list, and store this as dead_ends. I raise an error if there is not exactly one item in this list.

def no_connection(routes: list) -> str:
    origins = [v[0] for v in routes]
    destinations = [v[1] for v in routes]
    dead_ends = [d for d in destinations if d not in origins]

    if len(dead_ends) > 1:
        raise ValueError(
            'There are multiple routes with no outgoing connection')

    if len(dead_ends) == 0:
        raise ValueError('All routes have an outgoing connection')

    return dead_ends[0]

Examples

$ ./ch-1.py B C C D D A
A

$ ./ch-1.py A Z
Z

Task 2: Making Change

Task

Compute the number of ways to make change for given amount in cents. By using the coins e.g. Penny, Nickel, Dime, Quarter and Half-dollar, in how many distinct ways can the total value equal to the given amount? Order of coin selection does not matter.

• A penny (P) is equal to 1 cent.
• A nickel (N) is equal to 5 cents.
• A dime (D) is equal to 10 cents.
• A quarter (Q) is equal to 25 cents.
• A half-dollar (HD) is equal to 50 cents.

My solution

Due to a (now fixed) bug in my code, this took a little longer to complete than I had hoped. I know both Python and Perl have a debugger, but some time you can't beat print statements :)

It's been a while since we have a task that calls for the use of a recursive function. For this task, I have a recursive function called making_change which takes the remaining change, and the last used coin. The first call sets the remaining_change value to the input and the last_coin value to None (undef in Perl).

Each call iterates through the possible coins, and does one of three things:

1. If the coin value is greater than the last_coin value, we skip it. This ensures that we don't duplicate possible combinations.
2. If the coin value is the same as the remaining change, we have a valid solution, so I add one to the combinations value.
3. If the coin value is less than the remaining value, I call the function again with the remaining value reduced by the coin used.

The combinations value is passed upstream so the final return will have the correct number of combinations.

def making_change(remaining: int, last_coin: int | None = None) -> int:
    combinations = 0

    for coin in [1, 5, 10, 25, 50]:
        if last_coin and last_coin < coin:
            continue
        if coin == remaining:
            combinations += 1
        if coin < remaining:
            combinations += making_change(remaining-coin, coin)

    return combinations

There are limits on recursion. Perl will warn when a recursion is (100 deep)[https://perldoc.perl.org/perldiag#Deep-recursion-on-subroutine-%22%25s%22]. This value can only be changed by recompiling Perl. By default, Python will raise a (ResursionError)[https://docs.python.org/3/library/exceptions.html#RecursionError] after 995 recursions, although this value can be modified at runtime.

Examples

$ ./ch-2.py 9
2

$ ./ch-2.py 15
6

$ ./ch-2.py 100
292