2017/08/23(水)ヒューマンリソースマシーン 素因数に分解せよ 70STEP解法

はてブ数 2017/08/23 23:41 つーさ
プログラマだしアセンブラもかじってるし楽勝すぎるかな と思って見合わせてたのだけど、
まぁ、面白そうだし、と思って買ってプレーしてクリアしてみた。

終盤はそれなりに手応えがあって楽しめた。

貧弱な命令セットかつスタックもないのに、
ソートを実装しろと言われた日にゃ……
どのアルゴリズムを採用すべきかから迷いましたが、ええ。
(バブルソートではスピード目標を満たせなかった……

今日は YEAR 40 素因数分解せよ の回答が、よくできた気がするので、記事にしておこうと思う。

元々は、スピード目標の想定解法がわからなかったのが理由だけど、
25セル使えるし、テーブル作れば速いんじゃね、と思ってやり始めたのだけど。
以下、ネタバレ含む。
 

 

 

 

 

 

本来はどのような数字が入力されても素因数分解できるプログラムが好ましいのだけど、
今回はステップ数の短縮が目的なので、テストに通ればOKとしよう。

試行錯誤

書いてはテスト書いてはテストを繰り返していたところ、
20までの素因数分解ができていればテストに通りそうな予感。

そこで最初に作ったのは、そう、こんなメモリ配置だったんだ。
VQ232
52723
2112132
3217219
2iZ
入力をアドレスとしてテーブルを引くと最小の素因数が出てくる。(V,Q,iは割算用の変数)
それをそのまま出力し、入力値をそれで割ったものに更新。
1になったら(bump-,ifzero,bump+)終了。

で、これをテストしているうちに思ったのは、
2の倍数は頻出するのに、割り算がちんたらしておせーな!
2の割り算だけ、結果を保持しておくかな!

で、これ。
VQ-13-2
5-37-43
-511-613-7
3-817-919
-10iZ
負値が来たら動作を分岐した。
3の割り算は表現方法が思いつかんので愚直に割り算。

この実行を眺めていてまた思う。

ループ終了時は必ず素数が来るんだから、わざわざそれ自身で割って1にするのも無駄じゃね?
テーブル内のアドレスと値が一致していたら、そのまま出せばいいわな。

うん? というか、この一致判定の代わりに、ゼロ入れとけば……。
うん? あれ、それなら、3の倍数もテーブルにできるんじゃ……。

最初から、素数表を作るつもりで、
素数のところには0入れとくとかすれば、
ここにたどり着くのはもっと早かったろうな……。

というわけで、最終形がこれだー。

V002
0304-3
50607
-58090
10Z
入力値vをセルのアドレスとすると、以下のような値が取り出せる。
・入力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 ステップ。