PWC 236 Task 1 A Change Would Do You Good

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

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:

- 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:

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.

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:

say "(", join(", ", @register), ")";

But it could be done with less clutter:

$" = ', ';
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.