by Arne Sommer

# Changing Loops with Raku

[256] Published 1. October 2023.

This is my response to The Weekly Challenge #236.

## Challenge #236.1: Exact Change

You are asked to sell juice each costs \$5. You are given an array of bills. You can only sell ONE juice to each customer but make sure you return exact change back. You only have \$5, \$10 and \$20 notes. You do not have any change in hand at first.

Write a script to find out if it is possible to sell to each customers with correct change.

Example 1: ```Input: @bills = (5, 5, 5, 10, 20) Output: true From the first 3 customers, we collect three \$5 bills in order. From the fourth customer, we collect a \$10 bill and give back a \$5. From the fifth customer, we give a \$10 bill and a \$5 bill. Since all customers got correct change, we output true. ``` Example 2: ```Input: @bills = (5, 5, 10, 10, 20) Output: false From the first two customers in order, we collect two \$5 bills. For the next two customers in order, we collect a \$10 bill and give back a \$5 bill. For the last customer, we can not give the change of \$15 back because we only have two \$10 bills. Since not every customer received the correct change, the answer is false. ``` Example 3: ```Input: @bills = (5, 5, 5, 20) Output: true ```

I am using a `BagHash` to keep track of the content of the cash register. This data type is a read-write version of `Bag`, a read-only (or write-once, rather) data structure with integer weight of the member values.

See docs.raku.org/type/BagHash for more information about `BagHash`.

File: exact-change ```#! /usr/bin/env raku unit sub MAIN (*@bills where all(@bills) ~~ Int # [1] && all(@bills) == any(<5 10 20>), # [1a] :v(:\$verbose)); my \$cash = BagHash.new(); # [2] my \$transaction = 0; # [3] for @bills -> \$bill # [4] { my \$change = \$bill - 5; # [5] print ":Transaction { ++\$transaction } | Payment: \$bill | Change: \$change" if \$verbose; \$cash{\$bill}++; # [6] if \$change # [7] { for \$cash.keys.sort.reverse -> \$note # [8] { while \$change >= \$note && \$cash{\$note} # [9] { \$cash{\$note}--; # [9a] \$change -= \$note; # [9b] } } } if \$change # [10] { say " | Unable to give change" if \$verbose; say 'false'; # [10a] exit; # [10b] } say " | Cash Register: { \$cash.kxxv.sort.join(",") }" if \$verbose; } say "true"; # [11] ```

[1] The bills, zero or more of them, they must all be integers [1], and of the values 5, 10 and 20 only [1a] (with an `any` junction).

[3] Used by verbose mode.

[4] Iterate over each bill (accompanied by a paying customer).

[5] How much change is required for the current customer?

[6] Add the bill to the cash register.

[7] Does the customer require any change?

[8] If so, iterate over the note types in the cash register, with the largest denomination first.

The "largest bill first" approach is the best. Do not give out small bills if you do not have to. A customer paying with a 20 bill should get 10+5 if possible (and not 5+5+5), so that you can handle future customers paying with 10 bills. An example: `@bills = (5, 10, 5, 10, 5, 5, 20, 10)`.

[9] Do the customer require change up to (and including) the current denomination and we have one or more notes of that type left? If so, take the note from the cash register [9a], and give it to the customer (we are counting down how much change we still owe the customer here) [9a].

[10] Still owing the customer more change? The we have failed, say so [10a] and exit [10b].

[11] Failure to fail (so to speak) means success.

Running it:

```\$ ./exact-change 5 5 5 10 20 true \$ ./exact-change 5 5 10 10 20 false \$ ./exact-change 5 5 5 20 true ```

Looking good.

With verbose mode:

```\$ ./exact-change -v 5 5 5 10 20 :Transaction 1 | Payment: 5 | Change: 0 | Cash Register: 5 :Transaction 2 | Payment: 5 | Change: 0 | Cash Register: 5,5 :Transaction 3 | Payment: 5 | Change: 0 | Cash Register: 5,5,5 :Transaction 4 | Payment: 10 | Change: 5 | Cash Register: 5,5,10 :Transaction 5 | Payment: 20 | Change: 15 | Cash Register: 5,20 true \$ ./exact-change -v 5 5 10 10 20 :Transaction 1 | Payment: 5 | Change: 0 | Cash Register: 5 :Transaction 2 | Payment: 5 | Change: 0 | Cash Register: 5,5 :Transaction 3 | Payment: 10 | Change: 5 | Cash Register: 5,10 :Transaction 4 | Payment: 10 | Change: 5 | Cash Register: 10,10 :Transaction 5 | Payment: 20 | Change: 15 | Unable to give change false \$ ./exact-change -v 5 5 5 20 :Transaction 1 | Payment: 5 | Change: 0 | Cash Register: 5 :Transaction 2 | Payment: 5 | Change: 0 | Cash Register: 5,5 :Transaction 3 | Payment: 5 | Change: 0 | Cash Register: 5,5,5 :Transaction 4 | Payment: 20 | Change: 15 | Cash Register: 20 true ```

