A Long Flipping Year

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,
2099

Method

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 = 1111

Method

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

https://theweeklychallenge.org

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s