laurent_r

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

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on November 7, 2021 at 24:00). 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: Long Year

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.

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

All years have 52 weeks, plus 1 day, or 2 days for leap years. How can you have years with 53 weeks? Well, it depends on how you define weeks. The most common convention is the following: all weeks start with Monday and each week belongs in the year in which the Thursday falls. This means that if the year starts on a Thursday or is a leap year and starts on a Wednesday, that particular year will have 53 numbered weeks.

Long Year in Raku

For this task, we use the built-in DateTime module, and the day-of-week and is-leap-year methods provided by the dateish role. We simply loop over the 1900-2100 range and print out the year if it starts on a Thursday, or if it starts on a Wednesday and is a leap year.

use v6;

for 1900..2100 -> $y {
    my $year = DateTime.new(:year($y));
    my $new-year-day = Date.new("$y-01-01").day-of-week;
    print "$y, " if $new-year-day == 4; # DoW 4 = Thursday
    print "$y, " if $year.is-leap-year and $new-year-day == 3;
}
say "";

This program displays the following output (slightly reformatted for the purpose of this blog post):

$ raku ./53-week-year.raku
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,

Update (Nov. 2, 2021): This can be made significantly simpler. Andrew Shitov sent me a message suggesting to use the week-number method (which is provided by the dateish role). All we need to do is to check whether the week number of the last day of the year is 53 (no need to check whether the year is leap). This can be done in just one code line, for example:

.say if Date.new($_, 12, 31).week-number == 53 for 1900..2100;

Long Year in Perl

In Perl, we use the Time::Local core module to figure out whether a year starts on a Thursday (or on a Wednesday in the case of leap years). Since Perl doesn’t have a built-in function for finding out whether a year is leap, we roll out our own is_leap_year subroutine. A year is leap if it is evenly divisible by 4 and not by 100 (unless it is also divisible by 400), so that 1900 and 2100 are not leap, but 2000 is leap.

#!/usr/bin/perl
use strict;
use warnings;
use feature qw/say/;
use Time::Local;

sub is_leap_year {
    my $year = shift;
    return 0 if $year % 4;   # not divisible by 4
    return 1 if $year % 100; # divisible by 4, not by 100
    return 0 if $year % 400; # divisible by 100, not by 400
    return 1;                # divisible by 400
}

for my $year (1900..2100) {
    my $date = timegm(0, 0, 0, 1, 0, $year);
    my $day_in_week = (gmtime $date)[6];
    print $year, ", " if $day_in_week == 4; # 4 = Thursday
    print $year, ", " if $day_in_week == 3 and is_leap_year $year;
}
say "";

This program displays the following output (sligthly reformatted for the purpose of this blog post):

$ perl ./53-week-year.pl
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,

Task 2: Lychrel Number

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.

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 a palindrome number.
 59 +  95 =  154
154 + 451 =  605
605 + 506 = 1111

It is now known whether there exists any Lychrel number in base ten, but some integers, such as 196, 295, and 394, are conjectured to be Lychrel numbers. They are sometimes called Lichrel candidates.

Note that the (a) stopping condition on the number of iterations is somewhat useless here, as we will reach the condition on the maximum size of the integer much faster. Starting with 1, the smallest positive integer, and applying the reverse and add algorithm will lead to a number larger than 10,000,000 is less than 20 iterations, as shown in the following Perl one-liner:

$ perl -E '$n = 1; for $i (1..500) { $n += reverse $n; say $i and last if $n >= 10_000_000;}'
19

Lychrel Numbers in Raku

We start with a 1..500 loop and break out of it if we’ve found a palindrome or if we’ve reached the 10,000,000 limit. In Raku, the built-in to reverse a word (or a number) is the flip method, which we use both for reversing the number and for finding out whether a result is a palindrome.

use v6;

sub is-lychrel (UInt $m) {
    my $n = $m;
    for 1..500 -> $i {
        return "$m is a Lychrel candidate. Reached the 1e7 limit"
            if $n > 10_000_000;
        $n += $n.flip;
        #`[say $n and] return 0 if $n == $n.flip;
    }
    return "$m is a lychrel candidate (made 500 iterations)";
}
for 10...20, 30, 50, 100, 196 -> $test {
    say "$test -> ", is-lychrel $test;
}

This program displays the following output:

$ raku ./lychrel.raku

10 -> 0
11 -> 0
12 -> 0
13 -> 0
14 -> 0
15 -> 0
16 -> 0
17 -> 0
18 -> 0
19 -> 0
20 -> 0
30 -> 0
50 -> 0
100 -> 0
196 -> 196 is a Lychrel candidate. Reached the 1e7 limit

