Task 1: Prime Sum
You are given a number $N. Write a script to find the minimum number of prime numbers required whose summation gives $N (assume 1 is not prime).
Example Output
Input: $N = 9
Output: 2 (2 + 7 = 9)
Input: $N = 10
Output: 2 (5 + 5 = 10 or 3 + 7 = 10)
Logic
We leverage Goldbach's conjectures:
- If
N itself is prime, exactly 1 prime is needed.
- If
N is even (N > 2), by Goldbach's strong conjecture it can always be expressed as the sum of 2 primes.
- If
N is odd and N - 2 is prime, then N = 2 + (N - 2), so 2 primes are needed.
- Otherwise, by Goldbach's weak conjecture (proven by Helfgott), every odd integer greater than 5 can be written as the sum of 3 primes (e.g.
3 + (N - 3) where N - 3 is even).
Perl Solution
ch-1.pl
sub get_nr_primes ($n) {
return 0 if $n < 2;
return 1 if is_prime($n);
return 2 if $n % 2 == 0;
return 2 if is_prime( $n - 2 );
return 3;
}
Python Solution
ch-1.py
def get_nr_primes(n: int) -> int:
"""Calculate minimum number of prime numbers required to sum to n."""
if n < 2:
return 0
if is_prime(n):
return 1
if n % 2 == 0:
return 2
if is_prime(n - 2):
return 2
return 3
Task 2: Word Search
Given a 2D letter grid and a dictionary of words, print all words found in the grid in any of the 8 directions (orthogonally and diagonally, backwards and forwards).
Example Output
Grid:
B I D E
H E A R
C D E F
Words found: BIDE, HEAR, CDEF, BEE, RAEH
Logic
From every starting cell (r, c) in the grid, we traverse outward in all 8 ray directions: horizontal, vertical, and the 4 diagonals. We concatenate each full ray into a search corpus separated by delimiters. A target word exists in the grid if and only if it appears as a substring within this corpus.
Perl Solution
ch-2.pl
sub find_words ( $grid_lines, $words, $min_len = 1 ) {
my $corpus = build_search_corpus($grid_lines);
my @found;
for my $word (@$words) {
next if length($word) < $min_len;
if ( index( $corpus, uc($word) ) != -1 ) {
push @found, $word;
}
}
return \@found;
}
Python Solution
ch-2.py
def find_words(
grid_lines: list[str], words: list[str], min_len: int = 1
) -> list[str]:
"""Find and return words present in the grid in any of 8 directions."""
corpus = build_search_corpus(grid_lines)
found: list[str] = []
for word in words:
if len(word) < min_len:
continue
if word.upper() in corpus:
found.append(word)
return found