We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #67: Maximum path sum II
Project Euler #67: Maximum path sum II
Contest ends in
+ 0 comments Here is my Python 3 100/- Points solution
def find_maximum_total(triangle): n = len(triangle) for i in range(n - 2, -1, -1): for j in range(len(triangle[i])): triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1]) return triangle[0][0] # Read the number of testcases t = int(input().strip()) for _ in range(t): n = int(input().strip()) triangle = [] for _ in range(n): row = list(map(int, input().strip().split())) triangle.append(row) result = find_maximum_total(triangle) print(result)
+ 0 comments In PHP
Since I'll be using a bottom-up approach, I've assembled the triangle in reverse before calling the solution function
<?php function solution($triangle) { $len = count($triangle); foreach ($triangle as $i => &$curr) { if ($i == $len - 1) { return $curr[0]; } $next = &$triangle[$i + 1]; foreach ($next as $j => $val) { $next[$j] += max($curr[$j], $curr[$j + 1]); } } } $_fp = fopen("php://stdin", "r"); $q = intval(trim(fgets($_fp))); while ($q--) { $j = intval(trim(fgets($_fp))); $triangle = array_fill(0, $j, null); while ($j--) { $triangle[$j] = array_map('intval', explode(' ', trim(fgets($_fp)))); } echo solution($triangle), PHP_EOL; } fclose($_fp);
+ 0 comments Solution in c#
static void Main(String[] args) { var tt = Convert.ToInt32(Console.ReadLine()); for(int i=0; i<tt; i++) { var list = new List<List<int>>(); var loop = Convert.ToInt32(Console.ReadLine()); for(int j=0; j<loop;j++) { var current = Console .ReadLine() .Trim() .ToString() .Split(' ') .Select(x=>Convert.ToInt32(x)) .ToList(); list.Add(current); } for (var m = list.Count - 2; m >= 0; m--) { for (var n = 0; n <= m; n++) { list[m][n] += Math.Max(list[m + 1][n], list[m + 1][n + 1]); } } Console.WriteLine(list[0][0]); } }
+ 0 comments Here is a clojure solution passed both #18 and #67.
(defn max-path-sum [tri] (let [max-sum (fn [a b c] (+ a (max b c))) fold-by (fn [bs as] (map max-sum as bs (rest bs)))] (first (reduce-right fold-by tri))))
Fold the triangle from bottom, taking the some of current element and max of adjacent elements below.
+ 0 comments I finally solved this problem (DP). The issue was an unclear definition of adjacent in the problem statement. Apparently, it excludes "down-left" in the right-angled representation of the triangle, but includes "down" and "down-right" corresponding to converting from the isosceles representation to the right-angled one. This is an asymmetric coordinate shift.
Load more conversations
Sort 54 Discussions, By:
Please Login in order to post a comment