Merge pull request #6514 from waltman/branch-for-challenge-175

Branch for challenge 175

6 files changed, 242 insertions, 39 deletions

diff --git a/challenge-175/walt-mankowski/README.md b/challenge-175/walt-mankowski/README.md
index 798ac25682..fb6c680974 100644
--- a/challenge-175/walt-mankowski/README.md
+++ b/challenge-175/walt-mankowski/README.md
@@ -1,62 +1,110 @@
 Solutions by Walt Mankowski.
 
-# Perl Weekly Challenge #173: Esthetic Numbers and Sylvester's Sequence
+# Perl Weekly Challenge #175: Last Sunday and Perfect Totient Numbers
 
-I did this week's challenge in Perl and Python.
+I did this week's challenge in Perl and C.
 
-## Task #1: Esthetic Numbers
+## Task #1: Last Sunday
 
-For this task we're given a number _n_ and need to determine if it's an Esthetic Number. An **Esthetic Number** is a positive integer where every pair of adjacent digits differ in value by exactly 1.
+For this task we're given a year and need to list the last Sunday of each month in that year.
 
-The only real trick to solve this in Perl is that we can turn a number `$n` into an array of digits `@d` with the statement `@d = split //, $n;`. Then we can wrap that in a function that checks the absolute value of each pair of points:
+My approach here was to find the day of the week for the final day of each month, then use that to determine the final Sunday. That's easy in Perl, since `DateTime.pm` has a `last_day_of_month` method. We can call the `day_of_week` method on the object it returns, which encodes Monday through Sunday as integers 1 through 7. If we take that value modulus 7 then we know how many days to subtract to get the final Sunday. Here's my full program:
 
 ```perl
-sub is_esthetic($n) {
-    my @d = split //, $n;
-    for my $i (1..$#d) {
-        return 0 unless abs($d[$i-1] - $d[$i]) == 1;
-    }
-    return 1;
+use v5.36;
+use DateTime;
+
+my $year = $ARGV[0];
+for my $month (1..12) {
+    my $dt = DateTime->last_day_of_month(year => $year, month => $month);
+    my $days_to_sunday = $dt->day_of_week % 7;
+    my $final_sunday = $dt->day - $days_to_sunday;
+    printf "%d-%02d-%02d\n", $year, $month, $final_sunday;
 }
 ```
 
-Python is more of a stickler about types than Perl, so to turn it into an array of digits I had to first turn it into a string. Then you can treat it as an array, and I turned each character back into an integer. That sounds like a lot of work, but it's just a one-liner with a linst comprehension:
-
-```python
-d = [int(c) for c in str(n)]
+It's a bit more work in C. First we need a function to determine if `year` is a leap year:
+```c
+const bool is_leap_year(const int year) {
+    if (year % 4)
+        return false;
+    else if (year % 100)
+        return true;
+    else if (year % 400)
+        return false;
+    else
+        return true;
+}
 ```
 
-## Task 2: Sylvester's Sequence
+We also need encode how many days are in each month, for both non-leap and leap years:
+```c
+const int days_in_month[2][12] = {
+    { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 },
+    { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }
+};
+```
+I used `mktime(3)` to find the day of week of the last day of the month. It's got a few differences from `DateTime.pm`, namely:
+
+* The months run from 0 to 11 instead of 1 to 12.
+* Years start at 1900 instead of 0, so we need to subtract 1900 from the year.
+* Sunday is day 0 instead of day 7.
+
+Here's my main loop:
+```c
+const int year = atoi(argv[1]);
+const int leap = is_leap_year(year);
+for (int month = 0; month < 12; month++) {
+    struct tm ts;
+    memset(&ts, 0, sizeof(ts));
+    ts.tm_mon = month;
+    ts.tm_year = year - 1900;
+    ts.tm_mday = days_in_month[leap][month];
+    ts.tm_isdst = -1;
+    mktime(&ts);
+    printf("%d-%02d-%2d\n", ts.tm_year + 1900, month+1, ts.tm_mday - ts.tm_wday);
+}
+```
 
-For this task we need to generate the first 10 terms of [Sylvester's Sequence](https://en.wikipedia.org/wiki/Sylvester%27s_sequence). **Sylvester's Sequence** is an integer sequence where every term is the product of all the previous terms, plus one.
+## Task 2: Perfect Totient Numbers
 
-Terms in Sylvester's Sequence get very large very fast (the 10th term has 20 digits) so we need to use the `bigint` module. I also used the `prod` function from `List::Util` to do the multiplication. With those modules in hand, we can solve this challenge in just a few lines of code:
+For this task we need to generate the first 20 [Perfect Totient Numbers](https://en.wikipedia.org/wiki/Perfect_totient_number). A perfect totient number is an integer that's equal to the sum of its iterated totients. The **totient** of an integer _n_ is the number of positive integers less than _n_ which are relatively prime to _n_. 
 
+Two integers are relatively prime if their greatest common divisor (GCD) is 1. I used the elegant [Euclidian Algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm) to compute the GCD:
 ```perl
