use Benchmark::Dumb 'cmpthese';

( $bar, $quux ) = qw( bar quux );

cmpthese( 0.0002, {
  conc => q{
    my $str = "xxx ";
    (((( $str .= "foo" ).= $::bar ).= "baz" ).= $::quux ).= "qux";
  },
  intp => q{
    my $str = "xxx ";
    $str .= "foo${::bar}baz${::quux}qux";
  },
} );

I don’t recall ever seeing anyone mention this.

(It is, of course, obvious, and it is, of course, irrelevant in most contexts, especially as it is, of course, not a huge difference. Perl structurally tends to make it less likely to make this mistake in an accidentally quadratic way compared to how Java tends to be written, anyway. And anyhow, instead of micro-optimising Perl code this way, we all rewrite it – of course – in C… right?)

I announced recently that for one of my perl modules, Number::Phone, I would be dropping support for 32-bit versions of perl. On the mailing list that I have for users I heard nary a peep, but when I announced it in public groups I got some pushback, so I thought it would be a good idea to explain why I'm doing this, and also why I don't think it's a problem.

So first, why? It's quite simple really. Bundled with Number::Phone is a lot of data. The 25MB (compressed) distribution tarball expands to 123MB, of which 98MB is one single data file. Disk space is cheap this century, so I didn't worry about this for ages, until one of the users asked if I could split that data file out into a separate optional add-on, as it was taking most of the space in his Docker containers, and was a substantial financial cost for him. Splitting it out would require a long deprecation cycle, so as a temporary work-around I have provided a build-time option to leave out that file when you install the module and save disk space in exchange for reduced functionality. But I really want to provide full functionality and save disk space.

The large file is a DBM::Deep database. DBM::Deep is a fantastic tool, it provides an on-disk representation of an arbitrary data structure of arrays, dictionaries and scalars. You can access all the data completely transparently, and it eats hardly any memory. You can even add, edit and delete bits of the structure. An on-disk data structure that requires minimal memory is exactly what I wanted. However, editability comes with costs. In particular it costs lots of disk space. Not only do you have to allow space for data structures to grow (at minimum this requires space for extra pointers to data that would be added at the end of the file), to edit in a reasonable time also means that you have to potentially store the same data a great many times if the same value appears in multiple places.

But I don't need editability. It's enough that I can create a database once, and the users only need to be able to read it. So I created a replacement. Data::CompactReadonly stores in 6.1MB what DBM::Deep needs 98MB for. Database creation is slower and requires more memory than with DBM::Deep, but I don't care about that. Database access for users requires no more memory than DBM::Deep if you accept it being about half the speed, or if you can accept it using a bit of memory it is four times faster than DBM::Deep. And that's an early version, I've put some work into optimisation, but I'm sure I can wring some more performance out.

I didn't want to just write something for use by Number::Phone though, I wanted a general-purpose tool. To be general-purpose it has to support 64-bit values, and because I am lazy the current version requires 64-bit integers. I may find the tuits to get rid of that requirement at some point, but I'm not going to put much effort into that, because ...

... I doubt I have any 32-bit users. Perl has supported 64-bit architectures since at least 2003, and also supports 64-bit integers on many platforms that only have 32-bit pointers. I gave a 2 year deprecation warning, so by the time I release a version that requires 64-bit integers they will have been available on all reasonable platforms and many thoroughly unreasonable ones for just a few months short of twenty years. It hasn't been possible to even buy reasonable server-grade 32-bit hardware for a decade or more and even unreasonable hobbyist servers like the common cheap ARM boxes can run a perl with 64-bit integers.

So there you are, that's why I'm deprecating 32-bit perl, and why I don't think anyone will notice when I stop supporting it.

Ten years ago Rudolf Winestock wrote The Lisp Curse, an essay that “attempt[ed] to reconcile the power of the Lisp programming language with the inability of the Lisp community to reproduce their pre-AI Winter achievements.”

His conclusion? The power and expressiveness of Lisp have conspired to keep its developers individually productive, but collectively unable to organize their work into complete, standardized, well-documented, ‑tested, and ‑maintained packages that they could coalesce into interoperable and widely-adopted solutions. Everything from object systems to types to asynchronous non-blocking programming and concurrency is up for grabs and has multiple competing implementations.

These social effects have doomed Lisp to also-ran status in an industry where “employers much prefer that workers be fungible, rather than maximally productive.” Free tooling support has lagged; although Emacs can be hacked endlessly to do anything, there is no out-of-the-box integrated development environment or batteries-included defaults to immediately ease new programmers into their job.

Does this all sound familiar to Perl developers?

Perl is renowned for its expressive capabilities , enshrined in the TIMTOWTDI (There Is More Than One Way To Do It) design principle. Stories abound of the productivity achieved by Perl programmers stitching together modules from CPAN with their own code. Select an object system (or don’t), maybe throw in an exception handler (or don’t), and you too can have a codebase that fellow developers critique for not following their favored techniques. Meanwhile, managers are struggling to fill the rest of the team with new programmers looking for IDE support and finding only a grab-bag of Vim extensions.

But there’s hope.

Perl has started incorporating features expected of modern programming languages into its core while making room for further experimentation via CPAN. The Language Server Protocol (from Microsoft of all places!) has enabled Perl IDE features in text editors to boost productivity for new and experienced developers alike. And there’s a pilot Request For Comment process for further improvements.

These efforts point to a future where Perl’s expressive strength is married with sensible defaults and features without breaking backward compatibility. Maybe the curse can be overcome.

Hi there!

Flavio Poletti has just completed one year of blogging. Mohammad S. Anwar has been editing the Perl Weekly for more than three years and running the Perl Weekly Challenge for more than two years.

I am not sure what the secret is, but something about creating a commitment, even if it is an artificial commitment that then you need to stick to. I am sure both of them had times when they thought of sleeping in and not doing the work that day or that week. After all, this is not their paid job, but the commitment kept them going. With time it became easier to do the task and the whole thing became a habit. I wish more people found the strength to do something like this.

Enjoy your week!

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

You are given text file with rows numbered 1-15 in random order but there is a catch one row in missing in the file.

Solution

use strict;
use warnings;
sub find_missing{
    my(@numbers) = sort {$a <=> $b} @_;
    for(my $i=0; $i< @numbers - 1; $i++){
        return $numbers[$i] + 1 if $numbers[$i] != $numbers[$i + 1] - 1;   
    }  
}

MAIN:{
    my @line_numbers; 
    while(){
        chomp;
        m/([0-9]+),.*/;
        push @line_numbers, $1;
    }
    my $missing = find_missing(@line_numbers);
    print "$missing\n"; 
}

__DATA__
11, Line Eleven
1, Line one
9, Line Nine
13, Line Thirteen
2, Line two
6, Line Six
8, Line Eight
10, Line Ten
7, Line Seven
4, Line Four
14, Line Fourteen
3, Line three
15, Line Fifteen
5, Line Five

Sample Run

$ perl perl/ch-1.pl
12

Notes

My approach here is likely the most common one for this problem I would think. We get a list of all the numbers and then iterate through the list to determine which one is missing. This code assumes the conditions of the problem hold, that there is always one missing number.

Part 2

You are given size of a triangle. Write a script to find all possible paths from top to the bottom right corner. In each step, we can either move horizontally to the right (H), or move downwards to the left (L) or right (R).

Solution

use strict;
use warnings;
use constant FINAL => "end"; 
use constant DEADEND => "-1"; 
use constant TRIANGLE_TOP => q|/\\| ;
use constant TRIANGLE_BOTTOM => q|/__\\|;

sub find_paths{
    my($n) = @_;
    my %paths;
    my @complete_paths;
    my @vertices; 
    for my $i (0 .. $n){
        for my $j (0 .. $i){
            push @vertices, "$i-$j";
        }
    }
    $paths{""}=["0-0",["0-0"]];    
    my %updated_paths;
    while((keys %paths) > 0){
        %updated_paths = ();
        for my $path (keys %paths){
            my @exists;
            my @visited; 
            my $current = $paths{$path}->[0];  
            my $visited = $paths{$path}->[1];
            my @ij = split(/\-/, $current);  
            my($left, $horizontal, $right) = (($ij[0] + 1) . "-" . $ij[1], $ij[0] . "-" . ($ij[1] + 1), ($ij[0] + 1) . "-" . ($ij[1] + 1));
            @exists = grep {$_ eq $left} @vertices;
            @visited = grep {$_ eq $left} @{$visited};
            if(@exists && !@visited){
               my $visited_left = [@{$visited}, $left];
               if($left eq "$n-$n"){
                   push @complete_paths, $path . "L"; 
               }
               else{
                   $updated_paths{$path . "L"} = [$left, $visited_left];     
               }
            }          
            @exists = grep {$_ eq $horizontal} @vertices;
            @visited = grep {$_ eq $horizontal} @{$visited};
            if(@exists && !@visited){
               my $visited_horizontal = [@{$visited}, $horizontal];
               if($horizontal eq "$n-$n"){
                   push @complete_paths, $path . "H"; 
               }
               else{
                   $updated_paths{$path . "H"} = [$horizontal, $visited_horizontal];     
               }
            }           
            @exists = grep {$_ eq $right} @vertices;
            @visited = grep {$_ eq $right} @{$visited};
            if(@exists && !@visited){
               my $visited_right = [@{$visited}, $right];
               if($right eq "$n-$n"){
                   push @complete_paths, $path . "R"; 
               }
               else{
                   $updated_paths{$path . "R"} = [$right, $visited_right];     
               }
            }           
        }  
        %paths = %updated_paths;  
    }   
    return @complete_paths; 
}

sub print_triangle{
    my($n) = @_;
    my $top = TRIANGLE_TOP . "  ";
    for my $i (1 .. $n ){
        print " ";
        print "  " x ($n - $i);
        print $top x $i  ;
        print "\n";
        print "  " x ($n - $i );
        print TRIANGLE_BOTTOM x ($i );
        print "\n";
    }
}

MAIN:{
    my($N);
    $N = 1;
    print_triangle($N);
    for my $path (find_paths($N)){
        print "$path ";
    } 
    print "\n"; 
    $N = 2;
    print_triangle($N);
    for my $path (find_paths($N)){
        print "$path ";
    } 
    print "\n"; 
    $N = 3;
    print_triangle($N);
    for my $path (find_paths($N)){
        print "$path ";
    } 
    print "\n"; 
    $N = 4;
    print_triangle($N);
    for my $path (find_paths($N)){
        print "$path ";
    } 
    print "\n"; 
}

Sample Run

$ perl perl/ch-2.pl
 /\  
/__\
R LH 
   /\  
  /__\
 /\  /\  
/__\/__\
RR LRH RLH LHR LLHH LHLH 
     /\  
    /__\
   /\  /\  
  /__\/__\
 /\  /\  /\  
/__\/__\/__\
RRR LHRR RLHR LRRH RRLH RLRH LRHR LLHRH LLRHH RLHLH LHRLH RLLHH LHLRH LLHHR LHLHR LRLHH LRHLH LHLHLH LHLLHH LLHLHH LLLHHH LLHHLH 
       /\  
      /__\
     /\  /\  
    /__\/__\
   /\  /\  /\  
  /__\/__\/__\
 /\  /\  /\  /\  
/__\/__\/__\/__\
RRRR LRRHR LRHRR RRLHR LRRRH RRLRH RLRRH RLHRR RLRHR LHRRR RRRLH LHRRLH RLRHLH RLHLRH RLHLHR LLRHRH RLLRHH RLLHRH LHLRRH LLRRHH LRRLHH LRHRLH RLLHHR LHLRHR LHLHRR LLRHHR RRLLHH LRLHHR RLHRLH RLRLHH LHRLRH LRLRHH LHRLHR LRLHRH LRHLHR LLHRRH LRRHLH LLHHRR RRLHLH LLHRHR LRHLRH LLHRHLH LLLHHHR LLHHRLH LRLLHHH LLLRHHH LRHLHLH LLLHRHH RLHLLHH LLHLHHR LHRLHLH LHLHLHR LLRHLHH LHLLHRH LRLHHLH LLHLRHH RLLHLHH LLHHLRH LHLRLHH LHLHRLH LLRHHLH LRLHLHH LHLRHLH RLLHHLH LLLHHRH LHRLLHH LLHHLHR LRHLLHH LHLLHHR RLHLHLH LHLHLRH LLHRLHH LHLLRHH LLRLHHH RLLLHHH LLHLHRH LLHHLHLH LLLHHLHH LHLLHHLH LHLLLHHH LHLHLLHH LLHLHLHH LLLLHHHH LLHLHHLH LHLHLHLH LLHLLHHH LLLHHHLH LHLLHLHH LLHHLLHH LLLHLHHH 

Notes

Here we see a great example of combinatorial explosion! As the triangle size grows the number of possible pathways increases extremely quickly. The number of possible paths when $N = 10 is 1,037,718. My code finds all of those in about 40 seconds when run on a 2019 MacBook Pro. Performance on more modest hardware is still reasonable.

When $N = 20 the complete number of paths is so large that maintaining a list of paths in memory will cause the Perl interpreter to run out of memory and crash. It is simply not possible to list them all!

Interestingly it turns out that the original author of the challenge thought simply counting the paths would be sufficient, but the problem was edited to instead list the paths. I have to say that listing them all, along with my own optional variation of drawing the triangles was fun. The only downside was a bit of initial surprise, and then realization, about just how large the number of paths grows.

