Changing Loops with Raku
[256] Published 1. October 2023.This is my response to The Weekly Challenge #236.
Challenge #236.1: Exact Change
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.
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.
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.
#! /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).
[2] We start with an empty cash register.
[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
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]
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]
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.
[7] Advance the current position.
[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;
[1] Positions already visited.
[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.