Originally published at Perl Weekly 695

Hi,

A month from now Randal Schwartz is going to give a presentation with the title "Half My Life with Perl". I tried to come up with a clever title for this issue of the newsletter that would reflect that title and I had to realize that I have been using Perl also for half of my life. It is probably similar for quite a lot of people in the hard-core of the Perl communities. Many have moved on to other languages. Some of those still have a nostalgic feeling for their 'first love' in the 'good old days'.

It is sad to see the decline in popularity. I remember the time when we had several conferences and workshops every year and hundreds of active Perl Monger groups with tens of monthly meetings around the world. Long before Meetup became a thing. Now there are only 18 groups listed and seeing the list of events at the bottom of this newsletter it seems only 3 or 4 are active.

The readership of this newsletter has also declined from a peak of 6,443 subscribers in May 2018 to 4,398 today.

But not all is lost. There are still people working on Perl as you can see from the grants. There are still people uploading libraries to CPAN as you can see from the recent report. There are still some people writing about Perl. There are still some companies using Perl.

Have a nice week!

--
Your editor: Gabor Szabo.

Announcements

Randal Schwartz: Half My Life with Perl

As part of year 25 of The Perl Advent Calendar, Perl luminary and co-author of O'Reilly's "Learning Perl" Randal Schwartz will be giving a presentation entitled "Half My Life with Perl". The presentation takes place on Saturday, Dec 14, 2024.

Articles

A link site of your very own

Another personal project of Dave that made it to CPAN as well. Think about it as a LinkTree clone. reddit

Discussion

Transitioning from Catalyst to Mojo, question about the model

Editing Perl Plug-in For Logitech Media Server

Grants

tony_cook

Maintaining Perl (Tony Cook) September 2024

Maintaining Perl 5 Core (Dave Mitchell): October 2024

Maintaining Perl (Tony Cook) August 2024

PEVANS Core Perl 5: Grant Report for October 2024

Perl

This week in PSC (168) | 2024-11-15 | Perl Steering Council

reddit

The Weekly Challenge

The Weekly Challenge by Mohammad Sajid Anwar will help you step out of your comfort-zone. You can even win prize money of $50 by participating in the weekly challenge. We pick one champion at the end of the month from among all of the contributors during the month, thanks to the sponsor Lance Wicks.

The Weekly Challenge - 296

Welcome to a new week with a couple of fun tasks "String Compression" and "Matchstick Square". If you are new to the weekly challenge then why not join us and have fun every week. For more information, please read the FAQ.

RECAP - The Weekly Challenge - 295

Enjoy a quick recap of last week's contributions by Team PWC dealing with the "Word Break" and "Jump Game" tasks in Perl and Raku. You will find plenty of solutions to keep you busy.

Break the Jump

Trying different approaches until you end up with one that gives the expected result. Thanks for sharing behind the scene story.

Taking A Break From All Your Worries

Clever regex magic is used to get the job done. Smart move, keep it up.

Jumping Words

Simply love the compact solution with lots of magic. Cutest contributions, well done.

loops and substitutions

Welcome back and thanks for sharing knowledge with us every week. My all time favourite is PostgreSQL solution. Keep it up great work.

Perl Weekly Challenge 295

Curious to know the benefit of the use of Memoize in the one-liner. Keep it up great work.

Jump, but Don't Break the Game

Interesting comparison of CPAN module and homemade logic. Pick your choice.

Spaced out jumps

Another good show of recursion where it does the job every efficiently. Keep up the great work.

The Weekly Challenge #295

Cool use of subroutine signature and recursive. Thanks for sharing knowledge with us every week.

Jump and Break

Demo of breadth-first search pattern in Raku for you. Highly recommended.

The Break Game

From Perl and Python expert, here we have mix of both. Easy narrative to follow, keep up great work.

Videos

Chemometrics with Perl & Pharmaceutical Applications

Weekly collections

NICEPERL's lists

Great CPAN modules released last week;
MetaCPAN weekly report;
StackOverflow Perl report.

The corner of Gabor

A couple of entries sneaked in by Gabor.

Improving the (software) development process

This seems to be a generic problem regardless of the programming language, though I wonder how does the age of the programming language and the traditions of the Open Source communities around the language impact this.

