Namaran

Code daily. Without assist.

2026-10-21

binom.zig

const std = @import("std");

var memo: [32]u64 = @splat(0);

fn binom(n: u5, k: u5) u64 {
    if (k == 0 or k == n) return 1;
    if (@inComptime()) return binom(n - 1, k - 1) + binom(n - 1, k);
    if (memo[n] == 0) memo[n] = binom(n - 1, k - 1) + binom(n - 1, k);
    return memo[n];
}

pub fn main(init: std.process.Init) !void {
    var buf: [256]u8 = undefined;
    var stdout_writer = std.Io.File.stdout().writer(init.io, &buf);
    const stdout = &stdout_writer.interface;
    try stdout.print("{d} {d} {d}\n", .{ comptime binom(4, 2), binom(4, 1), binom(4, 2) });
    try stdout.flush();
}

binom(n, k) は、異なる n 個から k 個を選ぶ組合せの数、二項係数(binomial coefficient)nCk を返すつもりの関数です。実行時は一度計算した値をグローバル変数の memo に覚えて再計算を省き、memo を読み書きできないコンパイル時は、そのまま再帰で計算します。main は 4C2 をコンパイル時に計算した値と、4C1、4C2 を実行時に計算した値を並べます。いまは 6 4 4 と出力されます。本来の出力は 6 4 6 です。

Answer

Wrong

var memo: [32]u64 = @splat(0);
    if (memo[n] == 0) memo[n] = binom(n - 1, k - 1) + binom(n - 1, k);
    return memo[n];

binom の値は n と k の2つで決まるのに、memo は n だけを添字にしています。先に呼ばれる binom(4, 1) は、nCk = n-1Ck-1 + n-1Ck(パスカルの三角形の関係)で binom(3, 1)、binom(2, 1) とたどり、memo[2] に2、memo[3] に3、memo[4] に4を書きます。続く実行時の binom(4, 2) は memo[4] が0でないので計算せず、k が違うのに4を返します。

同じ binom(4, 2) でも、comptime を付けた1つ目は正しく6になります。コンパイル時の呼び出しでは @inComptime() が true になり、再帰の途中も含めて memo を使う行に一度も届かないからです。コンパイル時の結果だけを見て関数を確かめると、実行時の経路の誤りは同じ関数の中にあっても見つかりません。

Right

var memo: [32][32]u64 = @splat(@splat(0));
    if (memo[n][k] == 0) memo[n][k] = binom(n - 1, k - 1) + binom(n - 1, k);
    return memo[n][k];

memo を n と k の2次元にすれば、binom(4, 1) の4は memo[4][1] に入り、binom(4, 2) は空の memo[4][2] を見て計算し直すので6を返します。二項係数は1以上なので、0を「まだ計算していない」の印に使えます。@inComptime で経路を分けた関数は、コンパイル時と実行時の両方で呼んで確かめる必要があります1。

  1. @inComptime の枝を消して両方の経路を1つにすると、comptime binom(4, 2) は memo を読むところで「unable to evaluate comptime expression」というコンパイルエラーになります。グローバルな var は実行時の値なので、コンパイル時には読めません。