It’s time for the Perl Weekly Challenge 236!
Task 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
Ok, how to attack this problem. I’m sure there’s a clever way to figure out whether or not the given assortment of bills can produce exact change, but as always, I’m going for straightforward and easy to understand over clever. A clever solution would be worth it if we needed performance.
So, the straightforward way is to keep a count of bills we take in and then return whether we can produce exact change. If at any point we don’t have the exact change on hand for a transaction, we can bail out of the function early and return false. If we get through all the transactions and are able to produce exact change for all of them, we return true. I’m going to use a hash because we’re tracking three bill amounts separated by a bit of space, and keeping those in a numerically indexed array would yield a bunch of empty elements I’d need to deal with.
sub isExactChangePossible {
my @bills = @_;
my %till; # we keep the bills in a "till"
BILLS: foreach my $collected ( @bills ) {
# put the bill we collected in the "till"
$till{$collected}++;
# calculate the required change
my $change_required = $collected - 5;
# if we don't need to make change,
# skip to the next bill collected!
next BILLS unless $change_required;
# loop through the bills we have on hand
# in descending size (try to make change
# with the largest bills possible)
foreach my $bill ( reverse sort { $a <=> $b } keys %till ) {
# as long as we have more of this bill and
# using it would not yield TOO MUCH change
while ($till{$bill} > 0 && $change_required - $bill >= 0) {
# deduct the amount from the required change
$change_required -= $bill;
# remove the bill from the till
$till{$bill}--;
}
# move on if we managed to make exact change!
next BILLS unless $change_required;
}
# if we weren't able to make change, fail
return 0 if $change_required;
}
# we successfully made change for all transactions!
return 1;
}
I’m just going to link to the full Perl script in GitHub.
The Raku version is almost identical:
sub isExactChangePossible(*@bills where ($_.all ~~ Int)) {
my %till; # we keep the bills in a "till"
BILLS: for @bills -> $collected {
# put the bill we collected in the "till"
%till{$collected}++;
# calculate the required change
my $change_required = $collected - 5;
# if we don't need to make change,
# skip to the next bill collected!
next BILLS unless $change_required;
# loop through the bills we have on hand
for %till.keys().sort({ .Int }).reverse() -> $bill {
# as long as we have more of this bill and
# using it would not yield TOO MUCH change
while (%till{$bill} > 0 && $change_required - $bill >= 0) {
# deduct the amount from the required change
$change_required -= $bill;
# remove the bill from the till
%till{$bill}--;
}
# move on if we managed to make exact change!
next BILLS unless $change_required;
}
# if we weren't able to make change, fail
return 0 if $change_required;
}
# we successfully made change for all transactions!
return 1;
}
The one thing to note is that we can just say that the items being sorted are .Int and Raku will handle the comparison. Here’s the full Raku script in GitHub.
For Python, I had to tweak my logic a little to get around not being able to continue to the next iteration of the outer for bills loop from within the inner for till loop.
def isExactChangePossible(bills):
till = {}; # we keep the bills in a "till"
for collected in bills:
# put the bill we collected in the "till"
#
# using .get(collected, 0) yields the value in the
# dict for the key 'collected' if it exists, or the
# specified default (in this case, 0) if it doesn't
till[collected] = till.get(collected, 0) + 1
# calculate the required change
change_required = collected - 5
# loop through the bills we have on hand
for bill in sorted(till, reverse=True):
# as long as we have more of this bill and
# using it would not yield TOO MUCH change
while till[bill] > 0 and change_required - bill >= 0:
# deduct the amount from the required change
change_required -= bill
# remove the bill from the till
till[bill] -= 1
# if we weren't able to make change, fail
if change_required:
return 0
# we successfully made change for all transactions!
return 1
Here’s the full Python script in GitHub.
And now to the Java version. It’s slightly more annoying because Java Maps aren’t native to the language, but the approach works well:
public static boolean isExactChangePossible(int[] bills) {
// we keep the bills in a "till"
HashMap<Integer, Integer> till =
new HashMap<Integer, Integer>();
for (int collected : bills) {
// put the bill we collected in the "till"
//
// using .getOrDefault(collected, 0) yields the value
// in the map for the key 'collected' if it exists, or
// the specified default (in this case, 0) if it doesn't
till.put(
collected,
till.getOrDefault(collected, 0) + 1
);
// calculate the required change
int change_required = collected - 5;
// loop through the bills we have on hand, making sure
// we go from largest to smallest bill
List<Integer> keys = new ArrayList<>(till.keySet());
Collections.sort(keys, Collections.reverseOrder());
for (Integer bill : keys) {
// as long as we have more of this bill and
// using it would not yield TOO MUCH change
while (till.get(bill) > 0 &&
change_required - bill >= 0) {
// deduct the amount from the required change
change_required -= bill;
// remove the bill from the till
till.put(bill, till.get(bill) - 1);
}
}
// if we weren't able to make change, fail
if (change_required > 0) {
return false;
}
}
return true;
}
Here’s the full Java script in GitHub.
Task 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]
So to attack this we want to loop over each item in @ints and see if a loop starts at that element. Things I thought about:
- I was worried about loops that don’t go back to the start, but one of the assumptions is that the list is unique integers, so we’re never going to have to worry about that.
- Double counting loops: if we start at an element that’s in a loop we’ve already counted, we shouldn’t count it again.
- When I wanted to pass multiple types of arguments to
loopExistsAt(), I decided it would be a good opportunity to use the idea of having named parameters for a Per sub by passing it a hash.
sub loopExistsAt {
my %params = @_;
my $ints = $params{ints};
my $start = $params{start};
my $seen = $params{seen};
# bail early if we're in a loop we've seen before
return if exists $seen->{$start};
my @loop;
my $i = $start;
for (;;) {
# keep track of the values in the order we visit them
push @loop, $ints->[$i];
# track where we've already been
# to avoid double-counting loops
$seen->{$i} = 1;
# get the next index
$i = $ints->[$i];
# make sure the index is in bounds
last unless $i >= 0 && $i <= $#{$ints};
# make sure we haven't seen the index before
last if exists $seen->{$i};
}
# if the last element points back to
# the start, it's a loop!
if ($loop[-1] == $start) {
return @loop;
}
# otherwise, return an empty list
return;
}
sub identifyLoops {
my @ints = @_;
my @loops;
my %seen; # keep track of indices we've seen
# to avoid duplicating loops
foreach my $start ( 0 .. $#ints ) {
my @loop = loopExistsAt(
start => $start,
ints => \@ints,
seen => \%seen
);
if (@loop) {
push @loops, \@loop;
}
}
return @loops;
}
Here’s the full Perl script in GitHub.
The Raku version wound up catching on bits of my Raku-newbie knowledge:
- When I attempted to return nothing with just
return;, what I wound up returning was anAnyobject. If I want to return an empty list, I need toreturn []; - I had to look up how to do named parameters in Raku.
sub loopExistsAt(:@ints, :$start, :%seen) {
# bail early if we're in a loop we've seen before
return [] if %seen{$start}:exists;
my @loop;
my $i = $start;
loop (;;) {
# keep track of the values in the order we visit them
push @loop, @ints[$i];
# track where we've already been
# to avoid double-counting loops
%seen{$i} = 1;
# get the next index
$i = @ints[$i];
# make sure the index is in bounds
last unless $i >= 0 && $i < @ints.elems;
# make sure we haven't seen the index before
last if %seen{$i}:exists;
}
# if the last element points back to
# the start, it's a loop!
if (@loop[*-1] == $start) {
return @loop;
}
# otherwise, return an empty list
return [];
}
sub identifyLoops {
my @ints = @_;
my @loops;
my %seen; # keep track of indices we've seen
# to avoid duplicating loops
for 0 .. $@ints.elems - 1 -> $start {
my @loop = loopExistsAt(
start => $start,
ints => @ints,
seen => %seen
);
if (@loop) {
push @loops, @loop;
}
}
return @loops;
}
Here’s the full Raku script in GitHub.
Python:
def loopExistsAt(ints=[], seen={}, start=0):
# bail early if we're in a loop we've seen before
if start in seen:
return []
loop = [] # initialize an empty list to start
i = start # initialize i to starting point
while True:
# keep track of the values in the order we visit them
loop.append(ints[i])
# track where we've already been
# to avoid double-counting loops
seen[i] = 1
# get the next index
i = ints[i]
# make sure the index is in bounds
if i < 0 or i >= len(ints):
break
# make sure we haven't seen the index before
if i in seen:
break
# if the last element points back to
# the start, it's a loop!
if loop[-1] == start:
return loop
# otherwise, return an empty list
return []
def identifyLoops(ints):
loops = []
seen = {}; # keep track of indices we've seen
# to avoid duplicating loops
for start in range(0, len(ints)):
loop = loopExistsAt(
start = start,
ints = ints,
seen = seen
)
if loop:
loops.append(loop)
return loops
Here’s the full Python script in GitHub.
Java:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.stream.Collectors;
public class Ch2 {
public static ArrayList<Integer> loopExistsAt(
int start, int[] ints, HashMap<Integer, Integer> seen
) {
// bail early if we're in a loop we've seen before
if (seen.get(start) != null) {
// return an empty ArrayList
return new ArrayList<Integer>();
}
// initialize an empty list to start
ArrayList<Integer> loop = new ArrayList<Integer>();
// initialize i to starting point
int i = start;
while (true) {
// keep track of the values in the order we visit them
loop.add(ints[i]);
// track where we've already been
// to avoid double-counting loops
seen.put(i, 1);
// get the next index
i = ints[i];
// make sure the index is in bounds
if (i < 0 || i >= ints.length) {
break;
}
// make sure we haven't seen the index before
if (seen.get(i) != null) {
break;
}
}
// if the last element points back to
// the start, it's a loop!
if (loop.get(loop.size() - 1) == start) {
return loop;
}
// otherwise, return an empty ArrayList
return new ArrayList<Integer>();
}
public static ArrayList<ArrayList<Integer>> identifyLoops(int[] ints) {
ArrayList<ArrayList<Integer>> loops =
new ArrayList<ArrayList<Integer>>();
HashMap<Integer, Integer> seen =
new HashMap<Integer, Integer>();
for (int i = 0; i < ints.length; i++) {
ArrayList<Integer> loop = loopExistsAt(i, ints, seen);
if (loop.size() > 0) {
loops.add(loop);
}
}
return loops;
}
public static String comma_joined(int[] ints) {
// we're using it more than once, make it a method
return Arrays.stream(ints)
.mapToObj(String::valueOf)
.collect(Collectors.joining(","));
}
public static void solution(int[] ints) {
System.out.println("Input: @ints = (" + comma_joined(ints) +
")");
ArrayList<ArrayList<Integer>> loops = identifyLoops(ints);
int count = loops.size();
System.out.println(String.format("Output: %1$d", count));
if (count > 0) {
String loop_noun = (count == 1) ? "Loop" : "Loops";
String are_verb = (count == 1) ? "is" : "are";
System.out.println("\n" + loop_noun + " " + are_verb +
" as below:");
for (ArrayList<Integer> loop : loops) {
String as_list = loop.stream()
.map(String::valueOf)
.collect(Collectors.joining(" "));
System.out.println("[" + as_list + "]");
}
}
}
public static void main(String[] args) {
System.out.println("Example 1:");
solution(new int[] {4,6,3,8,15,0,13,18,7,16,14,
19,17,5,11,1,12,2,9,10});
System.out.println("\nExample 2:");
solution(new int[] {0,1,13,7,6,8,10,11,2,14,16,
4,12,9,17,5,3,18,15,19});
System.out.println("\nExample 3:");
solution(new int[] {9,8,3,11,5,7,13,19,12,4,14,
10,18,2,16,1,0,15,6,17});
}
}
Here’s my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-236/packy-anderson