THE WEEKLY CHALLENGE - 236

https://theweeklychallenge.org/blog/perl-weekly-challenge-236/

Table of Contents

Task 1 - Exact Change

Introduction

In this blog post, we will explore solutions to two interesting coding problems: "Exact Change" and "Unequal Triplets". We'll break down the problems, discuss algorithms, and present solutions in Perl, Python, and Raku.

Problem 1: Exact Change

Problem Statement

You are selling juice for $5 and have an array of bills from customers. You can only give change in $5, $10, and $20 notes, and you don't have any change initially. Determine if you can give exact change to every customer.

Algorithm

  1. Initialize counters for $5 and $10 bills as 0.
  2. Loop through the array of customer bills.
  3. If the bill is $5, increase the $5 counter.
  4. If the bill is $10, check if you have a $5 bill for change. If yes, reduce the $5 counter and increase the $10 counter.
  5. If the bill is $20, check for change options: either one $10 and one $5, or three $5s.

Perl Code Snippet

for my $bill (@bills) {
    if ($bill == 5) {
        $five++;
    } elsif ($bill == 10) {
        return 0 if $five == 0;
        $five--;
    } else {
        # Handle $20 bill
    }
}

Raku Code Snippet

for @bills -> $bill {
    if $bill == 5 {
        $five++;
    } elsif $bill == 10 {
        return False if $five == 0;
        $five--;
    } else {
        # Handle $20 bill
    }
}

Python Code Snippet

def can_sell_with_exact_change(bills: list) -> bool:
    five, ten = 0, 0
    for bill in bills:
        if bill == 5:
            five += 1
        elif bill == 10:
            if five == 0:
                return False
            five -= 1
            ten += 1
        else:  # bill is 20
            if ten > 0 and five > 0:
                ten -= 1
                five -= 1
            elif five >= 3:
                five -= 3
            else:
                return False
    return True

Task 2 - Array Loops

Introduction

The "Array Loops" problem, submitted by Mark Anderson for the Perl Weekly Challenge, is an interesting one that tests our understanding of arrays and loops. The problem asks us to determine the number of loops that exist within a given array of unique integers. This may sound straightforward, but it involves a good deal of logic and algorithmic thinking.

Problem Statement

Given an array of unique integers, write a script to determine how many loops exist within the array. A loop starts at any index and follows the chain of integers until it returns back to the starting index.

For example, consider the array ([4, 6, 3, 8, 15, 0, 13, 18, 7, 16, 14, 19, 17, 5, 11, 1, 12, 2, 9, 10]). The loops in this array are:

  • (4 -> 15-> 1 -> 6 -> 13 -> 5 -> 0 -> 4)
  • (3 -> 8 -> 7 -> 18 -> 9 -> 16 -> 12 -> 17 -> 2 -> 3)
  • (14 -> 11 -> 19 -> 10 -> 14)

The output for this array should be (3).

Algorithm Explanation

To solve this problem, we can use the following algorithm:

  1. Initialize a set or hash to keep track of visited indices.
  2. Initialize a counter to keep track of the number of loops.
  3. For each unvisited index in the array:
    1. Mark the index as visited.
    2. Follow the chain of integers, marking each subsequent index as visited, until you reach an index that has already been visited.
    3. Increment the loop counter.
  4. Return the loop counter.

Let's implement this algorithm in Perl, Python, and Raku.

Perl Solution

Here's how we could implement the algorithm in Perl:

use strict;
use warnings;

sub find_loops {
    my @arr = @_;
    my %visited;
    my $loops = 0;

    for my $i (0..$#arr) {
        next if $visited{$i};
        my $j = $i;

        while (!exists $visited{$j}) {
            $visited{$j} = 1;
            $j = $arr[$j];
        }

        $loops++;
    }

    return $loops;
}

print find_loops(4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10);  # Output: 3

Python Solution

The Python solution uses a set data structure to keep track of visited indices:

def find_loops(arr: list) -> int:
    visited = set()
    loops = 0

    for i in range(len(arr)):
        if i in visited:
            continue
        j = i

        while j not in visited:
            visited.add(j)
            j = arr[j]

        loops += 1

    return loops

print(find_loops([4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10]))  # Output: 3

Raku Solution

In Raku, the algorithm stays largely the same:

sub find-loops(@arr) {
    my %visited;
    my $loops = 0;

    for 0..^@arr.elems -> $i {
        next if %visited{$i}:exists;
        my $j = $i;

        while !%visited{$j}:exists {
            %visited{$j} = 1;
            $j = @arr[$j];
        }

        $loops++;
    }

    return $loops;
}

say find-loops(4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10);  # Output: 3

Conclusion

The "Array Loops" problem is a good exercise in understanding how to traverse arrays while keeping track of visited elements. The algorithm is straightforward but requires careful implementation to ensure that all loops are counted correctly. With solutions available in Perl, Python, and Raku, we can appreciate the nuances of each language while solving the same algorithmic challenge.