Archive

Archive for November, 2021

MONKEY-SEE-NO-CROSSPRODUCT

November 30, 2021 1 comment

The challenge of the week is screaming: “Nest all the loops!”. I don’t like being yelled at, so I refuse to use any nested for/while/loop. The rules don’t require to put the two sub-challenges into separate files, so I won’t.

#! /usr/bin/env raku

use v6.d;

multi sub MAIN($divisors = 8, $? where $*PROGRAM-NAME.contains('-141-1')) {
    sub has-m-divisors($m, $n) {
        (1..∞).grep({ last if $_ > $n; $n %% $_ ?? (last if $++ ≥ $m; True) !! False })[^∞].elems == $m;
    }
    put (1..∞).grep(&has-m-divisors.assuming($divisors))[^10];
}

multi sub MAIN($m, $n where $*PROGRAM-NAME.contains('-141-2')) {
    use MONKEY-SEE-NO-EVAL;

    sub bind($o, Str $method-name) {
        sub (|c) { $o."$method-name"(|c) }
    }

    sub is-same-order(@l) {
        my @indices = @l.map(bind($m, 'index'));
        @indices ~~ @indices.sort;
    }

    say [$m, $n];
    my @a = $m.comb;
    my $expr = ('@a' xx @a).join(' X, '); # I can haz RakuAST macro plox?
    my @digits = (EVAL $expr)».unique.grep(-> @l { @l < @a && is-same-order(@l) }).sort(*.elems)».join.unique».Int;
    say @digits.grep: * %% $n;
}

multi sub MAIN($? where $*PROGRAM-NAME.contains('-141-2')) {
    for (1234, 2; 768, 4) -> [$m, $n] {
        MAIN($m, $n);
    }
}

To be able to run the 2nd task, ln -s pwc-141-1.raku pwc-141-2.raku is required. Since we can’t have a bare where-clause (yet), we need the optional positional in the MAINs.

Task one basically builds an infinite list of integers that have 8 divisors and then shows the first 10 of those. This is done by iterating to infinity and bailing as early as possible, if the condition of having 8 divisors is net or we get beyond the to be checked value. Since grep wants arity of 1, we use .assuming to please it.

The 2nd task is attacked (appropriate wording, as it took me 3 hours of struggle to get it done) in a similar fashion. First we build all possible combinations of an n-places integer. This would be done with an expression like @a xx @a ... $n where $n is the number of places. I don’t think we got such a construct in Raku so I had to macro it in with EVAL (also, it made a good blog title). We then proceed with eliminating all combinations that are forbidden by the task. First we weed out repetition with ».unique. Next we only take integers that are shorter then the original integer and don’t have the same order. We sort the result list by number of digits to make it pretty. At this point the digits are still represented as a list. We change that by forcing them into a Str via ».join and remove duplicates and turn them into Ints (not strictly necessary). Now we fulfil the last condition of divisibility by $n.

The sub is-same-order was where I spend the most time. And you can tell by how short it is. The idea is simple. We build a list of indices by walking the places of the number we want to check against the original integer. If the indices are all ascending, the order is the same. And we can tell by checking if those are already numerically sorted.

I’m not happy with using bind. This is another spot where Raku won’t allow functional programming to integrate well with OO. I’m gonna ask Santa if he can make &$m.index DWIM.

UPDATE

As perryprog kindly pointed out on IRC, there is sub cross, what makes the EVAL redundant.

my @digits = cross(@a xx +@a)».unique.grep(-> @l { @l < @a && is-same-order(@l) }).sort(*.elems)».join.unique».Int;

However, I think we can all agree that there is no immediate need to surrender a good blog post title.

Categories: Raku

Symmetric code

November 29, 2021 1 comment

