Problem 662: Fibonacci Paths

Problem 662 source code

C++

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
#include <cmath>
#include <functional>

namespace {

using u32 = std::uint32_t;
using u64 = std::uint64_t;

constexpr u32 kMod = 1'000'000'007U;

struct Steps {
    std::vector<int> vertical;
    std::vector<std::pair<int, int>> other;
    int max_dx = 0;
};

std::vector<int> fibonacci_upto(int limit) {
    std::vector<int> fib{1, 2};
    while (true) {
        const int nxt = fib[fib.size() - 1] + fib[fib.size() - 2];
        if (nxt > limit) break;
        fib.push_back(nxt);
    }
    return fib;
}

Steps build_steps(int w, int h) {
    const int max_len = static_cast<int>(std::sqrt(static_cast<long double>(w) * w +
                                                   static_cast<long double>(h) * h));
    const auto fib = fibonacci_upto(max_len);

    std::vector<std::pair<int, int>> all;
    for (int f : fib) {
        const int fsq = f * f;
        const int x_max = std::min(f, w);
        for (int x = 0; x <= x_max; ++x) {
            const int y2 = fsq - x * x;
            if (y2 < 0) continue;
            const int y = static_cast<int>(std::sqrt(static_cast<long double>(y2)));
            if (y * y != y2) continue;
            if (y > h) continue;
            if (x == 0 && y == 0) continue;
            all.emplace_back(x, y);
        }
    }

    std::sort(all.begin(), all.end());
    all.erase(std::unique(all.begin(), all.end()), all.end());

    Steps s;
    for (const auto& [dx, dy] : all) {
        if (dx == 0) {
            s.vertical.push_back(dy);
        } else {
            s.other.emplace_back(dx, dy);
            if (dx > s.max_dx) s.max_dx = dx;
        }
    }

    std::sort(s.vertical.begin(), s.vertical.end());
    std::sort(s.other.begin(), s.other.end());
    return s;
}

u32 solve_case(int w, int h) {
    const Steps steps = build_steps(w, h);
    const int row_len = h + 1;
    const int ring = steps.max_dx + 1;

    std::vector<u32> rows(static_cast<std::size_t>(ring) * static_cast<std::size_t>(row_len), 0);
    std::vector<u32> acc(static_cast<std::size_t>(row_len), 0U);

    auto row_ptr = [&](int ridx) -> u32* {
        return rows.data() + static_cast<std::size_t>(ridx) * static_cast<std::size_t>(row_len);
    };

    for (int x = 0; x <= w; ++x) {
        std::fill(acc.begin(), acc.end(), 0U);
        u32* cur = row_ptr(x % ring);
        std::fill(cur, cur + row_len, 0U);

        for (const auto& [dx, dy] : steps.other) {
            if (dx > x) break;
            const u32* src = row_ptr((x - dx) % ring);
            for (int y = dy; y <= h; ++y) {
                u32 v = acc[static_cast<std::size_t>(y)] + src[static_cast<std::size_t>(y - dy)];
                if (v >= kMod) {
                    v -= kMod;
                }
                acc[static_cast<std::size_t>(y)] = v;
            }
        }

        for (int y = 0; y <= h; ++y) {
            u32 val = acc[static_cast<std::size_t>(y)];
            if (x == 0 && y == 0) {
                val += 1;
                if (val >= kMod) val -= kMod;
            }
            for (int dy : steps.vertical) {
                if (dy > y) break;
                val += cur[static_cast<std::size_t>(y - dy)];
                if (val >= kMod) val -= kMod;
            }
            cur[static_cast<std::size_t>(y)] = static_cast<u32>(val);
        }
    }

    const u32* target_row = row_ptr(w % ring);
    return target_row[h];
}

}  // namespace

int main() {
    assert(solve_case(3, 4) == 278U);
    assert(solve_case(10, 10) == 215846462U);
    std::cout << solve_case(10'000, 10'000) << "\n";
    return 0;
}

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.util.*;
public class Euler662 {
    public static String solve() {
        int MOD=1000000007,w=10000,h=10000;
        int maxLen=(int)Math.sqrt((double)w*w+(double)h*h);
        List<Integer> fibs=new ArrayList<>();fibs.add(1);fibs.add(2);
        while(true){int nxt=fibs.get(fibs.size()-1)+fibs.get(fibs.size()-2);if(nxt>maxLen)break;fibs.add(nxt);}
        List<Integer> vertical=new ArrayList<>();List<int[]> other=new ArrayList<>();Set<Long> seen=new HashSet<>();
        for(int f:fibs){long fsq=(long)f*f;for(int x=0;x<=Math.min(f,w);x++){long y2=fsq-(long)x*x;if(y2<0)continue;
            int y=(int)Math.sqrt(y2);if((long)y*y!=y2||y>h)continue;if(x==0&&y==0)continue;
            long key=(long)x*100001+y;if(seen.add(key)){if(x==0)vertical.add(y);else other.add(new int[]{x,y});}}}
        Collections.sort(vertical);other.sort(Comparator.comparingInt(a->a[0]));
        int maxDx=0;for(int[] o:other)maxDx=Math.max(maxDx,o[0]);
        int ring=maxDx+1,rl=h+1;long[][] rows=new long[ring][rl];
        for(int x=0;x<=w;x++){long[] acc=new long[rl];long[] cur=rows[x%ring];Arrays.fill(cur,0);
            for(int[] o:other){if(o[0]>x)break;long[] src=rows[(x-o[0])%ring];
                for(int y=o[1];y<=h;y++)acc[y]=(acc[y]+src[y-o[1]])%MOD;}
            for(int y=0;y<=h;y++){long val=acc[y];if(x==0&&y==0)val=(val+1)%MOD;
                for(int dy:vertical){if(dy>y)break;val=(val+cur[y-dy])%MOD;}cur[y]=val;}}
        return String.valueOf(rows[w%ring][h]);}
    public static void main(String[] args){System.out.println(solve());}
}