#アルゴリズム
23 件
モールス符号 — 表が一つ、曖昧さが二つ、細部が三つ
モールス自体は簡単で、難しいのは細部です。空白は誰のものか、全角の点をどう正規化するか、そして「1 単位」がどれだけか。
落下点を計算するが、少しだけ外す相手
遊べるポン AI に必要なのは二つ。ボールの落下点を正確に求めること、そして毎回わざと少し外すこと。前者は三角波一回、後者はラリーごとに引き直します。
big O の誤用：定数と前提が次数より結果を決めることが多い
O(n log n) の整列が O(n²) の挿入整列に負けることも、O(1) のハッシュ探索が配列の線形走査に負けることもあります。入力規模・定数・メモリ局所性を先に確認します。
git bisect：「どのコミットで壊れたか」を一本のコマンドにする
退行調査の難所は二分探索ではなく「壊れている」の定義です。自動で判定するスクリプトを先に書けば、bisect は n 回のビルドを log n 回に縮めます。
五目並べ AI：必殺判定と探索の分業
素の alpha-beta では五目で必殺手を逃します。勝ち・受け・活四の三段で確定する手を先に処理し、残りだけを反復深化と置換表に渡す構成にしました。
メモリ配置：同じアルゴリズムが十倍遅い原因はたいていキャッシュ
主記憶への一回のアクセスは数百サイクル、キャッシュ行の取得は一回です。逐次アクセスとランダムアクセスの差は次数を上回ることが多いです。
デッドロック：四つの条件のどれか一つを壊せばよい
相互排他・保持と待機・横取り不可・循環待機。四つが同時に成立して初めて起きます。実務で壊しやすいのは循環待機で、ロックに全体順序を与えます。
壊滅的なバックトラック：正規表現が CPU を埋める理由
入れ子の量指定子は試行回数を指数関数的に増やします。(a+)+b は長い非一致入力一つでプロセスを止められます。入れ子を外すか、制限時間を設けます。
SQLite のインデックス：最左前置は制約ではなく整列の帰結
複合インデックス (a, b) は a が等しい範囲でのみ b が整列します。a を飛ばして b で絞るのは、使えるものが無いというだけのことです。整列として捉えれば暗記は不要です。
タイムゾーンと夏時間：UTC で保存しないと必ず壊れる
夏時間の日は 23 時間か 25 時間で、切り替え付近のローカル時刻は存在しないか二度現れます。UTC で保存し表示時に変換するのが唯一安定する模型です。
中国将棋のルールで間違えやすい四箇所
馬の足止め、象の目塞ぎ、砲の台越し、両王対面。着手生成を幾何層と合法層に分けることで、間違いの大半は消えました。
cron パーサを書く：5 フィールド、和集合の規則、そして 2 月 30 日
構文は 30 分で書けます。難しいのは意味論です。日と曜日を両方指定したときは積ではなく和、存在しない日時には終了条件が要り、7 も 0 も日曜です。
CSV はカンマで切るものではない：RFC 4180 の引用符と改行
引用符付きのフィールドが 1 つ現れた時点で split は破綻します。引用符は区切り文字と改行を包み、内部の引用符は 2 つ重ねて書きます。30 行の状態機械が正規表現より確実です。
リバーシの合法手：8 方向を 1 回の走査で
空きマスが合法なのは、8 方向のうち少なくとも 1 方向で相手を挟める場合です。判定と反転は同じ走査で済み、置いて戻すシミュレーションは要りません。
数独ジェネレーター：穴を掘り、唯一解を保つ、そしてページを固めたバグ
完成した解を先に作り、一マスずつ掘りながら唯一解を検証します。求解器で 0 を「無制限」と解釈していたため、空盤では全解を列挙し、新規ゲームが固まりました。
一貫性ハッシュ：マシンを 1 台足してもほぼ全鍵を並べ直さない理由
剰余による分割は台数が変わるとほぼ全データが移動します。ハッシュ空間を環にして時計回りで最初のノードに割り当てれば、動くのは 1 区間だけ。代償は仮想ノードです。
五目並べの勝敗判定：置いた 1 点だけ見れば足りる
着手ごとに盤面全体を走査するのは無駄です。勝敗は最新の 1 手でしか変わりません。置いた点から 4 方向へ伸ばして数えれば、盤面の大きさに依りません。
スライディングウィンドウ：「窓が何を保つか」を先に決める
窓が成立するのは、窓の妥当性が左右の端に対して単調に変わる場合です。保つ状態と縮める条件を先に書き出せば、2 ポインタの二重構造は自然に O(n) に償却されます。
単調スタック：「次に大きい要素」を O(n²) から O(n) へ
各添字は高々 1 回 push され 1 回 pop されるので、二重ループに見える形が線形になります。左右で最初に大きい／小さいものを探す形なら、同じ雛形が使えます。
2 進数に 1 がいくつあるか：ループから SWAR まで
popcount には 3 通りあります。1 の個数だけ回すループ、表引き、そしてビット列を並列に数える SWAR。桁違いに差が出ますが、Rust と WebAssembly は既に単一命令として持っています。
Union-find：2 行の最適化で 1 回の操作がほぼ定数になる
経路圧縮は木を平らにし、サイズによる併合は木を高くしません。両方入れて初めて計算量が逆アッカーマン関数に落ち、実用上は 5 を超えません。
2048：四方向を一つの操作に畳み込む
スライド・合成・得点は一度書けば足り、残り三方向は転置と反転で再利用できます。難しいのは「各タイルは 1 回の移動で最大 1 回しか合成しない」という規則です。
マインスイーパー：地雷の配置を最初のクリックまで遅らせる
最初のクリックで負けうるマインスイーパーは未完成です。配置を遅らせ、クリック位置の周囲 3×3 を除外することが、ここで最も重要な設計判断です。