Weekly Challenge 236
Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.
This weeks pull request and blog post comes after the deadline. It's a long weekend here, so a virtual Sunday for me :)
Task 1: Exact Change
Task
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.
My solution
For this task, I have a dict (hash in Perl) called wallet
. This will record the change I have. The key is the note denomination and the value is how many notes I have.
I have a loop for each customer, and add the note they gave me to my wallet. If they gave $5, I don't need to give any change so I move on to the next customer.
for customer_note in notes:
wallet[customer_note] = wallet.get(customer_note, 0) + 1
if customer_note == 5:
continue
If change is required, I have a loop that iterates over the notes in my wallet, largest denomination first. The number of notes I use is the lesser of the notes I have or the notes that can be used. I remove the note from my wallet
and reduce the change
amount as well. Once the change is $0, I move on to the next customer. If I've looped over all the notes in my wallet without giving all the change, I print false
and exit.
for wallet_note in sorted(wallet, reverse=True):
note_count = min(wallet[wallet_note], change // wallet_note)
if note_count > 0:
wallet[wallet_note] -= note_count
change -= wallet_note * note_count
if change == 0:
break
else:
print('false')
return
Examples
$ ./ch-1.py 5 5 5 10 20
true
$ ./ch-1.py 5 5 10 10 20
false
$ ./ch-1.py 5 5 5 20
true
Task 2: Array Loops
Task
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.
My solution
I initially over-engineered my solution. I thought the task to to print out the loops, rather than the number of loops. Today's lesson is to always read all the details first :)
Like the other task, this also uses a double loop. The outer loop iterates from 0
to one less than the length of the array. This is called first
, and represents the first position in a loop.
My inner loop will see if there is a loop. It will exit if the next position (the integer at the first
position) has been seen before (was was as part of a previous loop, denoted by setting the value to None) or is out of bounds. If it sees a next value as part of the current loop, I increment the loop variable and exit the inner loop.
loop = []
pos = first
while pos >= 0 and pos < len(ints) and ints[pos] is not None:
loop.append(pos)
# What is the next number
next_pos = ints[pos]
# Mark this position as used
ints[pos] = None
if next_pos in loop:
# We have a loop
loops += 1
break
# Continue with the next position
pos = next_pos
Examples
$ ./ch-2.py 4 6 3 8 15 0 13 18 7 16 14 19 17 5 11 1 12 2 9 10
3
$ ./ch-2.py 0 1 13 7 6 8 10 11 2 14 16 4 12 9 17 5 3 18 15 19
6
$ ./ch-2.py 9 8 3 11 5 7 13 19 12 4 14 10 18 2 16 1 0 15 6 17
1
Top comments (0)