Java8で「ソフトウェアエンジニアならば1時間以内に解けなければいけない5つの問題」の5問目を解いてみた

既出だけど「1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に」の問題5をJava8でやってみた。

1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる

    public static void main(String[] args) {
        f(values(1, 9))
                .filter(exp -> sum(exp) == 100)
                .forEach(System.out::println);
    }
    
    /**
     * sからeまでの連続した数値のリストを返す。
     */
    static List<Integer> values(int s, int e) {
        return IntStream.rangeClosed(s, e)
                .mapToObj(Integer::valueOf)
                .collect(Collectors.toList());
    }
    
    /**
     * 数値のリストから数式の全組み合わせを作成して、文字列のストリームで返す。
     * 例：[1, 2] -> ["1 +2",　"1 -2",　"12"]
     */
    static Stream<String> f(List<Integer> vals) {
        if (vals.size() == 1) return Stream.of(vals.get(0).toString());
        return Stream.of(" +", " -", "")
                .flatMap(op -> f(vals.subList(1, vals.size()))
                        .map(x -> vals.get(0).toString() + op + x)
                );
    }
    
    /**
     * 合計値を返す。
     */
    static int sum(String exp) {
        return Arrays.stream(exp.split(" "))
                .mapToInt(Integer::parseInt)
                .sum();
    }

結果

1 +2 +3 -4 +5 +6 +78 +9
1 +2 +34 -5 +67 -8 +9
1 +23 -4 +5 +6 +78 -9
1 +23 -4 +56 +7 +8 +9
12 +3 +4 +5 -6 -7 +89
12 +3 -4 +5 +67 +8 +9
12 -3 -4 +5 -6 +7 +89
123 +4 -5 +67 -89
123 +45 -67 +8 -9
123 -4 -5 -6 -7 +8 -9
123 -45 -67 +89