It turns out that this task is a slightly disguised description of what is known as a Quantum Pascal's Triangle. The possible number of paths, the count that is, can be obtained directly from a closed form approach. No need to actually traverse the paths!

What I did here was to effectively do a breadth first traversal.

• A hash is kept of all paths. Keys are the paths themselves and values are an array reference containing the current position and all previously visited nodes on that path.
• Each path is examined and updated to move to the next position proved that next position exists and has not yet been visited. (See more on visited positions next).
• The hash of paths is refreshed by moving paths that are completed to an array. Also, this code allows for catching paths which deadend (i.e. end up in a corner which is impossible to get out of without backtracking over a visited node). Without horizontal leftward movements this is not really possible however. Some CPU cycles can be saved by eliminating these checks, but I decided to leave them in anyway. Please do note the unnecessary extra work, however!
• The traversal ends when all paths have been exhausted, the loop ends, and the paths are returned.

References

Challenge 117

Quantum Pascal's Triangle

Recently I came across this tweet from Curtis/Ovid, which references longer post about a proposal to integrate a better, more modern object-oriented “system” (Corinna) in Perl 5.

The proposal itself is not what I’d like to address here. I haven’t followed Corinna’s evolution. I believe it goes in a positive direction for the language, FWIW.

From that original tweet, a comment from Rafael followed:

[…] but I’m still wondering what are the real factors that make companies seek an exit strategy from Perl 5. Who makes this kind of expensive decision, and why? I suspect obscure OO syntax is not a major one.

This is what I replied with:

This is indicative of the fundamental problem in the Perl echo chamber. Some people still have no idea why companies are moving away from Perl. If you want to hear the perspective from someone who has seen this happen in multiple companies, let me know :-)

Sorry for this premise, but I was afraid what follows would make no sense otherwise.

Why is Perl dying today?

First of all, I don’t think “ is dying” is a useful question to ask, nor it is indicative of anything particularly interesting. I’m sure everyone reading this will have encountered plenty of “C is dying”, “Java is dying” or similar, and yet, C and Java are still being used everywhere. In one sense, no language really dies ever. In Perl’s situation, things are slightly different though, as (I believe) Python slowly conquered Perl’s space over time.

What does it mean for a language to die, or to be dead?

From an end user point of view , let’s say a random programmer employed in a company or freelance, a language could be dying if a task they want to accomplish using that language is hard because there are no supporting libraries for it (think CPAN or PyPi), or the libraries are so old they don’t work anymore. That situation surely conveys the idea that the language is not in use anymore, or very few people must be using that language. One would expect that a common task in 2021 must be easy to accomplish with a language worth using in 2021.

What about a company ‘s point of view? The reality is that companies don’t have an opinion on languages, only people do. Teams do have an opinion on languages. The group dynamics inside a team influence what languages are acceptable for current and new projects.

Is Perl dying then?

My experience

Some years ago I was a fairly active member of the Perl community, I attended and presented at various Perl conferences around Europe, talking about my experience using Perl at a few small and large companies.

I remember picking up Perl for the first time based on a suggestion from my manager back then. He gave me a hard copy print-out of the whole of Perl 5.004 man pages, and said: “We are going to use this language. It’s amazing, take some time to study it and we’ll start!”. This was 1998, and I had such a fantastic time :-). I was such a noob, but Perl was amazing. It could do everything you needed and then some, and it was easy and simple. The language was fast already back then, and it got faster over time. At that point in time, I was working in a very small company, we were three people initially, and we ended up writing a complete web framework from scratch that is still in use today, after more than 20 years. If that’s not phenomenal, I don’t know what is. It’d be cool to talk about this framework: it was more advanced than anything that’s ever been done even considering it’s 2021… a story for another time.

And by the way, we were running our Perl code on *anything*, and I mean anything, Windows PCs, Linux, Netware and even AS/400, a limited subset of it at least, at a time when Java’s “write once, run everywhere” was just an empty marketing promise. Remember this was the time of Netscape Navigator and Java applets. Ramblings, I know, but perhaps useful to understand where things have gone wrong.

In 2007, I left my job in Italy and moved to Norway to work for Opera Software. Back then, Opera’s browser was still running the Presto engine, and a little department inside Opera was in charge of web services. That’s where I was headed. Most services there were written in Perl. Glorious times for me, I would learn an awful lot there, meet a lot of skilled developers. Soon after I started working there, 2007, some colleagues were already making fun of Perl. It’s a “write-only language”, “not meant for serious stuff”, “lack of web frameworks”, etc… Those were the times when Python frameworks started to emerge, some of which would eventually disappear. I remember a few colleagues strongly arguing to move to this Python framework called Pylons, and then eventually to Django.

I believe this general attitude towards Perl originated from different factors:

• personal preference towards other languages and/or dislike towards Perl
• the desire to be working with the latest “hip” framework or language
• the discomfort of maintaining an aging codebase with problems

These factors exist and are legitimate reasons to want to move away from any language or framework. I’m not saying they are justified, but I do understand why people wanted that. In our field, I have seen it’s quite common to try and avoid the objective difficulties of maintaining a legacy project, going the greener way of an overly optimistic rewrite, which normally ends in tears.

Throughout the years, I noticed other contributing factors to the progressive abandonment of Perl, even in companies like Opera.

I’ll mention two that I experienced directly:

1. Outdated or non existent supporting libraries
2. Teams composition

There was a time a few years ago, when CPAN was awesome, the best language support system in existence and every other language community was envying it. CPAN pretty much was selling Perl by itself. In my case, the libraries on CPAN educated me and made me adopt a testing culture that no other language (in my knowledge) had before Perl. Today, seeing npm modules being installed without running tests makes me uncomfortable :-)

Then over time (years) a shift happened. You would search on CPAN for a library that would help you with a common task and you wouldn’t find anything, or you would only find quick hacks that didn’t really work properly. In my case, I remember the first example of that being OAuth2. If I had to speculate, I would say this is a product of many elements, one of which is the average age of Perl programmers getting higher.

Another related shift I remember from those years is companies publishing their APIs/SDKs started dismissing Perl, at first relying on some CPAN module to eventually appear, then completely omitting Perl support. In the beginning, we politely complained to those companies, trying to make a point, but unfortunately there was no turning back. These days almost no SDK comes with a Perl component.

The second major aspect I have experienced is related to teams. In 2012 I was tasked with writing my first ever greenfield project, entirely from scratch, a project that would turn out to be one of the things I’m most proud of, Opera Discover , an online news recommendation system for the Opera browser, still working today! A team of three veteran engineers (myself included) was assembled, and there and then, we were faced with a decision: what language should we use for this?

While I was most experienced in Perl and knew Python a little, the other two colleagues didn’t know Perl. They had experience in C++ mostly, as this was Opera after all. We were chosen not based on our programming language expertise, rather (I suppose) based on our capability to tackle such a big and complex project. While I could have proposed that the project be written in Perl, in good conscience I knew that choice was not viable. Django was readily available and could provide a wide range of functionality we actually needed. No alternative in the Perl world could come close to such a good value proposition. The fact that Python was (like Perl had been for me!) a very accessible choice, simple to pick up, easily installed on any Linux system, and with plenty of solid up-to-date libraries, made the choice obvious.

With the Discover project, I started learning Python properly as a day-to-day programming language. I remember being horrified (and making fun of) the httplib2/httplib3 situation initially. Then I learned about the requests module and forgot all about it. This is to say, Python also has its quirks of course. The disastrous Python 2 vs Python 3 decision in the Python community caused a lot of grief and uncertainty for people (Perl could have learned something from that…). Nowadays, that’s a non-argument, everything runs on Python 3 and if you still haven’t moved, you will soon.

In general, having learned Python quite well, my mindset with regards to programming and my job changed completely. I’m not a Perl programmer. I’m not a Python programmer either. I can use different tools whenever they are more suited to what I need to do. In fact, in my last four years I have written software in NodeJS and Java of all things… I used to despise and make fun of Java, but I had never worked on any professional project before. While I do maintain that Java has some horrible aspects, contrary to my expectations, I have enjoyed working with it, it has an efficient runtime, awesome threading, solid libraries and debugging/inspection tools.

Conclusions

While I do understand Ovid’s point about wanting to keep the business going, and enjoying Perl as a language, I have personally moved on many years ago. I still use Perl for the occasional script when it’s convenient, but for other use cases, like web APIs, I prefer Python and FastAPI, PyTorch for machine learning, etc.. so my conclusion is that it’s the libraries and the ecosystem that drive language use, and not the language itself.

A better OO system will unfortunately do nothing for Perl (in my opinion at least). Better marketing will without a doubt do nothing for Perl. As if a prettier website could change the situation and the aspects I talked about… it can’t! The situation we have in front of us in 2021 is the result of technological and social changes started at least a decade ago.

I realize this may be an incoherent post. Sorry about that, I tried to write it right away or it would have probably never come out.

If you have questions or comments, let me know and I’ll try to address them if I can.

Most importantly, I do not wish to convince anyone that what I wrote is true. It is simply my experience. If there’s one thing I wish people would take from it, it’s to move away from the thought of yourself being a “X Programmer” and broaden your horizons and set of tools available to you. It was a tremendously positive move for myself, one I wished I had done before.

Peace.

Recursion in computer science is when a function calls itself to resolve the problem. Each recursive call usually tries to solve a simpler version of the original problem till we reach a point where the solution is obvious and does not need any further recursive calls.

A probably well known game of Google is that if you search for Recursion that will offer to redirect you to "recursion" again, ad infinitum. Probably the only escape from this is to click on the definition of recursion in Wikipedia

These are some answers to the Week 117 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a couple of days (June 20, 2021). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: Missing Row

You are given text file with rows numbered 1-15 in random order but there is a catch one row in missing in the file.

11, Line Eleven
1, Line one
9, Line Nine
13, Line Thirteen
2, Line two
6, Line Six
8, Line Eight
10, Line Ten
7, Line Seven
4, Line Four
14, Line Fourteen
3, Line three
15, Line Fifteen
5, Line Five

Write a script to find the missing row number.

If the numbers are really 1 to 15 and if only one number is missing, then we could sum the numbers that we have and subtract the result from the sum of all integers between 1 and 15 (120), which would give us the missing number.

However, I’ll work on a task that is a bit more general: rather than only 1 to 15, I’ll use a range from 1 to any larger integer, and I’ll also suppose that there can be more than 1 number missing.

Missing Row in Raku

I will simulate the input file as a string variable. We read the input data and store in the %seen hash the row numbers. At the end, we go through the range and print out numbers that are not in the hash.

use v6;

my $file = "11, Line Eleven
1, Line one
9, Line Nine
13, Line Thirteen
2, Line two
6, Line Six
8, Line Eight
10, Line Ten
7, Line Seven
4, Line Four
14, Line Fourteen
3, Line three
15, Line Fifteen
5, Line Five";

my %seen;
my $max = 0;

for $file.lines -> $line {
    my $num = $line ~~ /^(\d+)/;
    %seen{$num} = 1;
    $max = $num if $num > $max;
}
for 1..$max -> $i {
    say "Missing number = ", $i unless %seen{$i}:exists;
}

This program displays the following output:

raku ./missing_row.raku
Missing number = 12

Missing Row in Perl

This is essentially a port to Perl of the Raku program above, except that we store the input in a __DATA__ section:

use strict;
use warnings;
use feature "say";

my %seen;
my $max = 0;

while (my $line = <DATA>) {
    my $num = $1 if $line =~ /^(\d+)/;
    $seen{$num} = 1;
    $max = $num if $num > $max;
}
for my $i (1..$max) {
    say "Missing number = ", $i unless exists $seen{$i};
}

__DATA__
11, Line Eleven
1, Line one
9, Line Nine
13, Line Thirteen
2, Line two
6, Line Six
8, Line Eight
10, Line Ten
7, Line Seven
4, Line Four
14, Line Fourteen
3, Line three
15, Line Fifteen
5, Line Five

This program displays the same output as the Raku program:

$ perl missing_row.pl
Missing number = 12

Task 2 - Find Possible Paths

You are given size of a triangle.

Write a script to find all possible paths from top to the bottom right corner.

In each step, we can either move horizontally to the right (H), or move downwards to the left (L) or right (R).

BONUS: Try if it can handle triangle of size 10 or 20.

Example 1:

Input: $N = 2

           S
          / \
         / _ \
        /\   /\
       /__\ /__\ E

Output: RR, LHR, LHLH, LLHH, RLH, LRH

Example 2:

Input: $N = 1

           S
          / \
         / _ \ E

Output: R, LH

First, I will not try the bonus, because the result would just be insanely large: a triangle of size 10 has more than one million possible paths and a triangle of size 20 has billions or possibly trillions of paths.

Possible Paths in Raku

We use the recursive visit subroutine to build all possible paths.

use v6;

sub visit ($row, $col, $path) {
    print "$path " and return if $row == $col == $*end;
    visit($row + 1, $col + 1, "{$path}R") if $row < $*end and $col < $*end;
    visit($row, $col + 1, "{$path}H") if $col < $row;
    visit($row + 1, $col, "{$path}L") if $row < $*end;
}   

sub MAIN(UInt $size = 3) {
    my $*end = $size;
    visit(0, 0, '');
}

