Reducing sets

This week´s PWC asks us for hexadecimal words and distinctly different directories.

sub term:<pwc-166-1> {
    sub less-substitutions-then ($_, $n) {
        .subst(/<-[olist]>/, :g, '').chars < $n
    }

    '/usr/share/dict/words'.IO.words.race\
        .grep({.chars ≤ 8 && .&less-substitutions-then(4)})\
        .map(*.trans(<o l i s t> => <0 1 1 5 7>))\
        .grep(/^ <[0..9 a..f A..F]>+ $/)\
        .sort(-*.chars)\
        .say;
};

Once again, we write the algorithm down. Get the words, drop anything longer then 8 chars or what would need more then 4 substitutions. Then do the substitutions and grep anything that looks like a hexadecimal numeral. Sort for good measure and output the first 100 elements.

The second task provides us with a little challenge. We need to mock listing directories and working with them. Since dir returns a sequence of IO::Path I can create those by hand and mixin a role that mimics some filesystem operations. I can overload dir to provide a drop-in replacement.

sub term:<pwc-166-2> {
    sub basename(IO::Path $_) { .basename ~ (.d ?? '/' !! '') }
    sub pad(Str $_, $width, $padding = ' ') { .Str ~ $padding x ($width - .chars) }

    sub dir(Str $name) {
        sub mock-file(*@names) { @names.map({ IO::Path.new($_) but role :: { method f ( --> True ) {}; method e ( --> True ) {} } } ) }
        sub mock-dir(*@names) { @names.map({ IO::Path.new($_) but role :: { method d ( --> True ) {}; method e ( --> True) {} } }) }

        constant %dirs = dir_a => flat(mock-file(<Arial.ttf Comic_Sans.ttf Georgia.ttf Helvetica.ttf Impact.otf Verdana.ttf>), mock-dir(<Old_Fonts>)),
                         dir_b => mock-file(<Arial.ttf Comic_Sans.ttf Courier_New.ttf Helvetica.ttf Impact.otf Tahoma.ttf Verdana.ttf>),
                         dir_c => mock-file(<Arial.ttf Courier_New.ttf Helvetica.ttf Impact.otf Monaco.ttf Verdana.ttf>);

        %dirs{$name}
    }

    sub dir-diff(+@dirs) {
        my @content = @dirs».&dir».&basename;
        my @relevant = (([∪] @content) ∖ [∩] @content).keys.sort;

        my @columns = @content.map(-> @col { @relevant.map({ $_ ∈ @col ?? $_ !! '' }) });
        my $col-width = [max] @columns[*;*]».chars;

        put @dirs».&pad($col-width).join(' | ');
        put (''.&pad($col-width, '-') xx 3).join('-+-');
        .put for ([Z] @columns)».&pad($col-width)».join(' | ');
    }

    dir-diff(<dir_a dir_b dir_c>);
};

I’m asked to add a / to directories and do so with a custom basename. The rest is liberal application of set theory. Only names that don’t show up in all directories are relevant. Columns are created by matching the content of each directory against the relevant names. The width of columns is the longest string. The header is put on screen. To output the columns line by line, x and y are flipped with [Z].

After careful study of the solutions written in other languages, I believe it is fair to call Raku an eco-friendly language. Our keyboards are going to last at least twice a long.

Writing it down

PWC 165 refers us to mathsisfun for the algorithm to be used. Let’s write it down.

    my $input = '333,129  39,189 140,156 292,134 393,52  160,166 362,122  13,193
                341,104 320,113 109,177 203,152 343,100 225,110  23,186 282,102
                284,98  205,133 297,114 292,126 339,112 327,79  253,136  61,169
                128,176 346,72  316,103 124,162  65,181 159,137 212,116 337,86
                215,136 153,137 390,104 100,180  76,188  77,181  69,195  92,186
                275,96  250,147  34,174 213,134 186,129 189,154 361,82  363,89';

    my @points = $input.words».split(',')».Int;

    my \term:<x²> := @points[*;0]».&(*²);
    my \xy = @points[*;0] »*« @points[*;1];
    my \Σx = [+] @points[*;0];
    my \Σy = [+] @points[*;1];
    my \term:<Σx²> = [+] x²;
    my \Σxy = [+] xy;
    my \N = +@points;

    my $m = (N * Σxy - Σx * Σy) / (N * Σx² - (Σx)²);
    my $b = (Σy - $m * Σx) / N;

    say [$m, $b];

