CODEWITHSUNDEEP
rubyprimesmemoizationboolean-expressionsieve-algorithm
user12947930
user12947930

Reputation:

Overcoming The Boolean Input Tests in the Codewars Kata: "Master your primes: sieve with memoization" - Ruby

I'm currently doing the 5kyu "Master your primes: sieve with memoization" kata on Codewars. The challenge gives you a cached array of the first 4 prime numbers, and you must check if n (e.g. 5) is a prime in that array, if so, return true. If necessary (e.g. if n = 143), you must add primes to the cached array and stop when you get to n, then check if n is in the array (and hence a prime a number).

My code (below) is passing the tests for checking if prime or not. The problem is they've thrown in some strange inputs:

n = ($primes.size-5).abs<3 (test expects true)

n = ($primes.size-9).abs<3 (test expects true)

My code is currently only failing these 2 inputs. When I've evaluated them based on the where the cached array will be at that time, they both evaluate to false. The first line in my method attempts to return true if the value of n is false, I've tried this in 2 other ways also, nothing works so far.

Frustratingly, there's no mention whatsoever of these surprise tests in the kata description. As far as I'm aware the inputs ask "is the absolute value of the length of $primes minus 5 (and later 9), less than 3?"

Someone please explain to me if I'm wrong, what those inputs mean and how I can improve my code to pass these tests (and the kata).

require "prime"

$primes = [2,3,5,7]

def is_prime(n)
  return true if n.class == FalseClass
  return true if n <= $primes.max && $primes.include?(n)
  ($primes.max+1..n).each do |p|
    next if !p.prime?
    $primes << p
  end
  $primes.include?(n) ? true : false
end

Upvotes: 1

Views: 262

Answers (1)

Max
Max

Reputation: 22335

You are supposed to solve this kata without using the prime gem. If you do the prime test yourself you will see why the tests make sense.

The tests from that Kata, in order, are

Test.assert_equals(is_prime(1),false)
Test.assert_equals(is_prime(2),true)
Test.assert_equals(is_prime(5),true)
Test.assert_equals(is_prime(143),false)
Test.assert_equals(($primes.size-5).abs<3,true)
Test.assert_equals(is_prime(-1),false)
Test.assert_equals(is_prime(29),true)
Test.assert_equals(is_prime(53),true)
Test.assert_equals(is_prime(529),false)
Test.assert_equals(($primes.size-9).abs<3,true)

Testing 1, 2, and 5 can be done without modifying the memo, but 143 is the first number where the prime test could involve adding more primes to the memo. 143 = 11x13 so an absolutely minimal memo would only include [2,3,5,7,11] at this point. I believe that the kata is trying to verify that you aren't adding unnecessary primes to the memo. For some reason they added some wiggle room so you can have two extra primes in the memo and it will still pass.

The next tests are a little more advanced. 29 is prime, but again we don't have to add anything to the memo to detect that. As we go through the memo of known primes, we'll check if it is divisible by 2, 5, and... we're done actually. 5x5=25 which is less than 29 but 7x7=49 which is greater than 29. That means if 29 was divisible by 7 or some larger prime, it would also be divisible by a smaller prime than 7. But we've already checked all smaller primes and it isn't divisible. Therefore 29 is prime.

The same technique works for 53 because we already have 11 in the memo and 11x11>53.

The last check for 529 is similar to the one before. 529=23x23 so we have to get up to 23, which is the 9th prime.

Upvotes: 0

Related Questions