Lychrel Numbers in Perl

We’re using essentially the same algorithm as in Raku. In Perl, we use the reverse built-in function.

#!/usr/bin/perl
use strict;
use warnings;
use feature qw/say/;

sub is_lychrel {
    my $m = shift;
    my $n = $m;
    for my $i (1..500) {
        return "$m is a Lychrel candidate. Reached the 1e7 limit" 
            if $n > 10_000_000;
        $n += reverse $n;
        return 0 if $n == reverse $n;
    }
    return "$m is a lychrel candidate (made 500 iterations)";
}
for my $test (10..20, 30, 50, 100, 196) {
    say "$test -> ", is_lychrel $test;
}

This program displays the following output:

$ perl ./lychrel.pl
10 -> 0
11 -> 0
12 -> 0
13 -> 0
14 -> 0
15 -> 0
16 -> 0
17 -> 0
18 -> 0
19 -> 0
20 -> 0
30 -> 0
50 -> 0
100 -> 0
196 -> 196 is a Lychrel candidate. Reached the 1e7 limit

Lychrel Numbers in Some Other Languages

In Julia

Contrary to Raku and Perl, and as in most other languages we will use below, in Julia, we need to perform some explicit integer to string and string to integer conversions to be able to perform a reverse operation on the digits of an integer. This is quite simple, though:

rev = parse(Int64, reverse(string(n)))

Besides that, the program is quite simple:

function is_lychrel(n) 
    m = n
    for k = 1:500
        if (n > 10_000_000) 
            return "$m is a Lychrel candidate. Reached the 1e7 limit"
        end
        rev = parse(Int64, reverse(string(n)))
        if (n == rev) return 0 end
        n += rev
    end
    return "$m is a lychrel candidate (made 500 iterations)";
end

for test in [10, 20, 30, 50, 100, 196]
    println("$test ->  $(is_lychrel(test))")
end

Note the use of the $ sign in Julia for value interpolations within strings, even (with parentheses) for values returned by code fragments such as function calls

Output:

$ julia ./lychrel.jl
10 -> 0
20 -> 0
30 -> 0
50 -> 0
100 -> 0
196 -> 196 is a Lychrel candidate. Reached the 1e7 limit

In Python

Contrary to Raku and Perl, and as in most other languages we will use, in Python, we need to perform some integer to string and string to integer conversions to be able to perform a reverse operation on the digits of an interger.

#!/usr/bin/python3

def is_lychrel(m):
    n = m
    for i in range(500):
        j = int(str(n)[::-1])
        if j == n:
            return 0
        n += j
        if n > 10000000:
            return "n is a lychrel candidate. Reached the 1e7 limit."
    return "n is a lychrel candidate. Made 500 iterations."

for test in range(10, 20):
    print(test, " -> ", is_lychrel(test))

for test in 10, 20, 30, 50, 100, 196:
    print(test, " -> ", is_lychrel(test))

Note that I wasn’t able to find the right syntax to include in the same test suite a range and a list of integers, so that I needed to use two separate for loops for the tests.

Output:

$ python3 lychrel.py
10  ->  0
11  ->  0
12  ->  0
13  ->  0
14  ->  0
15  ->  0
16  ->  0
17  ->  0
18  ->  0
19  ->  0
10  ->  0
20  ->  0
30  ->  0
50  ->  0
100  ->  0
196  ->  n is a lychrel candidate. Reached the 1e7 limit.

In Ruby

#! /usr/bin/ruby

def is_lychrel(m)
    n = m
    for k in 1..500
        j = n.to_s.reverse.to_i
        if j == n then
            return 0
        end
        n += j
        if n > 10000000 then
            return "#{m} is  a Lychrel candidate (reached the 1e7 limit)"
        end
    end
    return "#{m} is a lychrel candidate (made 500 iterations)"
end

for test in [10, 20, 30, 50, 100, 196]
    print  "#{test} -> ", is_lychrel(test), "\n"
end

Output:

10 -> 0
20 -> 0
30 -> 0
50 -> 0
100 -> 0
196 -> 196 is  a Lychrel candidate (reached the 1e7 limit)

In C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>  
#define MAX_ITER 500
#define MAX_VAL 10000000
#define NB_TESTS 6

void reverse_str(char* str) {  
    int len, tmp;  
    len = strlen(str); 
    for (int i = 0; i < len/2; i++) {  
        tmp = str[i];  
        str[i] = str[len - i - 1];  
        str[len - i - 1] = tmp;  
    }  
}  

