Programming Challenge: Given a triangle of numbers, find the path from the top to the bottom of the triangle with the largest sum.

I think I did this one on codewars before, couldn't find the code anymore though. So here, have some fresh, ugly, probably-correct Python3.

num_rows = int(input())

pyramid = [
    [int(c) for c in input().split()]
    for i in range(num_rows)
][::-1]

for rownum, row in enumerate(pyramid[1:], 1):
    prev_row = pyramid[rownum-1]
    pyramid[rownum] = [
        d + max(prev_row[i], prev_row[i+1])
        for i, d in enumerate(row)
    ]

print(pyramid[-1][0])

yes, it modifies values in pyramid while looping over it, but only ones that have already been seen, so it should be fine.

Edit: MORE GOLFING!

from functools import reduce
print(reduce(lambda s,r:[d+max(s[i:i+2])for i,d in enumerate(r)],[list(map(int,input().split()))for _ in range(int(input()))][::-1])[0])

Here's my GNU APL solution:

{⍺+2⌈/⍵}/{⍵,⊂⎕}⍣⎕ ⍬

The part {⍵,⊂⎕}⍣⎕ ⍬ gets the input:

• We start with an empty value (⍬)
• The ⍣ in this case applies the function before it ({⍵,⊂⎕}) as often as the number behind it (⎕, which is a number inputted by the user and the first line) to the result of the previous iteration and starts with the empty value
• The function {⍵,⊂⎕} gets a new line from input, encloses it (so it is a single array element even if it is an array itself) and appends it to the existing array we are iterating on

The part {⍺+2⌈/⍵}/ computes the sum:

• Now we have an array which contains the arrays of the triangle in ascending order, where we apply the reduce operator (/), which evaluates by essentially putting the function before it ({⍺+2⌈/⍵}) between every element in the target array (the indiviual triangle rows) and applies them from right to left in usual apl fashion (from the longest triangle row to the smallest one)
• The function {⍺+2⌈/⍵} takes the maximum per two neighboring elements from the right array (2⌈/⍵, which is just the reduce operator per 2 elements with the maximum function ⌈) and adds them element-wise to the array on the left

Thanks for posting these coding challenges, they're fun! Here's a O(n^2) solution in C:

#include <stdlib.h>
#include <stdio.h>

int main()
{
    int rows = 0;
    fscanf(stdin, "%d", &rows);
    // Fill in triangle from the input.
    int *triangle = calloc(rows * rows, sizeof(int));
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < i + 1; ++j)
            fscanf(stdin, "%d", &triangle[i * rows + j]);
    }
    // Compute maximum sums bottom-up.
    int *sums = calloc((rows + 1) * (rows + 1), sizeof(int));
    for (int i = rows - 1; i >= 0; --i) {
        for (int j = 0; j < i + 1; ++j) {
            int left = sums[(i + 1) * (rows + 1) + j];
            int right = sums[(i + 1) * (rows + 1) + j + 1];
            sums[i * (rows + 1) + j] = triangle[i * rows + j] +
             (left > right ? left : right);
        }
    }
    printf("%d\n", sums[0]);
    return 0;
}

I did it on a whiteboard to practice for my upcoming job interview. I got some off by one errors when I typed it in. And I didn't use user input but a given String. When I typed it in I used the user input but java was causing trouble with the scanner and whitespace so instead I seperate the values by dots

My solution and If I see it right some others here, was basically to fill the table up top to bottom with the highest value of the 2 values under it. This should solve it in linear time? Please correct me if I am wrong.
Also, isn't this dynamic programming?

import java.util.Arrays;
import java.util.Scanner;

public class HighestValuePyramid {
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        System.out.println("Enter rows");
        int rows = s.nextInt();

        int[][] pyramidArray = new int[rows][rows];
        for(int i = 0;i<rows;i++){
            System.out.println("Enter values for the pyramid");
            String row = s.next();
            String[] rowA = row.split("\\.");
            for(int j = 0; j<rowA.length;j++){
                pyramidArray[i][j]=Integer.parseInt(rowA[j]);
            }
        }
        int highestValue = highestValue(pyramidArray);
        System.out.println(highestValue);

    }

    private static int highestValue(int[][] pyramidArray) {
        int[][] valuePyramid = new int[pyramidArray.length][pyramidArray.length];
        valuePyramid[pyramidArray.length-1]=pyramidArray[pyramidArray.length-1]; // keep last row the same
        for(int row=pyramidArray.length-2;row>=0;row--){
            for(int col = 0;col<=row;col++){
                valuePyramid[row][col]= Math.max(valuePyramid[row+1][col],valuePyramid[row+1][col+1])+pyramidArray[row][col];
            }
        }
        System.out.println(Arrays.deepToString(valuePyramid));

        return valuePyramid[0][0];
    }
}