That was exceedingly simple. If the point cloud is large, this might also be exceedingly slow. There are no side effects and everything is nice and constant. Should be easy to get the CPU busy.

    sub delayed(&c) is rw {
        my $p = start { c };
        Proxy.new: STORE => method (|) {}, FETCH => method { await $p; $p.result }
    }

    my \term:<x²> = delayed { @points[*;0]».&(*²) };
    my \xy = delayed { @points[*;0] »*« @points[*;1] };
    my \Σx = delayed { [+] @points[*;0] };
    my \Σy = delayed { [+] @points[*;1] }
    my \term:<Σx²> = delayed { [+] x² };
    my \Σxy = delayed { [+] xy };
    my \N = +@points;

    my $m = (N * Σxy - Σx * Σy) / (N * Σx² - (Σx)²);
    my $b = (Σy - $m * Σx) / N;

    say [$m, $b];

Since I use sigil-less symbols, I get binding for free. This in turn makes using Proxy easy. The await $p part is called more then once per Proxy but not in a loop so there is no real need to optimise here. On my box the Proxyed version is almost twice as fast. A nice win for such a simple change.

I somehow feel this solution might please a mathematician — as Raku should.

Antipairing

As suspicious questions on IRC and Discord revealed, there are quite a few solutions to the PWC that are not made public. One question in particular indicates that there is a build-in missing in Raku.

Nemokosch: let’s say I have a 5×5 table for some reason

PWC162-2 is asking to implement an encryption algorithm that uses a simple substitution table. Having a data-struction that allowes to turn a character into a 2-dimensional @index and then use it to @replacement[||@index] would be very helpful indeed. We can use .antipairs to turn a simple list into something we can assign to a Hash and be done with it. With 2-dimension, we have to create our own.

proto sub deepantipairs(@positional, $dimensions --> Positional) {*}
multi sub deepantipairs(@a, 2) {
    @a.pairs.map({ my $outer-key = .key; .value.antipairs.map({ .key => ($outer-key, .value) }) }).flat
}
my $phrase = 'Spring has sprung!';
my @table = flat($phrase.lc.comb.grep(/\w/), 'a'..'z').unique[^25].batch(5);
my %antitable = @table.&deepantipairs(2);

# OUTPUT:

# Array @table = [("S", "p", "r", "i", "n"), ("g", "h", "a", "s", "u"), ("!", "b", "c", "d", "e"), ("f", "j", "k", "l", "m"), ("o", "q", "t", "v", "w")]
# Hash %antitable = {"!" => $(2, 0), :S($(0, 0)), :a($(1, 2)), :b($(2, 1)), :c($(2, 2)), :d($(2, 3)), :e($(2, 4)), :f($(3, 0)), :g($(1, 0)), :h($(1, 1)), :i($(0, 3)), :j($(3, 1)), :k($(3, 2)), :l($(3, 3)), :m($(3, 4)), :n($(0, 4)), :o($(4, 0)), :p($(0, 1)), :q($(4, 1)), :r($(0, 2)), :s($(1, 3)), :t($(4, 2)), :u($(1, 4)), :v($(4, 3)), :w($(4, 4))}

Let’s rotate the table (the basic idea behind the Enigma) to create a much more interesting cypher-text.

