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