Problem 680: Yarra Gnisrever

Project Euler Problem 680 Solution

EulerSolve provides an optimized solution for Project Euler Problem 680, Yarra Gnisrever, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Start from the identity permutation $$A^{(0)}=(0,1,2,\dots,n-1).$$ Let the reversal endpoints be $$a_0\equiv 1 \pmod n,\qquad b_0\equiv 1 \pmod n,$$ and for each step $j=0,1,\dots,k-1$, reverse the closed interval $$\left[\min(a_j,b_j),\max(a_j,b_j)\right],$$ then update $$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv b_j+a_{j+1} \pmod n.$$ The target is the weighted sum $$R(n,k)=\sum_{i=0}^{n-1} i\,A_i^{(k)} \pmod{10^9}.$$ The challenge is that $n$ is enormous, so the final permutation cannot be built element by element. Mathematical Approach The implementation succeeds by tracking only the large monotone blocks created by the reversals, not the individual entries. Those blocks always remain simple arithmetic progressions with common difference $+1$ or $-1$. Step 1: The reversal intervals can be generated online The endpoints satisfy a Fibonacci-like recurrence modulo $n$: $$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv a_j+2b_j \pmod n.$$ So the $j$-th reversal interval is known as soon as the $(j-1)$-st step finishes. No table of all intervals is needed. Starting from $(1,1)$, the unreduced pairs are $$ (1,1),\ (2,3),\ (5,8),\ (13,21),\dots $$ which shows why consecutive Fibonacci numbers keep appearing behind the modular updates....

Detailed mathematical approach

Problem Summary

Start from the identity permutation

$$A^{(0)}=(0,1,2,\dots,n-1).$$

Let the reversal endpoints be

$$a_0\equiv 1 \pmod n,\qquad b_0\equiv 1 \pmod n,$$

and for each step $j=0,1,\dots,k-1$, reverse the closed interval

$$\left[\min(a_j,b_j),\max(a_j,b_j)\right],$$

then update

$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv b_j+a_{j+1} \pmod n.$$

The target is the weighted sum

$$R(n,k)=\sum_{i=0}^{n-1} i\,A_i^{(k)} \pmod{10^9}.$$

The challenge is that $n$ is enormous, so the final permutation cannot be built element by element.

Mathematical Approach

The implementation succeeds by tracking only the large monotone blocks created by the reversals, not the individual entries. Those blocks always remain simple arithmetic progressions with common difference $+1$ or $-1$.

Step 1: The reversal intervals can be generated online

The endpoints satisfy a Fibonacci-like recurrence modulo $n$:

$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv a_j+2b_j \pmod n.$$

So the $j$-th reversal interval is known as soon as the $(j-1)$-st step finishes. No table of all intervals is needed. Starting from $(1,1)$, the unreduced pairs are

$$ (1,1),\ (2,3),\ (5,8),\ (13,21),\dots $$

which shows why consecutive Fibonacci numbers keep appearing behind the modular updates.

Step 2: The permutation stays piecewise arithmetic

Call a block a run if it has the form

$$B(x,\sigma,\ell)=\bigl(x,\ x+\sigma,\ x+2\sigma,\ \dots,\ x+(\ell-1)\sigma\bigr),\qquad \sigma\in\{1,-1\}.$$

Initially the whole permutation is one increasing run:

$$B(0,1,n).$$

Now reverse any subarray of a sequence that is already a concatenation of such runs. Only the two boundary runs may need to be cut. Every interior run is reversed as a whole block, and the reverse of

$$x,\ x+\sigma,\ \dots,\ x+(\ell-1)\sigma$$

is again an arithmetic run, namely

$$x+(\ell-1)\sigma,\ x+(\ell-2)\sigma,\ \dots,\ x,$$

which simply flips the sign of the step. Therefore the representation is invariant under every operation.

Step 3: Each reversal creates only constant new structure

Because only the two boundary runs can be split, a single reversal creates at most two new runs. If we start with one real run, then after $k$ reversals the number of real runs is at most

$$2k+1.$$

This is the crucial compression: the permutation has length $n$, but its description has size only $O(k)$. A self-adjusting sequence tree can therefore manage the whole process efficiently.

Step 4: A whole run contributes by closed formulas

Suppose a run occupies positions $p,p+1,\dots,p+\delta$, where $\delta=\ell-1$. Define the standard sums