sub encrypt($phrase, $text --> Str) {
    my @table = flat($phrase.lc.comb.grep(/\w/), 'a'..'z').unique[^25].batch(5);
    my %antitable = @table.&deepantipairs(2);

    my $retval;

    for $text.lc.comb.grep(/\w/) -> $char {
        my @deepindex := %antitable{$char};
        $retval ~= @table[||@deepindex];
        @table = @table».List.flat[1..*,0].flat.batch(5);
    }

    $retval
}

say encrypt($phrase, 'As suspicious questions on IRC and Discord revealed, there are quite a few solutions to the PWC that are not made public. One question in particular indicates that there is a build-in in Raku missing.');

# OUTPUT:
# aprdnhbmdrodhvpkdtdxtjpppcuhjkuhmpdvfybpwannjpuychrfvdasojvvadgnwcqcwqkjmndpxexcepjcvjnagvpiopidyalietcknsbseejeqkbopsbpwypbrcuwknsejinlxjsmkxppwdasrrniboewbauejl

Please note the tripple “p” in the cypher. By rotating the replacement table, we mess up statistical properties of the natural language we encrypt. This makes limiting the key-space much harder.

As you likely spotted, I defined a proto with the argument $dimensions (our item may be an Iterable so we can’t infer this argument). Raku has many very handy methods defined in List that work very well with a single dimension. There may be more work to do when we start to support fixed size shaped arrays well.

A Subset of Red

SmokeMachine reported on IRC to have found an unusual use of subset.

class Base {}
class SubClass is Base {}

multi sub trait_mod:<of>(\type, Base $base, |c) { dd type; dd c }

subset Better of SubClass where { put "where: $_"; True };

my Better $a = 42;
# OUTPUT: Better
#         \()
#         where: 42

subset creates a new type with a metaclass of Perl6::Metamodel::SubsetHOW and registers a symbol for it. The of trait is a macro-ish sub that is called at compile time, right after the new type was created. We can get hold of both arguments of that trait and do whatever we want with those type-objects. (There are no further argument, hence the \()).

The where-clause is part of the subset and is called every time we assign a value to a container which is type-checked by the type created with subset. And that is cool. We basically get a callback into container assignment but only for types that are subclasses of a user-defined type. We can even create a fancy runtime error, based on the to be assigned value.

subset Universe of Base where { die 'wrong answer' unless $_ == 42; True }
my Universe $b = 43;
# OUTPUT: wrong answer
            in block  at 2021-03-08.raku line 1513

Red is doing all sorts of fancy meta-programming and I can highly recommend to read its source. With this discovery we got another nice tool in box.

Trust issues

On IRC japhb told us that he needs a class to trust another class that can’t see the to be trusted class.

class B {…}

class A {
    trusts B;
}

class B {

}

This is nice and simple and allows B to call private methods on A. Sadly, that only works if A and B reside in the same file because a forward declaration will cause a compile time error, unless we define the declared type in the same compilation unit.

Method resolution is a runtime creature in Raku. By carefully looking at the code, we can learn where Rakudo stores what we need to cheat with.

class A {
    has $!a = 'private';
    method !a { $!a }
}

multi sub trait_mod:<is>(Mu:U \obj, :$spying!) {
    A.^add_trustee(obj);
}

class B is spying(A) {
    has A $.a = A.new;
    method m { say $!a!A::a }
}

B.new.m;

Luckily, the trait is operates quite early at compile time, so we don’t mess up method dispatch. I’m not feeling to bad poking with a trait where I should not peek. We can always move quickly into NQP-land and break things.

    method cheating {
        use nqp;
        say nqp::getattr($.a, A, 'a');
    }

As shown above, privacy is a matter of politeness. What leaves the question, if forcing a forward declaration to be resolved locally, to be a good design decision. I shall ponder to file a problem solving issue.

That meant war

I try to avoid to allow politics or current events to seep into my blog. The topic is the 100 year language and as such wont be history. Sadly, the head-oligarch has publicly given obvious bullshit-reasons to invade a neighbouring country. I would like to use the powers of … to shed some light into the current darkness.

