WeChall - Few Bonaccis

Challenge

题目要求提交一个公网可访问的 HTTP endpoint。WeChall 会多次请求 ?n=N，服务需要返回第 N 个 Fibonacci 数的十进制字符串 MD5；每次请求的耗时上限是 2.618 秒。

题面给出的样例是：n=100 时，F(100) = 354224848179261915075，返回值应为 d8400bceb05dfe785afcd2da4fdb010e。

Solution

服务监听本地 8765 端口，读取查询参数 n，计算 Fibonacci 数，再对它的十进制表示计算 MD5。

#!/usr/bin/env python3
"""Fast Fibonacci MD5 microservice for WeChall Few Bonaccis challenge.
Returns MD5 of the Nth Fibonacci number (as decimal string).
Uses gmpy2.fib() which is highly optimized GMP implementation.
Handles negative indices: F(-n) = (-1)^(n+1) * F(n)
"""
import hashlib
import sys
import gmpy2
from http.server import HTTPServer, BaseHTTPRequestHandler
from urllib.parse import urlparse, parse_qs

# Remove int->str conversion limit for large numbers
sys.set_int_max_str_digits(0)


def fib(n):
    """Compute F(n) for any integer n (including negative).
    F(-n) = (-1)^(n+1) * F(n)
    """
    if n >= 0:
        return gmpy2.fib(n)

    pos_n = -n
    f_pos = gmpy2.fib(pos_n)
    if pos_n % 2 == 0:
        return -f_pos
    return f_pos


class FibHandler(BaseHTTPRequestHandler):
    def do_GET(self):
        parsed = urlparse(self.path)
        params = parse_qs(parsed.query)
        n_str = params.get("n", [None])[0]

        if n_str is None:
            self.send_error(400, "Missing n parameter")
            return

        try:
            n = int(n_str)
        except ValueError:
            self.send_error(400, "Invalid n")
            return

        f = fib(n)
        fib_str = str(f)
        md5_hash = hashlib.md5(fib_str.encode()).hexdigest()

        body = md5_hash.encode()
        self.send_response(200)
        self.send_header("Content-Type", "text/plain")
        self.send_header("Content-Length", str(len(body)))
        self.end_headers()
        self.wfile.write(body)

    def log_message(self, format, *args):
        sys.stderr.write(f"[Fib] {args[0]} {args[1]} {args[2]}\\n")


if __name__ == "__main__":
    port = 8765
    server = HTTPServer(("0.0.0.0", port), FibHandler)
    print(f"Fibonacci MD5 service listening on port {port}", flush=True)
    server.serve_forever()

把本地端口通过 cloudflared 暴露出去，并把公网入口提交给 WeChall：

$ cloudflared tunnel --url http://127.0.0.1:8765