Merge pull request #5542 from waltman/branch-for-challenge-148

Branch for challenge 148

1 files changed, 20 insertions, 43 deletions

diff --git a/challenge-148/walt-mankowski/README.md b/challenge-148/walt-mankowski/README.md
index fa45e8c3d8..0ed2bb3e10 100644
--- a/challenge-148/walt-mankowski/README.md
+++ b/challenge-148/walt-mankowski/README.md
@@ -1,58 +1,35 @@
 Solutions by Walt Mankowski.
 
-# Task #1: GCD Sum
+# Task #1: Eban Numbers
 
-For this task we're given a positive integer N. We need to find the sum of the greatest common divisors (GCDs) of all the pairs of integers between 1 and N.
+For this task we need to write a script to generate all **Eban Numbers** <= 100. An Eban number is a number that has no letter 'e' in it when the number is spelled in English (American or British).
 
-There's a simple recursive formula for the GCD:
+I used the CPAN module `Lingua::EN::Numbers`, which
+> provides a function "num2en", which converts a number (such as 123) into English text ("one hundred and twenty-three").
+
+Using `num2en` we can generate the Eban numbers with a single line of code:
 ```perl
-sub gcd($a, $b) {
-    return $b == 0 ? $a : gcd($b, $a % $b);
-}
+my @eban = grep { num2en($_) !~ tr/e// } 1..100;
 ```
-Once we have that the solution can be easily calculated using 2 nested loops:
-```perl
-my $sum = 0;
-for my $i (1..$n-1) {
-    for my $j ($i+1..$n) {
-        $sum += gcd($j, $i);
-    }
-}
 
-say $sum;
-```
+# Task 2: Cardano Triplets
 
-# Task 2: Magical Matrix
+For this task we need to generate the first 5 **Cardano Triplets**. The formula for Cardano Triplets involves square and cube roots. Github's Markdown engine doesn't support inline math, so I'll refer the reader to a [Project Euler](https://projecteuler.net/problem=251) problem involving them.
 
-For this task we need to create a 3 x 3 magic square; i.e. a matrix where each row, column, and diagonal sums to the same value. We're restricted to the numbers 1-9, so the sums should all be 15.
+There's no obvious method to sort Cardano Triplets, so instead of generating the first 5, I decided to generate all the solutions where a, b, and c are all less than or equal to 100. I didn't use anything fancy to generate them, just 3 nested `for` loops.
 
-This is trivial in Matlab and Octave since there's a built in function to create magic squares, so all we need to do is say
-```Matlab
-magic(3)
-```
+The only real difficulty here is that the second cube root term is often negative. This is the case for the example of (2,1,5) given in the problem description. Like all nonzero real numbers, 2 - sqrt(5) has exactly one real cube root, but since it's negative Perl's `**` operator returns `NaN`. To get around this I take the cube root of the absolute value, then make it negative:
 
-We have to do a bit more work in Perl, but fortunately there's a simple algorithm for creating these sorts of magic squares called the [Siamese method](https://en.wikipedia.org/wiki/Siamese_method). It works for any m x m magic square where m is odd. Here's the algorithm:
-1. Start with a 1 in the middle column of the top row.
-2. For each subsequent number, try to move to the cell to the northeast (1 row up and 1 column right), wrapping around to the left and bottom when we reach the edge.
-3. If that cell is occupied, move one 1 down (wrapping around to the top if we're on the bottom row) instead of moving to the northeast.
+```perl
+my $tmp = $a - $b * sqrt($c);
+my $t2 = ($tmp >= 0) ? $tmp ** $THIRD : -abs($tmp) ** $THIRD;
+```
 
-This is easy to do in Perl, and we don't even have to initialize the matrix.
+Also, since we're dealing with floating point numbers and potential round off errors, we'll accept it as a match if the sum is within epsilon of 1:
 ```perl
-my @m;
-my $m = 3;
-my $r = 0;
-my $c = 1;
-
-# fill in the magic square using the Siamese method
-for my $i (1..9) {
-    $m[$r][$c] = $i;
-    my $r1 = ($r - 1) % $m;
-    my $c1 = ($c + 1) % $m;
-    if (defined $m[$r1][$c1]) {
-        $r = ($r + 1) % $m;
-    } else {
-        $r = $r1;
-        $c = $c1;
-    }
+my $EPS = 1e-6;
+...
+if (abs($t1 + $t2 - 1) < $EPS) {
+    say "($a, $b, $c) ", $a + $b + $c ;
 }
 ```