## 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.

## 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:

- If the coin value is greater than the
`last_coin`

value, we skip it. This ensures that we don't duplicate possible combinations. - If the coin value is the same as the remaining change, we have a valid solution, so I add one to the
`combinations`

value. - 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
```

## Top comments (0)