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 Proxy
ed 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 Array
s, 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 Int
s 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.
You must be logged in to post a comment.