Excel LAMBDA関数で「ハノイの塔」を解く

paiza×Qiita記事投稿キャンペーン「プログラミング問題をやってみて書いたコードを投稿しよう！」に参加してみた。

問題はハノイの塔

残念ながら、問題通りのアウトプットが作れませんでした。配列の状態を書き換えるのができないので、書き換えずに常に3本の杭の状態を返す関数を作ればよいのだと思うのですが、難しい。。。
=>何とか解くことができましたので、完成版はこちら。

使い方はこんな感じ。
円盤3枚を初期値として、4回まで動かすとしたら、=HANOI(3,4)とするイメージ。

Excel LAMBDA関数版「ハノイの塔」のコード

コード

HANOI = LAMBDA(_n, _t,
    LET(
        // Zコンビネータ。無名関数で再帰を実現するヘルパー関数
        Z, LAMBDA(_functionTemplate,
            LET(
                _applyFunction, LAMBDA(_recursiveFunction,
                    _functionTemplate(LAMBDA(_a1,_a2,_a3,_a4,_a5, _recursiveFunction(_recursiveFunction)(_a1,_a2,_a3,_a4,_a5)))
                ),
                _applyFunction(_applyFunction)
            )
        ),
        // ハノイの塔を解く関数。再帰呼び出しで実現
        _fncHanoi,Z(LAMBDA(_fnc, LAMBDA(_moves, _n, _from, _to, _work,
            IF(_n = 0,
                // voidをreturnできないので、空を表すレコードをスタックに積む
                VSTACK(_moves, HSTACK(_n, 0, 0)),
                LET(
                    _moveFromToOther, _fnc(_moves, _n-1,_from, _work, _to),
                    _pusedhMoveLog, VSTACK(_moveFromToOther, HSTACK("円盤:"&_n&"を", _from & "から", _to & "へ。")),
                    _return, _fnc(_pusedhMoveLog, _n-1, _work, _to, _from),
                    _return
                )
            )))),
        //　ハノイの塔を解く
        _solvedHanoi, _fncHanoi(VSTACK(0),_n,"杭A","杭C","杭B"),
        // 空のレコードを取り除く
        _removedEmptyDisc, LAMBDA(_table, FILTER(_table, INDEX(_table, 0, 1) <> 0))(_solvedHanoi),
        _toSeq, IF(ROWS(_removedEmptyDisc)<_t, SEQUENCE(ROWS(_removedEmptyDisc)), SEQUENCE(_t)),
        _return, MAP(_toSeq, LAMBDA(_i, TEXTJOIN("",TRUE, INDEX(_removedEmptyDisc,_i)))),
        _return
    )
);

JavaScript版「ハノイの塔」のコード

こんな感じ。

コード

const  hanoi=(n, t)=>{
    // 初期状態の杭
    let pegs = [
        Array.from({ length: n }, (_, i) => n - i),
        [],
        []
    ];

    // 移動の記録
    let moves = [];

    // ハノイの塔の再帰関数
    const _hanoi=(n, from, to, work)=>{
        if (n === 0) return;
        _hanoi(n - 1, from, work, to);
        moves.push([from, to]);
        _hanoi(n - 1, work, to, from);
    };

    // ハノイの塔を解く
    _hanoi(n, 0, 2, 1);

    // 指定された回数 t まで移動を実行
    for (let i = 0; i < t; i++) {
        let [from, to] = moves[i];
        pegs[to].push(pegs[from].pop());
    }

    // 各杭の状態を出力
    pegs.forEach(peg => {
        if (peg.length === 0) {
            console.log("-");
        } else {
            console.log(peg.join(" "));
        }
    });
};