1
\$\begingroup\$

Link to problem: https://www.codewars.com/kata/5539fecef69c483c5a000015/train/powershell

I have a working solution in Codewars but my solution is slow for some reason and
I need to improve the efficiency.

Please look over my solution and offer any suggestions on things I could do to
improve what I have.

Instructions for problem:

Backwards Read Primes are primes that when read backwards in base 10 (from right
to left) are a different prime. (This rules out primes which are palindromes.)

Examples: 13 17 31 37 71 73 are Backwards Read Primes 13 is such because it's prime and read from right to left writes 31 which is prime too. Same for the others.

Task Find all Backwards Read Primes between two positive given numbers (both inclusive), the second one always being greater than or equal to the first one. The resulting array or the resulting string will be ordered following the natural order of the prime numbers.

Example backwardsPrime(2, 100) => [13, 17, 31, 37, 71, 73, 79, 97] backwardsPrime(9900, 10000) => [9923, 9931, 9941, 9967] backwardsPrime(501, 599) => []

Note for Forth Return only the first backwards-read prime between start and end or 0 if you don't find any

Don't use Ruby Prime class, it's disabled. backwardsPrime(2, 100) => [13, 17, 31, 37, 71, 73, 79, 97] backwardsPrime(9900, 10000) => [9923, 9931, 9941, 9967]

Thanks.


$primes = @{ 2 = 2; 3 = 3; 5 = 5; 7 = 7; 11 = 11; 13 = 13; 17 = 17; 31 = 31; 37 = 37; 71 = 71; 73 = 73; 79 = 79; 97 = 97; 107 = 107; 113 = 113; 149 = 149; 157 = 157; 167 = 167; 179 = 179; 199 = 199 };

function backwards-prime($start, $stop) 
{

    function revNum ([int] $n) {
        $numStr = $n.ToString();
        return ($numStr[-1..-($numStr.Length)] -join "") -as [int];
    }

    function isPrime ($num) {

        if ($primes.containsKey($num)) {
            return $true;
        }

        if ($num -lt 3) {
            return $num -gt 1;
        }

        if ($num % 2 -eq 0 -or $num % 3 -eq 0) {
            return $false;
        }

        $i = 5;

        while ($i * $i -le $num) {
            if ($num % $i -eq 0 -or $num % ($i + 2) -eq 0) {
                return $false; 
            }

            $i += 6;
        }

        $primes[$num.ToString()] = $num;

        return $true;
    }

    $res = @();
    
    if($start % 2 -eq 0) { $start = $start + 1; }
    if($stop % 2 -eq 0) { $stop = $stop - 1; }

    for ($i = $start; $i -le $stop; $i += 2) {
        $nPrime = isPrime $i;
        $nReversed = revNum $i;
        $nPrimeReverse = isPrime $nReversed;

        if ($nPrime -and $nPrimeReverse -and $i -ne $nReversed -and $i -ge 13) {
            $res += $i;
        }
    }

    return ($res -join ", ").Trim();
}

\$\endgroup\$
1
\$\begingroup\$

Update: Later this night after I asked my question I continued to think of ways I could have improved the performance of my solution. I made some refactors that I'm going to share which gave me enough boost to beat the time requirement for this problem.

But please continue to post your answers, I'm here to learn as well. And any new nugget of efficiency I can add or look at is still super valuable to me.

Thanks in advance...

So the fist changes I made even though a bit small was

I removed the .ToString() to my $num in my isPrime function, I realized that it was not even needed, and yes that's a small change but every bit helps in this case...

The update isPrime function below...


  function isPrime ($num) {

      if ($primes.containsKey($num)) {
          return $true;
      }

      if ($num -lt 3) {
          return $num -gt 1;
      }

      if ($num % 2 -eq 0 -or $num % 3 -eq 0) {
          return $false;
      }

      $i = 5;

      while ($i * $i -le $num) {
          if ($num % $i -eq 0 -or $num % ($i + 2) -eq 0) {
              return $false; 
          }

          $i += 6;
      }

      $primes[$num] = $num; # removed the .ToString() here... very small optimization but it all matters I guess.

      return $true;
  }

Next I went to the for-loop and realized that I was doing 2 isPrime calls and a reverse number call as well... It dawned on me that I could easily just declare and assign $nPrime variable and then check if it's false then no need to continue and just go to the next iteration, same with $nPrimeReverse. But before that I would call revNum and test if $nReversed is equal to $i if it is, then also I would call continue and start the next iteration. Then finally I just add a check at the start determining if $i is greater than 13.

Here is the updated for-loop:


  for ($i = $start; $i -le $stop; $i += 2) {
  
      if ($i -lt 13) { continue; }
  
      $nPrime = isPrime $i;
      
      if ($nPrime -eq $false) { continue; }
      
      $nReversed = revNum $i;
      
      if ($nReversed -eq $i) { continue; }
      
      $nPrimeReverse = isPrime $nReversed;
      
      if ($nPrimeReverse -eq $false) { continue; }

      $res += $i;
  }

After all these small changes my solution passed within the time constraint.

Please feel free to comment any additional items that I could refactor and improve.

Warm Regards

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.