Perl Weekly Challenge: The Water Fell on the Floor!

Posted on by

Perl Weekly Challenge 393‘s tasks are “Pythagoras Multiplied” and “Prime Steps”.

As much as I hate the band, when I saw “steps”, I thought of Gimmie Three Steps by Lynyrd Skynyrd. Then I remembered three is a prime number.

sigh. Sometimes the songs pick themselves.

Task 1: Pythagoras Multiplied

You are given a positive integer n.

Find the number of all positive integer triplets (a, b, c) so that a^2 + b^2 = c^2 and a, b and c are integers <= n.

Example 1

Input: $n = 20
Output: 12

(3,4,5),  (4,3,5),   (5,12,13),(6,8,10),
(8,6,10), (8,15,17), (9,12,15),(12,5,13),
(12,9,15),(12,16,20),(15,8,17),(16,12,20)

Example 2

Input: $n = 7
Output: 2

(3,4,5),(4,3,5)

Example 3

Input: $n = 1
Output: 0

Example 4

Input: $n = 15
Output: 8

Example 5

Input: $n = 30
Output: 22

Approach

Well, we can loop through the values of a, b, and c to see which values meet the formula, but we can make certain optimizations: whenever we find a set of a, b, and c that works, we know that swapping a and b will also work, so we can count it as two and not check values where b <= a. We don’t have to check values where a and b are equal, because when a=1 and b=1 then c=√2; so whenever a and b are multiples of 1, then c will be a multiple of √2, and because √2 is irrational, any multiple of it will also be irrational. And we don’t have to check values of a above the square root of half of n^2, because we’ll either have already seen them as b values or they would produce c values larger than n. Also, once we reach values of b that produce values of c > n, we can bail out of that loop and go to the next value of a.

Raku

This was a fairly straightforward implementation of the algorithm in Raku.