$$S_1(\delta)=\sum_{u=0}^{\delta} u=\frac{\delta(\delta+1)}{2},\qquad S_2(\delta)=\sum_{u=0}^{\delta} u^2=\frac{\delta(\delta+1)(2\delta+1)}{6}.$$

If the run is increasing, its values are $x,x+1,\dots,x+\delta$, so

$$\sum_{u=0}^{\delta} (p+u)(x+u)=(\delta+1)px+(p+x)S_1(\delta)+S_2(\delta).$$

If the run is decreasing, its values are $x,x-1,\dots,x-\delta$, so

$$\sum_{u=0}^{\delta} (p+u)(x-u)=(\delta+1)px+(x-p)S_1(\delta)-S_2(\delta).$$

Thus the final weighted sum can be accumulated run by run, without expanding the full permutation.

Step 5: Worked Example: $R(5,4)=27$

Take $n=5$. The intervals come from the endpoint sequence

$$ (1,1)\to(2,3)\to(0,3)\to(3,1). $$

Now apply the reversals:

$$\begin{aligned} A^{(0)}&=(0,1,2,3,4),\\ [1,1]&:\ (0,1,2,3,4),\\ [2,3]&:\ (0,1,3,2,4),\\ [0,3]&:\ (2,3,1,0,4),\\ [1,3]&:\ (2,0,1,3,4). \end{aligned}$$

Therefore

$$R(5,4)=0\cdot2+1\cdot0+2\cdot1+3\cdot3+4\cdot4=27,$$

which matches the checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations all use the same fast idea: store the permutation as an ordered collection of maximal runs inside an implicit sequence tree. Each node records the first and last value of one run, a lazy reversal flag, and the total number of array positions represented by its subtree.

For every reversal, the implementation locates the two boundary positions by rank, splits a boundary run only if the cut lands inside it, isolates the middle interval, and marks that interval as reversed. Laziness is enough because reversing a concatenation of runs only requires two effects: reverse the order of the blocks and flip the direction inside each block.

After all $k$ steps, an in-order traversal visits the runs from left to right. The current starting index of each run is known from subtree sizes, so the formulas from Step 4 give the contribution of the entire run modulo $10^9$ in constant time.

The Python and Java versions delegate to the same optimized solver logic, so their mathematical behavior is identical to the C++ implementation.

Complexity Analysis

Let $m_j$ be the number of runs after $j$ reversals. Since each reversal adds at most two runs, $m_j=O(j)$, hence $m_k=O(k)$. Each operation performs only a constant number of positional searches, local splits, and subtree reversals in an implicit splay tree, giving amortized $O(\log m_j)$ time per step. Summing over all $k$ steps yields

$$O(k\log k)$$

time. The final traversal is linear in the number of runs, so it costs $O(k)$. The memory usage is also

$$O(k),$$

because only the compressed run representation is stored.

Footnotes and References

Problem page: https://projecteuler.net/problem=680
Splay tree: Wikipedia - Splay tree
Arithmetic progression: Wikipedia - Arithmetic progression
Fibonacci number: Wikipedia - Fibonacci number
Square pyramidal number and $\sum u^2$: Wikipedia - Square pyramidal number

Problem 680 source code

C++

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <pthread.h>
#include <unistd.h>
#include <vector>

namespace {

using i64 = long long;
using u64 = std::uint64_t;
using u128 = unsigned __int128;

struct Options {
    i64 n = 1000000000000000000LL;
    i64 k = 1000000;
    i64 mod = 1000000000;
    bool run_checkpoints = true;
};

bool parse_i64_after_prefix(const std::string& arg, const std::string& prefix, i64& value) {
    if (arg.rfind(prefix, 0U) != 0U) return false;
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) return false;
    i64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') return false;
        parsed = parsed * 10 + (c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_i64_after_prefix(arg, "--N=", options.n)) continue;
        if (parse_i64_after_prefix(arg, "--K=", options.k)) continue;
        if (parse_i64_after_prefix(arg, "--mod=", options.mod)) continue;
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.n > 0 && options.k >= 0 && options.mod > 0;
}

inline i64 add_mod(i64 a, i64 b, i64 mod) {
    const i64 threshold = mod - b;
    return a >= threshold ? a - threshold : a + b;
}

inline i64 sub_mod(i64 a, i64 b, i64 mod) {
    return a >= b ? a - b : mod - (b - a);
}

