paiza×Qiita記事投稿キャンペーン「プログラミング問題をやってみて書いたコードを投稿しよう！」に参加してみた。
問題はハノイの塔
先日のExcel LAMBDA関数で「ハノイの塔」を解くでは、問題通りのアウトプットが作れなかったですが、今回はそのリベンジ。無事解くことができました。
リベンジ:「ハノイの塔」を解く。
使い方はHANOI(3,4)のように使います。
hハノイの塔と接頭辞が付いてますが、これは先日紹介したExcel LabsアドインでExcel LAMBDA関数をモジュール化しているためです。
できあがったコードは次の通り。。。ですが、遅い。。。円盤3枚でもまぁまぁ遅いですが、4枚にするとHANOI(4,8)くらいになると全然応答が返ってこないです。。。
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)
)
),
// 杭1の初期化。3枚の円盤なら{0, 3, 2, 1}を生成
_fncInitStartPeg, LAMBDA(_n,
LET(
_return, HSTACK(0,MAKEARRAY(1, _n, LAMBDA(_r, _c, IF(_r = 1, (_n - _c) + 1, 0)))),
_return
)
),
// ハノイの塔を解く関数。再帰呼び出しで実現
_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
)
)))),
// 引数_nまで_mvoes配列に格納されたFrom杭とTo杭の円盤を動かす指示に従って円盤を動かす
_fncGetHanoiDiscStatus, Z(LAMBDA(_fnc, LAMBDA(_moves, _n, _peg1, _peg2, _peg3,
IF(_n = 0,
VSTACK(_peg1, _peg2, _peg3),
LET(
_return, LET(
_disc, INDEX(_moves, 1, 1),
_from, INDEX(_moves, 1,2),
_to, INDEX(_moves, 1, 3),
_index, _from * 10 + _to,
_return, SWITCH(_index,
// 杭1からPOPして杭2にPUSH
12, _fnc(DROP(_moves, 1,), _n-1, DROP(_peg1, , -1), HSTACK(_peg2, _disc), _peg3),
// 杭1からPOPして杭3にPUSH
13, _fnc(DROP(_moves, 1,), _n-1, DROP(_peg1, , -1), _peg2, HSTACK(_peg3, _disc)),
// 杭2からPOPして杭1にPUSH
21, _fnc(DROP(_moves, 1,), _n-1, HSTACK(_peg1, _disc), DROP(_peg2, , -1), _peg3),
// 杭2からPOPして杭3にPUSH
23, _fnc(DROP(_moves, 1,), _n-1, _peg1, DROP(_peg2, , -1), HSTACK(_peg3, _disc)),
// 杭3からPOPして杭1にPUSH
31, _fnc(DROP(_moves, 1,), _n-1, HSTACK(_peg1, _disc), _peg2, DROP(_peg3, , -1)),
// 杭3からPOPして杭2にPUSH
32, _fnc(DROP(_moves, 1,), _n-1, _peg1, HSTACK(_peg2, _disc), DROP(_peg3, , -1)),
NA()),
_return
),
_return
)
)))),
// ハノイの塔を解く
_solvedHanoi, _fncHanoi(VSTACK(0),_n,1,3,2),
// 空を表すレコードを取り除く
_removedEmptyDisc, LAMBDA(_table, FILTER(_table, INDEX(_table, 0, 1) <> 0))(_solvedHanoi),
// どこまで円盤を動かすか
_toNum, IF(ROWS(_removedEmptyDisc) < _t, ROWS(_removedEmptyDisc), _t),
// 指定した円盤の移動回数動かした結果を取得
_hanoiDiscStatus, _fncGetHanoiDiscStatus(_removedEmptyDisc, _toNum, _fncInitStartPeg(_n), HSTACK(0), HSTACK(0)),
// 一番左の列がダミーのゼロ列なので取り除く
_s1, DROP(_hanoiDiscStatus,,1),
// 空のセルは#N/Aなので空文字""に変換。そうしないとTEXTJOINが#N/Aになってしまう
_s2, IF(ISNA(_s1), "", _s1),
// BYROWで行単位に移動し、カレント行を空白1文字区切りでTEXTJOINした結果の文字長さがゼロなら"-"に変換し、違うならそのまま返す
_return, BYROW(_s2, LAMBDA(_CurrentRow, LET(
_line, TEXTJOIN(" ", TRUE, _CurrentRow),
IF(LEN(_line) = 0,
"-",
_line
)))),
_return
)
);