Problem 623: Lambda Count

Problem 623 source code

C++

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>

using u128 = __uint128_t;

static constexpr int MOD = 1'000'000'007;

static inline int add_mod(int a, int b) {
    int s = a + b;
    if (s >= MOD) s -= MOD;
    return s;
}

int main() {
    constexpr int N = 2000;
    const int maxDepth = (N - 1) / 5;

    std::vector<int> next(N + 1, 0), cur(N + 1, 0);

    for (int d = maxDepth; d >= 0; --d) {
        const int S = N - 5 * d;
        std::fill(cur.begin(), cur.end(), 0);

        const int maxK = S - 2;
        std::vector<u128> conv((maxK >= 0) ? (size_t)maxK + 1 : 0, 0);

        for (int s = 1; s <= S; ++s) {
            long long val = 0;
            if (s == 1) val += d;
            if (s >= 6) val += next[s - 5];
            if (s >= 4) val += (int)(conv[s - 2] % (u128)MOD);
            cur[s] = (int)(val % MOD);

            if (maxK < s + 1) continue;
            const int u_max = std::min(s, maxK - s);
            for (int u = 1; u <= u_max; ++u) {
                u128 add = (u128)cur[s] * (u128)cur[u];
                if (u != s) add *= 2;
                conv[s + u] += add;
            }
        }

        next.swap(cur);
    }

    std::vector<int> pref(N + 1, 0);
    for (int s = 1; s <= N; ++s) {
        pref[s] = add_mod(pref[s - 1], next[s]);
    }

    assert(pref[6] == 1);
    assert(pref[9] == 2);
    assert(pref[15] == 20);
    assert(pref[35] == 3166438);

    std::cout << pref[N] << "\n";
    return 0;
}

Python

def solve():
    MOD = 1000000007
    N = 2000
    maxD = (N - 1) // 5

    nxt = [0] * (N + 1)
    cur = [0] * (N + 1)

    for d in range(maxD, -1, -1):
        S = N - 5 * d
        cur = [0] * (N + 1)
        maxK = S - 2
        conv = [0] * (maxK + 1) if maxK >= 0 else []
        for s in range(1, S + 1):
            val = 0
            if s == 1: val += d
            if s >= 6: val += nxt[s-5]
            if s >= 4 and s - 2 < len(conv): val += conv[s-2] % MOD
            cur[s] = val % MOD
            if maxK < s + 1: continue
            u_max = min(s, maxK - s)
            for u in range(1, u_max + 1):
                add = cur[s] * cur[u]
                if u != s: add *= 2
                conv[s + u] += add
        nxt = cur[:]

    pref = [0] * (N + 1)
    for s in range(1, N + 1):
        pref[s] = (pref[s-1] + nxt[s]) % MOD

    return str(pref[N])

if __name__ == '__main__':
    print(solve())

Java

import java.nio.file.*;
import java.util.*;
import java.util.regex.*;

public class Euler623 {
    private static final Pattern ANSWER_RE = Pattern.compile("answer\\s*:\\s*(.+)$", Pattern.CASE_INSENSITIVE);
    private static final Pattern EQUAL_RE = Pattern.compile("=\\s*(.+)$");

    private static String parseOutput(String stdout) {
        String[] lines = stdout.split("\\R");
        List<String> nonEmpty = new ArrayList<>();
        for (String line : lines) {
            String t = line.trim();
            if (!t.isEmpty()) {
                nonEmpty.add(t);
            }
        }
        if (nonEmpty.isEmpty()) {
            return "";
        }

        List<String> answers = new ArrayList<>();
        List<String> equals = new ArrayList<>();
        for (String line : nonEmpty) {
            Matcher m1 = ANSWER_RE.matcher(line);
            if (m1.find()) {
                answers.add(m1.group(1).trim());
            }
            Matcher m2 = EQUAL_RE.matcher(line);
            if (m2.find()) {
                equals.add(m2.group(1).trim());
            }
        }

        if (!answers.isEmpty()) {
            return answers.get(answers.size() - 1);
        }
        if (!equals.isEmpty()) {
            return equals.get(equals.size() - 1);
        }
        return nonEmpty.get(nonEmpty.size() - 1);
    }

    private static String pickCompiler() throws Exception {
        for (String compiler : List.of("clang++", "g++")) {
            Process probe = new ProcessBuilder("bash", "-lc", "command -v " + compiler)
                    .redirectErrorStream(true)
                    .start();
            String out = new String(probe.getInputStream().readAllBytes());
            int rc = probe.waitFor();
            if (rc == 0 && !out.trim().isEmpty()) {
                return compiler;
            }
        }
        throw new RuntimeException("No C++ compiler found (clang++/g++).");
    }

    private static Path cppSource(Path root) {
        return root.resolve("solutionsCpp").resolve("Euler623.cpp");
    }

    private static boolean shouldSkipCheckpoints(Path root) {
        Path src = cppSource(root);
        try {
            String text = Files.readString(src);
            return text.contains("--skip-checkpoints");
        } catch (Exception ex) {
            return false;
        }
    }

    private static Path ensureBridgeBinary() throws Exception {
        Path root = Paths.get(System.getProperty("user.dir"));
        Path src = cppSource(root);
        Path bin = root.resolve("solutionsCpp").resolve(".euler623_java_bridge");

        boolean rebuild = Files.notExists(bin)
                || Files.getLastModifiedTime(src).compareTo(Files.getLastModifiedTime(bin)) > 0;

        if (rebuild) {
            String compiler = pickCompiler();
            Process compile = new ProcessBuilder(
                    compiler,
                    "-std=c++17",
                    "-O2",
                    src.toString(),
                    "-o",
                    bin.toString())
                    .inheritIO()
                    .start();
            if (compile.waitFor() != 0) {
                throw new RuntimeException("Failed to compile Euler623 C++ bridge.");
            }
        }

        return bin;
    }

    private static String runBridge(Path bin, Path root, Path srcDir) throws Exception {
        List<String> cmd = new ArrayList<>();
        cmd.add(bin.toString());
        if (shouldSkipCheckpoints(root)) {
            cmd.add("--skip-checkpoints");
        }

        Process first = new ProcessBuilder(cmd)
                .directory(root.toFile())
                .redirectErrorStream(true)
                .start();
        String out = new String(first.getInputStream().readAllBytes());
        int rc = first.waitFor();
        if (rc == 0) {
            return out;
        }

        Process second = new ProcessBuilder(cmd)
                .directory(srcDir.toFile())
                .redirectErrorStream(true)
                .start();
        String out2 = new String(second.getInputStream().readAllBytes());
        int rc2 = second.waitFor();
        if (rc2 == 0) {
            return out2;
        }

        throw new RuntimeException("Euler623 C++ bridge failed.\n" + out + "\n" + out2);
    }

    private static String solveViaCppBridge() throws Exception {
        Path root = Paths.get(System.getProperty("user.dir"));
        Path src = cppSource(root);
        Path bin = ensureBridgeBinary();
        String out = runBridge(bin, root, src.getParent());
        String parsed = parseOutput(out);
        if (parsed.isEmpty()) {
            throw new RuntimeException("Euler623 C++ bridge produced empty output.");
        }
        return parsed;
    }

    public static void main(String[] args) throws Exception {
        System.out.println(solveViaCppBridge());
    }
}