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.
Top comments (0)