CY's Take on The Weekly Challenge #112

If you want to challenge yourself on programming, especially on Perl and/or Raku, go to https://perlweeklychallenge.org, code the latest challenges, submit codes on-time (by GitHub or email).

Do tell me, if I am wrong or you strongly oppose my statements!

Task 1: Canonical Path

For the . cases, we can choose to ignore them (grep { $_ ne "." }).

For the .. cases, naturally they are handled by a stack ‐ pop and push operations in Perl arrays.

For cases with multiple consecutive slashes, we can choose to ignore the empty string (grep { $_ ne "" }).

my $origin = $ARGV[0] || "/a//b/c/../../"; my @directories = grep { $_ ne "" && $_ ne "." } split "/", $origin; my @new_dirs = (); for (@directories) { if ($_ ne "..") { push @new_dirs, $_; } else { pop @new_dirs; } } print ( "/" . (join "/", @new_dirs)); print "\n";

The followings are some output of the program, it is good that the Perl interpreter does not complain on pop @empty_array:

$ perl ch-1.pl "/../../"
/
$ perl ch-1.pl "/a/"
/a
$ perl ch-1.pl "/a/b//c/"
/a/b/c
$ perl ch-1.pl "/a/b/c/../.."
/a

Task 2: Climb Stairs

If you had studied a bit about the Fibonacci sequence, did the domino-monomino covering problem cross your mind?

Consider a 1-by-n chessbaord. You have plenty of monomino(1×1) pieces and domino(1×2) pieces. How many ways are there to cover the chessboard?

It is a standard exercise of programming to display the n-th Fibonacci number. Let us go further. Can we display the details of the options?

After some thoughts, I realized it can be accomplished by combinations:

use Algorithm::Combinatorics qw/combinations/; #... for my $i ($n%2+$n/2 .. $n-1) { my $iter = combinations([0..$i-1] , ($n-$i) ); my $str = "1" x $i; while (my $c = $iter->next) { my $str_clone = $str; substr($str_clone, $_, 1) = "2" for (@{$c}); push @all, $str_clone; } }

The followings are some output of the program:

$ perl ch-2.pl 3
For 3 steps to climb, the number of options is 3:
21
12
111

$ perl ch-2.pl 5
For 5 steps to climb, the number of options is 8:
221
212
122
2111
1211
1121
1112
11111

$ perl ch-2.pl 10
For 10 steps to climb, the number of options is 89:
22222
222211
222121
  ... 
111111121
111111112
1111111111

As a dessert for this blogpost: a math question popped in my mind: what is the total number of 2's occurs on the options? Then I came to this integer sequence:

A001629 Self-convolution of Fibonacci numbers.

The recent weekly challenge tasks contain some sophisticated math sequences ‐ refer to FUSC Sequence in Week 104 (Task 1) and Bell Numbers in Week 108 (Task 2).

Besides, I wish I have knowledge and time to write Common Lisp solution(s) for the tasks, but I am stuck on exam preparation. Therefore, leave the "guest language conquer" after May.

Stay alert and healthy! □

link for codes: ch-1.pl, ch-2.pl

Contact on twitter: @e7_87.

Created Date: 16th May, 2021; last updated: 21:50 HKT

The Weekly Challenge ‐ Perl and Raku