The weekly challenge 393 - Task 2: Prime Step

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-393/#TASK2
  3 #
  4 # Task 2: Prime Step
  5 # ==================
  6 #
  7 # You are given a string with English alphabetic characters only.
  8 #
  9 # What is the absolute difference of the sum of the ASCII values of the
 10 # characters in the string to the nearest prime number?
 11 #
 12 ## Example 1
 13 ##
 14 ## Input: $str = "hello"
 15 ## Output: 9
 16 ##
 17 ## The ordinal values of "hello" are [104,101,108,108,111], summing up to 532.
 18 ## The nearest prime number to 532 is 523, resulting in an absolute difference of 9.
 19 #
 20 ## Example 2
 21 ##
 22 ## Input: $str = "football"
 23 ## Output: 2
 24 ##
 25 ## Starting with the values [102,111,111,116,98,97,108,108] and the sum 841.
 26 ## We find 839 as the nearest prime number, so the difference is 2.
 27 #
 28 ## Example 3
 29 ##
 30 ## Input: $str = "a"
 31 ## Output: 0
 32 #
 33 ## Example 4
 34 ##
 35 ## Input: $str = "challenge"
 36 ## Output: 2
 37 ##
 38 ## The ordinal values of "challenge" are [99, 104, 97, 108, 108, 101, 110, 103, 101], which sum up to 931.
 39 ## The nearest prime number to 931 is 929, so the difference is 2.
 40 #
 41 ## Example 5
 42 ##
 43 ## Input: $str = "perl"
 44 ## Output: 2
 45 ##
 46 ## The ordinal values of "perl" are [112, 101, 114, 108], summing up to 435.
 47 ## Nearest prime is 433, so the difference is 2.
 48 #
 49 ############################################################
 50 ##
 51 ## discussion
 52 ##
 53 ############################################################
 54 #
 55 # First, we calculate the sum by applying ord() to all letters in the input.
 56 # Then, we check all numbers up to this number for primes and keep note of
 57 # the biggest one, plus all numbers bigger than the sum until we find the next
 58 # prime (of course we jump out of the whole loop if the sum happens to be a
 59 # prime since then we can just return 0). Of the differences from the sum
 60 # to both the biggest prime smaller than the input and the next prime after it,
 61 # we pick the smaller one for the result.
 62 
 63 use v5.36;
 64 
 65 prime_step("hello");
 66 prime_step("football");
 67 prime_step("a");
 68 prime_step("challenge");
 69 prime_step("perl");
 70 
 71 sub prime_step($str) {
 72     say "Input: \"$str\"";
 73     my $sum = 0;
 74     map { $sum += ord($_) } split //, $str;
 75     say "-> $sum";
 76     my ($smaller, $bigger) = (0, 0);
 77     my $i = 0;
 78     while($i <= $sum or not is_prime($i)) {
 79         $i++;
 80         # print "$i... ";
 81         if($i < $sum and is_prime($i)) {
 82             $smaller = $i;
 83         }
 84         if($i == $sum and is_prime($i)) {
 85             return say "Output: 0";
 86         }
 87         if($i > $sum and is_prime($i)) {
 88             $bigger = $i;
 89         }
 90     }
 91     my $d1 = $sum - $smaller;
 92     my $d2 = $bigger - $sum;
 93 
 94     if($d1 > $d2) {
 95         say "Output: $d2";
 96     } else {
 97         say "Output: $d1";
 98     }
 99 }
100 
101 
102 # We keep a cache of entries for everything we already calculated
103 # so we don't need to recalculate whether any number happens to be
104 # a prime multiple times.
105 {
106    my $cache;
107    sub is_prime {
108       my $num = shift;
109       return 0 if $num == 1;
110       return $cache->{$num} if defined $cache->{$num};
111       my $divider = 2;
112       while($divider <= sqrt($num)) {
113          if(int($num/$divider) == $num/$divider) {
114             $cache->{$num} = 0;
115             return 0;
116          }
117          $divider++;
118       }
119       $cache->{$num} = 1;
120       return 1;
121    }
122 }