The Weekly Challenge 064

Minimum Sum Path and Word Break

Solutions on GitHub

Task 1: Minimum Sum Path

Find a path from top-left to bottom-right of an M x N grid which minimizes the sum of numbers along its path.

Example Output

Grid: [1, 3, 1] [1, 5, 1] [4, 2, 1] Minimum sum: 7

Logic

Use dynamic programming where table[i][j] = matrix[i][j] + min(table[i-1][j], table[i][j-1]).

Perl Solution

ch-1.pl

sub min_sum_path { my ($matrix) = @_; my $rows = @$matrix; my $cols = @{$matrix->[0]}; for my $i (0 .. $rows-1) { for my $j (0 .. $cols-1) { next if $i == 0 && $j == 0; my $top = $i > 0 ? $matrix->[$i-1][$j] : 1e9; my $left = $j > 0 ? $matrix->[$i][$j-1] : 1e9; $matrix->[$i][$j] += $top < $left ? $top : $left; } } return $matrix->[-1][-1]; }

Python Solution

ch-1.py

def min_sum_path(matrix: List[List[int]]) -> int: rows, cols = len(matrix), len(matrix[0]) for i in range(rows): for j in range(cols): if i == 0 and j == 0: continue top = matrix[i-1][j] if i > 0 else float('inf') left = matrix[i][j-1] if j > 0 else float('inf') matrix[i][j] += min(top, left) return matrix[-1][-1]

Task 2: Word Break

Determine if string S can be segmented into a space-separated sequence of dictionary words.

Example Output

S = 'perlweeklychallenge', W = ['weekly', 'challenge', 'perl'] Result: ['perl', 'weekly', 'challenge']

Logic

Recursive backtracking / DP matching dictionary prefixes against the remaining substring.

Perl Solution

ch-2.pl

sub helper { my ($s, $W, $words) = @_; return $words if length($s) == 0; for my $word (@$W) { if ($s =~ /^\Q$word\E/) { my $res = helper(substr($s, length($word)), $W, [@$words, $word]); return $res if $res; } } return undef; }

Python Solution

ch-2.py

def word_break(s: str, words: List[str]) -> List[str]: def helper(sub_s, path): if not sub_s: return path for w in words: if sub_s.startswith(w): res = helper(sub_s[len(w):], path + [w]) if res: return res return None return helper(s, [])