The "largest bills first" example works out:

```\$ ./exact-change -v 5 10 5 10 5 5 20 10 :Transaction 1 | Payment: 5 | Change: 0 | Cash Register: 5 :Transaction 2 | Payment: 10 | Change: 5 | Cash Register: 10 :Transaction 3 | Payment: 5 | Change: 0 | Cash Register: 5,10 :Transaction 4 | Payment: 10 | Change: 5 | Cash Register: 10,10 :Transaction 5 | Payment: 5 | Change: 0 | Cash Register: 5,10,10 :Transaction 6 | Payment: 5 | Change: 0 | Cash Register: 5,5,10,10 :Transaction 7 | Payment: 20 | Change: 15 | Cash Register: 5,10,20 :Transaction 8 | Payment: 10 | Change: 5 | Cash Register: 10,10,20 true ```

## Challenge #236.2: Array Loops

You are given an array of unique integers.

Write a script to determine how many loops are in the given array.

To determine a loop: Start at an index and take the number at `array[index]` and then proceed to that index and continue this until you end up at the starting index.

Example 1: ```Input: @ints = (4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10) Output: 3 To determine the 1st loop, start at index 0, the number at that index is 4, proceed to index 4, the number at that index is 15, proceed to index 15 and so on until you're back at index 0. Loops are as below: [4 15 1 6 13 5 0] [3 8 7 18 9 16 12 17 2] [14 11 19 10] ``` Example 2: ```Input: @ints = (0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3,18,15,19) Output: 6 Loops are as below: [0] [1] [13 9 14 17 18 15 5 8 2] [7 11 4 6 10 16 3] [12] [19] ``` Example 3: ```Input: @ints = (9,8,3,11,5,7,13,19,12,4,14,10,18,2,16,1,0,15,6,17) Output: 1 Loop is as below: [9 4 5 7 19 17 15 1 8 12 18 6 13 2 3 11 10 14 16 0] ```

The three examples have the same input values as the indices in the arrays (i.e. 0..19), even though the challenge does not say that this is a requirement. An integer that does not correspond with an index will cause the loop detection to stop. So let us assume that the values must indeed be the same as the indices, for now.

Implication: We have one or more directed graphs, as the values are unique and the indices certainly are as well. This implies that the only way a sequence can end is when it reaches the start value, thus forming a loop. The examples specifies that a one-value list is a loop, so we can conclude that all the values are in a (as in one and only one) loop. They number of graphs can vary from 1 (all the values) to one for each value.

File: array-loops-all ```#! /usr/bin/env raku unit sub MAIN (*@ints where all(@ints) ~~ UInt # [1] && @ints.elems == @ints.unique.elems, # [1a] :v(:\$verbose)); say ":Index:Value: ", (^@ints).map({ \$_ ~ ":" ~ @ints[\$_] }).join(", ") if \$verbose; my \$loop-count = 0; # [2] for ^@ints.elems -> \$start # [3] { my \$pos = \$start; # [4] my @loop = "[\$start]"; # [5] loop # [6] { \$pos = @ints[\$pos]; # [7] @loop.push: \$pos; # [8] last if \$pos == \$start; # [9] } \$loop-count++; # [10] say ":Loop { @loop.join(" ") }" if \$verbose; } say \$loop-count; # [11] ```

[1] Non-negative integers only, and they must be unique [1a]. The challenge says that we should allow integers, which include negative values, but that does not make sense as negative values are not legal indices in Raku.

[2] The number of array loops.

[3] Iterate over the indices in the input array.

[4] Set the current position.

[5] This array is used by verbose mode.

[6] An eternal loop, until the condition in [9] has been met.

[8] Add the current position to the array set up in [5].

[9] Abort the loop if we have reached the start position (again).

[10] One more array loops has been found.

[11] Print the number of array loops.

Running it:

