The Weekly Challenge 077

Fibonacci Sum and Lonely X

Solutions on GitHub

Task 1: Fibonacci Sum

You are given a positive integer $N. Write a script to find out all possible combinations of unique Fibonacci numbers required to get $N on addition. You are not allowed to repeat a number. Return 0 if none found.

Example Output

Input: $N = 6 Output: 5 + 1 = 6 3 + 2 + 1 = 6 Input: $N = 9 Output: 8 + 1 = 9 5 + 3 + 1 = 9

Logic

Generate all Fibonacci numbers less than or equal to N starting with 1, 2, 3, 5, 8, ... (omitting duplicate 1s to ensure uniqueness). Then use recursive backtracking to collect all subsets of these Fibonacci numbers whose sum equals exactly N.

Perl Solution

ch-1.pl

sub find_fibonacci_sums ($max_n) { return [0] if $max_n < 1; my @all_fibs = get_fibs_up_to($max_n); my @solutions; my $backtrack; $backtrack = sub ( $idx, $current_combo, $current_sum ) { if ( $current_sum == $max_n ) { push @solutions, [@$current_combo]; return; } for my $i ( $idx .. $#all_fibs ) { my $fib = $all_fibs[$i]; next if $current_sum + $fib > $max_n; $backtrack->( $i + 1, [ @$current_combo, $fib ], $current_sum + $fib ); } }; $backtrack->( 0, [], 0 ); return @solutions ? \@solutions : [0]; }

Python Solution

ch-1.py

def find_fibonacci_sums(max_n: int) -> list[list[int]] | int: """Find all combinations of unique Fibonacci numbers that sum to max_n.""" if max_n < 1: return 0 all_fibs = get_fibs_up_to(max_n) solutions: list[list[int]] = [] def backtrack(idx: int, current_combo: list[int], current_sum: int) -> None: if current_sum == max_n: solutions.append(current_combo) return for i in range(idx, len(all_fibs)): fib = all_fibs[i] if current_sum + fib > max_n: continue backtrack(i + 1, current_combo + [fib], current_sum + fib) backtrack(0, [], 0) return solutions if solutions else 0

Task 2: Lonely X

You are given an m x n character matrix consisting of O and X only. Write a script to count the total number of X surrounded by O only (horizontally, vertically, and diagonally).

Example Output

Input: [ O O X ] [ X O O ] [ X O O ] Output: 1 (only the X at row 0, col 2 is surrounded by O only)

Logic

Iterate through every cell in the m x n grid. When an 'X' is found, examine its 8 adjacent neighbors. If none of the adjacent neighbors (within grid bounds) is an 'X', increment the lonely count.

Perl Solution

ch-2.pl

sub count_lonely_x ($matrix) { return 0 if !@$matrix || !@{ $matrix->[0] }; my $rows = scalar @$matrix; my $cols = scalar @{ $matrix->[0] }; my $count = 0; for my $r ( 0 .. $rows - 1 ) { for my $c ( 0 .. $cols - 1 ) { next if $matrix->[$r][$c] ne 'X'; $count++ if is_cell_lonely( $matrix, $r, $c ); } } return $count; }

Python Solution

ch-2.py

def count_lonely_x(matrix: list[list[str]]) -> int: """Count the total number of 'X' surrounded only by 'O' in an m x n matrix.""" if not matrix or not matrix[0]: return 0 rows = len(matrix) cols = len(matrix[0]) count = 0 for r in range(rows): for c in range(cols): if matrix[r][c] == "X" and is_cell_lonely(matrix, r, c): count += 1 return count