１８問目

http://projecteuler.net/index.php?section=problems&id=18
三角形に配置された数字を頂点から反対側の辺まで辿るときに、数字の和が最大となるような経路を求める。
６７問目が同じ問題で、より大量のデータを対象としているということで、そちらも解けるプログラムを目指しました。
アイデアは比較的早く思いついたのですが、それを実装に落とすのが大変でした。いざできてみると短いし、単純なんですけどね。
僕の持てる力を全てつぎ込んでいます。

main = do
    cs <- readFile "euler018.txt"
    print $ euler018 $ map ((map read) . words) $ lines cs

euler018 :: [[Int]] -> Int
euler018 triangle = maximum $ last $ scanl1 sumMaximum triangle

sumMaximum :: [Int] -> [Int] -> [Int]
sumMaximum pre this = zipWith (+) this $
    zipWith max ([0] ++ pre) (pre ++ [0])

下はHaskellが遅かったときに書いたJavaです。やっぱりHaskellは短いなぁ。

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class Euler018 {

    public Euler018(long length) {
    }

    private List<List<Integer>> prepare() throws IOException {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();
        BufferedReader reader = new BufferedReader(new FileReader("euler018.txt"));
        String line;
        while ((line = reader.readLine()) != null) {
            String[] words = line.split(" ");
            List<Integer> row = new ArrayList<Integer>(words.length);
            for (int i = 0; i < words.length; i++) {
                row.add(Integer.parseInt(words[i]));
            }
            triangle.add(row);
        }
        return triangle;
    }
    
    private List<Integer> sumLast(List<List<Integer>> triangle) {
        if (triangle.size() == 1) {
            return triangle.get(0);
        } else {
            List<Integer> sum = sumLast(triangle.subList(0, triangle.size() - 1));
            List<Integer> sum0 = new ArrayList<Integer>(sum);
            sum0.add(0, 0);
            List<Integer> sum1 = new ArrayList<Integer>(sum);
            sum1.add(0);
            List<Integer> max = new ArrayList<Integer>(triangle.get(triangle.size() - 1));
            for (int i = 0; i < max.size(); i++) {
                max.set(i, max.get(i) + Math.max(sum0.get(i), sum1.get(i)));
            }
            return max;
        }
    }
    
    public static void main(String[] args) throws IOException {
        Euler018 e = new Euler018(1000000);
        List<Integer> sum = e.sumLast(e.prepare());
        int max = 0;
        for (int i = 0; i < sum.size(); i++) {
            if (sum.get(i) > max) {
                max = sum.get(i);
            }
        }
        System.out.println(max);
    }
    
}