This program displays the following output:

raku ./possible_path.raku 3
RRR RRLH RLRH RLHR RLHLH RLLHH LRRH LRHR LRHLH LRLHH LHRR LHRLH LHLRH LHLHR LHLHLH LHLLHH LLRHH LLHRH LLHHR LLHHLH LLHLHH LLLHHH

We can also find the number of paths with an input value of 10:

raku ./possible_path.raku 10 | wc
      0 1037718 18474633

Possible Paths in Perl

This a port to Perl of the above Raku program:

use strict;
use warnings;
use feature "say";

my $end = shift // 3;

sub visit  { 
    my ($row, $col, $path) = @_;
    print "$path " and return if $row == $end and $col == $end;
    visit($row + 1, $col + 1, "${path}R") if $row < $end and $col < $end;
    visit($row, $col + 1, "${path}H") if $col < $row;
    visit($row + 1, $col, "${path}L") if $row < $end;
}   

visit(0, 0, '');

This program displays the following output:

$ perl possible_path.pl 3
RRR RRLH RLRH RLHR RLHLH RLLHH LRRH LRHR LRHLH LRLHH LHRR LHRLH LHLRH LHLHR LHLHLH LHLLHH LLRHH LLHRH LLHHR LLHHLH LLHLHH LLLHHH

$ perl possible_path.pl 2
RR RLH LRH LHR LHLH LLHH

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, June 27, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.

1. App::Cmd - write command line apps with less suffering
   • Version: 0.334 on 2021-06-19
   • Votes: 41
   • Previous version: 0.333 was 3 months, 5 days before
2. App::cpm - a fast CPAN module installer
   • Version: 0.997004 on 2021-06-13
   • Votes: 53
   • Previous version: 0.997003 was 3 months, 18 days before
3. App::Uni - command-line utility to find or display Unicode characters
   • Version: 9.005 on 2021-06-19
   • Votes: 14
   • Previous version: 9.004 was 11 months, 16 days before
4. Dist::Zilla - distribution builder; installer not included!
   • Version: 6.020 on 2021-06-14
   • Votes: 175
   • Previous version: 6.017 was 7 months, 11 days before
5. Dist::Zilla::Plugin::PodWeaver - weave your Pod together from configuration and Dist::Zilla
   • Version: 4.009 on 2021-06-19
   • Votes: 14
   • Previous version: 4.008 was 5 years, 1 month, 25 days before
6. Email::Sender - a library for sending email
   • Version: 1.300036 on 2021-06-17
   • Votes: 44
   • Previous version: 1.300035 was 8 months, 7 days before
7. JSON::Validator - Validate data against a JSON schema
   • Version: 4.20 on 2021-06-18
   • Votes: 28
   • Previous version: 4.17 was 1 month, 20 days before
8. LWP - The World-Wide Web library for Perl
   • Version: 6.55 on 2021-06-17
   • Votes: 153
   • Previous version: 6.54 was 1 month, 11 days before
9. MIME::Lite - Handy-dandy MIME mailing class
   • Version: 3.033 on 2021-06-12
   • Votes: 31
   • Previous version: 3.031 was 1 year, 7 months, 17 days before
10. Minion::Backend::SQLite - SQLite backend for Minion job queue
    • Version: v5.0.5 on 2021-06-16
    • Votes: 13
    • Previous version: v5.0.4 was 4 months before
11. Mojo::SQLite - A tiny Mojolicious wrapper for SQLite
    • Version: 3.006 on 2021-06-16
    • Votes: 24
    • Previous version: 3.005 was 4 months before
12. Mojolicious::Plugin::OpenAPI - OpenAPI / Swagger plugin for Mojolicious
    • Version: 4.04 on 2021-06-17
    • Votes: 40
    • Previous version: 4.03 was 1 month, 19 days before
13. OpenAPI::Client - A client for talking to an Open API powered server
    • Version: 1.01 on 2021-06-17
    • Votes: 14
    • Previous version: 1.00 was 3 months, 22 days before
14. PDL - Perl Data Language
    • Version: 2.051 on 2021-06-14
    • Votes: 42
    • Previous version: 2.050 was 12 days before
15. PerlPowerTools - BSD utilities written in pure Perl
    • Version: 1.025 on 2021-06-16
    • Votes: 28
    • Previous version: 1.024 was 2 months, 28 days before
16. Pod::Weaver - weave together a Pod document from an outline
    • Version: 4.018 on 2021-06-19
    • Votes: 32
    • Previous version: 4.017 was 2 months, 2 days before
17. POE::Component::IRC - A fully event-driven IRC client module
    • Version: 6.93 on 2021-06-15
    • Votes: 12
    • Previous version: 6.92 was 7 days before
18. Prima - a perl graphic toolkit
    • Version: 1.62 on 2021-06-16
    • Votes: 33
    • Previous version: 1.61 was 1 month, 23 days before
19. Search::Elasticsearch - The official client for Elasticsearch
    • Version: 7.713 on 2021-06-14
    • Votes: 41
    • Previous version: 7.712 was 2 months, 20 days before
20. Sub::Exporter - a sophisticated exporter for custom-built routines
    • Version: 0.988 on 2021-06-19
    • Votes: 33
    • Previous version: 0.987 was 7 years, 8 months, 1 day before
21. Test::Routine - composable units of assertion
    • Version: 0.028 on 2021-06-19
    • Votes: 13
    • Previous version: 0.027 was 2 years, 9 months, 23 days before
22. Text::CSV - comma-separated values manipulator (using XS or PurePerl)
    • Version: 2.01 on 2021-06-19
    • Votes: 69
    • Previous version: 2.00 was 2 years, 1 month, 8 days before
23. Throwable - a role for classes that can be thrown
    • Version: 0.201 on 2021-06-19
    • Votes: 37
    • Previous version: 0.200013 was 5 years, 11 months, 18 days before
24. Toadfarm - One Mojolicious app to rule them all
    • Version: 0.83 on 2021-06-17
    • Votes: 20
    • Previous version: 0.82 was 1 year, 8 months, 28 days before
25. Yancy - The Best Web Framework Deserves the Best CMS
    • Version: 1.074 on 2021-06-18
    • Votes: 39
    • Previous version: 1.073 was 11 days before

This is the weekly favourites list of CPAN distributions. Votes count: 40

Week's winners (+3): Object::Pad 

Build date: 2021/06/19 16:31:02 GMT

Clicked for first time:

• DBIx::Class::TopoSort - The addition of topological sorting to DBIx::Class
• PERLANCAR::Parse::Arithmetic - Parse arithmetic expmatchsion
• Plack::Middleware::TrafficAdvice - handle requests for /.well-known/traffic-advice

Increasing its reputation:

• App::cpanminus (+1=256)
• App::Netdisco (+1=13)
• App::perlimports (+1=4)
• autobox::Core (+1=22)
• Beam::Wire (+1=18)
• Bitcoin::RPC::Client (+1=6)
• Carton (+1=105)
• CHI (+1=49)
• Crypt::Eksblowfish (+1=17)
• Crypt::Passphrase (+1=5)
• Data::Types (+1=2)
• Deep::Hash::Utils (+1=5)
• Devel::Camelcadedb (+1=4)
• File::Slurp (+1=68)
• Future::AsyncAwait (+1=39)
• Getopt::Mini (+1=6)
• Gimp (+1=7)
• Hash::Fold (+1=4)
• Hash::Merge::Simple (+1=17)
• Hash::Path (+1=2)
• libwww::perl (+1=153)
• Mojolicious (+2=453)
• MongoDB (+1=86)
• Object::Pad (+3=11)
• PDF::Table (+1=4)
• PDL (+1=42)
• Perl::LanguageServer (+1=23)
• Plack::Middleware::Deflater (+1=5)
• Scalar::Induce (+1=2)
• Scalar::Util::Numeric (+1=3)
• Selenium::Remote::Driver (+1=44)
• Test::Compile (+2=8)
• Win32::Shortcut (+1=2)

These are the ten most rated questions at Stack Overflow last week.
Between brackets: [question score / answers count]
Build date: 2021-06-19 16:21:19 GMT

1. Replacing all occurrence after nth occurrence in a line in perl - [3/7]
2. What version of Perl introduced try / catch? - [3/2]
3. Parsing command line args, but not validating - [3/1]
4. Overlooping script: how to solve? - [2/5]
5. How to properly parse regular expression in Perl? - [2/3]
6. Why does Test::LeakTrace say this Perl code is leaking memory? - [2/1]
7. Intellij Perl5 add Perl5 interpreter - [2/1]
8. Regex on Perl to capture this type of value (a)(2) - [2/1]
9. Test::BDD::Cucumber::Harness::Html breaks UTF-8 characters - [2/0]
10. sed or Perl one liner + how to replace path in file only when full match - [1/4]

DBD::SQLite 1.67_07 (with SQLite 3.36.0) is a release candidate for the next stable DBD::SQLite. This release has a notable change to improve how to deal with Unicode/Latin-1 characters, contributed by Felipe Gasper. If you write a new application, it is recommended to use one of the newly added modes like this:

use DBI;
use DBD::SQLite::Constants qw(:dbd_sqlite_string_mode);

my $dbh = DBI->connect("dbi:SQLite:$dbname", "", "", {

    sqlite_string_mode => DBD_SQLITE_STRING_MODE_UNICODE_FALLBACK,

    # or 

    # sqlite_string_mode => DBD_SQLITE_STRING_MODE_BYTES,

    ...

});

These two new modes are, however, slightly incompatible with the old sqlite_unicode's behavior. If you want to use them with existing databases, you might need to convert them first (by retrieving all the data with the old flag and inserting them into new databases with a new mode, etc).

See Changes for other fixes and changes.

This release also updates bundled SQLite from 3.32.3 to 3.36.0, which means now you can use built-in math functions and ALTER TABLE DROP COLUMN among others.

I'll wait for about a month as always, and release 1.68 around the end of July if there's no blocker nor request to wait for more. Thank you for your patience.

The Grants Committee has concluded voting on the May 2021 round. Two grant requests were submitted:

Grant Proposal: Raku Dispatch and Compiler Improvements (USD 12,000)

VOTING RESULTS: Approved. 7 YES vote (27 points), 0 NO votes, 3 ABSTAIN

Grant Proposal: Persistent Data Structures for Raku (USD 7,000)

VOTING RESULTS: Approved. 7 YES vote (26 points), 0 NO votes, 3 ABSTAIN

The Grants Committee is excited to see work begin on these.

We accept proposals throughout the year; our next round of review will begin in July. You can submit proposals at any time.

If you want to help with funding and increase our budget, please visit our donations page. We sincerely appreciate all the donors which make the grant program possible. If you donate, please take advantage of your employers' matching donation program.

As always, thanks to our donors, both large and small, who support this program to give back to the community.

Regexp::Grammars can be scary. Let's try to have a simple and useful example.

I thought I’d try out Tau Station for a couple of days and get a quick blog post out of it. That was three months and 11 levels ago. It took 2 months to wind down my obsessive nature and if not for Tau, I could have pushed a couple of new module versions to CPAN by now. That’s rather the reason that I don’t play games in the first place, so I can’t give great comparisons.

To sum up, Tau Station is a web-based, second-person adventure with resource management in real-time: a Choose-your-own-Adventure book crossed with Freeciv. Oh, and it’s free. Well, freemium, but the least obtrusive freemium game I’ve ever seen.

At first, I used it as a rationalization. Every time I saw something that wasn’t amazing, I’d tell myself “But it’s free”. After a while, I started wondering “How is this free?” After 3 days and on the verge of screaming Shut up and take my money, I see the shopping cart icon that I ignore everywhere on t’Internet and the lightbulb flickers on. For me that’s a symptom of a Good UI - when you start to think about the question, the answer presents itself. They’ve put a lot of thought into Accessibility and the mobile version is as close to being as good as the desktop as you can get.

I spent a month playing free (on principle) and it’s challenging but rewarding. Stumping up the cash only really buys you time. Playing free doesn’t get you locked out of anything, really, which is astounding. I’m not as tight-fisted with Perl projects, so I’d always planned on making a donation, but as the month went on, I started making plans on what I could be doing with the various levels of backer. And yes, playing faster is fun. The virtual coffee mug is cute, one of the many small details in the background that make me smile.

The nice thing about the missions is that they maintain a sense of fun with references to Eighties movies, literary and historical figures as well as generating tension with a few crucial decisions. The first day I’m still trying to figure out how I want to play this role and then get confronted with ethical decisions that have consequences (I’d never considered my position on Robotic Rights before)

In the early days, I found myself scurrying back and forth between work and my room trying to pay for university courses. Also like real life, I found myself running to catch a shuttle, trying to remember everything I need, get a visa and some spending credits. The only difference between that and reality is I’d go to the Gym more times a day in the game than I’ve been in the last year and I’ve also written more blog posts there than here.

Players have written spoiler-free guides to Tau which you can search for or you can make it a voyage of discovery. There is enough complexity to keep it engaging over time and a welcoming community for those that like to be social. It’s a great game for the newly furloughed. It interrupts your thinking, but doesn’t take over your life. Good for waiting in the checkout or at the bus stop. My only suggestion is that if you play free, take notes. I made myself persona non grata at one station and now I can’t remember which one to avoid.