```\$ ./array-loops-all 4 6 3 8 15 0 13 18 7 16 14 19 17 5 11 1 12 2 9 10 20 \$ ./array-loops-all 0 1 13 7 6 8 10 11 2 14 16 4 12 9 17 5 3 18 15 19 20 \$ ./array-loops-all -v 9 8 3 11 5 7 13 19 12 4 14 10 18 2 16 1 0 15 6 17 20 ```

That is not right.

Let us try verbose mode:

```\$ ./array-loops-all -v 4 6 3 8 15 0 13 18 7 16 14 19 17 5 11 1 12 2 9 10 :Index:Value: 0:4, 1:6, 2:3, 3:8, 4:15, 5:0, 6:13, 7:18, 8:7, 9:16, 10:14, 11:19, 12:17, 13:5, 14:11, 15:1, 16:12, 17:2, 18:9, 19:10 :Loop [0] 4 15 1 6 13 5 0 :Loop [1] 6 13 5 0 4 15 1 :Loop [2] 3 8 7 18 9 16 12 17 2 :Loop [3] 8 7 18 9 16 12 17 2 3 :Loop [4] 15 1 6 13 5 0 4 :Loop [5] 0 4 15 1 6 13 5 :Loop [6] 13 5 0 4 15 1 6 :Loop [7] 18 9 16 12 17 2 3 8 7 :Loop [8] 7 18 9 16 12 17 2 3 8 :Loop [9] 16 12 17 2 3 8 7 18 9 :Loop [10] 14 11 19 10 :Loop [11] 19 10 14 11 :Loop [12] 17 2 3 8 7 18 9 16 12 :Loop [13] 5 0 4 15 1 6 13 :Loop [14] 11 19 10 14 :Loop [15] 1 6 13 5 0 4 15 :Loop [16] 12 17 2 3 8 7 18 9 16 :Loop [17] 2 3 8 7 18 9 16 12 17 :Loop [18] 9 16 12 17 2 3 8 7 18 :Loop [19] 10 14 11 19 20 \$ ./array-loops-all -v 0 1 13 7 6 8 10 11 2 14 16 4 12 9 17 5 3 18 15 19 :Index:Value: 0:0, 1:1, 2:13, 3:7, 4:6, 5:8, 6:10, 7:11, 8:2, 9:14, 10:16, 11:4, 12:12, 13:9, 14:17, 15:5, 16:3, 17:18, 18:15, 19:19 :Loop [0] 0 :Loop [1] 1 :Loop [2] 13 9 14 17 18 15 5 8 2 :Loop [3] 7 11 4 6 10 16 3 :Loop [4] 6 10 16 3 7 11 4 :Loop [5] 8 2 13 9 14 17 18 15 5 :Loop [6] 10 16 3 7 11 4 6 :Loop [7] 11 4 6 10 16 3 7 :Loop [8] 2 13 9 14 17 18 15 5 8 :Loop [9] 14 17 18 15 5 8 2 13 9 :Loop [10] 16 3 7 11 4 6 10 :Loop [11] 4 6 10 16 3 7 11 :Loop [12] 12 :Loop [13] 9 14 17 18 15 5 8 2 13 :Loop [14] 17 18 15 5 8 2 13 9 14 :Loop [15] 5 8 2 13 9 14 17 18 15 :Loop [16] 3 7 11 4 6 10 16 :Loop [17] 18 15 5 8 2 13 9 14 17 :Loop [18] 15 5 8 2 13 9 14 17 18 :Loop [19] 19 20 \$ ./array-loops-all -v 9 8 3 11 5 7 13 19 12 4 14 10 18 2 16 1 0 15 6 17 :Index:Value: 0:9, 1:8, 2:3, 3:11, 4:5, 5:7, 6:13, 7:19, 8:12, 9:4, 10:14, 11:10, 12:18, 13:2, 14:16, 15:1, 16:0, 17:15, 18:6, 19:17 :Loop [0] 9 4 5 7 19 17 15 1 8 12 18 6 13 2 3 11 10 14 16 0 :Loop [1] 8 12 18 6 13 2 3 11 10 14 16 0 9 4 5 7 19 17 15 1 :Loop [2] 3 11 10 14 16 0 9 4 5 7 19 17 15 1 8 12 18 6 13 2 :Loop [3] 11 10 14 16 0 9 4 5 7 19 17 15 1 8 12 18 6 13 2 3 :Loop [4] 5 7 19 17 15 1 8 12 18 6 13 2 3 11 10 14 16 0 9 4 :Loop [5] 7 19 17 15 1 8 12 18 6 13 2 3 11 10 14 16 0 9 4 5 :Loop [6] 13 2 3 11 10 14 16 0 9 4 5 7 19 17 15 1 8 12 18 6 :Loop [7] 19 17 15 1 8 12 18 6 13 2 3 11 10 14 16 0 9 4 5 7 :Loop [8] 12 18 6 13 2 3 11 10 14 16 0 9 4 5 7 19 17 15 1 8 :Loop [9] 4 5 7 19 17 15 1 8 12 18 6 13 2 3 11 10 14 16 0 9 :Loop [10] 14 16 0 9 4 5 7 19 17 15 1 8 12 18 6 13 2 3 11 10 :Loop [11] 10 14 16 0 9 4 5 7 19 17 15 1 8 12 18 6 13 2 3 11 :Loop [12] 18 6 13 2 3 11 10 14 16 0 9 4 5 7 19 17 15 1 8 12 :Loop [13] 2 3 11 10 14 16 0 9 4 5 7 19 17 15 1 8 12 18 6 13 :Loop [14] 16 0 9 4 5 7 19 17 15 1 8 12 18 6 13 2 3 11 10 14 :Loop [15] 1 8 12 18 6 13 2 3 11 10 14 16 0 9 4 5 7 19 17 15 :Loop [16] 0 9 4 5 7 19 17 15 1 8 12 18 6 13 2 3 11 10 14 16 :Loop [17] 15 1 8 12 18 6 13 2 3 11 10 14 16 0 9 4 5 7 19 17 :Loop [18] 6 13 2 3 11 10 14 16 0 9 4 5 7 19 17 15 1 8 12 18 :Loop [19] 17 15 1 8 12 18 6 13 2 3 11 10 14 16 0 9 4 5 7 19 20 ```

