Perl Weekly Challenge 49: Survivors and Palindrome Dates

One way to let me improve my knowledge about Raku (aka Perl 6) is to implement programs in it. Unluckily, I don’t have any production code to implement in Raku yet (sob!). So, why not try solving the Perl Weekly Challenge tasks?

In the following, the assigned tasks for Challenge 49.

• Task 1
• Task 2

PWC 49 - Task 1

The first task required to find out the smallest multiple of a given number, with the restriction that the multiple number must be made only by 1s and 0s. My personal solution, even if not very elegant, involved a simple for loop and a regular expression matching:

sub MAIN( Int :$number! where { $number > 0 } ) {
    "Minor multiple of $number made up by 0 and 1 only is { $number * $_ }".say && exit if ( $number * $_ ) ~~ / ^ <[01]>+ $ /
    for 2 .. Inf;
}

It reads as follows:

• for every number from 2 (thus excluding the number itself) to infinity;
• the multiple is $number * $_;
• if that result matches against a regular expression that imposes only 1 and 0 from begin to end I print the result and issue an exit that terminates the program (and the loop).

PWC 49 - Task 2

This was a little more long to implement: an Least Recently Used cache.
I decided to implement it via a specific class, named (you guess!) LRU:

class LRU {
    # contains a list of Pairs (not an hash!)
    # where every pair has the value of times it has been used
    # and every key is the number
    has Pair @!values;
    has Int $.capacity;


    method get( Int $what ) {
        # find the first $what value and see where it is within the
        # array
        my ( Int $where, Pair $pair ) = @!values.first: { .key == $what }, :kv;

        # not found
        return -1 if ! $pair;

        # now remove the element from the array and
        # insert it on the right incremented
        @!values.splice( $where, 1 );
        @!values.append: $pair.key => $pair.value + 1;

        # here $pair still holds the old value
        return $pair.value;
    }

    # Is the cache full?
    method !is-full() { return @!values.elems >= $!capacity; }

    # remove the least recently used value, always the one on the left
    method !make-space() { @!values.splice( 0, 1 ); }

    method set( Int $value, Int $how-many-times ) {
        # make some space if the cache is full
        self!make-space() if self!is-full;
        @!values.push: $value => $how-many-times;
    }


    method Str() {
        my $string = "\n[Capacity: {$!capacity}]\n[Least Recently Used] -->>>";
        $string = "%s\t%d (used %d times)".sprintf( $string, $_.key, $_.value)  for @!values;
        $string ~= " <<<-- [Most Recently Used]\n";
        return $string;
    }
}

The class has an array named @!values that contains a list of Pairs, each one with the number to store in the cache as the key and the number of times it has been accessed as the value.
When we require a new number, method get(), the array searches for such an existant Pair in it (or better, it searches for the first one Pair). If nothing has been found, the special value -1 is returned, otherwise there is some work to do. The Pair is removed from the array, and a new Pair with the same key is inserted at the end of the array (the end meaning the most recently used value). Then, the old pair value is returned.
The set() method is somehow simpler: it pushes a new Pair object to the end of the array. However, in the case the array is full, the make-space() method removes the very first element of the array (meaning the least recently used one).
The rest of the code is boilerplate.
Therefore, my LRU cache uses an array where the first element is the least recently used, and the last element is the most recently used.

Update 2020-02-24

Of course, there is no need to use splice() and friends, but since I was running out of caffeine, I made my life too much complex. As shown in this commit, it is possible to simply delete the element from the array and append it to a fresh all-defined entries list. Similarly, the methods is-full() and make-sapce() can be removed to avoid code verbosity; I placed them there in a first implementation where I was prototyping the LRU object as an hash container.