inline i64 mul_mod(i64 a, i64 b, i64 mod) {
    return static_cast<i64>((static_cast<u128>(a) * static_cast<u128>(b)) % static_cast<u128>(mod));
}

inline i64 add_mod_n(i64 a, i64 b, i64 n) {
    const i64 threshold = n - b;
    return a >= threshold ? a - threshold : a + b;
}

struct Node {
    int parent = 0;
    int child[2]{0, 0};
    bool rev = false;
    i64 s = 0;
    i64 e = 0;
    i64 cnt = 0;
};

struct SplayTree {
    i64 n = 0;
    i64 mod = 1;
    std::vector<Node> nodes;

    explicit SplayTree(i64 n_, i64 mod_) : n(n_), mod(mod_) {
        nodes.resize(3000500);
        init();
    }

    void init() {
        nodes[0].child[0] = 1;
        nodes[0].cnt = n + 2;

        nodes[1].parent = 0;
        nodes[1].s = 0;
        nodes[1].e = n - 1;
        nodes[1].child[0] = 2;
        nodes[1].child[1] = 3;
        nodes[1].cnt = n + 2;

        nodes[2].parent = 1;
        nodes[2].s = -1;
        nodes[2].e = -1;
        nodes[2].cnt = 1;

        nodes[3].parent = 1;
        nodes[3].s = n;
        nodes[3].e = n;
        nodes[3].cnt = 1;

        top = 10;
    }

    int top = 0;

    static i64 seg_len(const Node& nd) {
        return std::llabs(nd.s - nd.e) + 1;
    }

    void push_down(int x) {
        Node& nd = nodes[x];
        if (!nd.rev) return;
        nd.rev = false;
        for (int dir = 0; dir < 2; ++dir) {
            if (nd.child[dir]) {
                nodes[nd.child[dir]].rev = !nodes[nd.child[dir]].rev;
                std::swap(nodes[nd.child[dir]].s, nodes[nd.child[dir]].e);
            }
        }
        std::swap(nd.child[0], nd.child[1]);
    }

    void update(int x) {
        Node& nd = nodes[x];
        i64 cnt = seg_len(nd);
        if (nd.child[0]) cnt += nodes[nd.child[0]].cnt;
        if (nd.child[1]) cnt += nodes[nd.child[1]].cnt;
        nd.cnt = cnt;
    }

    void rotate(int x, int dir) {
        int y = nodes[x].parent;
        push_down(y);
        push_down(x);

        nodes[y].child[dir ^ 1] = nodes[x].child[dir];
        if (nodes[x].child[dir]) nodes[nodes[x].child[dir]].parent = y;

        nodes[x].parent = nodes[y].parent;
        if (nodes[nodes[y].parent].child[0] == y) {
            nodes[nodes[y].parent].child[0] = x;
        } else {
            nodes[nodes[y].parent].child[1] = x;
        }

        nodes[x].child[dir] = y;
        nodes[y].parent = x;
        update(y);
    }

    void splay(int x, int target_parent) {
        for (push_down(x); nodes[x].parent != target_parent;) {
            int y = nodes[x].parent;
            int z = nodes[y].parent;
            if (z == target_parent) {
                if (nodes[y].child[0] == x) rotate(x, 1);
                else rotate(x, 0);
            } else {
                if (nodes[z].child[0] == y) {
                    if (nodes[y].child[0] == x) {
                        rotate(y, 1);
                        rotate(x, 1);
                    } else {
                        rotate(x, 0);
                        rotate(x, 1);
                    }
                } else {
                    if (nodes[y].child[1] == x) {
                        rotate(y, 0);
                        rotate(x, 0);
                    } else {
                        rotate(x, 1);
                        rotate(x, 0);
                    }
                }
            }
        }
        update(x);
    }

    int find(i64& key) {
        int curr = nodes[0].child[0];
        while (curr) {
            push_down(curr);
            i64 left_size = nodes[curr].child[0] ? nodes[nodes[curr].child[0]].cnt : 0;
            if (key <= left_size) {
                curr = nodes[curr].child[0];
                continue;
            }
            key -= left_size;
            i64 mid = seg_len(nodes[curr]);
            if (key <= mid) return curr;
            key -= mid;
            curr = nodes[curr].child[1];
        }
        return curr;
    }