Events

Purdue Perl Mongers

December 11, 2024, Virtual event

Boston.pm monthly meeting

December 11, 2024, Virtual event

Randal Schwartz: Half My Life with Perl

December 14, 2024, Virtual event

Perl Community Conference

December 18, 2024, Virtual

Toronto.pm December Social

December 19, 2024, In Person Event

You joined the Perl Weekly to get weekly e-mails about the Perl programming language and related topics.

Want to see more? See the archives of all the issues.

Not yet subscribed to the newsletter? Join us free of charge!

(C) Copyright Gabor Szabo
The articles are copyright the respective authors.

These are my solutions in Perl
for Challenge 295 Tasks 1 and 2 of The Weekly Challenge - Perl and Raku.

Summary

Task 1: Word Break.
A simple regular expression, built from the word list, delivers the solution. Very short, very nice.

Task 2: Jump Game
Implementing an unspectacular 'breadth first search' (BFS) algorithm.

Task 1: Word Break

You are given a string, $str, and list of words, @words.

Write a script to return true or false whether the given string can be segmented into a space separated sequnce of one or more words from the given list.

Example 1

Input: $str = 'weeklychallenge', @words = ("challenge", "weekly")
Output: true

 
Example 2

Input: $str = "perlrakuperl", @words = ("raku", "perl")
Output: true

 
Example 3

Input: $str = "sonsanddaughters", @words = ("sons", "sand", "daughters")
Output: false

We need to recognize words from the input word list in the string, making sure that after each recognized word, another word from the list begins.

That means we are checking whether the string is a sequence of one or more words from the list.
Wait a second...! Checking 'one or more' occurrences of something in a string?
What could be easier than using a regular expression for that?
The 'one or more' part directly translates to a + quantifier.

And the pattern? We form it as a list of alternatives, using the '|' character do separate the choices.

Then, we only have to match the string against our pattern:

use v5.36;

sub word_break( $str, $words ) {
    my $pattern = join "|", $words->@*;
    return $str =~ /^($pattern)+$/;
}

That was an easy one.

Task 2: Jump Game

You are given an array of integers, @ints.

Write a script to find the minimum number of jumps to reach the last element.
$ints[$i] represents the maximum length of a forward jump from the index $i.
In case last element is unreachable then return -1.

Example 1

Input: @ints = (2, 3, 1, 1, 4)
Output: 2
Jump 1 step from index 0 then 3 steps from index 1 to the last element.

 
Example 2

Input: @ints = (2, 3, 0, 4)
Output: 2

 
Example 3

Input: @ints = (2, 0, 0, 4)
Output: -1

Now this one requires some 'real programming'(tm).

First, let's get clear about the game mechanics. The description says:

$ints[$i] represents the maximum length of a forward jump from the index $i.

If we take $ints[$i] == 3 as an example, that means that we can choose to jump to $i+1, $i+2 or $i+3 in that move.
For each of those, the next move continues with the number that we find there.

Trying all possible combinations from the first entry in the list is like building a tree of possible paths. The root node is $int[0]. From there, there is one outgoing branch for every possible jump from there.

To find the 'shortest path' to the last entry, we need to find the shortest path in that tree that leads to a node with the index value of the last entry.

