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.

<span>def</span> <span>no_connection</span><span>(</span><span>routes</span><span>:</span> <span>list</span><span>)</span> <span>-></span> <span>str</span><span>:</span>
    <span>origins</span> <span>=</span> <span>[</span><span>v</span><span>[</span><span>0</span><span>]</span> <span>for</span> <span>v</span> <span>in</span> <span>routes</span><span>]</span>
    <span>destinations</span> <span>=</span> <span>[</span><span>v</span><span>[</span><span>1</span><span>]</span> <span>for</span> <span>v</span> <span>in</span> <span>routes</span><span>]</span>
    <span>dead_ends</span> <span>=</span> <span>[</span><span>d</span> <span>for</span> <span>d</span> <span>in</span> <span>destinations</span> <span>if</span> <span>d</span> <span>not</span> <span>in</span> <span>origins</span><span>]</span>
    <span>if</span> <span>len</span><span>(</span><span>dead_ends</span><span>)</span> <span>></span> <span>1</span><span>:</span>
        <span>raise</span> <span>ValueError</span><span>(</span>
            <span>'</span><span>There are multiple routes with no outgoing connection</span><span>'</span><span>)</span>
    <span>if</span> <span>len</span><span>(</span><span>dead_ends</span><span>)</span> <span>==</span> <span>0</span><span>:</span>
        <span>raise</span> <span>ValueError</span><span>(</span><span>'</span><span>All routes have an outgoing connection</span><span>'</span><span>)</span>
    <span>return</span> <span>dead_ends</span><span>[</span><span>0</span><span>]</span>
<span>def</span> <span>no_connection</span><span>(</span><span>routes</span><span>:</span> <span>list</span><span>)</span> <span>-></span> <span>str</span><span>:</span>
    <span>origins</span> <span>=</span> <span>[</span><span>v</span><span>[</span><span>0</span><span>]</span> <span>for</span> <span>v</span> <span>in</span> <span>routes</span><span>]</span>
    <span>destinations</span> <span>=</span> <span>[</span><span>v</span><span>[</span><span>1</span><span>]</span> <span>for</span> <span>v</span> <span>in</span> <span>routes</span><span>]</span>
    <span>dead_ends</span> <span>=</span> <span>[</span><span>d</span> <span>for</span> <span>d</span> <span>in</span> <span>destinations</span> <span>if</span> <span>d</span> <span>not</span> <span>in</span> <span>origins</span><span>]</span>

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

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

    <span>return</span> <span>dead_ends</span><span>[</span><span>0</span><span>]</span>
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]

Enter fullscreen mode Exit fullscreen mode

Examples

<span>$ </span>./ch-1.py B C C D D A
A
<span>$ </span>./ch-1.py A Z
Z
<span>$ </span>./ch-1.py B C C D D A
A

<span>$ </span>./ch-1.py A Z
Z
$ ./ch-1.py B C C D D A
A

$ ./ch-1.py A Z
Z

Enter fullscreen mode Exit fullscreen mode

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.

<span>def</span> <span>making_change</span><span>(</span><span>remaining</span><span>:</span> <span>int</span><span>,</span> <span>last_coin</span><span>:</span> <span>int</span> <span>|</span> <span>None</span> <span>=</span> <span>None</span><span>)</span> <span>-></span> <span>int</span><span>:</span>
    <span>combinations</span> <span>=</span> <span>0</span>
    <span>for</span> <span>coin</span> <span>in</span> <span>[</span><span>1</span><span>,</span> <span>5</span><span>,</span> <span>10</span><span>,</span> <span>25</span><span>,</span> <span>50</span><span>]:</span>
        <span>if</span> <span>last_coin</span> <span>and</span> <span>last_coin</span> <span><</span> <span>coin</span><span>:</span>
            <span>continue</span>
        <span>if</span> <span>coin</span> <span>==</span> <span>remaining</span><span>:</span>
            <span>combinations</span> <span>+=</span> <span>1</span>
        <span>if</span> <span>coin</span> <span><</span> <span>remaining</span><span>:</span>
            <span>combinations</span> <span>+=</span> <span>making_change</span><span>(</span><span>remaining</span><span>-</span><span>coin</span><span>,</span> <span>coin</span><span>)</span>
    <span>return</span> <span>combinations</span>
<span>def</span> <span>making_change</span><span>(</span><span>remaining</span><span>:</span> <span>int</span><span>,</span> <span>last_coin</span><span>:</span> <span>int</span> <span>|</span> <span>None</span> <span>=</span> <span>None</span><span>)</span> <span>-></span> <span>int</span><span>:</span>
    <span>combinations</span> <span>=</span> <span>0</span>

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

    <span>return</span> <span>combinations</span>
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

Enter fullscreen mode Exit fullscreen mode

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

<span>$ </span>./ch-2.py 9
2
<span>$ </span>./ch-2.py 15
6
<span>$ </span>./ch-2.py 100
292
<span>$ </span>./ch-2.py 9
2

<span>$ </span>./ch-2.py 15
6

<span>$ </span>./ch-2.py 100
292
$ ./ch-2.py 9
2

$ ./ch-2.py 15
6

$ ./ch-2.py 100
292

Enter fullscreen mode Exit fullscreen mode

原文链接：Making connections