    i64 cal(i64 s, i64 e, i64 idx) const {
        const i64 delta = std::llabs(s - e);
        const i64 mod2 = mod * 2;
        const i64 mod6 = mod * 6;
        const i64 is1 = static_cast<i64>((static_cast<u128>(delta) % mod2) * (delta + 1) % mod2 / 2 % mod);
        const i64 is2 = static_cast<i64>((static_cast<u128>(delta) % mod6) * (delta + 1) % mod6 *
                                         ((2 * delta + 1) % mod6) % mod6 / 6 % mod);

        if (s <= e) {
            i64 t = mul_mod(idx % mod, s % mod, mod);
            t = mul_mod(t, (delta + 1) % mod, mod);
            i64 term = mul_mod((idx + s) % mod, is1, mod);
            t = add_mod(t, term, mod);
            t = add_mod(t, is2 % mod, mod);
            return t;
        }
        i64 t = mul_mod(idx % mod, s % mod, mod);
        t = mul_mod(t, (delta + 1) % mod, mod);
        i64 term = mul_mod(((s - idx) % mod + mod) % mod, is1, mod);
        t = add_mod(t, term, mod);
        t = sub_mod(t, is2 % mod, mod);
        return t;
    }

    i64 idx = 0;
    i64 solve_impl(int r) {
        i64 ret = 0;
        push_down(r);
        if (nodes[r].child[0]) ret = add_mod(ret, solve_impl(nodes[r].child[0]), mod);

        const i64 len = seg_len(nodes[r]);
        if (idx >= 0 && idx + len <= n) {
            ret = add_mod(ret, cal(nodes[r].s, nodes[r].e, idx), mod);
        }
        idx += len;

        if (nodes[r].child[1]) ret = add_mod(ret, solve_impl(nodes[r].child[1]), mod);
        return ret;
    }

    i64 solve() {
        idx = -1;
        return solve_impl(nodes[0].child[0]);
    }

    void split_node(int id, i64 offset) {
        if (offset <= 1) return;
        splay(id, 0);
        int dir = nodes[id].s <= nodes[id].e ? 1 : -1;
        i64 olde = nodes[id].e;
        nodes[id].e = nodes[id].s + dir * (offset - 2);

        int z = nodes[id].child[1];
        push_down(z);
        while (nodes[z].child[0]) {
            z = nodes[z].child[0];
            push_down(z);
        }

        int new_id = top++;
        nodes[new_id].parent = z;
        nodes[new_id].child[0] = nodes[new_id].child[1] = 0;
        nodes[new_id].s = nodes[id].e + dir;
        nodes[new_id].e = olde;
        nodes[new_id].cnt = seg_len(nodes[new_id]);
        nodes[new_id].rev = false;
        nodes[z].child[0] = new_id;

        while (z != 0) {
            update(z);
            z = nodes[z].parent;
        }
    }

    void reverse_range(i64 s, i64 e) {
        if (s > e) std::swap(s, e);

        for (i64 target : {s + 2, e + 3}) {
            i64 x = target;
            int id = find(x);
            if (x != 1) {
                split_node(id, x);
            }
        }

        i64 x = s + 1;
        const int id1 = find(x);
        splay(id1, 0);

        i64 y = e + 3;
        const int id2 = find(y);
        splay(id2, id1);

        const int id3 = nodes[id2].child[0];
        nodes[id3].rev = !nodes[id3].rev;
        std::swap(nodes[id3].s, nodes[id3].e);
    }
};

u128 brute_force(i64 n, i64 k) {
    std::vector<i64> arr(static_cast<std::size_t>(n));
    for (i64 i = 0; i < n; ++i) arr[static_cast<std::size_t>(i)] = i;
    i64 s = 1 % n;
    i64 t = 1 % n;
    for (i64 step = 0; step < k; ++step) {
        i64 l = std::min(s, t);
        i64 r = std::max(s, t);
        std::reverse(arr.begin() + l, arr.begin() + r + 1);
        i64 ns = add_mod_n(s, t, n);
        i64 nt = add_mod_n(t, ns, n);
        s = ns;
        t = nt;
    }
    u128 sum = 0;
    for (i64 i = 0; i < n; ++i) sum += static_cast<u128>(i) * static_cast<u128>(arr[static_cast<std::size_t>(i)]);
    return sum;
}

