The weekly challenge 236 - Task 1: Exact Change

 1 #!/usr/bin/perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-236/#TASK1
 3 #
 4 # Task 1: Exact Change
 5 # ====================
 6 #
 7 #
 8 #
 9 # You are asked to sell juice each costs $5. You are given an array of bills.
10 # You can only sell ONE juice to each customer but make sure you return exact
11 # change back. You only have $5, $10 and $20 notes. You do not have any change
12 # in hand at first.
13 #
14 # Write a script to find out if it is possible to sell to each customers with
15 # correct change.
16 #
17 ## Example 1
18 ##
19 ## Input: @bills = (5, 5, 5, 10, 20)
20 ## Output: true
21 ##
22 ## From the first 3 customers, we collect three $5 bills in order.
23 ## From the fourth customer, we collect a $10 bill and give back a $5.
24 ## From the fifth customer, we give a $10 bill and a $5 bill.
25 ## Since all customers got correct change, we output true.
26 #
27 ## Example 2
28 ##
29 ## Input: @bills = (5, 5, 10, 10, 20)
30 ## Output: false
31 ##
32 ## From the first two customers in order, we collect two $5 bills.
33 ## For the next two customers in order, we collect a $10 bill and give back a $5 bill.
34 ## For the last customer, we can not give the change of $15 back because we only have two $10 bills.
35 ## Since not every customer received the correct change, the answer is false.
36 #
37 ## Example 3
38 ##
39 ## Input: @bills = (5, 5, 5, 20)
40 ## Output: true
41 #
42 ############################################################
43 ##
44 ## discussion
45 ##
46 ############################################################
47 #
48 # Each bill we get goes into our change hash. If we receive
49 # a bill > 5, we calculate the return value, then we try to
50 # pay it starting with a 10 bill if available. If in the end we
51 # still have something left to return, but no more fitting bills,
52 # we return false. Otherwise, we return true.
53 #
54 use strict;
55 use warnings;
56 use Data::Dumper;
57 
58 exact_change(5, 5, 5, 10, 20);
59 exact_change(5, 5, 10, 10, 20);
60 exact_change(5, 5, 5, 20);
61 
62 sub exact_change {
63    my @bills = @_;
64    my $change = {};
65    print "Input: (" . join(", ", @bills) . ")\n";
66    foreach my $bill (@bills) {
67       $change->{$bill}++;
68       my $to_return = $bill - 5;
69       foreach my $return_bill (10, 5) {
70          while ($to_return >= $return_bill && $change->{$return_bill} ) {
71             $to_return -= $return_bill;
72             $change->{$return_bill}--;
73          }
74       }
75       if($to_return > 0) {
76          print "Output: false\n";
77          return;
78       }
79    }
80    print "Output: true\n";
81 }