No Such Blog or Diary

人間抜かれると抜き返したくなる．ということで当初のプログラムからアルゴリズムを変えることなく約半分までがんばって縮めた．いまのところアルゴリズムの選択は間違っていなかったみたい．

red-black SOR を書いてみる．思いのほか単純にかけた．でもパラメータの値をどの程度にすればよいかわからず．ま，いいか．

文字列を与えられてたときに，その文字列を出力する最短の Brainf*ck プログラムを作りたい．使用するメモリセルの数を固定すると Assembly-line scheduling ににてるかなぁとか思ったら依存関係が思いのほか複雑で単純でないみたい．文字列を構成する文字の種類が限られているので，でかいテーブルをぶん回せばDPになるかも…

90bytes前後からなかなか縮まらなかったのだが，アルゴリズムを切り替えたら突然46bytesまで縮んだ．s コマンドのに p オプションをつけたのが正解らしい．

バブルソートを実装して走らせたら timeout を食らった．高々260文字程度のソートに7秒近くかかるのは駄目らしい．しょうがないのでバケットソートに切り替えてどうにか成功．サイズは204bytesで，これ以上はあまり縮みそうにない．バブルソートのほうが202bytesで少し小さいのが残念…　マージソートとかも書いてみようか？

よく考えたら 7 bytes 縮まった．現在 15 bytes．エンベッドモドキ強し．