i64 compute_fast(i64 n, i64 k, i64 mod) {
    SplayTree st(n, mod);
    i64 s = 1 % n;
    i64 t = 1 % n;
    for (i64 step = 0; step < k; ++step) {
        if (s != t) {
            st.reverse_range(s, t);
        }
        const i64 next_s = add_mod_n(s, t, n);
        const i64 next_t = add_mod_n(t, next_s, n);
        s = next_s;
        t = next_t;
    }
    return st.solve();
}

void run_checkpoints(i64 mod) {
    const u128 v1 = brute_force(5, 4);
    const u128 v2 = brute_force(100, 100);
    const u128 v3 = brute_force(10000, 10000);

    if (v1 != static_cast<u128>(27)) throw std::runtime_error("checkpoint R(5,4)");
    if (v2 != static_cast<u128>(246597)) throw std::runtime_error("checkpoint R(100,100)");
    if (v3 != static_cast<u128>(249275481640LL)) throw std::runtime_error("checkpoint R(10000,10000)");

    if (compute_fast(5, 4, mod) != static_cast<i64>(v1 % mod)) {
        throw std::runtime_error("fast mismatch R(5,4)");
    }
    if (compute_fast(100, 100, mod) != static_cast<i64>(v2 % mod)) {
        throw std::runtime_error("fast mismatch R(100,100)");
    }
    if (compute_fast(10000, 10000, mod) != static_cast<i64>(v3 % mod)) {
        throw std::runtime_error("fast mismatch R(10000,10000)");
    }
}

}  // namespace

int main(int argc, char** argv) {
    try {
        Options options;
        if (!parse_arguments(argc, argv, options)) return 1;
        if (options.run_checkpoints) {
            run_checkpoints(options.mod);
        }

        std::cout << compute_fast(options.n, options.k, options.mod) << '\n';
        return 0;
    } catch (const std::exception& ex) {
        std::cerr << "Error: " << ex.what() << '\n';
        return 1;
    }
}

Python

from __future__ import annotations

import re
import shutil
import subprocess
from pathlib import Path

ANSWER_RE = re.compile(r"answer\s*:\s*(.+)$", re.IGNORECASE)
EQUAL_RE = re.compile(r"=\s*(.+)$")


def parse_output(stdout: str) -> str:
    lines = [line.strip() for line in stdout.splitlines() if line.strip()]
    if not lines:
        return ""
    answers = []
    equals = []
    for line in lines:
        m1 = ANSWER_RE.search(line)
        if m1:
            answers.append(m1.group(1).strip())
        m2 = EQUAL_RE.search(line)
        if m2:
            equals.append(m2.group(1).strip())
    if answers:
        return answers[-1]
    if equals:
        return equals[-1]
    return lines[-1]


def should_skip_cpp_checkpoints(src: Path) -> bool:
    try:
        text = src.read_text(encoding="utf-8", errors="ignore")
    except OSError:
        return False
    return "--skip-checkpoints" in text


def run_cpp(binary: Path, src: Path, root: Path) -> str:
    cmd = [str(binary)]
    if should_skip_cpp_checkpoints(src):
        cmd.append("--skip-checkpoints")

    try:
        return subprocess.check_output(cmd, text=True, cwd=root)
    except subprocess.CalledProcessError:
        return subprocess.check_output(cmd, text=True, cwd=src.parent)


def solve() -> str:
    problem_id = __file__.split("Euler")[-1].split(".")[0]
    root = Path(__file__).resolve().parent.parent
    src = root / "solutionsCpp" / f"Euler{problem_id}.cpp"
    binary = root / "solutionsCpp" / f".euler{problem_id}_py_bridge"

    if not binary.exists() or src.stat().st_mtime > binary.stat().st_mtime:
        compiler = shutil.which("clang++") or shutil.which("g++")
        if not compiler:
            raise RuntimeError("No C++ compiler found (clang++/g++).")
        subprocess.check_call([compiler, "-std=c++17", "-O2", str(src), "-o", str(binary)])

    output = run_cpp(binary=binary, src=src, root=root)
    parsed = parse_output(output)
    if not parsed:
        raise RuntimeError(f"Euler{problem_id} bridge produced empty output.")
    return parsed


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

Java

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

public class Euler680 {
    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("Euler680.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(".euler680_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 Euler680 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("Euler680 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("Euler680 C++ bridge produced empty output.");
        }
        return parsed;
    }

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