-use bigint;
-use List::Util qw(product);
-
-my @sylvester;
-push @sylvester, 1 + product @sylvester while @sylvester < 10;
-say for @sylvester;
+sub gcd($a, $b) {
+    return $b ? gcd($b, $a % $b) : $a;
+}
 ```
 
-Python has the equivalent of `bigint` built-in, so I didn't need to do anything special there. Python has `sum` as a built-in function but it doesn't have `prod`. There are a few different ways to do write it; I chose to use the `reduce` function from the `functools` package:
-
-```python
-def product(lst):
-    return reduce(lambda x,y: x*y, lst, 1)
+To solve the problem I first computed the totient for every number up to 6000. Why 6000? Well, we know from the problem definition that the 20th perfect totient number is 5571, so I figured I'd go a little higher.
+```perl
+my @totient = (0,0);
+my $MAX = 6000;
+for my $n (2..$MAX) {
+    for my $i (1..$n-1) {
+        $totient[$n]++ if gcd($n, $i) == 1;
+    }
+}
 ```
 
-But it's so short that I decided to just write it inline. Here's my full program:
-
-```python
-from functools import reduce
-
-sylvester = []
-while len(sylvester) < 10:
-    sylvester.append(reduce(lambda x,y: x*y, sylvester, 1) + 1)
+Then it's easy to loop over `@totient` and find all the perfect values:
+```perl
+my @perfect;
+my $i = 2;
+while (@perfect < 20) {
+    my $tot = $totient[$i];
+    my $sum = $tot;
+    while ($tot != 1) {
+        last if $sum > $i;
+        $tot = $totient[$tot];
+        $sum += $tot;
+    }
+    push @perfect, $i if $sum == $i;
+    $i++;
+}
 
