The Weekly Challenge 076

Prime Sum and Word Search

Solutions on GitHub

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:

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