Finding the shortest path in a tree is typically done using a 'breadth first search' (or 'BFS') algorithm. All of the nodes on the same level ('breadth') are checked before any nodes on higher levels. So if one fulfils the end condition (here: it's the index of the last entry in the list), it's garanteed that there are no shorter paths.

A BFS algorithm is not difficult to set up:
We use a queue for the nodes to check.
For the queue entries, we use two-element anonymous arrays, containing the index value, and the length of the path that was needed to reach that node. That makes it easy to return the correct result once we find the shortest path.

We initialize our queue with the index of the first number in the list (which is 0, of course), and the number of jumps needed to get there (0, too!).
This represents the starting point of our tree.

Then we loop over the entries in the queue.
For each entry, we check whether it meets the end condition, and return the path length if it does. Done.

If we haven't reached the last entry yet, we add the next level of possible moves to the queue, making sure we don't add jumps that end beyond the end of the list.
The path length for these new queue entries is one higher than the one that we have so far.

If the queue runs empty, there is no possible path that reaches the last entry. We return the -1 as we should in that case.

use v5.36;

sub jump_game( @ints ) {
    my ( $index, $n_jumps ) = ( 0, 0 );
    my @queue = ( [ $index, $n_jumps ] );
    while ( @queue ) {
        my ( $index, $n_jumps ) = ( shift @queue )->@*;
        return $n_jumps
            if $index == $#ints;
        push @queue,
            map [ $_, $n_jumps + 1 ],
                grep $index <= $#ints,
                    reverse $index + 1 .. $index + $ints[$index];
    }
    return -1;
}

This BFS does not need a 'visited' structure to avoid running into circles. As we only move forward in the list, we don't need to fear running into that problem at all.

I have also created a solution using the Algorithm::Functional::BFS module from CPAN. It hides all the mechanics of the BFS algorithm and uses a functional approach: there are code blocks handed in to the search function, for checking whether a node meets the the end criteria, and for getting the list of successor nodes for a node. These are the only two variable parts of the algorithm.

In fact I found that the code is not significantly shorter when I use that module, because we need to supply the code blocks as parameters, and also set some parameters. So I am quite ok with having written it myself.

Thank you for the challenge!

Find the complete source code for both tasks, including tests and alternative solution implementations, on Github.

Weekly Challenge 295

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Word Break

Task

You are given a string, $str, and list of words, @words.

Write a script to return true or false whether the given string can be segmented into a space separated sequence of one or more words from the given list.

My solution

With TWC, I tend to think about how I would solve it on my commute home on Monday. I thought of the example of a string of winwine and the words win and wine, and also the string of winewin. There doesn't seem to be a deterministic way of seeing what word I should match first.

A few days later, I had a genius idea that I was actually solving the wrong problem. A much easier solution was to use regular expressions to see if one or more words matched the string s.

And that's what I wrote. I use re.escape in Python, and quotemeta in Perl to escape any special meta-characters in the words list.

def word_break(s: str, words: list) -> bool:
    pattern = '^(' + '|'.join(map(re.escape, words)) + ')+$'

    return True if re.search(pattern, s) else False

Examples

$ ./ch-1.py weeklychallenge challenge weekly
true

$ ./ch-1.py perlrakuperl raku perl
true

$ ./ch-1.py sonsanddaughters sons sand daughters
false

Task 2: Jump Game

Task

You are given an array of integers, @ints.

Write a script to find the minimum number of jumps to reach the last element. $ints[$i] represents the maximum length of a forward jump from the index $i. In case last element is unreachable then return -1.

My solution

When completing these tasks, I also use TDD, something I don't do in my day job. If the test fails, usually there is either an obvious error or something a little more tricky. This task was one of later. Lots of debugging ensued.

I know both Python and Perl have excellent built in debugging tools, but I'm still a fan of use a copious amount of print statements.

For this task, I have a recursive function called jump_game. It takes two parameters: ints is the list of integers (starting with the complete list), and moves which starts at one.

If the first integer is 0, I return None (undef in Python) as no further move is possible. I then iterate - with a variable i -from the value of int[0] to 1. If this value is greater than or equal to one less than the length of list, we have a solution and I return moves. For other values, I call the function again removing the i first values, and incrementing moves by one.

I have a min_moves variable to ensure we return the minimum number of moves for all the iterations.

def jump_game(ints: list, moves=1) -> int:
    min_moves = None
    for i in range(ints[0], 0, -1):
        if i >= len(ints)-1:
            return moves

        if ints[i] == 0:
            continue

        m = jump_game(ints[i:], moves+1)
        if m is not None and (min_moves is None or min_moves > m):
            min_moves = m

    return min_moves

What was my bug, you ask? I was checking for i >= len(ints) instead of i >= len(ints)-1.

Examples

$ ./ch-2.py 2 3 1 1 4
2

$ ./ch-2.py 2 3 0 4
2

$ ./ch-2.py 2 0 0 4
-1

Originally published at Perl Weekly 694

Hi there,

It has been two weeks since the London Perl and Raku Workshop 2024, and we are still receiving attendee reports. Thank you to everyone who took the time to share their experiences. Last week, I came across two such reports by Lee Johnson and Olaf Alders. I'm still hoping to find a moment to reflect on my own workshop experience.

LPW holds a special place in my heart, as it was the first workshop where I gave my first talk ever. I was introduced to LPW by a colleague at work. Back then, there was always an O'Reilly stall outside the theater room, selling Perl books and surrounded by a large crowd. I remember the days when we had three strong tracks running simultaneously and, especially, the last LPW organized by Mark Keating and his team. The transition was seamless, and we continued the workshop smoothly until COVID-19 struck. For a brief period, I was part of the organizing team, but my contributions were limited to promoting the event and assisting attendees on the day.

Bringing the workshop back after COVID-19 was the brainchild of Lee Johnson and Julien Fiegenhenn. Their hard work truly paid off, as the event was well-attended and praised for its smooth execution. I would like to take this opportunity to thank the organizing team for providing a platform to reconnect with friends from around the world. The future of LPW looks bright as I’m hearing a lot of positive feedback about next year’s workshop, and I'm keeping my fingers crossed.

Enjoy rest of the newsletter.

--
Your editor: Mohammad Sajid Anwar.

Announcements

London Perl & Raku Workshop 2024: Recordings & Thoughts

For all who missed the LPW 2024, we now have the recordings of the event. Audio quality may not be great, I must inform you upfront.

Articles

This week in PSC (167) | 2024-11-07

It seems very busy week, lots of topics discussed amd agreed upon. Happy to see things moving really fast. Thank you Perl Steering Council.

Multiple Inheritance vs Role

A simplified comparison between Multiple Inheritance and Roles.

Further on Perl Camel

The good old discussion of Perl Camel is back ...

Discussion

I wish Mojo::UserAgent could be made to not visit private IPs

An interesting discussion started around the use of Mojo::UserAgent. What is your view on this?

Grants

Dancer2 Documentation Grant Report

Great to see the improvement work being carried out in my favourite web framework, Dancer2.

The Weekly Challenge

The Weekly Challenge by Mohammad Sajid Anwar will help you step out of your comfort-zone. You can even win prize money of $50 by participating in the weekly challenge. We pick one champion at the end of the month from among all of the contributors during the month, thanks to the sponsor Lance Wicks.

The Weekly Challenge - 295

Welcome to a new week with a couple of fun tasks "Word Break" and "Jump Game". If you are new to the weekly challenge then why not join us and have fun every week. For more information, please read the FAQ.

RECAP - The Weekly Challenge - 294

Enjoy a quick recap of last week's contributions by Team PWC dealing with the "Consecutive Sequence" and "Next Permutation" tasks in Perl and Raku. You will find plenty of solutions to keep you busy.

TWC294

Rare pairing of 'unless' inside 'foreach' and we have a compact solution, very impressive. Please keep sharing knowledge with us.

Next Consecutive

The verbosity of solutions is the main attraction for me, not just this week but every week. It gives away lots of inner details. Great work, keep it up.

Perl Weekly Challenge: Week 294

Making good use of Raku built-in functions and getting job done in no time. Smart move, well done.

Consecutive Permutations

A very interesting discussion about the use of data structure to get around O(n) time. It's worth checking out, thanks for sharing.

Perl Weekly Challenge 294

Compact one-liner in Perl for all with enough discussion to get to the core. Well done and keep it up.

Consecutive Sequences of Permutations, Anyone?

The detailed analysis to sort out the O(n) time is very impressive. There is always something new to learn from your contributions.

No music, only numbers

Anyone looking for Raku magic then this is the best place where Raku implementation is discussed in details. Having said, I missed the musical aspect.

Sequential permutations

A detailed proof of O(n) time is worth checking. Kudos for the effort, thanks for sharing knowledge with us.

The Weekly Challenge #294

Thanks for sharing the research of finding the lexicographically next permutation. Plenty to learn from this week work.

Permutationally Consecutive

Another dose of Raku gems discussed and it is not to be missed. Highly recommended.

Rakudo

2024.43 One Of 21

Weekly collections

NICEPERL's lists

Great CPAN modules released last week;
MetaCPAN weekly report.

Event reports

Smashed TVs, Broken Windows, and Cracked Plates

Hear from the organiser of LPW what it takes to origanise an event. Kudos for all thier efforts.

How I Spent My First London Perl Workshop

A very colorful presentation, I must admit. Glad that you had great time in London.

Events

Boston.pm monthly meeting

November 12, 2024, Virtual event

Purdue Perl Mongers

November 13, 2024, Virtual event

Toronto Perl Mongers monthly meeting

November 28, 2024, Virtual event

Purdue Perl Mongers

December 11, 2024, Virtual event

You joined the Perl Weekly to get weekly e-mails about the Perl programming language and related topics.

Want to see more? See the archives of all the issues.

Not yet subscribed to the newsletter? Join us free of charge!

(C) Copyright Gabor Szabo
The articles are copyright the respective authors.

Challenge 294 solutions in Perl by Matthias Muth

These are my Challenge 294 Task 1 and 2 solutions in Perl
for The Weekly Challenge - Perl and Raku.

Summary

Task 1: Consecutive Sequences
$O(n)$ solution using a small data structure and a lookup hash to keep track of 'streaks' (consecutive sequences) and to merge them with new numbers as they are processed.

Task 2: Next Permutation
Working 'locally' to flip numbers to get the next permutation, without the need to create all permutations first.

Code:
Find the complete source code for both tasks, including more tests, on Github.

Task 1: Consecutive Sequence

You are given an unsorted array of integers, @ints.
Write a script to return the length of the longest consecutive elements sequence. Return -1 if none found. The algorithm must runs in O(n) time.

Example 1
Input: @ints = (10, 4, 20, 1, 3, 2)
Output: 4
The longest consecutive sequence (1, 2, 3, 4).
The length of the sequence is 4.

Example 2
Input: @ints = (0, 6, 1, 8, 5, 2, 4, 3, 0, 7)
Output: 9

Example 3
Input: @ints = (10, 30, 20)
Output: -1

Oh. Big Oh. $O(n)$ !

This restriction means that the simplest solution, sorting the array and then walking through the ordered numbers, is not allowed. That's because sort has an $O(n\log n)$ time complexity.

So what we are allowed to do for $O(n)$ is to walk through the array. As long as we don't use another loop within a loop, we can even walk through the array several times. This only means that the runtime spent for each number is slightly higher, but this still scales linearly with rising $n$ . Actually $O(2n)$ is the same as $O(n)$ .

In fact I do walk through the data twice! I use uniq on the input data, as a first pass (Example 2 contains a 0 twice!). I do this to make sure that double entries do not disturb the detection of sequences.

Let's call a 'consecutive sequence' a 'streak' for short.
We need to build up the 'streaks' as we encounter the numbers, one by one.
The data structure I use for representing a streak is a simple hash:

    $streak = { FROM => $a, TO => $b };

When a new number is encountered, I try to merge that number with any streak that already exists at the number's immediate left or immediate right.

For knowing whether those neighboring streaks already exists , I keep a lookup hash, %streaks. For every streak I create, I put a reference to the streak's data structure into that lookup hash, one with its starting number as the key, and one with its ending number. Thus, to access the left and right neighboring streaks for any new number $n, I only need to check $streaks{ $n - 1 } and $streaks{ $n + 1 }.. And once I have those, I know their 'other ends': the left streak's starting number, and the right streak's ending number. I then can create a new streak that covers them all, the left streak, the new number, and the right streak (if they exist, that is).

What is left to do then is to update the lookup table. I delete any references to the left and right streaks that will not be needed anymore, and I store references to the merged streak in the lookup hash at its starting and ending numbers.

For returning the length of the longest streak in the end, I check whether the new one is longer than what we already have, and update accordingly.

I have left the comments inside the code to make it easier to follow:

use v5.36;
use List::Util qw( uniq );

sub consecutive_sequence_using_hash( @ints ) {
    my $max_streak_length = -1;
    my %streaks;
    for my $n ( uniq @ints ) {
        # Create a new streak from this number,
        # possibly merged with any existing adjacent streaks
        # to the left or to the right.
        my ( $left, $right ) =
            ( $streaks{ $n - 1 }, $streaks{ $n + 1 } );
        my ( $from, $to ) = (
            $left ? $left->{FROM} : $n,
            $right ? $right->{TO} : $n,
        );
        my $streak = { FROM => $from, TO => $to };

        # Update the lookup entries:
        # Remove any entries that are *inside* the merged streak,
        # and add or update entries at the streak borders.
        delete $streaks{ $left->{TO} }
            if $left;
        delete $streaks{ $right->{FROM} }
            if $right;
        $streaks{$from} = $streaks{$to} = $streak;

        # Update the maximum length if this is a streak
        # (not just a single number) and it's longer than what we have.
        $max_streak_length = $to - $from + 1
            if $to > $from && $to - $from + 1 > $max_streak_length;
    }
    return $max_streak_length;
}

No loops inside!
I think this is proper $O(n)$ solution.

Task 2: Next Permutation

You are given an array of integers, @ints.
Write a script to find out the next permutation of the given array.
The next permutation of an array of integers is the next lexicographically greater permutation of its integer.

Example 1
Input: @ints = (1, 2, 3)
Output: (1, 3, 2)
Permutations of (1, 2, 3) arranged lexicographically:
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

Example 2
Input: @ints = (2, 1, 3)
Output: (2, 3, 1)

Example 3
Input: @ints = (3, 1, 2)
Output: (3, 2, 1)

A simple, but compute-intensive solution would be to create all permutations of the numbers involved, then sort them ('lexicographically'), then find the entry that corresponds to the permutation that is given, and then return the next one.
Actually I don't like this approach too much, because in my experience, anything that has to do with permutations or combinations has a tendency to use a lot of time , or a lot of memory, or both, very fast.

Let's find a solution that works 'locally'!

In order to modify an existing permutation to the next higher one, we need to find the number with the lowest significance that can be increased.
That means that we start at the right end (least significant), and find the first number that is lower than its right neighbor. All numbers at the right of that are ordered, highest first, so they can't be 'incremented'.

What if we didn't find any number that is lower than its right neighbor?
In that case, all numbers are ordered, highest first. This must be the last permutation possible. Which means that the next permutation will restart from the beginning of the cycle of all permutations.
In the first permutation, the numbers are ordered lowest first. To get there, we can just reverse that highest permutation sequence of numbers, and we can return that as the result.

If that's not the case, and we do have found a number that can be 'incremented', we need to find the next higher number to replace this number with.
We only look in the right part of the permutation, because using any number from further left would change the order more than we want.
We are looking for the lowest possible number that still is higher than our number.

Once we have found that replacement number, we exchange the two numbers.
We then have 'increased' our number by the next possible higher value of all permutations of the right part. At the same time, we have decreased the replacement number to the next possible lower number. So the ordering of the right part thus still is 'highest to lowest'. As we need the 'first' permutation of the right part, we can just reverse this.

That's it! We have found the lowest possible increment.

Again, I have left the comments in the code for easier following.

use v5.36;

sub next_permutation( @ints ) {
    return @ints
        if @ints <= 1;

    # Starting from the end, find the first number
    # that is lower than the one following it.
    my $index = $#ints;
    while( $index > 0 && $ints[ --$index ] gt $ints[ $index + 1 ] ) {
        # Everything is in the loop condition.
    }

    # No lower number found?
    # Then we are at the end of the permutations.
    return reverse @ints
        if $index == 0;

    my $value = $ints[$index];

    # Find the next highest value within the right part,
    # for using it to replace the current value.
    # (Remember that maybe not all values in the right part are higher!)
    # It has to be higher than the one to substitute, but the
    # lowest possible one.
    my ( $index_2, $replacement ) = ( $index + 1, $ints[ $index + 1 ] );
    for ( $index_2 + 1 .. $#ints ) {
        ( $index_2, $replacement ) = ( $_, $ints[$_] )
            if $value lt $ints[$_] lt $replacement;
    }

    # Swap the two numbers.
    @ints[ $index, $index_2 ] = @ints[ $index_2, $index ];

    # We know that the right side is sorted, highest first.
    # to have it sorted lowest first, we just need to reverse it.
    @ints[ $index + 1 .. $#ints ] =
        reverse @ints[ $index + 1 .. $#ints ];

    return @ints;
}

If we run this several times in a row, we will get a 'consecutive sequence of permutations'.
How nice for the title of this blog, combining the two tasks!

Thank you for the challenge!

Find the complete source code for both tasks, including tests, on Github.