We have just confirmed that every value is part of a loop. As I stated in the Implication.

The problem is that most of them are duplicate loops, and should only be counted (or presented) once. In the first example loop 0 has (indeed) a zero, as has loop 1. So loop 1 is a duplicate.

An illustration makes it easier to see that example 1 has three loops (shown with black, red, and green arrows):

The index is shown at the top (yellow background), with the value itself below it (green background).

Here are the loops, in loop order:

This is easy to fix.

File: array-loops-unique ```#! /usr/bin/env raku unit sub MAIN (*@ints where all(@ints) ~~ UInt && @ints.elems == @ints.unique.elems, :v(:\$verbose)); say ":Index:Value: ", (^@ints).map({ \$_ ~ ":" ~ @ints[\$_] }).join(", ") if \$verbose; my \$loop-count = 0; my %seen; # [1] for ^@ints.elems -> \$start { next if %seen{\$start}++; # [2] my \$pos = @ints[\$start]; my @loop = ( \$start == \$pos ) ?? () !! (\$start, \$pos); loop { \$pos = @ints[\$pos]; @loop.push: \$pos; %seen{\$pos}++; # [3] last if \$pos == \$start; } \$loop-count++; say ":Loop { @loop.join(" ") }" if \$verbose; } say \$loop-count; ```

[2] Skip the start position, if we have visited it already. Note the prefix `++` to mark it as seen, after the comparison.

[3] Mark the rest of the positions (after the very first one, done in [2]), as well.

Running it (with verbose mode):

```\$ ./array-loops-unique -v 4 6 3 8 15 0 13 18 7 16 14 19 17 5 11 1 12 2 9 10 :Index:Value: 0:4, 1:6, 2:3, 3:8, 4:15, 5:0, 6:13, 7:18, 8:7, 9:16, 10:14, 11:19, 12:17, 13:5, 14:11, 15:1, 16:12, 17:2, 18:9, 19:10 :Loop [0] 4 15 1 6 13 5 :Loop [2] 3 8 7 18 9 16 12 17 :Loop [10] 14 11 19 3 \$ ./array-loops-unique -v 0 1 13 7 6 8 10 11 2 14 16 4 12 9 17 5 3 18 15 19 :Index:Value: 0:0, 1:1, 2:13, 3:7, 4:6, 5:8, 6:10, 7:11, 8:2, 9:14, 10:16, 11:4, 12:12, 13:9, 14:17, 15:5, 16:3, 17:18, 18:15, 19:19 :Loop [0] :Loop [1] :Loop [2] 13 9 14 17 18 15 5 8 :Loop [3] 7 11 4 6 10 16 :Loop [12] :Loop [19] 6 \$ ./array-loops-unique -v 9 8 3 11 5 7 13 19 12 4 14 10 18 2 16 1 0 15 6 17 :Index:Value: 0:9, 1:8, 2:3, 3:11, 4:5, 5:7, 6:13, 7:19, 8:12, 9:4, 10:14, 11:10, 12:18, 13:2, 14:16, 15:1, 16:0, 17:15, 18:6, 19:17 :Loop [0] 9 4 5 7 19 17 15 1 8 12 18 6 13 2 3 11 10 14 16 1 ```

