Juicy loops

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

Challenge, My solutions

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