1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#!/usr/bin/python
"""
#===============================================================================
#
# FILE: ch_2.py
#
# USAGE: ./ch_2.py
#
# DESCRIPTION: Perl Weekly Challenge #100
# https://perlweeklychallenge.org/blog/perl-weekly-challenge-100/
# Triangle Sum
#
# AUTHOR: Lubos Kolouch
# CREATED: 2/20/2021 02:39:16 PM
#===============================================================================
"""
def min_sums(what):
""" Get the min sum as requested """
#
# 1
# |\
# 2 4
# |\|\
# 6 4 9
# |\|\|\
# 5 1 7 2
row_counter = 0
min_path = None
sums = {}
for row in what:
row_counter += 1
col_counter = 0
for item in row:
col_counter += 1
min_sum = sums.get((row_counter-1, col_counter), None)
if sums.get((row_counter-1, col_counter-1), None):
if (not min_sum or sums[(row_counter-1, col_counter-1)] < min_sum):
min_sum = sums[(row_counter-1, col_counter-1)]
if not min_sum:
min_sum = 0
sums[(row_counter, col_counter)] = item + min_sum
if row_counter == len(what):
if (not min_path) or (item + min_sum < min_path):
min_path = item + min_sum
return min_path
assert min_sums([[1], [2, 4], [6, 4, 9], [5, 1, 7, 2]]) == 8
assert min_sums([[3], [3, 1], [5, 2, 3], [4, 3, 1, 3]]) == 7
|
