« 「プラス・マイナス・ゼロ問題」の高度じゃないコード | トップページ | 「デスコロC #2」の高度じゃないコード »

2016年2月24日 (水)

「バイバイマンを数えよう」の高度じゃないコード

「高度じゃないコード」シリーズその5は「バイバイマンを数えよう」です。

バイバイマンは1日毎に体のサイズが倍増します。 そして、体の大きさが10を超えると、10の位の数のサイズと1の位の数のサイズの2匹に分裂します。 1日目にサイズ1のバイバイマンが1匹いる状態から開始し、1日目~100日目までのバイバイマンの数を出力してください。

バイバイマンのサイズは、1日毎に 1⇒2⇒4⇒8 と大きくなり、その翌日、1と6に分裂するので、ここで1匹増えます。そして、6の方がまた翌日に、1と2に分裂し、さらに1匹増えます。ということで、バイバイマンのサイズは、1・2・4・6・8 の5種類しか存在しません。そこで、それぞれのサイズのバイバイマンが何匹いるかを、a・b・c・d・e とすると、Rubyでは、a,b,c,d,e=d+e,a+d,b,e,c で翌日の匹数が計算できます。また、1匹増えるのは、分裂してサイズ1のバイバイマンが生まれた時なので、a の値を集計していけば、全部で何匹いるかがわかります。

これをRubyで組んだのが最初に提出した次のRuby57Bです。

Cで組む際には、int型ではオーバーフローするので、long long型を使用しました。ただ、Rubyのような書き方ができないので、必然的に長くなります。ちなみに、long long型の表示フォーマットに使う "%lld" は、色々と試してみると "%qd" でもいいことがわかりましたので、それを使い、色々と試行錯誤の末、次の87BがCの最終提出版となりました。

その後、再度、Rubyに戻って、Cと同様に配列を使うことで9バイト短くできたのが、次のRuby48Bです。

そして、今回、CodeIQで初めてAssemblerに挑戦してみることにしました。実行くんや ideone.com では2つの種類のAssemblerが選択でき、1つはgcc、もう1つはnasmですが、本番の環境では1種類しかなく、試してみるとnasmの方でした。コーディングする上での情報がまるでありませんでしたが、唯一の手がかりとなったのが、ideone.com でnasmを選択すると出て来る、「template」と「sample」のコードでした。それにより、80386のニーモニックで書けばいいこと、そして、使用されているのがLinuxのシステムコールであることがわかりました。

で、その昔、FM TOWNS用プログラムを組む際に非常にお世話になった「80386プログラミング」(別名電話帳)を引っ張り出して来て組んだのが次の548Bのコードです。少しでも短くするため、例えば、普通、xor eax,eax と書くところは mov eax,0 とかにしています。

最後のおまけはインチキコードです。Windows上のnasmで実行ファイルを作成し、コード部分をダンプしてデータとして16進数で入れました。ところが、実行くんでも ideone.com でも正常に動作したんですが、本番の環境では動作しませんでした・・・残念!

|

« 「プラス・マイナス・ゼロ問題」の高度じゃないコード | トップページ | 「デスコロC #2」の高度じゃないコード »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/99795/63255933

この記事へのトラックバック一覧です: 「バイバイマンを数えよう」の高度じゃないコード:

« 「プラス・マイナス・ゼロ問題」の高度じゃないコード | トップページ | 「デスコロC #2」の高度じゃないコード »