Lookin good.

But what about the assumption about only using the indices themselves as values? The program does not enforce it:

```\$ ./array-loops-unique 99 1 13 7 6 8 10 11 2 14 16 4 12 9 17 5 3 18 15 19 Use of uninitialized value \$pos of type Any in string context. Methods .^name, .raku, .gist, or .say can be used to stringify it to something meaningful. in block at ./array-loops-unique line 20 Use of uninitialized value \$pos of type Any in string context. Methods .^name, .raku, .gist, or .say can be used to stringify it to something meaningful. in block at ./array-loops-unique line 20 Use of uninitialized value of type Any in numeric context in block at ./array-loops-unique line 21 6 ```

We could enforce the rule, but allowing (and detecting) non-index values is probably better, as the challenge does not mention this rule at all.

Let us do both; the default is allowing non-index values, and we can enforce index values only with the «-i» command line option.

File: array-loops ```#! /usr/bin/env raku unit sub MAIN (*@ints where all(@ints) ~~ Int # [1] && @ints.elems == @ints.unique.elems, # [1a] :i(:\$index), # [2] :v(:\$verbose)); die "Use the index values (0..{@ints.end}) only" if \$index && @ints.min != 0 && @ints.max != @ints.end; # [2a] say ":Index:Value: ", (^@ints).map({ \$_ ~ ":" ~ @ints[\$_] }).join(", ") if \$verbose; my \$loop-count = 0; my %seen; FORLOOP: # [4a] for ^@ints.elems -> \$start { next if %seen{\$start}++; my \$pos = \$start; my @loop = "[\$start]"; loop { unless 0 <= \$pos <= @ints.end # [3] { say ":Non-Loop: { @loop.join(" ") }" if \$verbose; next FORLOOP; # [4] } \$pos = @ints[\$pos]; @loop.push: \$pos; %seen{\$pos}++; last if \$pos == \$start; } \$loop-count++; say ":Loop { @loop.join(" ") }" if \$verbose; } say \$loop-count; ```

[1] Using `Int` instead of `UInt` allows negative integers as well.

[2] Use this command line option to ensure that we have specified the array indices only. We know that the values are unique (courtesy of [1a]), so checking the lowest (`.min`) and highest (`.max`) value will suffice.

[3] Do we have a valid position (index)? Note that we will always have a valid position if the «-i» command line option is used, so in that case this will never be triggered.

[4] If not skip the rest of the current iteration on the `for` loop with `next` and a label to indicate the loop (as the default is the nearest, in this case the `loop` one). Using `last` without a label would not work, as the 4 lines of code after the `unless` block would have been executed. (We could have fixed that by placing those 4 lines of code in an `if` clause; `if \$pos == \$start`, but this is more elegangt.)

Running it:

```\$ ./array-loops -i 99 1 13 7 6 8 10 11 2 14 16 4 12 9 17 5 3 18 15 19 Use the index values (0..19) only in sub MAIN at ./array-loops line 5 in block <unit> at ./array-loops line 1 \$ ./array-loops -v 99 1 13 7 6 8 10 11 2 14 16 4 12 9 17 5 3 18 15 19 :Index:Value: 0:99, 1:1, 2:13, 3:7, 4:6, 5:8, 6:10, 7:11, 8:2, 9:14, 10:16, 11:4, 12:12, 13:9, 14:17, 15:5, 16:3, 17:18, 18:15, 19:19 :Non-Loop: [0] 99 :Loop [1] 1 :Loop [2] 13 9 14 17 18 15 5 8 2 :Loop [3] 7 11 4 6 10 16 3 :Loop [12] 12 :Loop [19] 19 5 \$ ./array-loops -v 7 4 1 -741 :Index:Value: 0:7, 1:4, 2:1, 3:-741 :Non-Loop: [0] 7 :Non-Loop: [1] 4 :Non-Loop: [2] 1 4 :Non-Loop: [3] -741 0 ```

And that's it.