The official numbers (read: favouringly rounded up) for the population of Russia is 145805947 people. If only they could get themselves a decent government, that could have been quite a few hugs. But hugging they ain’t do enough, resulting in a birthrate of 1.82 children per woman. Let’s write that down.

my $woman = 145_805_947 / 2;
my $girls-per-woman := 0.91;

role Degression { }
my \degression = (2022, $woman), -> [$y, $w] { ($y + 35, $w * $girls-per-woman) but Degression } … ∞;
multi sub pretty(Degression [$year, $woman]) {
    "year: $year, Russians in RU: {$woman * 2}"
}

say degression[1000/35].&pretty;
# year: 3002, Russians in RU: 10397626.7
say "Soldiers available in {(1000/35).Int} generations: {Int(degression[1000/35][1]/$woman * 140000)}";
# Soldiers available in 28 generations: 9983

Here, I use an empty role to mark each value in the lazy list. Since I start with a 2-element list, I have to use destructuring and return a list in the generator function. The role allows for multi dispatch and other type checks, as shown in sub pretty.

Russia tries to build up independent industry for more then 10 years. That doesn’t work with a negative population growth. So they utterly depend on immigration from former soviet countries. They also depend on those counties to carry the financial burden to teaching the Russian language. Ukraine wants to join the EU in hopes to repeat the success of the Czechs (Hi Jonathan!) and Polsky (lol, Brexit!) to return to their spiritual home and grow the economy of their ancestors.

If you want to avoid future wars, don’t go to Russia. No people, no soldiers, no war. Also, being paid in ₽ may not be the most solid plan.

Self-referring labels

Lizmat kindly allowed Label to expose its file and line-number. That is handy if we want to convey messages about the code itself, without having to worry about edits invalidating our line-numbers. The first use case that came to mind are lightweight singletons that are easy to find.

barcode: Nil;
qrcode: Nil;

say [barcode ~~ qrcode, barcode === qrcode, barcode =:= qrcode]; # [False False False]
put barcode; # barcode ../label-introspection.raku:16

This might be handy when sending messages through a Channel.

my $ch = Channel.new;
start {
    HERE: Nil;
    THERE: Nil;
    $ch.send(.item) for ((1, 2, HERE, THERE) xx ∞).flat;
}

.put for @$ch;
# OUTPUT: 1
#         2
#         HERE ../label-introspection.raku:24
#         THERE ../label-introspection.raku:25
#         …

If those signals end up in a Str unintended, we have a good chance to find the source of the error, even when we have to look at the sender-end of a Channel.

We can also create error messages that point to a different line then a stacktrace might.

sub may-return-nil { }

ENIL: my $var is default(Failure.new(ENIL)) = may-return-nil;
say $var;

EWHOOPSY: fail(EWHOOPSY);

CATCH {
    when X::AdHoc && .payload ~~ Label {
        put "WELP! I encountered {.name} in {.file}:{.line}" with .payload;
    }
}

POD doesn’t allow us to do compile time interpolation (yet). Since it is made up of Arrays, we can cheat.

DOCLABEL: sub described {

}

=begin pod
Sub described is defined in L<PLACEHOLDER>.
=end pod

CHECK $=pod[0].contents[0].contents[1] = DOCLABEL.&{.file ~ ':' ~ .line};

say $=pod;

# OUTPUT: [Pod::Block::Named{:name("pod")}
#             Pod::Block::Para
#             Sub described is defined in
#             ../label-introspection.raku:31
#             .
#         ]

There are quite a few things hidden in CORE and I don’t like to use nqp::attr to get hold of them. A public interface is better then an accidental one. The former make way better idioms.

Pushing …

Thanks to ∖, PWC 154 part 1 is so boring, I’m not going into details. Part two however is a bit of a head scratcher. We are asked to implement a sequence with the properties:

