No Such Blog or Diary

ということで，横でゲームをしつつ冪を下位桁からの辞書順にソートするプログラムを組んでみた．冪をソートするときにはその桁数が大きすぎてメモリに載らないことが問題になる．そこで，基本的にメモリの節約をメインに考えて作成した．節約のための重要点は，冪をソートするといってもその全ての桁が必要ではなく，基本的には下位の桁の一部しか必要でないこと．そして，冪の下位桁は上位桁を計算しなくても正確に求められ，再計算も簡単であること．これらに基づき，最初は下位の一部を計算しておき，ソートのときに区別が付かなければより上位の桁まで再計算するようにした．

実際に計算してみると，２の冪の場合には冪が20000000になっても下位16桁だけでソートが完了．思いのほか下位桁がバラバラのようである．このときのメモリ使用量は 1G強．時間は...　分単位．それなりに動くプログラムが出来上がって満足．単位は去年とってしまったけど課題を提出しても良いかなぁ？

講義（単位取得済み）の課題で適当な基数の冪を下の桁からの辞書順でソートするプログラムを作れというものが出た．ついでに，階乗も同様にソートせよとの指示も出ている．

とりあえず，階乗を下の桁からソートするのは単純なのでプログラムする気力なし．やり方は以下のとおり．階乗の場合は 5 の倍数が現れるごとに 0 が少なくとも一つ増えるので，再開桁から連続する 0 の数が等しい５個程度の組をソートしておけば，あとはその組を 0 の数の多い順に並べるだけである．よって，このソートは入力サイズを n とすると O(n) で終了する．ちなみに，５個程度の組をソートするのに必要な有効桁数は１０桁もあれば足りるはずなので，

階乗を順に生成するのも n に関係ないオーダでできる．

ということで，ターゲットは冪のソートで，基数最下位桁が 0 でないものに．とりあえず案はできているのでコードを書きますか．

無名クラスの中で無名クラスを使いつつ，初期化用のメソッドまで呼んでいる分かりにくいコードを書いてみた．

        xpane.add(delTabButton = new JButton(){      // "Del Tab" ボタン
                JButton init(){
                    setText("Del Tab");
                    addActionListener(new ActionListener(){
                            public void actionPerformed(ActionEvent e){
                                delTab();
                            }
                        });
                    return this;
                }
            }.init());

init() が this をリターンしているのが鍵ですな．

そろそろみんなでACM/ICPCの練習会をしましょうということで，輪講の資料がやばいにもかかわらず数時間プログラム作成で現実逃避．とりあえず慣らしのために簡単なDPとして 会津国内予選のC を組むことに．今年の参加資格のない人間が３人と参加できる人が３人でやっていたのだが，参加資格のない人間のほうが早い...（私は１５分弱）　こんなんでいいのだろうか？　まあ，これから練習してなれてくれば大丈夫でしょうけど．さて，来週はもう少し人数を増やしてがんばろう．

IOCCC2004 のプログラムを眺めていたら omoikane.c なるファイルを発見（omoikaneはハンドルネームらしい）．名前がいい感じなのでソースを見てみる．なにやら何かのキャラクターのAAになってるらしい．よく見てみると "Moekan" "kero Q" なる文字が...　説明テキストを読むと "Rinia is a tool for embedding CRCs in text files." だし...　ということで，もえカンのリニアを模しているらしいが，作者のコメントどおりあまり良く分からない．

それはさておき，プログラムの動作自体はとても面白い．テキストファイルとかを読み込んで，CRCをそのテキストの中に埋め込むらしい．もちろん，そのCRCは「埋め込まれたCRCの文字列を含んたファイルのCRC」である．まあ，CRCを埋め込むファイル全体のCRCが変わるわけで，簡単に埋め込めないことは容易に理解できる．仕組みとしては，入力でCRCを埋め込む場所とCRC調整のために使える置換してもいい部分を用意してもらう．そんで，現在時刻を使って最後の置換可能文字（もしくはCRC埋め込み位置）までのCRCを決めちゃって，それを種にしてその後ろのCRCを計算してそれをファイルに埋め込む．あとは，がんばってその適当に決めてしまったCRCを達成するように置換文字を全パタン試す．うまくCRCを調整できたらおわり．まあ，それ以外のやり方が無いよねと思う．

ところで，IOCCCに出されるだけあってソースは読みにくい．３項演算子が大量に使われているのが主な原因．でも根気で読んでみると結構知らなかった書き方などを学べて勉強になる．この作者は他にもいろいろやっているようで，ホームページを見てみるとかなり面白い．どうやらソフト屋さんのようでACM/ICPCで World Final にいってたり ICFP のプロコンにでたりもしたらしい．Development Tools に vim はあっても emacs が無いあたりもすばらしい．なにより，日本人じゃないだろうにドメインが uguu.org だったり...　とにかくすげぇなぁ．

とりあえず，bash などのシェルスクリプトで外部の yes と head を呼ぶバージョン:

yes $0|head -$1

ただし，"Hello World"というファイル名で保存して，

bash Hello\ World 10

などで実行．とりあえず 15バイトで今のところ最小．

次に，perl で

print"$0\n"x$ARGV[0]

を同様に "Hello World" というファイル名で保存．

perl Hello\ World 10

などで実行．とりあえず 20 バイトで外部コマンド使用せず．

実行時のファイル名を使用しない場合には，それぞれ $0 を Hello World で置き換えるべし．その場合，24バイトと29バイトになる．

さて，これ以上縮まるかどうか...　とりあえず言語の候補としては perl 以外に無い気がするのでむりかも．文字列と数値を自動で変換してくれて繰り返しが簡単でコマンドライン引数が簡単に扱えて...　そんな言語が他にあったかなぁ？