Perl Weekly Challenge: Week 49

Challenge 1:

Smallest Multiple

Write a script to accept a positive number as command line argument and print the smallest multiple of the given number consists of digits 0 and 1.

For example:

For given number 55, the smallest multiple is 110 consisting of digits 0 and 1.

It seemed to me this could be solved by brute force, i.e. just going through all the multiples of the input number and checking to see if they are made up of 1's and 0's. This is my perl version:

my $num = shift;
my $multiple = $num;

while ($multiple !~ / \A [01]+ \z /gmx) {
    $multiple += $num;
}

say $num, ' x ', $multiple / $num, ' = ', $multiple;

(Full code on Github.)

I tested it with all the numbers from 1 to 100 and it worked pretty well except for multiples of 9 which gave extremely long output.

For Raku, I chose to use a lazy list of multiples.

multi sub MAIN(Int $num) {
    my $multiple =
        ($num, $num + $num ... ∞).grep({ $_.Str ~~ / ^ <[01]>+ $ /; })[0];
    say $num, ' x ', $multiple / $num, ' = ', $multiple;
}

(Full code on Github.)

And again, for the most part it worked pretty well—except for multiples of 9 that is. From my Perl attempt, I was expecting their calculation to be slow but Raku was really slow. I mean many minutes slow. (For 63, for instance, I gave up waiting after a whole hour.) I thought maybe it might be something to do with possible inefficiency in lazy lists so I rewrote the script in the style of the Perl version but no dice. So I don't know what's going on there.

Challenge 2:

LRU Cache

Write a script to demonstrate LRU Cache feature. It should support operations get and set. Accept the capacity of the LRU Cache as command line argument.

Definition of LRU: An access to an item is defined as a get or a set operation of the item. “Least recently used” item is the one with the oldest access time.

For example:

  capacity = 3
  set(1, 3)
  set(2, 5)
  set(3, 7)

  Cache at this point:
  [Least recently used] 1,2,3 [most recently used]

  get(2)      # returns 5

  Cache looks like now:
  [Least recently used] 1,3,2 [most recently used]

  get(1)      # returns 3

  Cache looks like now:
  [Least recently used] 3,2,1 [most recently used]

  get(4)      # returns -1

  Cache unchanged:
  [Least recently used] 3,2,1 [most recently used]

  set(4, 9)

  Cache is full, so pushes out key = 3:
  [Least recently used] 2,1,4 [most recently used]

  get(3)      # returns -1

I found this amazing post talking about LRU Cache.

package Data::LRUCache;
use Moo;
use namespace::clean;

has _cache => (
    is => 'rw',
    default => sub { [] }
);

has _index => (
    is => 'rw',
    default => sub { {} }
);

has _capacity => (
    is => 'ro',
);

sub BUILDARGS {
    my ($orig, $class, @args) = @_;

    return { _capacity => $args[0] };
};

sub get {
    my ($self, $key) = @_;

    if (!grep { $_ == $key } @{ $self->{_cache} }) {
        return -1;
    }
    @{ $self->{_cache} } = grep { $_ != $key } @{ $self->{_cache} };
    unshift @{ $self->{_cache}}, $key;
    return $self->{_index}->{$key};
}

sub set {
    my ($self, $key, $value) = @_;

    if (scalar @{ $self->{_cache} } == $self->{_capacity}) {
        my $last = pop @{ $self->{_cache} };
        delete $self->{_index}->{$last};
    }
    unshift @{ $self->{_cache} }, $key;
    $self->{_index}->{$key} = $value;
}

sub print() {
    my ($self) = @_;

    for my $e (@{ $self->{_cache} }) {
        print "$e => ", $self->{_index}->{$e}, "\n";
    }
}

1;

(Full code on Github.)

class Data::LRUCache {

    has Int @!cache = ();
    has %!index = ();
    has Int $!capacity is required;

    submethod BUILD( :$capacity ) {
        $!capacity = $capacity;
    }

    method get(Int $key where { $_ > 0 }) {
        if ($key != any @!cache) {
            return -1;
        }
        @!cache = @!cache.grep({ $_ != $key });
        @!cache.unshift($key);
        return %!index{$key}
    }

    method set(Int $key, Any $value) {
        if @!cache.elems ~~ $!capacity {
            my $last = @!cache.pop;
            %!index{$last} :delete;
        }
        @!cache.unshift($key);
        %!index{$key} = $value;
    }

    method print() {
        for @!cache -> $e {
            say "$e => ", %!index{$e};
        }
    }
}

(Full code on Github.)