P(0) = P(1) = P(2) = 1
P(n) = P(n-2) + P(n-3)

Using the sequence operator requires a trick thought.

my \padovan = 1, 1, 1, * + * + 0 * * … ∞;
my \padovan-prime = padovan.grep(*.is-prime).unique;

I have to convince it to operate on the 1th and 2nd element of the initial list and then advance by one. For once, math is on my side because with 0 * * I can force a 3rd automatic variable into existence, without having it take part in building the sum. The rest is just filtering out anything that isn’t prime.

There is another way to skip arguments if we are willing to use a pointy-block.

my \padovan = 1, 1, 1, -> $a, $b, $ { $a + $b } … ∞;

This is not as clever but looks intentional. It’s probably better that way.

Looplessly simple

PWC#153 is asking us to do two things that are almost comically simple, given we omit loops.

Task one would like us to output the first 10 left factorials.

sub MAIN() {
    my \leftfact = [\+] 0, 1, * * ++$ … ∞;
    say leftfact[1..10];
}

I’m doing so by writing down the definition of left factorials as a sequence and then indexing into the resulting lazy list.

In the 2nd task we need to check if the sum of the factorials of a digit equal that number.

sub MAIN(Int() $n) {
    my \fact = 1, * * ++$ … ∞;
    say fact[$n.comb].sum == $n ?? 1 !! 0
}

Again, I write down the definition of a factorial to get a lazy list in return. Then I can index into that list with a list of chars. Thankfully, Raku is considered enough to turn that list of chars into Ints for me. The sum is then checked against the whole number.

If you wonder what numbers are factorions, we can calculate them all.

my \fact = 1, * * ++$ … ∞;
fact[0..10];
.say for (^∞).hyper(:batch(1000)).grep({ fact[.comb].sum == .Int });

Hypering and sequences don’t really mix. State variables even less so. Luckily we only ever need the factorials of 0 to 10. I prime the lazy list with those values and happily hyper away.

I had a peak into the solutions on Rosattacode for left factorials. While scrolling past so many loops I had to think of Mr T.

Fuzzy commands

Reading can make one learned. Today I had a peak into lizmat´s new module shorten-sub-commands and learned about Parameter.constraint_list. We need this method to introspect a routines literal parameters.

use MONKEY-TYPING;
augment class Parameter {
    method literal {
        !self.name && !self.named && self.type ~~ Str|Numeric && self.constraint_list == 1
            ?? self.constraint_list.head
            !! Nil
    }
}

multi sub foo('literal', 42) { }
multi sub foo($not-a-literal, 42) { }
.say for &foo.candidates».signature».params».literal;

# OUTOUT: (literal 42)
#         (Nil 42)

We can generalise lizmat´s idea of transforming command line arguments.

multi sub MAIN('foo', |c) { say 'foo', @*ARGS[0] }
multi sub MAIN('Barbara', |c) { say ['bar', @*ARGS[0]] }

sub transform-first-arg(Mu:D $test is raw, &mapper) {
    &MAIN.add_dispatchee: sub (Str:D $subcommand, |c) is hidden-from-USAGE {
        my &this-candidate := &?ROUTINE;
        my @real-subcommands = &MAIN.candidates.grep(* !=:= &this-candidate)».signature».params».[0]».literal;
        if $subcommand ~~ $test {
            MAIN(mapper($subcommand), |c)
        }
    }
}

transform-first-arg({ .lc.contains(<fo ba>.any) }, { .trans: ['fo', /:i ba.*/] => ['foo', 'Barbara'] });

This program is now very generous when it comes to it’s first argument. Even !./% bAR will result in the right MAIN-candidate to be called.

I used augment because this doesn’t feel like an ENODOC. One needs to know quite a lot of the internal workings of Parameter to make use of method constraint_list. We may have to support more then just string and numeral literals in the future. So maybe there is a PR in order.