PWC 236 Task 1 A Change Would Do You Good
Tags: perl, perlweeklychallenge, pwc
Published: 2023-09-27 13:10:03

Task 1 of Perl Weekly Challenge 236 asks us to run a juice business in a highly ethical way: either customers get their juice, or we close the shop in humiliation, unable to give them correct change. 

## [Task 1 Exact Change](https://theweeklychallenge.org/challenges/236/#TASK1)
```text
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`

### Ruminations
The direct path is going to be to simulate the customer interactions, tracking the number of 5 and 10 bills on hand.  Is there anything better or more Perl-ish?  Not clear.

There might be some sort of state-machine here: after each transaction, we're in a state where we could make change for a 10, or a state where we could make change for a 20, or both, or neither.  But it's still going to be necessary to keep track of the number of 5 and 10 bills, so it's not clear that a state model would do anything other than complicate.

Maybe there's a purely math solution? Some kind of list reduction? To give change, we have to have an amount on hand that's a multiple of 5 or a multiple of 15.  But again, we have to know how many bills of each kind (30 on hand is a multiple of 15, but if its three 10s, that's useless for giving change).  We might as well just simulate the transactions.

So let's write a little simulation of juice-buying transactions.

We could model the transactions literally with stacks of 5 and 10 bills, '@five' and '@ten'.  We don't have to keep track of 20s because they don't factor into making change.  Each transaction would be a set of `pop` and `push` operations:
```perl
- input 5 --> push @five, 5
- input 10 --> pop @five; push @ten, 10
- input 20 --> ( pop 10; pop 5 ) || (pop5 for 1, 2, 3)
```
The code's not quite that clean, however.  We have to test the stacks before we try to `pop`, or test the result of every `pop`.  Especially in the case of trying to give change for a 20, we don't want the side effect of popping a 10, only to fail and have to restore it if we can pop three 5s.

Enough rumination.  Here's code that models a cash register with slots for 5s and 10s, and takes transactions until we run out of exact change:

```perl
sub exactChange(@bills)
{
    use constant { FIVE => 0, TEN => 1, TWENTY => 2 };
    my @register = ( 0, 0, 0 );

    my $changeGiven = true;
    while ( (my $payment = shift @bills) && $changeGiven )
    {
        if ( $payment == 5 )
        {
            say "Got a 5, register=(@register)" if $Verbose;
            $register[FIVE]++;
        }
        elsif ( $payment == 10 )
        {
            say "Got a 10, register=(@register)" if $Verbose;
            if ( $register[FIVE] )
            {
                say "   Gave change 5" if $Verbose;
                $register[FIVE]--;
            }
            else
            {
                say "   NO 5, FAIL" if $Verbose;
                $changeGiven = false;
            }
            $register[TEN]++;
        }
        elsif ( $payment == 20 )
        {
            say "Got a 20, register=(@register)" if $Verbose;
            if ( $register[TEN] && $register[FIVE] )
            {
                say "   Gave a 5 and a 10" if $Verbose;
                $register[TEN]--;
                $register[FIVE]--;
            }
            elsif ( $register[FIVE] >= 3 )
            {
                say "   Gave three 5s" if $Verbose;
                $register[FIVE] -= 3;
            }
            else
            {
                say "   No 15, FAIL" if $Verbose;
                $changeGiven = false
            }
            $register[TWENTY]++;
        }
        else
        {
            say "Got a fake bill" if $Verbose;
        }
    }
    say "DONE: register:(@register) customer=(@bills) change=$changeGiven" if $Verbose;
    return @bills == 0 && $changeGiven;
}
```
### Perl Notes
[Notes. Get it? Notes? See what I did there?]

I chose to make my model of a cash register be an array, indexed by constant values. Another choice would have been to make it a hash, so that I could use `5`, `10`, and `20` as keys. Having implemented hashes on a couple of occasions, I'm probably too sensitive to how hash functions and collisions can be unexpectedly expensive, so I generally tend to try arrays before hashes.  It obviously wouldn't be an issue here.

Perl now has `true` and `false` literals (albeit experimental).  I still take advantage of implicit truth-iness and false-iness -- for example `if ( $register[FIVE] )` -- but it's nice to be able to have an explicit boolean variable.
```perl
use builtin qw/true false/; no warnings "experimental::builtin";
```
Perl can interpolate an array into a string, which I do here in verbose tracing statements. The default for interpolation is to separate elements with a space, but the separator can be changed with the `$"` variable. To show a comma-separated list, I might first reach for `join`:
```perl
say "(", join(", ", @register), ")";
```
But it could be done with less clutter:
```perl
$" = ', ';
say "(@register)";
```
Overall, this solution doesn't do much to show off Perl.  It's a loop, an array, and some if/then/else statements, which could be translated into any procedural language.