The one thing that I’d ask is, please, for the sake of the Community, find your NON-Perl friends and say “Check this game out. I think it’s written in $your_favourite_language, too”

-

Other second person adventures are available.

In my talk at The Perl and Raku Conference in the Cloud 2021,
I already announced it. I'm doing the release of the Perl developer version
5.35.1, and you can watch it live Sunday, 20th June on Twitch.

You can expect to watch me talk through the steps of the Perl
Release Managers Guide and if you join the Twitch chat, or #p5p
on irc.perl.org , we can chat a bit.

I assume I'll start Sunday at 10:00 UTC (12:00 CEST), and the whole thing will
take around 4 hours unless there are some major mishaps.

The following is adapted from my lightning talk “Blogging Outside the Bubble” at last week’s Perl and Raku Conference in the Cloud 2021. You can watch the presentation and download the slides here. Also, a tip: most of this applies to anyone who wants to start a blog.

Let’s say you’re a Perl developer distraught at the continued decline in usage and mindshare of your favorite language.

You know that you do good work and that your tools and techniques are sound, but the world outside of Perl-specific forums, software archives, social media groups, and IRC channels regards it as antiquated, out-of-date, or worse, that IT epithet legacy. (And the newer developers haven’t even heard of IRC!)

Let’s say you’re worried about your professional prospects both at your current employer and with possible future employers. Even though you know or can easily be trained in other languages, Perl is still your favorite.

Let’s say you’re me.

What do you do?

Step 1: Get a blog

There are two basic types of blogs: standardized format and customizable. If you’re just starting and you want to spend more time writing and less time fiddling with templates and software, choose standardized. Here are some sites that enable you to publish your work while getting out of your way and that have developer-centric communities. Pick one and set up an account:

• blogs.perl.org
• Dev.to
• DZone
• Medium

If you want more customization options, you could try:

• WordPress.com (hosted, but lets you change some things around)
• GitHub Pages (good if you’re already used to collaborative software development there, but requires more setup including blog generation software)
• Or your preferred hosting provider—look for ready-to-go blogging apps like WordPress

What did I choose? I set up WordPress on a shared plan at HostGator (full disclosure: I work there). They also offer easy managed WordPress hosting for a bit more, but I like to tinker.

And yes, the WordPress software is based on PHP. Don’t sweat that it’s not Perl. PHP doesn’t have to “lose” for Perl to “win.”

Step 2: Write

Finding a topic to write about can seem hard, but it doesn’t have to be. The Perl (and Raku) Weekly Challenge publishes two new programming challenges every week. Work on those and publish your solution along with commentary.

Or write about whatever you’re working on or would like to work on. Write about your favorite Perl module or feature. It doesn’t matter if someone else wrote about it; you have a unique perspective.

Coming up with a pithy title for your posts may be harder—you want to be clickbait-y but honest, and you want to mention Perl so that search engines associate your posts with the topic.

The important thing to do is write something. And length doesn’t matter; one or two paragraphs is fine.

Step 3: Promote

Here’s the bad news: no one is going to find your blog posts on their own. You need to put them in front of readers where they already are.

This means posting links on social networks like Twitter, Facebook, and LinkedIn. It means discussion groups and #hashtags (like #perl, #programming, #webdev, etc.) on those social networks. It means news forums like Reddit and Hacker News. And it means posting inside and outside of Perl-specific groups. Here are a couple of examples of the latter:

• LinkedIn FOSS (Free and Open Source Software) Professionals
• Reddit r/coding, r/programming, r/webdev

This social promotion might get tedious after a while, so look into plugins for your blogging platform and services like IFTTT and Zapier that will monitor your blog’s news feed and automatically post on your behalf.

Also, remember when I said above that there were blogging sites with developer-centric communities? Even if your main blog isn’t on one of them, set up accounts and cross-post. I repost my articles on Dev.to, DZone, and Medium; all of these offer ways to import posts from your main site. One caveat: their importers don’t seem to be very smart when it comes to source code, so you may need to do a bit of editing and reformatting after import.

Lastly, I would be remiss if I didn’t mention the Perl Weekly newsletter. Every Monday a fresh batch of Perl content is sent to people’s inboxes and you could be part of it. Contact editor Gábor Szabó about publishing links to your new blog.

Step 4: Repeat

Remember that consistency builds trust from your audience. Make time to write regularly and publish posts as often as you can manage. I set a goal to publish at least once a week and have kept up this pace since January of this year. You can often find new topics as you monitor and participate in the social forums in which you’re promoting your blog, especially in the comments. Even negative comments can drive new topics.

Did this article inspire you to start a blog? Do you have more questions? Let me know in the comments below!

Challenge, My solutions

TASK #1 › Missing Row

Task

You are given text file with rows numbered 1-15 in random order but there is a catch one row in missing in the file.

My solution

This is relatively straight forward, and can be broken down to two sub-tasks. The first is to read the file, and put any line numbers found in the %lines hash. I then have a counter that finds the first key in the hash that does not exist.

Example

$ ./ch-1.pl input.txt 
12

TASK #2 › Find Possible Paths

Task

You are given size of a triangle.

Write a script to find all possible paths from top to the bottom right corner.

In each step, we can either move horizontally to the right (H), or move downwards to the left (L) or right (R).

BONUS: Try if it can handle triangle of size 10 or 20.

My solution

For this task I used a recursive subroutine _make_move to walk the path of all possible solutions. The inputs to the subroutine are the target size, the current x and y position, and a string representing the current path to get to that point.

The rules are pretty simple:

1. If $y is less than $size, then we can move both diagonally left and right.
2. if $x is less than $y, we can also walk horizontally to the right.

As we output as we go, this allows us to go big without using too much memory. Right now my screen is spewing out all the solutions when the size is 20 rows.

This sequence is documented in OEIS A006318, also known as Schröder number. With 20 rows there are 17,518,619,320,890 possible solutions. Even at 1000 results per second, it would take over 200 days to print the list. My solution will print out all the solutions, just don't expect the list by the time you read this :)

Examples

Because I do the walking in a different order (left, right and then sidewides), the solutions differ from the examples. It still results in the same solution.

$ ./ch-2.pl 1
Output: LH, R
A total of 2 paths found

$ ./ch-2.pl 2
Output: LLHH, LRH, LHLH, LHR, RLH, RR
A total of 6 paths found

$ ./ch-2.pl 10
... about 19 MB of text skipped ...
A total of 1037718 paths found

Hi there

The highlight of last week was the Conference in the Cloud. It gave us the opportunity to meet and greet Perl and Raku fans from across the globe. On top of that, we got loads of quality talks by experts. Before I talk about anything else, let me thank and congratulate all the organisers and volunteers for such a successful event. I am personally impressed with the video quality of the live and recorded talks.

For me, I find the timing little bit odd as I am in the UK. The day started at 6:30pm British Summer Time, which is not ideal. At the end of a full day at $work, there is hardly any energy left to attend the talks live. But the best part wasthat the recorded talks were available on YouTube immediately. I find it convenient, as I can watch at my own time. Also I can fast-forward if I want to.

Please find below my personal favourites in no particular order.

1. perlimports or "Where did that symbol come from?" by Olaf Alders

2. Local dev setup for a complex app using docker-compose by Thomas Klausner

3. Introduction to Perl Data Types by William N. Braswell, Jr.

4. Rummaging in the clOOset by Curtis Poe

5. Life after Perl (and Raku) by Peter Sergeant

6. What's new in Perl? by Ricardo Signes

7. Perl's Amazing Time Machine by Paul Evans

8. Valiant - Heroic validations for Moo and DBIC classes by John Napiorkowski

9. Our shared vision of Perl by Andrew Solomon

10. Cross-platform native GUIs: {trade,pay}offs, {integra,distribu}tion by Zaki Mughal

There are plenty more to watch later. You can find the complete list here.

Enjoy the rest of the newsletter and please stay safe.

Since the release of Perl 5.6 in 2000 we can and should use the warnings pragma. It allows the turning on and off of warnings in lexical blocks, that is withing any set of curly praces.

It also allows us to create our own warnings together with our own warning categories.

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

You are given a number $N >= 10. Write a script to split the given number such that the difference between two consecutive numbers is always 1, and it shouldn't have a leading 0. Print the given number if it impossible to split the number.

Solution

use strict;
use warnings;
use boolean;
use AI::Genetic;

use constant THRESHOLD => 0;
use constant NUMBERS   => "1234";

sub no_op{
    my($x) = @_;
    return (caller(0))[3] if !defined($x);
    return $x;
}

sub get_1{
    my($s) = @_;
    return (caller(0))[3] if !defined($s);
    return substr($s, 0, 1);
}

sub get_2{
    my($s) = @_;
    return (caller(0))[3] if !defined($s);
    return substr($s, 0, 2);
}

sub get_3{
    my($s) = @_;
    return (caller(0))[3] if !defined($s);
    return substr($s, 0, 3);
}

sub get_4{
    my($s) = @_;
    return (caller(0))[3] if !defined($s);
    return substr($s, 0, 4);
}

sub fitness{
    my($genes) = @_;
    my $s = NUMBERS;
    my $fitness = -1 * (length($s) -1);
    my @operands;
    for my $gene (@{$genes}){
        if(my($i) = $gene->() =~ m/get_([1-4])/){
            push @operands, $gene->($s);
            return -1 * NUMBERS if length($s) < $i;
            $s = substr($s, $i) if length($s) >= $i;
        }
    }
    $s = NUMBERS;
    for(my $i = 0; $i < @operands - 1; $i++){
        if($operands[$i] == ($operands[$i + 1] - 1)){
            $fitness++;
            my $chars = length($operands[$i]);
            $s = substr($s, $chars);
        }
    }
    if($operands[@operands - 1] && $operands[@operands - 2]){
    if($operands[@operands - 1] == ($operands[@operands - 2] + 1)){
        my $chars = length($operands[@operands - 1]);
        $s = substr($s, $chars);
    }
    }
    $fitness *= length($s);
    return $fitness;
}

sub terminate{
    my($aig) = @_;
    my $top_individual = $aig->getFittest();
    if($top_individual->score == THRESHOLD){
        my $genes = $top_individual->genes();
        my $s = NUMBERS;
        my @operands;
        for my $gene (@{$genes}){
            if(my($i) = $gene->() =~ m/get_([1-4])/){
                push @operands, $gene->($s);
                $s = substr($s, $i);
            }
        }
        print join(",", @operands) . "\n";
        return true;
    }
    print NUMBERS . "\n";
    return true;
}

MAIN:{
    my $aig = new AI::Genetic(
        -fitness    => \&fitness,
        -type       => "listvector",
        -population => 50000,
        -crossover  => 0.9,
        -mutation   => 0.1,
        -terminate  => \&terminate,
    );
    my $genes = [];
    for (0 .. 7){
        push @{$genes}, [\&get_1, \&get_2, \&get_3, \&get_4, \&no_op],
    }
    $aig->init(
        $genes
    );
    $aig->evolve("tournamentUniform", 1000);
}

Sample Run

$ perl perl/ch-1.pl
1,2,3,4

Notes

Task #1 is slightly similar to the Only 100, please task from Challenge 044. In that previous task we are given a string of numbers and asked to split the string with only + or - operations to arrive at a value of 100. Here we must similarly split the string of numbers, but the criteria is different. Here we need to assemble the string into numbers that differ only by 1, if possible.

As done in that previous challenge we use a not so brutish, yet forceful, approach using AI::Genetic. In this way our program learns the best way to achieve our goal given a fitness function which allows it to evaluate different splitting patterns and smartly choose the next attempt.

While avoiding evaluating a great many possible combinations, I must admit to a certain brutishness here in that I did not spend much time tuning the parameters used. Also, the get_ functions will not scale very well for very long strings. It would be possible to generate these functions in a loop using a functional programming style currying approach dependent on the length of the input string. Imagine an input of 1 followed by 999 0s, then a 1 followed by 998 0s and final 1. This use of AI::Genetic would certainly work with such an input given proper get_ functions, very many of which would be quickly be lost in the evolutionary dust, so to speak.

The use of function references for the genes is not something I am aware of outside of my own usage. I like to call this a Functional Genome.

Part 2

You are given a number $N >= 10. Write a script to find out if the given number $N is such that sum of squares of all digits is a perfect square. Print 1 if it is otherwise 0.

Solution

use strict;
use warnings;
use POSIX;