sub pythagMult($n) {
  my $count = 0;
  my $sn = ($n ** 2 / 2).sqrt.Int;
  for 1 .. $sn -> $a {
    for $a + 1 .. $n -> $b {
      my $c = ($a ** 2 + $b ** 2).sqrt;
      last if $c > $n;
      $count += 2 if $c == $c.Int;
    }
  }
  return $count;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: $n = 20
Output: 12

Example 2:
Input: $n = 7
Output: 2

Example 3:
Input: $n = 1
Output: 0

Example 4:
Input: $n = 15
Output: 8

Example 5:
Input: $n = 30
Output: 22

Perl

And the Perl solution is mostly just like the Raku solution with the for loop variables moved to the front of the statements.

sub pythagMult($n) {
  my $count = 0;
  my $sn = int sqrt($n ** 2 / 2);
  for my $a ( 1 .. $sn ) {
    for my $b ( $a + 1 .. $n ) {
      my $c = sqrt($a ** 2 + $b ** 2);
      last if $c > $n;
      $count += 2 if $c == int $c;
    }
  }
  return $count;
}

View the entire Perl script for this task on GitHub.

Python

And the Python solution is mostly the same as well.

import math

def pythag_mult(n):
  count = 0
  sn = int(math.sqrt(n ** 2 / 2))
  for a in range(1, sn+1):
    for b in range(a + 1, n+1):
      c = math.sqrt(a ** 2 + b ** 2)
      if c > n: break
      if c == int(c): count += 2
  return count

View the entire Python script for this task on GitHub.

Elixir

But because looping with Enum.reduce_while/3 is, imho, a bit of a pain, I opted to use recursive calls to handle my looping.

def pythag_mult(_, sn, a, _, count) when a > sn, do: count

def pythag_mult(n, sn, a, b, count) do
  c = :math.sqrt(a ** 2 + b ** 2)
  if b > n or c > n do
    # increment a, start b at a+1
    pythag_mult(n, sn, a+1, a+2, count)
  else
    count = if c == trunc(c), do: count+2, else: count
    # increment b
    pythag_mult(n, sn, a, b+1, count)
  end
end

def pythag_mult(n) do
  pythag_mult(n, trunc(:math.sqrt(n ** 2 / 2)), 1, 2, 0)
end

View the entire Elixir script for this task on GitHub.

Task 2: Prime Step

You are given a string with English alphabetic characters only.

What is the absolute difference of the sum of the ASCII values of the characters in the string to the nearest prime number?

Example 1

Input: $str = "hello"
Output: 9

The ordinal values of "hello" are [104,101,108,108,111], summing up to 532.
The nearest prime number to 532 is 523, resulting in an absolute difference of 9.

Example 2

Input: $str = "football"
Output: 2

Starting with the values [102,111,111,116,98,97,108,108] and the sum 841.
We find 839 as the nearest prime number, so the difference is 2.

Example 3

Input: $str = "a"
Output: 0

Example 4

Input: $str = "challenge"
Output: 2

The ordinal values of "challenge" are [99, 104, 97, 108, 108, 101, 110, 103, 101], which sum up to 931.
The nearest prime number to 931 is 929, so the difference is 2.

Example 5

Input: $str = "perl"
Output: 2

The ordinal values of "perl" are [112, 101, 114, 108], summing up to 435.
Nearest prime is 433, so the difference is 2.

Approach

Since we had Pythagoras in the last task, I figure we need to find our primes in this task using the sieve of Eratosthenes. Since we sometimes need primes larger than the sum, I’m going to calculate primes out to twice the sum (since we know there are primes below the sum, even if there are no primes above the sum before sum × 2, we’d run into one of the primes below it), and cache the result in a list for future calls so we don’t have to re-calculate each time.

Raku

However, because lists are 0-indexed, I have to add @s[0] and @s[1] to the sieve’s list and then account for those elements being there.

We wind up extending the sieve list twice. Example 1’s sieve calculates primes up to 1064, but then example 2 needs primes up to 1682. Example 3 only needs up to 194, so it uses the cache, but then example 4 needs up to 1862. Example 5 is able to use the cache again because it only needs up to 870. 

my @isPrime; 
sub sieve($n is copy) {
  # so we always have enough primes, caclulate out to 2n
  $n *= 2;
  # if we've already calculated primes this far, return
  return if @isPrime.end >= $n;
  # extend the sieve to accommodate $n elements
  if (@isPrime.end < $n) {
    @isPrime.append: True xx ($n - @isPrime.elems);
  }
  for 2 .. $n.sqrt.Int+1 -> $i {
    next if @isPrime[$i] == False; # already deemed not prime
    loop (my $j = $i ** 2; $j <= $n; $j+=$i) {
      @isPrime[$j] = False;
    }
  }
}

sub primeStep($str) {
  my $ordsum = $str.comb.map({ $_.ord }).sum;
  sieve($ordsum); # populate the sieve
  my $i = 0;
  repeat {
    return $i
      if @isPrime[$ordsum + $i] || @isPrime[$ordsum - $i];
  } until ++$i >= $ordsum;
  return -1; # we should never get here
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: $str = "hello"
Output: 9

Example 2:
Input: $str = "football"
Output: 2

Example 3:
Input: $str = "a"
Output: 0

Example 4:
Input: $str = "challenge"
Output: 2

Example 5:
Input: $str = "perl"
Output: 2

Perl

As usual, the Perl solution is a pretty straight translation of the Raku solution. We need to use (true) on line 14 so x sees the value as being a list and repeats it as a list repetition operator.

use List::AllUtils qw( sum );

my @isPrime; 
sub sieve($n) {
  # so we always have enough primes, caclulate out to 2n
  $n *= 2;
  # if we've already calculated primes this far, return
  return if $#isPrime >= $n;
  # extend the sieve to accommodate $n elements
  if ($#isPrime < $n) {
    push @isPrime, (true) x ($n - $#isPrime);
  }
  for my $i ( 2 .. int(sqrt($n))+1 ) {
    next if $isPrime[$i] == false; # already deemed not prime
    for (my $j = $i ** 2; $j <= $n; $j+=$i) {
      @isPrime[$j] = false;
    }
  }
}

sub primeStep($str) {
  my $ordsum = sum map { ord($_) } split //, $str;
  sieve($ordsum); # populate the sieve
  my $i = 0;
  do {
    return $i
      if $isPrime[$ordsum + $i] || $isPrime[$ordsum - $i];
  } until ++$i >= $ordsum;
  return -1; # we should never get here
}

View the entire Perl script for this task on GitHub.

Python

And the same for Python: a straight translation from Raku.

import math

is_prime = []
def sieve(n):
  # so we always have enough primes, caclulate out to 2n
  n *= 2
  # if we've already calculated primes this far, return
  if len(is_prime) >= n: return
  # extend the sieve to accommodate $n elements
  if len(is_prime) < n:
    is_prime.extend([ True for i in range(n+1 - len(is_prime)) ])
  for i in range(2, int(math.sqrt(n))+2):
    if is_prime[i] == False: continue # already deemed not prime
    for j in range(i ** 2, n+1, i):
      is_prime[j] = False

def prime_step(string):
  ordsum = sum([ ord(c) for c in string ])
  sieve(ordsum) # populate the sieve
  i = 0
  while i < ordsum:
    if is_prime[ordsum + i] or is_prime[ordsum - i]: return i
    i += 1
  return -1; # we should never get here

View the entire Python script for this task on GitHub.

Elixir

Caching in Elixir is a pain (I’d need to load some non-native modules to use an external cache) and I figured I wasn’t going to bother with that. I also ditched storing the sieve in a List, opting instead to use a Map because it’s easier to do random-access with a Map—I had originally done it using a list, but to set the value at j in a list s to false I needed to do List.update_at(s, j, &( &1 and false )) because List.update_at/3 insists on having a function that accepts a single parameter as its third parameter… and at that point, I thought “Isn’t this easier using a Map?” Initializing the Map was just as easy (Map.new(1..n, fn i -> {i, true} end) instead of List.duplicate(true, n+1) on line 8), and so was using Map.get/3 instead of Enum.at/3 (lines 11 and 23), and instead of a janky call to List.update_at/3 on line 13, I was able to do a simple call to Map.put/3 that accepted a value to assign to the element, not a function to call against it. Also, because a Map doesn’t need to have a 0th and 1st element, I can just start with 2.

The fun discovery was that I didn’t need to split the string into characters and then get their integer code points: there’s a function that does it all in one step, String.to_charlist/1.

def sieve(n) do
  # so we always have enough primes, caclulate out to 2n
  n = n * 2
  # make a list of n true elements
  is_prime = Map.new(2..n, fn i -> {i, true} end)
  final = trunc(:math.sqrt(n))+1
  Enum.reduce(2..final, is_prime, fn i, is_prime ->
    if Map.get(is_prime, i) do
      Enum.reduce((i ** 2)..n//i, is_prime, fn j, is_prime ->
        Map.put(is_prime, j, false)
      end)
    else
      is_prime # already deemed not prime
    end
  end)
end

def prime_step(is_prime, ordsum, j) do
  cond do
    Map.get(is_prime, ordsum+j) or Map.get(is_prime, ordsum-j)
      -> j
    j < ordsum
      -> prime_step(is_prime, ordsum, j+1) # recusive call
    true
      -> -1 # we should never get here
  end
end

def prime_step(str) do
  ordsum = str |> String.to_charlist |> Enum.sum
  prime_step(sieve(ordsum), ordsum, 0)
end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GitHub: https://github.com/packy/perlweeklychallenge-club/tree/challenge-393-packy-anderson/challenge-393/packy-anderson

Leave a Reply