Merge pull request #6384 from waltman/branch-for-challenge-171

Branch for challenge 171

6 files changed, 125 insertions, 84 deletions

diff --git a/challenge-168/walt-mankowski/perl/.perl-version b/challenge-168/walt-mankowski/perl/.perl-version
index 04a883217e..795df42654 100644
--- a/challenge-168/walt-mankowski/perl/.perl-version
+++ b/challenge-168/walt-mankowski/perl/.perl-version
@@ -1 +1 @@
-5.34.0
+5.36.0
diff --git a/challenge-171/walt-mankowski/README.md b/challenge-171/walt-mankowski/README.md
index 13731abfec..7e4eff8dc2 100644
--- a/challenge-171/walt-mankowski/README.md
+++ b/challenge-171/walt-mankowski/README.md
@@ -1,107 +1,61 @@
 Solutions by Walt Mankowski.
 
-## primes.pm
-Both of this week's challenge involve prime numbers. This module contains 2 utility functions, `primes_to` and `prime_factors`. `primes_to($n)` computes the primes up to `$n` using the [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). `prime_factors($n, $primes)` finds the prime factors of `$n` using the primes returned by `primes_to()`.
+# Task #1: Abundant Odd Numbers
 
-The Sieve algorithm uses an array of flags, and after it's finished any entry with a true value is a prime. To convert that to a list I used the new [`indexed` keyword](https://perldoc.perl.org/builtin#indexed) in Perl 5.36:
-```perl
-my @primes;
-for my ($i, $v) (indexed @is_prime) {
-    push @primes, $i if $v;
-}
-```
-This little `for` loop is using 2 different experimental features. Also `indexed` is Perl's new `builtin` namespace. In order to get this to run without warnings I needed to add some boilerplate code to the top of the module:
-```perl
-use v5.36;
-use builtin 'indexed';
-no warnings 'experimental::for_list';
-no warnings 'experimental::builtin';
-```
+For this task we need to find the first 20 odd **Abundant Numbers**. An [Abundant number](https://en.wikipedia.org/wiki/Abundant_number) is a number which is less than the sum of its proper divisors.
+
+I don't have much to say about this because it was quite simple to solve this by brute force. My only insight is to note that odd numbers can only have odd divisors, so we only have to check half the possible values.
 
-To find the prime factorization of `$n` we loop through the primes in order. If a prime `$p` divides `$n` evenly, we repeatedly add `$p` to the list of prime factors and divide `$n` by `$p` until it doesn't.
 ```perl
-# return the prime factors of $n as a sorted list
-sub prime_factors($n, $primes) {
-    my @factors;
-    for my $p ($primes->@*) {
-        return @factors if $p > $n;
-        while ($n % $p == 0) {
-            push @factors, $p;
-            $n /= $p;
-        }
+sub odd_divisors($n) {
+    my @od = (1);
+    my $max = $n / 2;
+    for (my $i = 3; $i <= $max; $i += 2) {
+        push @od, $i if $n % $i == 0;
     }
+    return @od;
 }
 ```
 
-# Task #1: Brilliant Numbers
+I also did a version in Python. In Python we can write `odd_divisors()` basically as a one-liner since `range()` lets us avoid a for loop:
 
-For this task we need to find the first 20 **Brilliant Numbers**. A Brilliant number is a number with exactly 2 prime factors of the same length.
-
-This is easy to compute with the functions in `primes.pm`. Since we know from the problem description that the 20th Brilliant number is 299, I start by finding all the primes less than 300. I also set Perl's special variable `$,` to `' '` so when print the values at the end they'll be spaced out nicely.
-```perl
-$, = ' ';
-my $MAX = 300;
-my $primes = primes_to($MAX);
+```python
+def odd_divisors(n):
+    od = [i for i in range(1,n//2+1,2) if n % i == 0]
+    return od
 ```
 
-Then the main loop just follows the problem description. I start the loop at 4 since that's the first composite number.
-```perl
-my @brilliant;
-for (my $n = 4; @brilliant < 20 && $n <= $MAX; $n++) {
-    my @factors = prime_factors($n, $primes);
-    if (@factors == 2 && length($factors[0]) == length($factors[1])) {
-        push @brilliant, $n;
-    }
-}
-
-say @brilliant;
-```
+# Task 2: First-class Function
 
-# Task 2: Achilles Numbers
+For this task we needed to create a function `compose(f,g)` that takes in two parameters `f` and `g` as subroutine references, and returns the subroutine `f(g(x))`.
 
-For this task we need to find the first 20 **Achilles Numbers**. An [Achillies number](https://en.wikipedia.org/wiki/Achilles_number) is a number that is **powerful** but not a perfect power. A number is powerful if every prime factor appears at least squared in the factorization.
+I just wrote this as a very simple function in Perl:
 
-To test if a number is powerful, I just count how many times each prime factor appears:
 ```perl
-# a number is powerful if there are at least 2 of each prime factor
-sub is_powerful(@factors) {
-    my %cnt;
-    for my $i (@factors) {
-        $cnt{$i}++;
-    }
-    for my $v (values %cnt) {
-        return 0 if $v == 1;
-    }
-    return 1;
+sub compose($f, $g) {
+    return sub { $f->($g->(@_)) };
 }
 ```
 
-Testing if a number is a perfect power is trickier. Fortunately we know from the problem that we don't need any perfect powers greater than 1800, and powers get big fast so there aren't that many of them. This function generates all of them:
+Then I tested it by composing 2 functions, one which sums its arguments and another which doubles each of its arguments:
+
 ```perl
-# there aren't that many perfect powers less than 1800, so since we know
-# the answer we'll cheat a little and generate them all ahead of time
-sub powers_upto($n) {
-    my %powers;
-    for my $i (2..sqrt($n)) {
-        my $val = $i * $i;
-        while ($val <= $n) {
-            $powers{$val} = 1;
-            $val *= $i;
-        }
-    }
-    return \%powers;
+sub sum {
+    my $sum = 0;
+    $sum += $_ for @_;
+    return $sum;
 }
-```
 
-As with Challenge 1 this week, once we have the functions set up, the actual loop to compute the values is simple.
-```perl
-my @achilles;
-for (my $n = 2; @achilles < 20 && $n <= $MAX; $n++) {
-    my @factors = prime_factors($n, $primes);
-    if (is_powerful(@factors) && !$perfect_power->{$n}) {
-        push @achilles, $n;
-    }
+sub double {
+    return map { $_ * 2 } @_;
 }
+```
 
-say @achilles;
+Here's an example of using it. The output is `20`.
+
+```perl
+my $c = compose(\&sum, \&double);
+say $c->(1,2,3,4);
 ```
+
+I never got a version of this working in Python.
diff --git a/challenge-171/walt-mankowski/perl/ch-1.pl b/challenge-171/walt-mankowski/perl/ch-1.pl
new file mode 100644
index 0000000000..5e4f769156
--- /dev/null
+++ b/challenge-171/walt-mankowski/perl/ch-1.pl
@@ -0,0 +1,40 @@
+#!/usr/bin/env perl
+use v5.36;
+use List::Util qw(sum);
+
+# Task 1: Abundant Number
+#
+# Write a script to generate first 20 Abundant Odd Numbers.
+#
+# According to wikipedia,
+#
+#     A number n for which the sum of divisors σ(n) > 2n, or,
+#     equivalently, the sum of proper divisors (or aliquot sum) s(n) >
+#     n.
+#
+# For example, 945 is the first Abundant Odd Number.
+#
+# Sum of divisors:
+# 1 + 3 + 5 + 7 + 9 + 15 + 21 + 27 + 35 + 45 + 63 + 105 + 135 + 189 + 315 = 975
+
+sub odd_divisors($n) {
+    my @od = (1);
+    my $max = $n / 2;
+    for (my $i = 3; $i <= $max; $i += 2) {
+        push @od, $i if $n % $i == 0;
+    }
+    return @od;
+}
+
+my @abundant;
+my $n = 1;
+while (@abundant < 20) {
+    my @od = odd_divisors($n);
+    if (sum(@od) > $n) {
+        push @abundant, $n;
+        printf "%2d: %s = %d > %d\n", scalar @abundant, join(" + ", @od), sum(@od), $n;
+    }
+    $n += 2;
+}
+$" = ", ";
+say "[@abundant]";
diff --git a/challenge-171/walt-mankowski/perl/ch-2.pl b/challenge-171/walt-mankowski/perl/ch-2.pl
new file mode 100644
index 0000000000..7fc612c59d
--- /dev/null
+++ b/challenge-171/walt-mankowski/perl/ch-2.pl
@@ -0,0 +1,28 @@
+#!/usr/bin/env perl
+use v5.36;
+
+# Task 2: First-class Function
+# Submitted by: Mohammad S Anwar
+
+# Create sub compose($f, $g) which takes in two parameters $f and $g as
+# subroutine refs and returns subroutine ref i.e. compose($f, $g)->($x)
+# = $f->($g->($x))
+
+sub compose($f, $g) {
+    return sub { $f->($g->(@_)) };
+}
+
+sub sum {
+    my $sum = 0;
+    $sum += $_ for @_;
+    return $sum;
+}
+
+sub double {
+    return map { $_ * 2 } @_;
+}
+
+$, = " ";
+my $c = compose(\&sum, \&double);
+say $c->(1,2,3,4);
+
diff --git a/challenge-171/walt-mankowski/python/.python-version b/challenge-171/walt-mankowski/python/.python-version
index a5c4c76339..c84ccce96a 100644
--- a/challenge-171/walt-mankowski/python/.python-version
+++ b/challenge-171/walt-mankowski/python/.python-version
@@ -1 +1 @@
-3.9.0
+3.10.5
diff --git a/challenge-171/walt-mankowski/python/ch-1.py b/challenge-171/walt-mankowski/python/ch-1.py
new file mode 100644
index 0000000000..90da29528a
--- /dev/null
+++ b/challenge-171/walt-mankowski/python/ch-1.py
@@ -0,0 +1,19 @@
+#!/usr/bin/env python
+
+def odd_divisors(n):
+    od = [i for i in range(1,n//2+1,2) if n % i == 0]
+    return od
+
+abundant = []
+n = 1
+while len(abundant) < 20:
+    od = odd_divisors(n)
+    if sum(od) > n:
+        abundant.append(n)
+        sum_str = ' + '.join([str(i) for i in od])
+        print(f"{len(abundant):2d}: {sum_str} = {sum(od)} > {n}")
+    n += 2
+print(abundant)
+
+
+