-for syl in sylvester:
-    print(syl)
+say "@perfect";
 ```
+
+This runs in a little over 40 seconds on my home Linux box using perl 5.36.0. My C solution, which uses exactly the same algorithm, runs in about 0.7 seconds.
\ No newline at end of file
diff --git a/challenge-175/walt-mankowski/c/Makefile b/challenge-175/walt-mankowski/c/Makefile
new file mode 100644
index 0000000000..d1cec8a239
--- /dev/null
+++ b/challenge-175/walt-mankowski/c/Makefile
@@ -0,0 +1,18 @@
+C = /usr/bin/cc
+CFLAGS = -Wall -O3
+
+all: ch-1 ch-2
+
+%.o: %.cpp
+	$(CPP) $(CPPFLAGS) -c $<
+
+ch-1: ch-1.o
+	$(C) -o $@ ch-1.o
+
+ch-2: ch-2.o
+	$(C) -o $@ ch-2.o
+
+clean:
+	rm -f *~
+	rm -f *.o
+	rm -f ch-1 ch-2
diff --git a/challenge-175/walt-mankowski/c/ch-1.c b/challenge-175/walt-mankowski/c/ch-1.c
new file mode 100644
index 0000000000..346c8fdb0b
--- /dev/null
+++ b/challenge-175/walt-mankowski/c/ch-1.c
@@ -0,0 +1,36 @@
+#include <stdio.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+const bool is_leap_year(const int year) {
+    if (year % 4)
+        return false;
+    else if (year % 100)
+        return true;
+    else if (year % 400)
+        return false;
+    else
+        return true;
+}
+
+int main(int argc, char *argv[]) {
+    const int days_in_month[2][12] = {
+        { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 },
+        { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }
+    };
+
+    const int year = atoi(argv[1]);
+    const int leap = is_leap_year(year);
+    for (int month = 0; month < 12; month++) {
+        struct tm ts;
+        memset(&ts, 0, sizeof(ts));
+        ts.tm_mon = month;
+        ts.tm_year = year - 1900;
+        ts.tm_mday = days_in_month[leap][month];
+        ts.tm_isdst = -1;
+        mktime(&ts);
+        printf("%d-%02d-%2d\n", ts.tm_year + 1900, month+1, ts.tm_mday - ts.tm_wday);
+    }
+}
diff --git a/challenge-175/walt-mankowski/c/ch-2.c b/challenge-175/walt-mankowski/c/ch-2.c
new file mode 100644
index 0000000000..81d217dc81
--- /dev/null
+++ b/challenge-175/walt-mankowski/c/ch-2.c
@@ -0,0 +1,38 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+const int gcd(const int a, const int b) {
+    return b ? gcd(b, a % b) : a;
+}
+
+int main(int argc, char *argv[]) {
+    const int MAX = 6000;
+    int *totient = calloc(MAX, sizeof(int));
+
+    for (int n = 2; n <= MAX; n++)
+        for (int i = 1; i <= n-1; i++)
+            if (gcd(n, i) == 1)
+                totient[n]++;
+
+    int perfect[20];
+    int i = 2;
+    int n = 0;
+    while (n < 20 && i < 6000) {
+        int tot = totient[i];
+        int sum = tot;
+        while (tot != 1) {
+            if (sum > i)
+                break;
+            else {
+                tot = totient[tot];
+                sum += tot;
+            }
+        }
+        if (sum == i)
+            perfect[n++] = i;
+        i++;
+    }
+    for (int i = 0; i < 20; i++)
+        printf("%d ", perfect[i]);
+    printf("\n");
+}
diff --git a/challenge-175/walt-mankowski/perl/ch-1.pl b/challenge-175/walt-mankowski/perl/ch-1.pl
new file mode 100644
index 0000000000..51fa5a6b8b
--- /dev/null
+++ b/challenge-175/walt-mankowski/perl/ch-1.pl
@@ -0,0 +1,28 @@
+#!/usr/bin/env perl
+use v5.36;
+use DateTime;
+
+# Task 1: Last Sunday
+# Submitted by: Mohammad S Anwar
+# Write a script to list Last Sunday of every month in the given year.
+# For example, for year 2022, we should get the following:
+# 2022-01-30
+# 2022-02-27
+# 2022-03-27
+# 2022-04-24
+# 2022-05-29
+# 2022-06-26
+# 2022-07-31
+# 2022-08-28
+# 2022-09-25
+# 2022-10-30
+# 2022-11-27
+# 2022-12-25
+
+my $year = $ARGV[0];
+for my $month (1..12) {
+    my $dt = DateTime->last_day_of_month(year => $year, month => $month);
+    my $days_to_sunday = $dt->day_of_week % 7;
+    my $final_sunday = $dt->day - $days_to_sunday;
+    printf "%d-%02d-%02d\n", $year, $month, $final_sunday;
+}
diff --git a/challenge-175/walt-mankowski/perl/ch-2.pl b/challenge-175/walt-mankowski/perl/ch-2.pl
new file mode 100644
index 0000000000..abe403e9f1
--- /dev/null
+++ b/challenge-175/walt-mankowski/perl/ch-2.pl
@@ -0,0 +1,35 @@
+#!/usr/bin/env perl
+use v5.36;
+
+# Task 2: Perfect Totient Numbers
+# Submitted by: Mohammad S Anwar
+#
+# Write a script to generate first 20 Perfect Totient Numbers.
+
+sub gcd($a, $b) {
+    return $b ? gcd($b, $a % $b) : $a;
+}
+
+my @totient = (0,0);
+my $MAX = 6000;
+for my $n (2..$MAX) {
+    for my $i (1..$n-1) {
+        $totient[$n]++ if gcd($n, $i) == 1;
+    }
+}
+
+my @perfect;
+my $i = 2;
+while (@perfect < 20) {
+    my $tot = $totient[$i];
+    my $sum = $tot;
+    while ($tot != 1) {
+        last if $sum > $i;
+        $tot = $totient[$tot];
+        $sum += $tot;
+    }
+    push @perfect, $i if $sum == $i;
+    $i++;
+}
+
+say "@perfect";