const char* lychrel (int n) {
    char out[20];
    for (int k = 1; k <= MAX_ITER; k++) {
        if (n > MAX_VAL) {
            return "is a Lychrel candidate. Reached the 1e7 limit";
        }
        char to_str[20];
        char rev[20];
        sprintf(to_str, "%d", n);
        strcpy(rev, to_str);
        reverse_str(rev);
        if (strcmp(to_str, rev) == 0) {
            return "0";
        }
        n += atoi(rev);
    }
    return "is a Lychrel candidate. Reached 500 iterations";
}

int main() {
    int tests[NB_TESTS] = { 10, 20, 30, 50, 100, 196};
    for (int i = 0; i < NB_TESTS; i++) {
        printf("%d -> %s\n", tests[i], lychrel(tests[i]));
    }
}

Output:

$ lychrel
10 -> 0
20 -> 0
30 -> 0
50 -> 0
100 -> 0
196 -> is a Lychrel candidate. Reached the 1e7 limit

In Lua

function is_lychrel(n) 
    m = n
    for k =1, 500 do
        if n > 10000000 then
            return string.format("%s is a Lychrel candidate. Reached the 1e7 limit", m)
        end
        rev = tonumber(string.reverse(tostring(n)))
        if n == rev then return 0 end
        n = n + rev
    end
    return string.format("%s is a lychrel candidate (made 500 iterations)", m);
end

for key, test in ipairs({10, 20, 30, 50, 100, 196}) do
    print(test, " -> ", is_lychrel(test)) 
end

Output:

$ lua ./lychrel.lua
10   ->     0
20   ->     0
30   ->     0
50   ->     0
100  ->     0
196  ->     196 is a Lychrel candidate. Reached the 1e7 limit

In Rust

In Rust, I wasn’t able to perform the integer to string conversion, reverse operation, and conversion back from string to integer. (Well, to tell the truth, I found a way to do it on the Internet, but I don’t really understand how it works and will therefore not use it.) So, for Rust, I decided to implement a function (reverse_num) performing the reverse operation directly on integers, using integer division, modulo, addition and multiplication opetators.

fn reverse_num (m: i32) -> i32 {
    let mut n = m;
    let mut rev = 0;
    while n > 0 {
        rev *= 10;
        rev += n % 10;
        n /= 10;
    }
    return rev;
}

fn is_lychrel(m: i32) -> String {
    let mut n = m;
    for _k in 1..500 {
        let j = reverse_num(n);
        if j == n {
            return 0.to_string();
        }
        n += j;
        if n > 10000000 {
            return "Lychrel candidate (reached the 1e7 limit)".to_string();
        }
    }
    return "Lychrel candidate (500 iterations)".to_string(); 
}
fn main() {
    for test in [10, 20, 30, 100, 196] {
        println!("{} -> {}", test, is_lychrel(test));
    }
}

Output:

10 -> 0
20 -> 0
30 -> 0
100 -> 0
196 -> Lychrel candidate (reached the 1e7 limit)

In awk

#!/usr/bin/awk

function reverse (num) {
    rev = ""
    len = length(num)
    for (i = len; i > 0; i--) {
        rev = rev substr(num, i, 1);
    }
    return rev
}
function is_lychrel(n) {
    for (i = 1; i <= 5; i++) {
        if (n > 10000000) {
            return "is a Lychrel candidate. Reached the 1e7 limit"
        }
        rev = reverse(n)
        # print n, rev
        if (n == rev) { return 0 }
        n += rev
    }
    return "is a lychrel candidate (made 500 iterations)"
}
/[0-9]+/ { print $0, " -> ", is_lychrel($0) }

To run this awk program we need either to supply a file with the test values, or to pipe such data to the awk program standard input:

$ echo '20
30
40
50
100
196' |  awk -f lychrel.awk
20  ->  0
30  ->  0
40  ->  0
50  ->  0
100  ->  0
196  ->  is a Lychrel candidate. Reached the 1e7 limit

In bc

define reverse (n) {
    rev = 0
    while (n > 0) {
        rev *= 10
        rev += n % 10
        n /= 10
    }
    return (rev)
}


define is_lychrel(n) {
    for (i = 1; i < 500; i++) {
        if (n >= 10000000) { return -1}
        rev = reverse(n)
        /* print n, " ", rev, "\n" */
        if (n == rev) {return 0;}
        n += rev
    }
    return -1
}

while (1) {
    n = read ()
    if (is_lychrel (n) == -1) {
        print n, " Lychrel candidate", "\n"
    } else { 
        print n, " ", 0, "\n" 
        }
}
quit

We need to run this script in a way similar to awk:

$ echo ' 10
15
20
196' | bc lychrel.bc
10 0
15 0
20 0
196 Lychrel candidate

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 November 14, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.