2017/08/23(水)ヒューマンリソースマシーン 素因数に分解せよ 70STEP解法
2017/08/23 23:41 まぁ、面白そうだし、と思って買ってプレーしてクリアしてみた。
終盤はそれなりに手応えがあって楽しめた。
貧弱な命令セットかつスタックもないのに、
ソートを実装しろと言われた日にゃ……
どのアルゴリズムを採用すべきかから迷いましたが、ええ。
(バブルソートではスピード目標を満たせなかった……
今日は YEAR 40 素因数分解せよ の回答が、よくできた気がするので、記事にしておこうと思う。
元々は、スピード目標の想定解法がわからなかったのが理由だけど、
25セル使えるし、テーブル作れば速いんじゃね、と思ってやり始めたのだけど。
以下、ネタバレ含む。
本来はどのような数字が入力されても素因数分解できるプログラムが好ましいのだけど、
今回はステップ数の短縮が目的なので、テストに通ればOKとしよう。
試行錯誤
書いてはテスト書いてはテストを繰り返していたところ、20までの素因数分解ができていればテストに通りそうな予感。
そこで最初に作ったのは、そう、こんなメモリ配置だったんだ。
| V | Q | 2 | 3 | 2 |
| 5 | 2 | 7 | 2 | 3 |
| 2 | 11 | 2 | 13 | 2 |
| 3 | 2 | 17 | 2 | 19 |
| 2 | i | Z |
それをそのまま出力し、入力値をそれで割ったものに更新。
1になったら(bump-,ifzero,bump+)終了。
で、これをテストしているうちに思ったのは、
2の倍数は頻出するのに、割り算がちんたらしておせーな！
2の割り算だけ、結果を保持しておくかな！
で、これ。
| V | Q | -1 | 3 | -2 |
| 5 | -3 | 7 | -4 | 3 |
| -5 | 11 | -6 | 13 | -7 |
| 3 | -8 | 17 | -9 | 19 |
| -10 | i | Z |
3の割り算は表現方法が思いつかんので愚直に割り算。
この実行を眺めていてまた思う。
ループ終了時は必ず素数が来るんだから、わざわざそれ自身で割って1にするのも無駄じゃね？
テーブル内のアドレスと値が一致していたら、そのまま出せばいいわな。
うん？ というか、この一致判定の代わりに、ゼロ入れとけば……。
うん？ あれ、それなら、3の倍数もテーブルにできるんじゃ……。
最初から、素数表を作るつもりで、
素数のところには0入れとくとかすれば、
ここにたどり着くのはもっと早かったろうな……。
というわけで、最終形がこれだー。
| V | 0 | 0 | 2 | |
| 0 | 3 | 0 | 4 | -3 |
| 5 | 0 | 6 | 0 | 7 |
| -5 | 8 | 0 | 9 | 0 |
| 10 | Z |
・入力vが素数であるとき 0
・入力vのもっとも小さい素因数が2のとき、vを2で割った結果
・入力vのもっとも小さい素因数が3のとき、vを3で割って符号反転した結果。
このテーブルさえできてしまえば、
あとはテーブルを引いていくだけで素因数分解ができる。
すなわち、
・値が0のとき それを出力して終了、
・値が正のとき 2を出力して入力を値で上書き、
・値が負のとき 3を出力して入力を値の補数で上書き
するだけ。
ああ、もう割り算しなくていいんだ……。
以下、プログラム全体。
[init] copy from 24 (0が入ってる) copy to 2 copy to 3 copy to 5 copy to 7 copy to 9 copy to 11 copy to 13 copy to 17 copy to 19 copy to 4 bump + 4 bump + 4 copy to 6 bump + 6 copy to 8 bump + 8 copy to 10 bump + 10 copy to 12 bump + 12 copy to 14 bump + 14 copy to 16 bump + 16 copy to 18 bump + 18 copy to 20 bump + 20 copy from 24 sub 6 copy to 9 sub 4 copy to 15 jump to main <output_i> copy from 0 outbox <main> inbox copy to 0 <loop> copy from [0] if zero jump to <output_i> if negative jump to <divide_by_3> <divide_by_2> copy to 0 copy from 4 (2が入ってる) outbox jump to <loop> <divide_by_3> sub [0] sub [0] copy to 0 copy from 6 (3が入ってる) outbox jump to <loop>実行してみたところ、これで 70 ステップ。