While reading Arne`s solution for Challenge #140.2, I spotted a nested simple loop.

for 1 .. $i -> $ii                                               # [3]
{
  for 1 .. $j -> $jj                                             # [3]
  {
    @result.push: $ii * $jj;                                     # [4]
  }
}

In Raku-land, we don’t really need simple loops. Often we can .map or use a hyper operator. I had the nagging feeling this is also the case for simple nested loop. A good night’s sleep later I remembered that “X” marks the spot.

The cross-product-operator X is implemented with 2 nesting loops and returns a list of lists. In Raku we construct lists with infix:<,>.

use Test;
is-deeply ((1,2) X, (3,4)), ((1,2) X (3,4)), 'yep!';

So we are actually calling X,. If we replace infix:<,> with infix:<*>, we get what Arne did without the temporary container.

for [2, 3, 4; 3, 3, 6; 200, 300, 40; 0, 0, 0] -> [$i, $j, $k] {
    put ((1..$i) X* (1..$j)).sort[$k - 1];

    CATCH { when X::OutOfRange { warn „Sorry, I can't find position $k in the multiplication table of $i and $j.“ } }
}

I wonder if there are more cases, where we could look at the implementation of a high-level language feature, to spot places worthy of replacing wordy code with a single operator call.

Categories: Raku

Leaky Rakudo

November 28, 2021 1 comment

Yesterday the discord-bridge-bot refused to perform its 2nd job: EVAL All The Things! The EVALing is done via shell-out and requires a fair bit of RAM (Rakudo is equally slim then Santa). After about 3 weeks the fairly simple bot had grown from about halve a GB to one and a halve – while mostly waiting for the intertubes to deliver small pieces of text. I complained on IRC and was advised to take heap snapshots. Since I didn’t know how to make heaps of snapshots, I had to take timo’s directions towards use Telemetry. As snap(:heap) wasn’t willing to surrender the filename of the snapshot (I want to compress the file, it is going to get big over time) I had a look at the source. I also requested a change to Rakudo so I don’t have to hunt down the filename, which was fulfilled by lizmat 22 minutes later. Since you may not have a very recent Rakudo, the following snipped might be useful.

    multi sub postfix:<minute>(Numeric() \seconds) { seconds * 60 }
    multi sub postfix:<minutes>(Numeric() \seconds) { seconds * 60 }
    multi sub postfix:<hour>(Numeric() \seconds) { seconds * 3600 }
    multi sub postfix:<hours>(Numeric() \seconds) { seconds * 3600 }
    multi sub postfix:<day>(Numeric() \seconds) { seconds * 86400 }
    multi sub postfix:<days>(Numeric() \seconds) { seconds * 86400 }

    start react whenever Supply.interval(1day) {
        note ‚taking snapshot‘;
        use Perl6::Compiler:from<NQP>;
        sub compress(Str() $file-name) { run «lz4 -BD --rm -qf $file-name» }

        my $filename = 'raku-bot-' ~ now.DateTime.&{ .yyyy-mm-dd ~ '-' ~ .hh-mm-ss } ~ '.mvmheap';
        Perl6::Compiler.profiler-snapshot(kind => "heap", filename => $filename<>);
        $filename.&compress or warn(‚compression failed‘);

        note ‚done‘;
    }

If you got a long running MoarVM process, please consider to check if it slowly fills all RAM and provide the snapshots to #rakudev.

Categories: Raku

2nd class join

November 8, 2021 2 comments

For challenge #137.1 we are looking for long years. We can implement the algorithm as described in Wikipedia (and ignore that Dateish got .week-number to have a reason for showing off with junctions).

multi sub infix:«|,»(\left, \right) is equiv(&infix:<Z>) { |left, |right }

say (1900..2100).grep({ Date.new(.Int, 1, 1).day-of-week | Date.new(.Int, 12, 31).day-of-week == 4 });

# OUTPUT: 1903 1908 1914 1920 1925 1931 1936 1942 1948 1953 1959 1964 1970 1976 1981 1987 1992 1998 2004 2009 2015 2020 2026 2032 2037 2043 2048 2054 2060 2065 2071 2076 2082 2088 2093 2099

The output doesn’t look too nice. It would be better to group the years in column.

put ( (1900..2100).grep({ Date.new(.Int, 1, 1).day-of-week | Date.new(.Int, 12, 31).day-of-week == 4 }) Z (' ' xx 7 |, $?NL) |xx ∞ ).flat.head(*-1).join('');

# OUTPUT: 1903 1908 1914 1920 1925 1931 1936 1942
          1948 1953 1959 1964 1970 1976 1981 1987
          1992 1998 2004 2009 2015 2020 2026 2032
          2037 2043 2048 2054 2060 2065 2071 2076
          2082 2088 2093 2099

That is pretty long and convoluted. The reason why I need Z with an infinite list and have to remove the last redundant element (either a newline or space) is that .join isn’t all that smart. Let’s build a smarter function.

multi sub smart-join(Seq:D \separator, *@l --> Str:D) {
    my $ret;
    my $sep-it = separator.iterator;
    my $list-it = @l.iterator;

    loop {
        my $e := $list-it.pull-one;
        last if $e =:= IterationEnd;

        $ret ~= $e;
        $ret ~= $sep-it.pull-one if $list-it.bool-only;
    }

    $ret
}

multi sub infix:«|xx»(Mu \left, Mu \right) is equiv(&infix:<xx>) { (left xx right).flat }

1900..2100
==> grep({ Date.new(.Int, 1, 1).day-of-week | Date.new(.Int, 12, 31).day-of-week == 4 })
==> smart-join( (' ' xx 7 |, $?NL) |xx ∞ )
==> say();

Now we can use (the sadly under-used) feed operator. The lazy list that is generating the alternating separators might be a bit slow. If we go functional the code, both for smart-join and the alternator, gets simpler.

multi sub smart-join(&separators, *@l --> Str:D) {
    my $ret;

    while @l {
        $ret ~= @l.shift;
        $ret ~= separators if +@l;
    }

    $ret
}

1900..2100
==> grep({ Date.new(.Int, 1, 1).day-of-week | Date.new(.Int, 12, 31).day-of-week == 4 })
==> smart-join({ ++$ %% 8 ?? $?NL !! ' '})
==> say();

Right now there is no easy way to add this as a module because sub join is not a multi. Since we use Z with such infinite lists quite often, I believe a proper functional way in CORE could not hurt. Raku does support functional programming in many places but some subs are still 2nd class citizen. It may be reasonable to make a list so I can hand it over to Santa.

UPDATE:

As lizmat noted, sub join is a multi already. So there is room for a module.

Categories: Raku

Should it mutate or not? YES!

November 5, 2021 1 comment

On Discord Hydrazer was looking for a list concatenation operator. That leaves the question if it should mutate like Array.push or return a new list of Slips.

sub infix:«|<<»(\a, \e) {
    Proxy.new(FETCH => method { |a, |e },
              STORE => method (\e) {})
              but role { method sink { a.push: e } };
}

my @a = 1,2,3;
@a |<< 4;
dd @a;
my @b = @a |<< 5;
dd @a, @b;

In sink-context returning a new list would not make sense. With a Proxy that provides a sink-method we can answer the question with “YES!”.

This made me wonder if Proxy should have the optional argument SINK. Right now there is no way to define containers in pure Raku. Even with subclassing we would have to decent into nqp-land. As newdisp has shown, it tends to be quite brittle to make modules depend on use nqp;`.

