What happens when we take what we’ve learned and look at it back to front? Does it still look the same as it did before? If not we try again, and again, and again until we get it right. It seems we’ll always get it right in the end, but it’s going to be a long year.
THE WEEKLY CHALLENGE – PERL & RAKU #137
episode one:
“Give It an Extra Week. I’ll See What I Can Do.”
Task 1
Long Year
Submitted by: Mohammad S Anwar
Write a script to find all the years between 1900 and 2100 which is a Long Year.
A year is Long if it has 53 weeks.
Update: For more information about Long Year, please refer to wikipedia.
Expected Output
1903, 1908, 1914, 1920, 1925,
1931, 1936, 1942, 1948, 1953,
1959, 1964, 1970, 1976, 1981,
1987, 1992, 1998, 2004, 2009,
2015, 2020, 2026, 2032, 2037,
2043, 2048, 2054, 2060, 2065,
2071, 2076, 2082, 2088, 2093,
2099Method
A year, nominally 365 days, divided into 7-day weeks yield 52 and 1/7, or one extra day. If it is leap year, with 366 days, there will be two extra days. So by my reckoning, every year has 53 weeks worth of days already: the acknowledged 52 plus a part of a week that isn’t part of any of those weeks, so is… another week? A part of a week? What about the rest of that week? Speaking to this last part is the crux of the difficulty. So this challenge hinges on which day of the week starts the year, and further, which day of the week starts a given week. If the extra day lands within the same week as that of the 364th we will only count 52 weeks total. If we roll over into a new one, however, we will find a 53rd.
Two commonly accepted week-counting schemes are for a new week to either start on Monday, running through Sunday, or for the week to start on Sunday, running through the following Saturday. Although continents seem to agree on one scheme or the other, the world as a whole does not. Notably in the United States they start their weeks on Sunday, in Europe they use Monday. That, I can see, is going to cause some internationalization problems with our global community.
In light of this sketchiness, the ISO has set up a week-numbering standard that the first week of the year is to be considered the week that contains January 4, which is to say the first week containing at least 4 days, or put yet another way the first week where the majority of days falls within the new year. Oh, and weeks start on Mondays. We need that to be clear. Under this thinking if a year starts on a Thursday, then it will have 53 weeks, as the following Sunday will be January 4th, and the start of the week will have been on Monday, the 29th of December of the previous year. Leap years shift everything an extra day.
Yes, all of this is very confusing, but on the upside using this standard assigns a single unambiguous week number to every week in the year. Businesses like this because it makes the bookkeeping easier. Ordinary folk don’t normally care much about the week-number and are more concerned with the week day, or perhaps looking a little broader the month and date. Years change rarely and don’t often come into play in daily life. Ordinary folk in lockdown, in my observation, don’t seem to care much about dates at all. ,
We could solve this mathematically, by determining the start day of January 1, 1900, and advancing the weekday either one or two per year depending on the arcane rules for placing leap years, and then noting when the weekdays properly align to create a rollover week.
But then again, that’s why we have computers, to do this dreary, repetitive work for us. Enter Dave Rolsky, and his DateTime module. As Dave gently reminds us, hammer in hand, “Do Not Write Your Own Date and Time Manipulation Code!” Wise man, that Dave.
What we can do, then, is choose the 28th of December in a given year, and check its week number. This is the last day of the week before the first week containing January 4th. If that value is 53, then the week has 53 ISO weeks. Sometimes it’s easier to count backwards from the end than all the way through from the beginning. Easy peasy. Of course we’ve offloaded all the hard parts onto DateTime. This is wise and good.
As this result matches the expected output, we will suppose the ISO interpretation of weeks in a year was what was being requested at the beginning. A little further research at the Wiki article cited and it seems I did get the analysis right. How nice — not just for me, but also for all of you who have spent time reading this. Date manipulations are incredibly confusing, which puts me solidly with Dave on this one.
PERL 5 SOLUTION
As noted, we’re using DataTime to keep track of the tricky stuff here. I’m sure Dave spent a lot of time making sure all the fiddly parts are correctly lined up and that is to be respected. Sometimes it’s instructive to reinvent tools, to learn the processes better. Other times its good to learn to use the tools available to better know what they can do. This is one of those times.
use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';
use DateTime;
use DateTime::Duration;
my @years;
my $dt = DateTime->new (
year => 1900 ,
month => 12 ,
day => 28 ) ;
my $dur = DateTime::Duration->new (
years => 1 );
for (1..200) {
if ($dt->week_number == 53) {
push @years, $dt->year;
}
$dt->add( $dur );
}
## output phase
local $" = ', ';
my @five;
for (@years) {
push @five, $_;
if (scalar @five == 5) {
say "@five";
@five = ();
}
}
say "@five";
raku solution
When designing Raku, it appears they looked at the DateTime module and said “I gotta get me some of that”, lifting nearly all of the functionality intact and building it directly into the language. As a result the port is rather ridiculously compact. We can use the gather/take syntax to collect the list of matching years to an output array, then duplicate the example easily by using .rotor to group sublists of 5, join them with commas and print the resulting strings. It really is a beautiful language.
unit sub MAIN () ;
my @out = gather {
for 1900..2100 {
my $d = Date.new( $_, 12, 28 );
take $d.year if $d.week-number == 53;
}
}
.join(', ')
.say
for @out.rotor(5, :partial);episode two:
“100% Acrylic Lycra Blend”
task 2
Lychrel Number
Submitted by: Mohammad S Anwar
You are given a number, 10 <= $n <= 1000.
Write a script to find out if the given number is Lychrel number. To keep the task simple, we impose the following rules:
a. Stop if the number of iterations reached 500.
b. Stop if you end up with number >= 10_000_000.
Update: If you stop because of any of the above two rules then we expect 1 as an output.
According to wikipedia:
A Lychrel number is a natural number that cannot form a palindrome through the iterative process of repeatedly reversing its digits and adding the resulting numbers.
Example 1
Input: $n = 56
Output: 0
After 1 iteration, we found palindrome number.
56 + 65 = 121
Example 2
Input: $n = 57
Output: 0
After 2 iterations, we found palindrome number.
57 + 75 = 132
132 + 231 = 363
Example 3
Input: $n = 59
Output: 0
After 3 iterations, we found palindrome number.
59 + 95 = 154
154 + 451 = 605
605 + 506 = 1111Method
Lychrel Numbers remind me of fractals and chaos theory and my once-upon-at-time forays into phase space. Take a simple function, iterate it over and over, and see what happens. Does it converge? If we perform this on the complex plane then we may have the Mandelbrot Set. Tweak a few parameters and we enter a space of infinite Julia Sets instead. In this case we reverse and sum the number over and over, and stop when we have obtained a palindrome. As though chaos theory wasn’t weird enough already, now we’ve gone and added numeraux concrète positional number theory to it, just to make things extra freaky.
We’re just toying around with the idea here, and aren’t really making a stab at solving for 196, which has been taken to a billion iterations without finding a palindrome. The mathematics behind the process are complex, and so far any actual proof that 196 will not eventually resolve has been elusive, as is the case of every other base-10 number that remains open. There are a number of candidates, though.
Here we’re allowed an out, several actually but only one that counts. We are allowed to stop at either reaching a number above 10 million, or at 500 iterations, whichever comes first. We are also bounded within the space of candidates between 10 and 1000.
I said only one criteria matters, because the size limit, 10 million, will always be reached before 500 iterations. The math behind this assertion is a very interesting problem in itself, but fortunately we don’t need to solve the whole thing to demonstrate this is true. It’s a question of adding digits when we sum: the upper limit has 8 digits, and summing pairs of equally-sized numbers will add an additional digit to it’s length 50% of the time. The leading digit of the starting number can only have the digits 1 through 9, and the reversed value 0 through 9, allowing a leading 0 in this case. We have 90 possibilities to sum the leading digits and 45 of those are above 9. Randomly it would take on average about 24 iterations to get to 10 million, using log2(10000000) = 23 and change. To get to 500 iterations we would need to add an extra digit only 1.4% of the time. Quite a difference. As we can, in theory, add 0 to the first digit establishing a lower bound of the possibilities is tricky, to say the least, but seems to me to be the way to proceed.
Sidestepping the math of that particular rabbit-hole, we’ll come from the other direction and note that the longest known sequence has 288 iterations, reaching a palindrome with 142 digits. The relationship of 142 to 288 is pretty strong evidence we’re on the right track with our 50% estimated chance of adding an additional digit.
PERL 5 SOLUTION
Because the input is restricted to the range of 10 to 1000, rather than accept input I decided to compute all the values and make a report from the data. Hence the bookkeeping and output take up the bulk of the script. We collect the intermediate terms as we go and should we find a solution we return the list. If we error we return the error instead. Because we have either a list of a scalar returned, we need to check that using ref() to decide what to print.
use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';
use integer;
for my $num ( 10..1000 ) {
say "input: $num";
my @ret = lychrel( $num );
say "output: ", $ret[0];
ref($ret[1]) eq 'ARRAY'
? do {say "steps: (", scalar $ret[1]->@*, ")"; say "\t $_" for $ret[1]->@*}
: say $ret[1];
say '';
}
sub lychrel ( $num ) {
my @chain = ($num);
return (0, @chain) if $num == reverse $num;
for (1..500) {
my $revsum = $num + reverse $num;
push @chain, $revsum;
return (0, \@chain) if $revsum == reverse $revsum;
$num = $revsum;
return (1, "number too large: $num") if $num > 10_000_000;
}
say (1, "too many iterations, more than 500");
}
The output:
...
input: 284
output: 0
steps: (4)
284
766
1433
4774
input: 285
output: 0
steps: (4)
285
867
1635
6996
input: 286
output: 1
number too large: 17735476
input: 287
output: 0
steps: (8)
287
1069
10670
18271
35552
61105
111221
233332
input: 288
output: 0
steps: (3)
288
1170
1881
input: 289
output: 0
steps: (3)
289
1271
2992
input: 290
output: 0
steps: (5)
290
382
665
1231
2552
...Raku Solution
In Raku we have access to arbitrarily sized integers, which allows us more breathing room to play. Here I’ve expanded the valid range to 10 billion, which finds a few longer chains. Pushing the internal configuration out into constants is a nice touch too: Raku computes this at compile time, in the BEGIN phaser, so we can use our maximum values to generate our error messages, which is cool. Of note here too we aren’t required to use sigils in Raku — it just makes things less clear to Perl programmers and maybe more clear to those used to some other languages. One is limited somewhat, though, but this sigil-less forms work wonderfully for constants, just the way one would want.
unit sub MAIN () ;
constant MAX-ITER = 500;
constant MAX-VALUE = 10_000_000_000;
constant ERR-LARGE = 'number too large - larger than ' ~ MAX-VALUE;
constant ERR-MANY = 'too many iterations - more than ' ~ MAX-ITER;
for 10..1000 -> $num {
my ($out, $res) = lychrel( $num );
say qq:to/END/;
Input: $num
Output: $out
$res
END
}
sub lychrel ( $num is copy ) {
my @chain = $num;
return 0, @chain if $num == $num.flip;
for 1..MAX-ITER {
my $revsum = $num + $num.flip;
@chain.push: $revsum;
return 0, @chain if $revsum == $revsum.flip;
$num = $revsum;
return 1, ERR-LARGE if $num > MAX-VALUE;
}
return 1, ERR-MANY;
}
The Perl Weekly Challenge, that idyllic glade wherein we stumble upon the holes for these sweet descents, is now known as
The Weekly Challenge – Perl and Raku
It is the creation of the lovely Mohammad Sajid Anwar and a veritable swarm of contributors from all over the world, who gather, as might be expected, weekly online to solve puzzles. Everyone is encouraged to visit, learn and contribute at
Programming Excursions in Perl and Raku 