sub sum_squares{
    my($n) = @_;
    my @digits = split(//, $n);
    my $sum = 0;
    map { $sum += ($_ ** 2) } @digits;
    return (ceil(sqrt($sum)) == floor(sqrt($sum)));
}

MAIN:{
    my($N);
    $N = 34;
    if(sum_squares($N)){
        print "1\n";
    }
    else{
        print "0\n";
    }
    $N = 50;
    if(sum_squares($N)){
        print "1\n";
    }
    else{
        print "0\n";
    }
    $N = 52;
    if(sum_squares($N)){
        print "1\n";
    }
    else{
        print "0\n";
    }
}

Sample Run

$ perl perl/ch-2.pl
1
1
0

Notes

This task is well suited for Perl. We can make quick work of what might be a heavier lift in other languages by split-ting the number into individual digits and then using a map to perform the summing of the squares. The POSIX module provides convenient ceil and floor functions for checking to see if the result is a perfect square.

References

Challenge 116

Challenge 044 | Only 100, please

1. App::lcpan - Manage your local CPAN mirror
   • Version: 1.068 on 2021-06-05
   • Votes: 14
   • Previous version: 1.067 was before
2. Dancer2 - Lightweight yet powerful web application framework
   • Version: 0.301004 on 2021-06-06
   • Votes: 125
   • Previous version: 0.301003 was 3 days before
3. Minion - Job queue
   • Version: 10.22 on 2021-06-10
   • Votes: 84
   • Previous version: 10.21 was 2 months, 21 days before
4. Minion::Backend::mysql - MySQL backend
   • Version: 0.29 on 2021-06-07
   • Votes: 12
   • Previous version: 0.28 was 3 days before
5. Mojolicious::Plugin::Authentication - A plugin to make authentication a bit easier
   • Version: 1.37 on 2021-06-10
   • Votes: 17
   • Previous version: 1.36 was 1 month, 19 days before
6. POE::Component::IRC - A fully event-driven IRC client module
   • Version: 6.92 on 2021-06-08
   • Votes: 12
   • Previous version: 6.91 was 3 days before
7. SPVM - Static Perl Virtual Machine. Fast Calculation, Fast Array Operation, and Easy C/C++ Binding.
   • Version: 0.9006 on 2021-06-11
   • Votes: 21
   • Previous version: 0.9005 was 15 days before
8. Yancy - The Best Web Framework Deserves the Best CMS
   • Version: 1.073 on 2021-06-07
   • Votes: 39
   • Previous version: 1.072 was 12 days before

This is the weekly favourites list of CPAN distributions. Votes count: 149

Week's winners (+3): Perl::LanguageServer 

Build date: 2021/06/12 14:33:40 GMT

Clicked for first time:

• aliased::factory - shorter versions of a class tree's constructors
• Alt::common::sense::TOBYINK - provides a clean-room reimplementation of common::sense
• App::Acmeman - manages ACME certificates
• App::Env - manage application specific environments
• App::pathed - munge the Bash PATH environment variable
• Arguments - Perl subroutine type-checking
• Argv - Provide an OO interface to an arg vector
• Attribute::Overload - Attribute that makes overloading easier
• Attribute::Property - Easy lvalue accessors with validation. ($foo->bar = 42)
• Attribute::SubName - Naming anonymous subroutines via attributes
• Attribute::TieClasses - Attribute wrappers for CPAN Tie classes
• Beekeeper - Framework for building applications with a microservices architecture
• Boulder - An API for hierarchical tag/value structures
• Builder - Build XML, HTML, CSS and other outputs in blocks
• callee - support recursive anonymous functions
• Cfwp::fio -
• Class::Accessor::Complex - Arrays, hashes, booleans, integers, sets and more
• Class::Dynamic - Rudimentary support for coderefs in @ISA
• Class::Factory::Enhanced - More functionality for Class::Factory
• Class::SingletonMethod - Extend individual objects with additional methods
• Class::Std::Slots - Provide signals and slots for standard classes.
• Class::Wrap - Proxy an entire class's methods.
• Closure::Loop - redo, last, next for closure based loops
• Data::Container - Base class for objects containing a list of items
• Data::Domain - Data description and validation
• Data::DRef - Delimited-key access to complex data structures
• Data::Inherited - Hierarchy-wide accumulation of list and hash results
• Data::Miscellany - Collection of miscellaneous subroutines
• Data::Object::AutoWrap - Autogenerate accessors for R/O object data
• Data::Pack - Pack data structures so only real content remains
• Data::PathSimple - Navigate and manipulate data structures using paths
• Data::Semantic - Common API for data with semantics attached to them
• Data::SmartMunge - Munge scalars, hashes and arrays in flexible ways
• Data::Template - Generate data structures from templates
• Decision::Depends - Perform actions based upon file dependencies
• Digest::MD6 - Perl interface to the MD6 Algorithm
• fields::aliased - create aliases for object fields
• File::Attributes - Manipulate file metadata
• File::Attributes::Recursive - Inherit file attributes from parent
• File::Find::Upwards - Look for a file in the current directory and upwards
• Getopt::Attribute - Attribute wrapper for Getopt::Long
• Getopt::Inherited - Handling inherited command-line options
• import - import all modules with the same package prefix, aliasing it away.
• Importer::Zim::Lexical - Import functions as lexical subroutines
• like - Declare support for an interface
• Loop::Control - FIRST and NEXT functions for loops
• Mic - Simplified OOP with emphasis on modularity and loose coupling.
• Module::Changes - Machine-readable Changes file
• Module::Changes::ADAMK - Parse a traditional Changes file (as ADAMK interpretes it)
• Net::BigIP - REST interface for BigIP
• Object::Accessor - Per object accessors
• Object::Extend - add and override per-object methods
• once - Execute code only once throughout the program's lifetime
• overload::reify - Provide named methods for inherited overloaded operators
• Perl6::Export - Implements the Perl 6 'is export(...)' trait
• pkg - transparently use packages and inner packages
• Property::Lookup - Object property lookup across multiple layers
• rubyisms - Steal some features from Ruby
• Shell::GetEnv - extract the environment from a shell after executing commands
• Soo - Simple object oriented system for Perl
• Sub::AliasedUnderscore - transform a subroutine that operates on $_ into
• Sub::Become - Syntactic sugar to allow a sub to replace itself
• Sub::CharacterProperties - Support for user-defined character properties
• Sub::Documentation - Collect documentation for subroutines
• Sub::Replace - Replace subroutines in packages with controlled effects
• uninit - Warn about uninitialized variables
• UNIVERSAL::ref - Turns ref() into a multimethod
• Var::Mystic - Monitor your state, tracked in colour
• version::Limit - Perl extension for fine control of permitted versions
• Win32::Shortcut - Perl Module to deal with Windows Shortcuts
• with - Lexically call methods with a default object.

Increasing its reputation:

• aliased (+1=30)
• Alt (+1=6)
• App::ElasticSearch::Utilities (+2=7)
• as (+1=3)
• Attribute::Handlers (+1=8)
• Attribute::Types (+1=2)
• Brickyard (+1=2)
• Class::Accessor::Constructor (+1=2)
• Class::Generate (+1=2)
• Class::Mix (+1=2)
• Class::Monkey (+1=2)
• Class::Null (+1=2)
• Class::ReturnValue (+1=2)
• CLI::Helpers (+1=5)
• Crypt::Argon2 (+1=6)
• Crypt::Passphrase (+1=4)
• Crypt::URandom (+1=4)
• Data::Find (+1=2)
• Data::Focus (+1=2)
• Data::Reach (+1=2)
• DhMakePerl (+1=5)
• Expect::Simple (+1=2)
• File::ExtAttr (+1=2)
• Filter (+1=8)
• Future::AsyncAwait (+1=38)
• Hash::Inflator (+1=2)
• Hash::SharedMem (+1=3)
• Hash::Type (+1=2)
• Import::Box (+1=2)
• Importer::Zim (+1=3)
• IO::AIO (+1=15)
• latest (+1=4)
• List::Categorize (+1=3)
• MARC::Record (+1=6)
• MCE (+1=85)
• Minion (+1=84)
• Modern::Perl (+1=46)
• Mojolicious::Plugin::AssetPack (+1=48)
• Moose (+1=319)
• MooX::TaggedAttributes (+1=2)
• namespace (+1=2)
• nonsense (+1=2)
• Nothing::Tiny (+1=2)
• Number::Bytes::Human (+1=7)
• Object::Pad (+1=8)
• Object::Result (+1=3)
• optimize (+1=2)
• optimizer (+1=2)
• Parallel::WorkUnit (+1=6)
• perl (+1=378)
• Perl6::Export::Attrs (+1=3)
• Perl6::Gather (+1=5)
• Perl6::Rules (+1=2)
• Perl6::Slurp (+1=9)
• Perl::LanguageServer (+3=23)
• Pod::Usage (+1=40)
• Progress::Any (+1=8)
• Quantum::Superpositions (+1=6)
• Scalar::Properties (+1=2)
• Scope::With (+1=3)
• Set::Object (+1=10)
• Shell (+1=5)
• Shell::Autobox (+1=2)
• Shell::Perl (+1=4)
• SOAP::Lite (+1=20)
• StreamFinder (+1=3)
• Sub::Genius (+2=2)
• Term::ReadPassword (+1=3)
• true (+1=5)
• Type::TinyX::Facets (+1=2)
• Var::Pairs (+1=11)
• Variable::Magic (+1=24)
• version (+1=19)
• Version::Next (+1=4)
• XML::RSS (+1=7)

As I can see The Perl and Raku Conference in the cloud starts tomorrow. I am a bit confused as don't remember a lot of promotion of the event.

Some people complain that the content created by the Perl Weekly Challenge has flooded the Perl Weekly Newsletter. I'd say if there was more Perl content outside of the PWC that we can share then we could consider reducing the amount of space the PWC takes up.

BTW that reminds me, I think the events page and the events section at the bottom of the newsletter is shrinkig as the event organizers rarely send updates. I guess having these links did not bring them visitors.

Enjoy your week!

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

You are given an array of strings. Write a script to find out if the given strings can be chained to form a circle. Print 1 if found otherwise 0. A string $S can be put before another string $T in circle if the last character of $S is same as first character of $T.

Solution

use strict;
use warnings;
use Graph;
use Graph::Easy::Parser;

sub build_graph{
    my @words;
    my %first_letter_name;
    my $graph = new Graph();
    while(my $s = ){
        chomp($s);
        my $first_letter = substr($s, 0, 1);
        if($first_letter_name{$first_letter}){
            push @{$first_letter_name{$first_letter}}, $s;
        }
        else{
            $first_letter_name{$first_letter} = [$s];
        }
        push @words, $s;
    }
    for my $word (@words){
        $graph->add_vertex($word) if !$graph->has_vertex($word);
        my $child_nodes = $first_letter_name{substr($word, -1)};
        for my $n (@{$child_nodes}){
            $graph->add_vertex($n) if !$graph->has_vertex($n);
            $graph->add_weighted_edge($word, $n, (-1 * length($n))) if !$graph->has_edge($word, $n);
            $graph->delete_edge($word, $n) if $graph->has_a_cycle();
        }
    }
    return $graph;
}

sub display_graph{
    my($graph) = @_;
    my $s = $graph->stringify();
    my @s = split(/,/, $s);
    my @lines;
    for my $n (@s){
        my @a = split(/-/, $n);
        push @lines, "[ $a[0] ] => [ ]" if @a == 1;
        push @lines, "[ $a[0] ] => [ $a[1] ]" if @a > 1;
    }
    my $parser = new Graph::Easy::Parser();
    my $graph_viz = $parser->from_text(join("", @lines));
    print $graph_viz->as_ascii();
}

MAIN:{
    my $graph = build_graph();
    my @cc = $graph->weakly_connected_components();
    print "1\n" if @cc == 1;
    print "0\n" if @cc != 1;
    display_graph($graph);
}

__DATA__
ab
bea
cd

Sample Run

$ perl perl/ch-1.pl
0
+----+     +-----+
| ab | ==> | bea |
+----+     +-----+
+----+
| cd | ==>
+----+
$ perl perl/ch-1.pl
1
+-----+     +-----+     +----+
| dea | ==> | abc | ==> | cd |
+-----+     +-----+     +----+

Notes

Task #1 is very similar to the Pokemon Name Ladder task from Challenge 025. This task is actually a part of that previous challenge in that here we do not need to compute the longest possible chain of strings; we just need to confirm that the chain exists.

The approach here is:

• read in the words and construct the directed graph
• check to see that the number of connected components is one. If so, print 1. Otherwise print 0.
• display the graph (an optional data visualization step)

The function used to determine the number of connected components is weakly_connected_components(). This is because the chain is constructed as a directed graph and the idea of a connected component is defined for undirected graphs. Weakly connected components are determined by whether or not the nodes are connected if we ignore the direction of the edges. This is what we want for our use case here, as opposed to strongly connected components. To determine strongly connected components we would need bi-directional edges for each link in the chain. No need to overcomplicate this with extra edges...the desired result is obtained just fine as is!

In the example output the first run shows two connected components, therefor no chain exists. In the second output the chain is shown, there is one connected component.

Part 2

You are given a list of positive integers (0-9), single digit. Write a script to find the largest multiple of 2 that can be formed from the list.

Solution

use strict;
use warnings;
sub largest_multiple_2{
    my @numbers = @_;
    return unless grep { $_ % 2 == 0 } @numbers;
    my @sorted = sort {$b <=> $a} @numbers;
    if(@sorted >= 2){
        my $ultima = @sorted[@sorted - 1];
        if($ultima % 2 != 0){
            my $swap_index = -1;
            for(my $i = @sorted - 2; $i >= 0; $i--){
                $swap_index = $i if $sorted[$i] % 2 == 0;
                last if $swap_index > 0;
            }
            $sorted[@sorted - 1] = $sorted[$swap_index];
            $sorted[$swap_index] = $ultima;
        }
    }
    return join("", @sorted);
}

MAIN:{
    my @N;
    @N = (1, 0, 2, 6);
    print largest_multiple_2(@N) . "\n";
    @N = (1, 4, 2, 8);
    print largest_multiple_2(@N) . "\n";
    @N = (4, 1, 7, 6);
    print largest_multiple_2(@N) . "\n";
}

Sample Run

$ perl perl/ch-2.pl
6210
8412
7614

Notes

Suppose we did not have the "multiple of 2" restriction and instead had to arrange a list of numbers to have maximal value when concatenated together. The solution, then, would be to sort the numbers in descending order and concatenate the digits in this sorted order.

Here we can still use that same logic but more care is needed.

First, let's remind ourselves that we can check to see if any number is a multiple of 2 by checking if it's rightmost digit is a multiple of 2 (including 0).

• We need to make sure we have at least one digit which is a multiple of 2. If not, then there is no need to continue.
• Sort the numbers, but then inspect the final digit in descending order. Is it a multiple of 2? If so, then we are done!
• If the final digit is not a multiple of 2 then search the sorted list starting from the final digit and working "upwards". We had previously made sure we had at least one multiple of 2 so we are certain to find one. When we find it we need to swap it with the final digit to insure that the entire number itself is a multiple of 2.

References

Challenge 115

Pokemon Name Ladder

Weakly Connected Component

Regarding his RakuAST Grant, Jonathan Worthington reports some awesome progress for May 2021.

Side note: due to a bug in the Markdown rendering in this blog post, the less-than and greater-than characters in code blocks are double-encoded. Please refer to this gist for a correctly rendered version.

Anyway, here is Jonathan's report:

During May I focused on filling out the regex part of RakuAST, with the result that the majority of the constructs found in Raku regexes now have AST nodes and can be compiled by the RakuAST-based compiler frontend. Of note, I did AST nodes for:

• Declarations in regexes (:my $foo)
• Code-based assertions (and)
• The \e, \f, \h, \r, \t, \v, and \0 escape sequences
• Character classes, including the common <[a..z_]> style, Unicode properties (<:l>), rules <+rulename>, and the combination of these using + and -
• Regex code evaluation (<{ ... }&>)
• Variable interpolation, both as data ($x) and in an assertion syntax as code (<$code>)
• Internal modifiers (:i, :m, etc.)
• Calls to lexical rules (<&rulename>), including passing of arguments

Furthermore, I corrected a mistake in handling of backtracking modifiers, and added a missing action method in the new compiler frontend that blocked regexes passing arguments from compiling.

Away from the regex language itself, I:

• Implemented a mechanism for an AST node to specify it would like to participate in CHECK time and report problems
• Implemented construction and collection of typed exceptions, both at CHECK time, but also so that the new compiler frontend can produce them. Probably some things that are done in the compiler frontend might want to become CHECK-time things in the AST nodes, since they can happen in synthetically constructed programs too. Those that are purely syntactic are often not possible to represent in the AST.
• Added RakuAST nodes for token/rule declarations, so that grammars can now be expressed and compiled in RakuAST (without protoregexes so far, however)
• Correctly set the scope on routine declarations
• Added missing operator properties for bitshifts, so they can be compiled

All of this work won a rather underwhelming 17 extra fully passing spectest files; as has been previously noted, the test files are quite good at depending on a lot of language features.

The Grants Committee has received the following grant proposals for the May 2021 round: * Raku Dispatch and Compiler Improvements * Persistent Data Structures for Raku

Before the Committee members vote on any proposal, we like to solicit feedback from the Perl and Raku communities.

Review the proposals at their individual links and please comment there by June 6, 2021. The Committee members will start the voting process following that and the conclusion will be announced shortly after.

Stats

Number of new CPAN distributions this period: 95

Number of authors releasing new CPAN distributions this period: 44

Authors by number of new CPAN distributions this period:

Hi there

First things first, I am a big fan of OOP in general. However I do agree OOP is not always the best choice. Since Perl promotes the idea of TIMTOWTDI (There's more than one way to do it), we have plenty of options to pick from. I have come across many Perl haters in the past complaining about lack of proper OOP support in Perl. With the introduction of postmodern object system for Perl, Moose, we finally had structured OOP support. I must confess I prefer Moo which is known as minimalist object orientation.

Fast forward to now, Curtis Poe joined hands with other Perl masters and came up with Corinna. It is proposed to be part of core Perl soon. I can't wait for that to happen. I sincerely applaud the efforts of each and every contributor of Corinna. I beleive it will be the best addition to the Perl core in recent times. I am confident it will be the highlight of the future Perl7.

In the last week edition of the weekly newsletter, Gabor reminded me that I forgot to celebrate the special 512th edition. What a shame, I missed the opportunity. I blame my busy routine for the missed opportunity. I am looking forward to my personal 100th edition of the weekly newsletter. This is the 79th edition for the record, not far off from the target.

Happy to see, the COVID-19 situation in India is getting better. I pray to ALLAH s.w.t for the complete protection from COVID-19. Please look after yourself and your loved ones.

To all our readers in the UK, enjoy your bank holiday with the weekly newsletter.

The 7th part of the live development course management application using Mojolicous together with Mark Gardner.

Name

Daniel Sockwell

Synopsis

Immutable, persistent data structures give a program certain superpowers that it's very hard to have in any other way: they allow the program to "time travel" (view previous application state); they allow let the program share data across threads or asynchronously save it to disk without needing locks; they enable a much more purely functional style of programming – which results in code that many software developers find much easier to reason about. Because of these benefits, many languages with strong support for functional programming (Clojure, Elm, Haskell, etc) offer persistent data structures in their standard library. And many multiparadigm languages that attempt to support programming in a fuctional style (C++, JavaScript, Java, Rust, Go, etc.) have well-maintained and popular libraries offering persistent data structures.

However, despite these benefits and despite the extremely strong support Raku generally provides for functional programming, Raku does not provide any persistent data structures, either in core or in a library. I am therefore seeking a grant to create a persistent data structures library for Raku.

If this grant is funded, I will build this library as an external module that can be used as soon as I have completed it. Additionally, I will structure the module in such a way that it can later be upstreamed into Rakudo if we decide that persistent data types are valuable enough to include in Roast/the core language (though accepting this grant proposal would, of course, not commit Raku to adding these types, and the types would provide most of the same benefits as a standalone library).

The Problem

As part of its support for functional programming, Raku provides several immutable data types – most notably, Lists, Maps, and Sets. These types work well, but they suffer from two well-known problems: (1) shallow clones with interior mutability and (2) expensive copies.

The problem of interior mutability can be seen in the following code

my Map $m1 = :key[].Map;
my Map $m2 = $m1.clone; 
$m2<key>.push: 2;
say $m1; # OUTPUT: «Map.new((key =&gt; [2]))»

That is, neither immutability nor clones are deep, so changes to $m2 end up causing changes to $m1. This behavior is not a bug; it is the intentional (and correct) consequence of the semantics of immutable types, Scalars, and clone. This correct behavior, however, negates much of the benefit that deeply immutable types can provide in terms of reasoning about the code and safely sharing data between threads.

You can overcome this problem (albeit at the cost of some verbosity) by manually deep-cloning data and/or ensuring that all the components of a type are themselves immutable. However, solving this problem leads you directly to the second: a deep clone of an immutable object is very expensive, because it involves literally copying the entire object (even if the copy is only slightly different). This makes using large immutable objects in Raku much slower than using their mutable equivalents.

Because copying immutable data structures is both syntactically annoying and computationally expensive, copying data is a less appealing prospect in Raku than in languages with persistent data structures. This, in turn, means that Raku programs are less likely make immutable copies of data and are more likely to share access to a mutable copy. This is a shame in any context, because it makes code harder to reason about and thus more likely to contain bugs. But it's especially problematic in concurrent programs – when programs share (rather than copy) data between threads, they have to use locks, which is both slower and more cumbersome. Since Raku otherwise offers excellent support for concurrent programming, the expense of copying large data structures is a real problem.

The Solution

I mentioned that the problems of interior mutability and expensive copies are well known and, fortunately, they also have a well-known solution: persistent data structures that provide structural sharing. The basic idea is that when you copy an immutable object, you don't need to literally copy all the data in it, you just need to point back to the copied object (which can't change because it's immutable). Then, the copy only needs to remember and ways it differs from the original rather than the entire object. (At a high level, this is similar to how some version control systems or commands work – for example, with git-send-email, you don't send a new copy, just a patch).

Many early persistent data structures provided these benefits, but only at an unacceptably high cost. For example, a linked-list qualifies as a persistent data structure because you can add a node to the list without mutating it and multiple modified "copies" of a linked list can share much of their data without making literal copies (aka "tail sharing"). However, the performance profile of a linked list (especially its lack of cache coherence, given the relative cost of a cache miss on modern hardware) make it an extremely poor fit for most general purpose programming tasks today.

However, in the past two decades, a new bread of persistent data structures have been developed – and these new structures combine the safely and cheap copying of previous data structures with a much-improved performance profile.

Prior Art

I have no interest in reinventing the wheel and persistent data structures have a long history both in academic computer science and in practical language implementations. Most notably, Phil Bagwell described a practical design for a persistent data structures in a 2001 paper titled Idle Hash Trees. This design describes a specific data structure called a Hash Array Mapped Trie. Here's a simplified description of how a HAMT works:

• create a tree where each node contains either
  • a sparse array of length 32 with references to further nodes.
  • a final value (i.e., it's a leaf node).
• To store the values of an array into the tree created above, parse the index of each element as a base 32 number and then convert that number into a list of digits. Starting at the root of the tree, look at the array element that matches the value of the last digit and go to (or create) the node referenced by that element. When you have done so, remove the digit from your list and repeat. Once you are out of digit, store the value in the current node.
• ^^^^ created a binary Trie, hence the name.
• Storing the values of a Hash is similar, except that the hash key must first be hashed into a 32 bit integer and the final nodes need to be buckets to handle hash collisions.
• This data structure is immutable, but supports creating a copy with certain values added (or deleted). Doing so only requires copying the nodes in the path from the root node to the inserted/deleted/changed node; the rest of the tree (which is unchanged) is shared between the copies.
• Note that the above omits some details, such as the use of a bitmap & dense array in place of the sparse array. For a more detailed explanation of how this works, refer to either the original paper or to https://hypirion.com/musings/understanding-persistent-vector-pt-1

In algorithmic terms, this data structure provides access to nodes in O(log₃₂(n)) time. A very pedantic academic might say that this should still be considered O(log(n)) time, but in practice it is much closer to O(n) – an HAMT with 6 levels can store over a billion items. Memory use (compared to full copying) is reduced by a similar factor.

In 2007, Clojure was released with HAMT-based persistent data structures backing all of its fundamental collection types. Since then, HAMT-based data structures have been developed for many languages, either as a core part of the language or as a third-party library.

While Raku does not have HAMT-based (or any) persistent data structures, it does have a few related features. First, it has strong support for laziness which can, in some cases, give Lists/Arrays performance gains similar to those they would get from a persistent data structure (Jonathan Worthington helpfully explained this distinction to me on StackOverflow: https://stackoverflow.com/a/67035827/10173009). This does not apply in all cases and does not apply at all to Hashes/Maps/Sets/etc. Second, Rakudo currently implements the Str type in a way that has some conceptual similarities to persistent data structures, though it does not offer the same guarantees and that implementation is not required by the Raku specification. Third, Jonathan Worthington has also implemented a trio of concurrent data structures that use tail sharing (a similar technique for creating persistent data structures). These modules – and, in particular, the Concurrent::Trie module – could be useful when implementing HAMT based data structures.

Given this prior art, implementing HAMT-based data structures will have a clear roadmap, even if much implementation work remains to be done.

Deliverables

The primary deliverable from this grant would be a collection of persistent data types based on Hash Array Mapped Tries (which, for type-naming purposes, I tentatively plan to refer to as Hash Array-mapped Tries, yielding the abbreviation 'Hat' rather than 'HAMT'). I would plan to deliver some or all of the following (time/budget permitting, as discussed in the schedule below), along with corresponding pod6 documentation suitable for future inclusion on docs.raku.org and corresponding tests suitable for future inclusion in Roast:

• ListHat (persistent Array)
• MapHat (persistent Hash)
• SetHat (persistent SetHash)
• BagHat (persistent BagHash)
• MixHat (persistent MixHash)

(Note: I don't love these names, since being backed by a HAMT is an implementation detail. But I would like to find a name that's short and memorable enough to make the types easy to use; "PersistentList"s seem unlikely to get much use. I'm open to ideas here.)

This covers the Raku collection types other than Pairs; creating new Pairs is already simple enough that creating a PairHat type would be pointless

Time permitting, I would also deliver benchmarks comparing the performance of the *Hat types with that of the corresponding deeply copied immutable types.

Project Details

Proposed API for deliverable types

In general, when implementing immutable types, the copying API can be designed along two lines: it can either require the user to use explicit copying operations, or it can offer an API that mirrors the API of mutable types but that returns a new value rather than mutating one in place. The current Raku immutable types provide an API of the first type. This API allows code like:

my List $list = (1, 2, 3);
my $new = |$l, |(4, 5, 6);  # correct
my $new = $l.push: 4, 5, 6; # NO - throws an error

This design choice makes sense for the existing immutable types, given that they don't provide inexpensive copying and that Raku's | operator makes combining collections easier. It also helps new users more quickly realize the difference between mutable and immutable types. However, even with the | operator, creating copies of immutable types can become syntactically cumbersome, especially if the type might be empty.

# mutable
class Foo {
    has @!values;
    method add($val) { @!values.push($val) }
}

# immutable 
class Bar {
    has List $!values;
    method add($val) { $!values = (|($!values // Empty), |($val // Empty)) }
} 

Again, this tradeoff makes sense for the existing types because copies are relatively expensive and so it makes sense to have syntax that implicitly discourages their use in non-trivial cases. However, since the *Hat types are designed for inexpensive copies, it makes sense to provide the second type of API:

my ListHat $l = (1, 2, 3);
my $new = $l.push: 4, 5, 6;

This approach is similar to the one taken by many libraries that add persistent data structures to languages that aren't purely functional; as one example, immutable.js. In other languages, this has the downside of creating a trap:

my Array $a = 1, 2, 3;
$a.push: 4; # works
my ListHat $l = 1, 2, 3;
$l.push: 4; # seems to work, but actualy does nothing

However, Raku offers the is pure trait; by implementing the relevant methods for the *Hat types with that trait, the incorrect line would generate a warning that a pure function was used in sink context.

I would also plan to offer an API for "batching" operations (which lets the data structure improve performance by skipping intermediate copies). I'm less sure of this part of the API, but think that an API similar to the one provided by Immer could be a good fit:

my MapHat $m = (:key1<val1> :key2<val2>);
my $m2 = $m.next: $draft -&gt; { $draft<key2> = 'new val' };
# Or, more concisely
my $m3 = $m.next: *<key2> = 'new val';
# $m2 and $m3 are both {:key<val1> :key2('new val')}

(This API is inspired by the JavaScript Immer, not the identically-named-but-unrelated C++ library, which provides a more traditional batch API based on a .commit method)

Of course, I am sure I will learn more in the course of the implementation, so all of the APIs shown above could change/evolve, but I present it here as a general guideline.

Limitations on scope

To keep the project limited in scope, there are two sets of features that I explicitly do not plan to include in the work for this grant (though either could be added later on).

First, I do not plan to implant the CHAMP optimizations to the HAMT data structure. This optimization, which was described in the academic literature in 2015, further reduces memory use and increases the data's cache locality (which, given the relative significance of cache misses on modern CPUs, provides a speed boost as well). However, it also significantly increases the implementation complexity. Perhaps because of that complexity or perhaps just because it was more recently presented, CHAMPs have not been as widely implemented in non-academic settings. Moreover, adding the CHAMP optimizations would not change the overall performance profile, appropriate uses, or API of the data structure, so we could add it later if we determine that the performance gains justify the added complexity.

Similarly, I do not plan to implement the *Hat types in a way that requires them to be included in Rakudo. As illustrated by Jonathan Worthington's Concurrent::Stack, Concurrent::Queue, and Concurrent::Trie data structures, it is entirely possible to implement performant Raku data structures entirely is userland code, and I plan to follow that approach.

It's possible that integrating more tightly with the compiler/VM could further increase performance. However I believe that it makes sense to defer that work until a working userland implementation proves the value of persistent data types via an external library. Creating an external library will also allow users to provide feedback on the *Hat types earlier and, if necessary, allow us to evolve their API without breaking Raku's stability guarantees.

Proposed Schedule and Grant Amount

I propose to work on this grant for 10 hours/week for 14 weeks our until the completion of all deliverables described above and to work for a reduced rate of $50/hour. Thus, I am seeking a grant of up to $7,000 (or less, if the implementation is completed before the end of the 14 weeks).

Benefits to the Raku Community

As mentioned above, adding persistent data types to Raku would have multiple benefits. First and most directly, these types would significantly improve the performance of Raku code that uses immutable data. Second, the new types would provide a more ergonomic API for copying immutable types.

Together, these two direct benefits would encourage Raku programmers to make greater use of immutable types and other functional programming idioms. This, in turn, would generally increase the likelihood that any given Raku module is robust and thread-safe (even if it was not written with thread safety in mind). Increased thread safety will help make the Raku ecosystem more suitable for concurrent workloads (already a strength, given Raku's strong concurrency and parallelism primitives and the existence of excellent concurrent modules such as Cro).

In addition to these practical benefits, adding these types (especially if they are eventually added to core Raku) will help in Raku's marketing/adoption efforts. Languages that have implemented persistent data types include Clojure, Elm, Haskell, and Scala; all of these languages are (1) functional and (2) modern – two traits that it would be both helpful and accurate for more developers to associate with Raku.

Finally, on a more personal note, this grant would benefit a project for which I am not seeking funding. I am independently working on Épée, a web framework for Raku inspired by React, Svelte, Pollen, and Hoplon (and both inspired by and designed to integrate smoothly with Cro). Épée uses immutable data via deep copies and thus would see performance benefits from my work on this grant. I mention this both as a benefit of the grant and to say that, although Épée would benefit from this grant, that benefit would not be high enough to make implementing these data structures worthwhile if the grant is not accepted (that is, I am not seeking a grant for work that I plan to do anyway!). I believe that my perspective as a future user of the API with a concrete use-case in mind would prove helpful during my work on this grant.

Biography

I am a contributor to Rakudo, Roast, and the Raku documentation; I serve on the Raku Steering Council and the Yet Another Society Legal Committee. Prior to becoming a programmer, I was a practicing attorney at Davis Polk & Wardwell, one of the top law firms in New York City – but decided to become a software developer after helping the firm build a web application that dealt with data breach law. I have used JavaScript and Rust professionally, but now focus primarily on writing free software in Raku.

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

You are given a positive integer $N. Write a script to find out the next Palindrome Number higher than the given integer $N.

Solution

use strict;
use warnings;
sub next_palindrome{
    my($n) = @_;
    {
        $n++;
        return $n if $n eq join("", reverse(split(//, $n)));
        redo;
    }
}

MAIN:{
    my($N);
    $N = 1234;
    print next_palindrome($N) . "\n";
    $N = 999;
    print next_palindrome($N) . "\n";
}

Sample Run

$ perl perl/ch-1.pl
1331
1001

Notes

This is probably the most straight forward approach to this task. Here we iterate upwards from our starting point and check each number using reverse. Since we are guaranteed of eventually finding a palindrome the loop is done (via redo) without any exit criteria or bounds checking other than returning when one is found.

Part 2

You are given a positive integer $N. Write a script to find the next higher integer having the same number of 1 bits in binary representation as $N.

Solution

use strict;
use warnings;
sub count_bits{
    my($n) = @_;
    my $total_count_set_bit = 0;
    while($n){
        my $b = $n & 1;
        $total_count_set_bit++ if $b;
        $n = $n >> 1;
    }
    return $total_count_set_bit;
}

sub next_same_bits{
    my($n) = @_;
    my $number_bits = count_bits($n);
    {
        my $next = $n + 1;
        return $next if count_bits($next) == $number_bits;
        $n = $next;
        redo;
    }
}

MAIN:{
    my($N);
    $N = 3;
    print next_same_bits($N) . "\n";
    $N = 12;
    print next_same_bits($N) . "\n";
}

Sample Run

$ perl perl/ch-2.pl
5
17

Notes

The count_bits subroutine is based on code written for Challenge 079. Otherwise, the approach to this task is very similar to what was done in the first one this week.

References

Challenge 114

Welcome to the latest ‘The Perl and Raku Conference in the Cloud’ newsletter.

This issue: * The schedule is available * Submit a Lightning Talk * Volunteers needed ( virtual moderators, hosts ) * Do you want to host a virtual BoF? * Order your conference shirt * About the Conference in the Cloud * Get your tickets * How to Reach Us

See you real soon

The conference is in just 2 weeks! We're really looking forward to seeing everyone again. We’ve got a lot of great talks lined up! The schedule is available on our website.

Give a Lightning Talk

Lightning Talks are short, 5 minute, talks that may be serious, funny, or both. They may be given by experienced speakers already giving full length talks or by first time speakers just starting out (this is a great way to get started if you have something to say). Adding the virtual component to lightning talks should add for some extra fun! If you are a first time speaker you will win a tie with an experienced speaker when the schedule is made, if it comes to it. Today’s first time speaker could be tomorrow’s keynote speaker! Sign up here.

Volunteers Needed

The Conference in the Cloud needs some volunteers! Email admin@perlconference.us to volunteer. Right now we need volunteers to help moderate rooms and coordinate day-of things: * Room moderators - Monitor the chat and help coordinate audience participation during a virtual presentation. * Room Hosts - Help coordinate speakers and manage the live stream to YouTube

Host a Birds of a Feather (BoF)

Do you have a topic you'd like to host for a virtual Birds of Feather (BoF) meeting? We'd love to help! Virtual meeting space will be reserved for BoFs on a first come, first served basis.

Start by proposing and then promoting your BOF on the conference wiki. TPRC staff is happy to help facilitate a meeting space if you need it. Just reach out to us on TPF Slack or email us at admin@perlconference.us

Order your conference shirt

We designed a logo and we’re sharing it with the community! Order a shirt or other cloud conference items at CafePress. We aren’t making any money (neither is TPF) on these products but we have designed a logo if you’d like to buy a momento!

About the Conference in the Cloud

The 2021 Perl and Raku Conference in the Cloud will be on June 8-10. If you see #TPRCiC around on social media, that’s our tag for the conference. At the Conference in the Cloud there will be Perl, Raku, and other related technology topics, just like you’ve seen at our in-person conferences. The Conference in the Cloud is organized and run by volunteers just like The Perl and Raku Conference. Presentations are also given by volunteers. The presentations at the conference were submitted during our Call For Presentations (CFP) and selected by organizers who volunteered to be on our talks-committee. We will have 2 or more tracks at this event with presentations (20-50 minutes long) on a variety of technical topics throughout each day.

Registration Cost

By paying a $10 fee attendees can interact live with speakers and other attendees (during BOFs, panels, and Q&A). The $10.00 fee is inclusive of the entire event. This fee helps secure a safe event, and covers the minor costs of hosting it.

Conference Time

In order to accommodate the most time zones possible, we have decided to go with 11AM to 6PM EDT or 15:00 to 22:00 UTC. Sched now supports time zones in their interface. Be sure to login and select your time zone!

Hosting Platform

The Perl and Raku Conference in the Cloud (TPRCiC) is going to be an online, interactive event hosted on the Zoom platform. The broadcast will be recorded and streamed simultaneously to YouTube.

Access to the interactive conference on Zoom will only be granted to people who register in advance, agree to the Code of Conduct, and pay a $10 registration fee for the whole conference. Presentations will be streamed live to YouTube so those who can’t pay the fee or won’t use Zoom, can still access most conference content. BOFs will not be available on YouTube.

Get Your Ticket

Event tickets are available on eventbrite for $10. The $10.00 fee is inclusive of the entire 3-day event. This fee helps secure a safe event, and covers the minor costs of hosting it. Sign up today!

How to Reach #TPRCiC Organizers

• Visit our website: https://perlconference.us/
• Follow us on Twitter: @PerlConferences
• Like us on Facebook: The Perl Foundation (@tpf.perl)
• Subscribe to the mailing list: https://perlconference.us/tprc-2021-cloud/keep-in-touch/
• Send any questions about The Perl Conference to admin@perlconference.us. An organizer will get back to you.

In Part 1, I compared Perl’s regexp features with sed and Awk. In this concluding part, I’ll cover examples that make use of Perl’s extensive built-in features and third-party modules.

Bigger library

Perl has a much bigger collection of built-in functions compared to Awk. For command-line usage, I often need tr, join, map and grep. I like that arrays and hashes are distinct in Perl and applying sort on these data types is much simpler compared to Awk.

Append items to a list

This problem wants to append columns to rows that have too few, like the b, c and d rows:

a,10,12,13
b,20,22
c,30
d,33

This appends zeros to list by using the /e again. This time, the Perl in the replacement counts the number of commas, and subtracts that from 3 to find out how many more columns it needs. The x is the string replication operator:

$ perl -pe 's|$|",0" x (3 - tr/,//)|e' ip.txt
a,10,12,13
b,20,22,0
c,30,0,0
d,33,0,0

Reversing things

In reverse complement DNA sequence for a specific field, I need to select part of the string, complement it, and turn it around. I want to work on the third column:

ABC DEF GATTAG GHK
ABC DEF GGCGTC GHK
ABC DEF AATTCC GHK

I use the tr and reverse in the replacement side (with /e again):

$ perl -pe 's/^(\H+\h+){2}\K\H+/reverse $&=~tr|ATGC|TACG|r/e' test.txt
ABC DEF CTAATC GHK
ABC DEF GACGCC GHK
ABC DEF GGAATT GHK

Alternatively, I can use -a, which automatically splits on whitespace and puts the result in @F. I work on the third element then output @F again:

$ perl -lane '$F[2]=reverse $F[2]=~tr/ATGC/TACG/r; print "@F"' test.txt
ABC DEF CTAATC GHK
ABC DEF GACGCC GHK
ABC DEF GGAATT GHK

Sort a CSV row

How about sorting rows in csv file without header & first column? Here’s some simple comma-separated values:

id,h1,h2,h3,h4,h5,h6,h7
101,zebra,1,papa,4,dog,3,apple
102,2,yahoo,5,kangaroo,7,ape

I use -a again, but also -F, to make comma as the field separator:

$ perl -F, -lane 'print join ",", $.==1 ? @F : (shift @F, sort @F)' ip.txt
id,h1,h2,h3,h4,h5,h6,h7
101,1,3,4,apple,dog,papa,zebra
102,2,5,7,ape,kangaroo,yahoo

The $. variable keeps track of the input line number. I use this to skip the first line (the header). In all other lines, I make a list of the first element of @F and the sorted list of the rest of the elements. Note that the numbers to be sorted in this example have the same number of digits, otherwise it wouldn’t work.

Insert incremental row and column labels

Insert a row and a column in a matrix needs to add numerical labels with a fixed interval:

2 3 4 1 2 3
3 4 5 2 4 6
2 4 0 5 0 7
0 0 5 6 3 8

Here, I use map to generate the header:

$ perl -lane 'print join "\t", "", map {20.00+$_*0.33} 0..$#F if $.==1;
              print join "\t", 100+(0.33*$i++), @F' matrix.txt
        20      20.33   20.66   20.99   21.32   21.65
100     2       3       4       1       2       3
100.33  3       4       5       2       4       6
100.66  2       4       0       5       0       7
100.99  0       0       5       6       3       8

# with formatting and alternate way to join print arguments
$ perl -lane 'BEGIN{$,="\t"; $st=0.33}
              print "", map {sprintf "%.2f", 20+$_*$st} 0..$#F if $.==1;
              print sprintf("%.2f", 100+($st*$i++)), @F' matrix.txt
        20.00   20.33   20.66   20.99   21.32   21.65
100.00  2       3       4       1       2       3
100.33  3       4       5       2       4       6
100.66  2       4       0       5       0       7
100.99  0       0       5       6       3       8

Using Perl modules

Apart from built-in functions, Standard or CPAN modules come in handy too. Load those with -M and put the import list after a =:

# randomize word list after filtering
$ s='floor bat to dubious four pact feed'
$ echo "$s" | perl -MList::Util=shuffle -lanE '
                    say join ":", shuffle grep {/[au]/} @F'
bat:four:pact:dubious

# remove duplicate elements while retaining input order
$ s='3,b,a,3,c,d,1,d,c,2,2,2,3,1,b'
$ echo "$s" | perl -MList::Util=uniq -F, -lanE 'say join ",", uniq @F'
3,b,a,c,d,1,2

# apply base64 decoding only for a portion of the string
$ s='123 aGVsbG8gd29ybGQK'
$ echo "$s" | perl -MMIME::Base64 -ane 'print decode_base64 $F[1]'
hello world

CPAN

The Comprehensive Perl Archive Network (CPAN) has a huge collection of modules for various use cases. Here are some examples.

Extract IPv4 addresses

The Regexp::Common has recipes for common things you want to match. Here’s some text with dotted-decimal IP addresses:

3.5.52.243 555.4.3.1 34242534.23.42.42
foo 234.233.54.123 baz 4.4.4.3123

It’s easy to extract the IPv4 addresses:

$ perl -MRegexp::Common=net -nE 'say $& while /$RE{net}{IPv4}/g' ipv4.txt
3.5.52.243
55.4.3.1
34.23.42.42
234.233.54.123
4.4.4.31

I can match only if the IPv4 address isn’t surrounded by digit characters, so I don’t match in the middle of 34242534.23.42.42:

$ perl -MRegexp::Common=net -nE '
        say $& while /(?<!\d)$RE{net}{IPv4}(?!\d)/g' ipv4.txt
3.5.52.243
234.233.54.123

Real CSV processing

Earlier I did some simple CSV processing, but if I want to do it for real I can use Text::CSV_XS to make sure everything happens correctly. This one handles the quoted field fox,42:

$ s='eagle,"fox,42",bee,frog\n1,2,3,4'

# note that neither -n nor -p are used here
$ printf '%b' "$s" | perl -MText::CSV_XS -E 'say $row->[1]
                     while $row = Text::CSV_XS->new->getline(*ARGV)'
fox,42
2

Processing XML

Processing XML files is another format that’s easy to mess up. Many people try to do this with regexp, but that can easily go wrong. Here’s an example file:

<doc>
    <greeting type="ask">Hi there. How are you?</greeting>
    <greeting type="reply">I am good.</greeting>
    <color>
        <blue>flower</blue>
        <blue>sand stone</blue>
        <light-blue>sky</light-blue>
        <light-blue>water</light-blue>
    </color>
</doc>

The xpath (a Perl program) and xmllint can be used for processing XML files:

$ xpath -e '//blue/text()' sample.xml
Found 2 nodes in sample.xml:
-- NODE --
flower
-- NODE --
sand stone
$ xpath -q -e '//blue/text()' sample.xml
flower
sand stone

$ xmllint --xpath '//blue/text()' sample.xml
flower
sand stone

Using the XML::LibXML module will help if you need Perl’s power:

$ perl -MXML::LibXML -E '
    $ip = XML::LibXML->load_xml(location => $ARGV[0]);
    say $_->to_literal() for $ip->findnodes("//blue")' sample.xml
flower
sand stone

$ perl -MXML::LibXML -E '
    $ip = XML::LibXML->load_xml(location => $ARGV[0]);
    say uc $_->to_literal() for $ip->findnodes("//blue")' sample.xml
FLOWER
SAND STONE

Processing JSON

JSON files have the same issue. You don’t want to do regexes on this:

$ s='{"greeting":"hi","marks":[78,62,93],"fruit":"apple"}'

Various JSON modules, such as Cpanel::JSON::XS can handle this. For example, pretty printing:

$ echo "$s" | cpanel_json_xs
{
   "fruit" : "apple",
   "greeting" : "hi",
   "marks" : [
      78,
      62,
      93
   ]
}

And here’s a particular selection:

$ echo "$s" | perl -MCpanel::JSON::XS -0777 -E '$ip=decode_json <>;
              say join ":", @{$ip->{marks}}'
78:62:93

Sometimes it’s easier to put that in a script (although that’s not really a one-liner anymore). I use a Bash function as a shortcut:

$ pj() { perl -MCpanel::JSON::XS -0777 -E '$ip=decode_json <>;'"$@" ; }

$ echo "$s" | pj 'say $ip->{fruit}'
apple
$ echo "$s" | pj 'say join ":", @{$ip->{marks}}'
78:62:93

A non-Perl example of the same thing is jq, but that’s something you have to install separately and might not be available:

$ echo "$s" | jq '.fruit'
"apple"
$ echo "$s" | jq '.marks | join(":")'
"78:62:93"

Speed

Perl is usually slower compared to specialized tools, but the regexp engine performs better for certain cases of backreferences and quantifiers.

$ time LC_ALL=C grep -xE '([a-z]..)\1' /usr/share/dict/words > f1
real    0m0.074s

$ time perl -ne 'print if /^([a-z]..)\1$/' /usr/share/dict/words > f2
real    0m0.024s

$ time LC_ALL=C grep -xP '([a-z]..)\1' /usr/share/dict/words > f3
real    0m0.010s

Perl’s hash implementation performs better compared to Awk’s associative arrays for large number of keys. The SCOWL-wl.txt file used below was created using app.aspell.net. words.txt is from /usr/share/dict/words. Mawk is usually faster, but GNU Awk does better in this particular case.

$ wc -l words.txt SCOWL-wl.txt
  99171 words.txt
 662349 SCOWL-wl.txt
 761520 total

# finding common lines between two files
# Case 1: shorter file passed as the first argument
$ time mawk 'NR==FNR{a[$0]; next} $0 in a' words.txt SCOWL-wl.txt > t1
real    0m0.296s
$ time gawk 'NR==FNR{a[$0]; next} $0 in a' words.txt SCOWL-wl.txt > t2
real    0m0.210s
$ time perl -ne 'if(!$#ARGV){$h{$_}=1; next}
                 print if exists $h{$_}' words.txt SCOWL-wl.txt > t3
real    0m0.189s

# Case 2: longer file passed as the first argument
$ time mawk 'NR==FNR{a[$0]; next} $0 in a' SCOWL-wl.txt words.txt > f1
real    0m0.539s
$ time gawk 'NR==FNR{a[$0]; next} $0 in a' SCOWL-wl.txt words.txt > f2
real    0m0.380s
$ time perl -ne 'if(!$#ARGV){$h{$_}=1; next}
                 print if exists $h{$_}' SCOWL-wl.txt words.txt > f3
real    0m0.351s

Other things to read

• My ebook on Perl one-liners

• Awesome Perl has a curated list of awesome Perl5 frameworks, libraries and software

• Perl XML::LibXML by example for a detailed book on XML::LibXML module

[image from Riccardo Maria Mantero on Flickr, (CC BY-NC-ND 2.0)]

Hi there!

I am disappointed. Mohammad does not like round numbers. He was editing both the 500th edition and the 512th edition and nothing. He did not even blink an eye. I hope he will not forget to celebrate the 1024 edition.

On another note, perl 5.34.0 was released.

I am not saying it is easy, but I really enjoy the live pair programming sessions with Mark Gardner, Upasana Shukla, Juan J. Merelo, Erik Hulsmann, Ferenc Erki, Thomas Klausner, Ynon Perek people whom I know from the Perl community and also Shai Berger, Ivett Ördög, Rachel Normand, Tally Barak, and Laia Asensio López, people I know from other places. One day you might also want to find a partner and try it. It is nice to work with other people who think differently from you.

Enjoy your week

The 6th part of the live development course management application using Mojolicous together with Mark Gardner.

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

You are given a positive integer $N and a digit $D. Write a script to check if $N can be represented as a sum of positive integers having $D at least once. If check passes print 1 otherwise 0.

Solution

use strict;
use warnings;
sub is_represented{
    my($n, $d) = @_;
    my @contains = grep { grep { $_ == $d } split(//) } (1 .. $n);
    return $n == unpack("%32C*", pack("C*",  @contains));
}

MAIN:{
    print is_represented(25, 7) + 0 . "\n";
    print is_represented(24, 7) + 0 . "\n";
}

Sample Run

$ perl perl/ch-1.pl
0
1

Notes

I've been trying to avoid using regexes in these challenges recently, to help promote some increased creativity. Here I use a nested grep to determine which numbers contain the digit $d.

I also use one of my favorite ways to sum a list of numbers using unpack and pack!

By default the false value in the first example will print as an empty string. The + 0 forces a numification to 0 (or 1 too) which then stringifies to what we expect.

Part 2

You are given a Binary Tree. Write a script to replace each node of the tree with the sum of all the remaining nodes.

Solution

use strict;
use warnings;
use Graph;
use Graph::Easy::Parser;

sub dfs_update{
    my($graph, $vertex, $graph_updated, $previous) = @_;
    my @successors = $graph->successors($vertex);
    for my $successor (@successors){
        my $sum_remaining = sum_remaining($graph, $vertex);
        $graph_updated->add_edge($previous, $sum_remaining) if $previous;
        dfs_update($graph, $successor, $graph_updated, $sum_remaining);
    }
    $graph_updated->add_edge($previous, sum_remaining($graph, $vertex)) if !@successors;
}

sub sum_remaining{
    my($graph, $visited) = @_;
    my $sum = 0;
    for my $vertex ($graph->vertices()){
        $sum += $vertex if $vertex != $visited;
    }
    return $sum;
}

sub display_graph{
    my($graph) = @_;
    my $s = $graph->stringify();
    my @s = split(/,/, $s);
    my @lines;
    for my $n (@s){
        my @a = split(/-/, $n);
        push @lines, "[ $a[0] ] => [ $a[1] ]";
    }
    my $parser = new Graph::Easy::Parser();
    my $graph_viz = $parser->from_text(join("", @lines));
    print $graph_viz->as_ascii();
}

MAIN:{
    my $graph = new Graph();
    my $graph_updated = new Graph();
    my $root = 1;
    $graph->add_edge($root, 2);
    $graph->add_edge($root, 3);
    $graph->add_edge(2, 4);
    $graph->add_edge(4, 7);
    $graph->add_edge(3, 5);
    $graph->add_edge(3, 6);
    dfs_update($graph, $root, $graph_updated);
    display_graph($graph);
    display_graph($graph_updated);
}

Sample Run

$ perl perl/ch-2.pl
+---+     +---+     +---+     +---+
| 1 | ==> | 2 | ==> | 4 | ==> | 7 |
+---+     +---+     +---+     +---+
  H
  H
  v
+---+     +---+
| 3 | ==> | 5 |
+---+     +---+
  H
  H
  v
+---+
| 6 |
+---+
+----+     +----+     +----+     +----+
| 27 | ==> | 26 | ==> | 24 | ==> | 21 |
+----+     +----+     +----+     +----+
  H
  H
  v
+----+     +----+
| 25 | ==> | 22 |
+----+     +----+
  H
  H
  v
+----+
| 23 |
+----+

Notes

Whenever I work these sort of problems with Trees and Graphs I use the Graph module. My main motivation is to maintain a consistent interface so the code I write is more re-usable for the many problems that can be solved using a graph based approach. The problem at hand is a clear candidate as it is explicitly stated as such. Sometimes, however, graph problems are somewhat in disguise although the use of a graph representation will yield the best solution.

The core of the solution is done via a Depth First traversal of the tree. Each vertex, as it is visited is used to generate a new edge on a tree constructed with the conditions of the problem statement.

The original and updated trees are visualized with Graph::Easy.

References

Challenge 113

Depth First Traversal

Mastering Algorithms with Perl is an excellent book with a very in depth chapter on Graphs.