Categories: Raku

TIMTOWTDItime

November 5, 2021 1 comment

On Discord flirora wished for a way to merge list elements conditional. In this instance the condition is that any element that starts with a space is part of a group.

{
    my @a = ("apple", " banana", " peach", "blueberry", "pear", " plum", "kiwi");

    multi sub merge-spacy([]) { () }
    multi sub merge-spacy([$x is copy, *@xs]) {
        if @xs[0].?starts-with(' ') {
            $x ~= @xs.shift;
            merge-spacy([|$x, |@xs])
        } else {
            $x, |merge-spacy(@xs)
        }
    }

    dd merge-spacy(@a);
}
# OUTPUT: ("apple banana peach", "blueberry", "pear plum", "kiwi")

This functional version is neat but slow. Rakudo can’t inline recursion and doesn’t do any other optimisations yet.

my @a = ("apple", " banana", " peach", "blueberry", "pear", " plum", "kiwi");

sub merge-with(@a, &c) {
    gather while @a.shift -> $e {
        if @a && &c(@a.head) {
            @a.unshift($e ~ @a.shift)
        } else {
            take $e;
        }
    }
}

dd @a.&merge-with(*.starts-with(' '));

# OUTPUT: ("apple banana peach", "blueberry", "pear plum", "kiwi").Seq

With gather/take we don’t have to worry about recursion and the returned Seq is lazy be default. This can provide a big win if the list gets big and is not wholly consumed.

my @a = ("apple", " banana", " peach", "blueberry", "pear", " plum", "kiwi");

multi sub join(*@a, :&if!) {
    class :: does Iterable {
        method iterator {
            class :: does Iterator {
                has @.a;
                has &.if;
                method pull-one {
                    return IterationEnd unless @!a;

                    my $e = @!a.shift;
                    return $e unless @!a;

                    while &.if.(@!a.head) {
                        $e ~= @!a.shift;
                    }

                    return $e;
                }
            }.new(a => @a, if => &if)
        }
    }.new
}

.say for join(@a, if => *.starts-with(' '));

This version should please lizmat as it uses iterators. The conditional is also factored out and CORE will use the Iterator lazily wherever possible. In production code I would get rid of the return-statements and replace them with ternary operators to get a little extra performance.

The original question (that clearly got me carried away) asked for the groups to be join. Once we lost a structure it can be difficult to reconstruct it.

my @a = ("apple", " banana", " peach", "blueberry", "pear", " plum", "kiwi");

#| &c decides if the group is finished
sub group-list(@a, &c) {
   my @group;
   gather while @a {
       my $e = @a.shift;
       my $next := +@a ?? @a.head !! Nil;
       @group.push($e);
       if !c($e, $next) {
           take @group.clone;
           @group = ();
       }
   }
}

dd @a.&group-list(-> $left, $right { $right && $right.starts-with(' ')});

Here the conditional gets two elements to decide if they belong to the same group. It is also the first time I used .clone.

Thanks to a simple question I learned quite a bit. It forced me to think about the disadvantages of my first idea. Maybe code challenges should explicitly asked for more then one answer for the same question.

Categories: Raku