無職なこともあり、とても楽しい問題だったこともあり、久々にほぼガチで参加してる会になりました。いや楽しかった。順位表が凍結された段階での最終順位は2位で、1位は絶対に無理、その後にできた変更はしょうもないので、おそらく7位とかそのあたりの、5位強みたいなところに落ちついているのでないかと想像してます。暫定2位といっても特に良いところはなく、得点を決める式のおかげで、大幅なとりこぼしが無いだけで、推定1位のウナギに対して全順序がついて負けてる形のはずで、大変くやしい。が、まあ僕的には頑張ったとは思う。 初動 パーサやシミュレータを実装して、簡単なシングルスレッドAI、下から順に塗っていって、既にあるブロックとつながっていないところに置かざるを得なくなると、 Flip する、というものを Ruby で書く。デフォルトよりは大幅によくなることを確認して、いい問題だなあ……と思いつつ、寝る。 シミ

https://beta.atcoder.jp/contests/wn2017_1/standings むっちゃ僅差で2位。残念。この212点差がどのくらい僅差かというと、最後にいじってたところにもう2行変更を入れることを思いつけていれば、軽く2000点は差がついて勝ててたと思いますし、そうでなくても後30分もあれば実装できた細かいヘッダの圧縮で逆転できた量です。自分に悔しがる気持ちというのがこれほど残ってたのか、と驚くほど悔しいです。でも勉強になったし楽しかったです。 やったことを書きつつ、そもそも圧縮アルゴリズムについて、私としては感動的だった知見を得られたので、書いてみようかと思います。 今回のコンテストは、チャンネル1つの(RGBじゃなくてグレースケールだと思えば良い)画像を64枚を可逆圧縮するというものでした。その64枚の画像は同じ座標について光の波長と時間を変えて気象衛星が観測

総じておだやかに楽しかった。 https://github.com/shinh/icfpc2014 1日目 初日、21時から問題を読む。んー普通だなーと思いつつとりあえず寝る。 起きて Lambda-man の AI を書きはじめる。普通だと思ったけど、 Lisp マシンってこういうふうな感じなんだなぁ、と、知らなかったので普通に勉強になった。とりあえず思った通りに動くものを作ろうということで、アセンブラを Ruby 上の DSL として書く。オペランドの数と型のチェックと、ラベルの解決をするくらいのやつ。 なんとなく何ができるかわかったところで、これはアセンブラ直書きは大変だし変更に弱い…ってことで、そのアセンブラの上に高級言語を作る必要を感じる。素直に Lisp でもいいけど、あまり Lisp 書き慣れてないので、 Ruby 上の DSL をもう1レイヤ重ねることにした。あとは bef

https://github.com/tric/trick2013 https://sites.google.com/site/trickcontest2013/home/ja 大変楽しく審査員をやらせてもらいました。いろいろ思ったことがあるので、いろいろ適当に書いていこうかと思います。 作品評 ざっくり僕が良いと思ったやつから順に書いていこうかと思います。 https://github.com/tric/trick2013/blob/master/usak/entry.rb $ruby.is_a?(Object){|oriented| language} これだけ短いコードに色々言えることがあってすごく良かったです。 is_a? Object と identifier じゃない ruby の構成要素が 2/5 という割合で入ってるのも良いし、ブロックを取らないメソッドにブロックを渡して良

有志でやってた、ぷよ AI 作ったりして遊ぶコードを github に起きました。 TODO やおかしいところがたくさんありますが、キリがないので、まあとりあえず置いておこうという… https://github.com/puyoai/puyoai 人類最強を実際のゲーム機上で倒すことを目標として作られてますが、脇道として色んなコードがごちゃごちゃ入っています。 Linux と Mac で動作するものが多いです。 duel/duel トップレベルで make してうまくいくとできる duel/duel は AI vs AI をシミュレータ上で戦わせることができます。例えば $ ./duel/duel cpu/hamaji/lps.sh cpu/shinyak/run.shなどとして AI 同士で戦わせることができます。 $ PUYO_REALTIME=1 ./duel/duel cpu/h

http://shinh.skr.jp/dat_dir/icfp12.tgz 二日目から遊んでました。 <vp0"L"2p0"F"0p0"E"0p0"D"*55p0"C"0p0"B"*25p0"A"0 p"d"00 v< >0"J"0p 0"M"0p v > >00g"F"0g2p 10g"F"0g1+2p :"F"0g2+ v v p0"N"0 < > "G"0p ^ > :"*"- #v_^ 2 v < ^ +1g0"G" _^#!-"@": < > :"\"- #v_ "G"0g v p > 010p 000p > #^~:00g 10g"e" +p:"R"-#^_00g 50p10g 60pv v p0"G"+1 < v< ^p00+1g00 _v#-5-5 < < p0"F"+3g0"F" < ^p01+1g01p000_v#g00< v < > ~$~$~$~$~$ "B" v

http://cr.yp.to/papers/primesieves.pdf を斜め読みしました。ドメインからわかる通り、 djb が共著なんですよね…アトキンさんが考えたふるいを djb が実装した、って感じですかね、たぶん。 N までの素数を高速に求める方法、って言うと誰でも思いつくのはアリストテレスエラトステネスさんのふるいで、誰でも意味がわかるし速いしでいいものなのですが、それより速くしましたよーという。具体的にはアリストテレスエラトステネス O(N log(N) log(log(N))) に対して O(N / log(log(N))) だそうです。 アイデアとしては、奇数を 4N+1 と 12N+7 と 12N+11 に分類して(4N+1 が 12N+1 と 12N+5 をカバーしてることと、 12N+3 と 12N+9 はどうせ 3 の倍数なんで自明に素数じゃないことを考えると

http://shinh.skr.jp/dat_dir/icfpc-2010/factory/genkey6.rb 任意の要求出力に対して、出力数 + 7 で回路を作れるコードです。とりあえず key prefix と Car #10060 への答えくらいは動いてることを確認したので、まぁ動いてるんじゃないかと。 説明を試みる。 ICFPC の問題の回路をどの程度短い回路で作れるか、っていう話があって、1入力ごとに遅延した回路を1つ増やして…っていう話がありました。言葉で説明できる気がしないので手順を書いてみます。 最初、 0 ターン目は 1 が欲しいです。 +------+ | | v v--+ | +---+ | | | 0 | | | +---+ | | | | | | +---+ | | | 1 | | | +---+ | | | +--|-+ | | v v--|----- 3よ

頑張りはしたんですが、正直もっとやれたんじゃないかとくやしい。最後まで有効なソルバ書けなかったって感じですし… コードはこのへん。こいうのって tgz とかよりディレクトリ置いとく方が面白いかなーと思ってそうした。 tern.rb あたりがひどい感じ。結果は 2002 台解いて 17 位。結果は悪くないんだよなぁ。 http://shinh.skr.jp/dat_dir/icfpc-2010/ 問題の内容は…略。作業の記憶をリプレイだけ。 まず最後にヒントとして key prefix というのを作る回路を作れと書いてあるので、それを頑張る。頑張ります。ゲートの推測とかどうやったか忘れた。1ゲートだけの回路を置いてみてどうなるかーとかで回路の特性を理解したんだと思う。ただこの段階では明確な規則は深く考えなかったし、自分の作った真理値表が正しいか自信なくてドキドキだった。 で、回路の特性がわか

最近ゴルフ場を新しいマシンに引越そうとしていて、ついでなのでシステムをもうちょっと丁寧にパッケージ化しようとしてます。そのついでとして、現在のゴルフ場について内部がどうなってるか、ということを少しまとめてみようと思いました。 結構似たようなことをするサービスもあるんですが(codepadとかllevalとか)、そのへんのコードとかは全く参考にしてないので、そういうのを見た方がいいかもしれませんし、あとゴルフ場固有の事情も色々あったりするかもしれません。まぁでも日本語でそのへん書いてるのはあんまり見たことがないので、多少参考になる部分もあるかもしれません。 今作業中のコードは github に入れていっています。 apt で入らないパッケージの処理以外はだいたい入ってるはずですが、まだ足りないものとかあるかもしれません。 http://github.com/shinh/ags システム自体は

なんか優勝しちゃったようです。それでエジンバラにいます。というわけでこの一年は C++ のわるくちを言うことはゆるされません。くれぐれも、気をつけて下さい。 勝因としては、まぁ運が良かったんだろうなーという。9位だったのに verification round で 1位になったそうですし。もうちょいポジティブに評価するならテストケース変わっても動く程度に robust だったってことですかねぇ。 なにか速報してくれてる方がいたのでリンクを。 http://twitter.com/liyanghu/status/3691832714 写真

今年もたのしかったです。個人的にはタイムロスな時間が多かったなぁと例年のことながら反省。 得点は 4141.0694 で内訳は 1001 verified 95 1002 verified 96 1003 verified 96 1004 verified 95 2001 verified 186.3992 2002 verified 179.83806 2003 verified 187.18097 2004 verified 186.2919 3001 verified 372.43011 3002 verified 355.6358 3003 verified 341.35196 3004 verified 366.24291 4001 verified 456.22528 4002 verified 457.82298 4003 verified 500.72479 4004 ve

7割くらい書いたところで存在を忘れていました。 http://slashdot.jp/sp/binary2008/bin2008_shinh.shtml 何かに使えることがあるかもだから(無いと思うが) com2txt 書いとくかーと書いたのでした。オリジナルの com2txt は短すぎないか。 base64 よりはちょっとデコードしやすそうなフォーマットだとはいえ。ただうちでは動かんかったのだけど。 でまぁ com2txt だけじゃつまらないのでどうでもいいネタをしょぼしょぼしこんだのでした。 以下解答。 ruby hh.gif > hh_ruby.comとかで出てきたファイルは ASCII のみで表現された Happy Hacking! と出力する COM ファイル オリジナルの GIF ファイルを出力する Ruby スクリプト オリジナルの GIF ファイルを出力する Perl スク

Quine の難しい点はたぶん、 自分自身を出力しようとして永久に書き終わらないよギャース クォート文字列中にクォート文字を入れられないよギャース という2点じゃないかなぁと思います。前者は変数を使えば簡単です。後者はクォート文字をエンコードできるようにしてやる、っていうのがまぁ基本的な考えかたではないかと思いますが、これは色々方法があります。一般的な作り方としては以下とかがすごくわかりやすかったです。 http://d.hatena.ne.jp/KeisukeNakano/20070814/1187070401 format 系 多くの言語で手軽に書ける…と思う。 %s で自分自身を出力できる && クォート文字列は %c で、っていうのが基本的な発想。 Ruby だと、 printf a="printf a=%c%s%c,34,a,34",34,a,34 とかが基本形。いくつか短くする

わーいなんか2位らしい。第一報ありがとうございます。ずっと見間違いを疑ってましたがビデオ見たので間違いない。1日なんで勝ったのか不思議だったので考えてたので、勝てば官軍ということで、勝因について書いてみます。 運 いやこれは運だろう…正直なところ、最後のラウンドに残ってた、ってとこまでは、死亡する率を減らす的な意味でプログラムの良し悪しも影響したかなぁ、とか思うんですけど、最後のラウンドはまぁ、一発勝負っぽいんで運が強いでしょうねえ…最後のラウンドまで残っていた、という意味の方も、まぁ運悪く火星人三回連続当たった事件とかありえるでしょうし… メタゲーム これも運みたいなもんですが、なんかこう、詳しく見れてないですが、あまりに期待通りの問題だったんじゃないかなぁと思います。迷路はまぁややこしいのはだいたい無理、っていう感じで良しとしてたんですが、時間がかかるマップだと、たまたまそのマップだけ

なんとなく小さい Web サーバを書いてみました。 Web サーバというかどんなリクエストでも固定応答するだけ。 http://shinh.org:40960/ 例のごとく 58Byte Hello を参考に。まだ縮むと思うけど飽きた。 BITS 32 ORG 0 DB 0x7F ; e_ident entry: inc ebp ; e_ident 'E' dec esp ; e_ident 'L' inc esi ; e_ident 'F' mov dl, 102 ; socketcall inc ebx ; socket(1) lea esp, [ecx+12] push byte 0 push byte 1 push byte 2 dw 2 ; EAX is broken dw 3 hige: xchg eax, edx int 0x80 inc ebx ; bind(2) add

Perl は正規表現とか " ではさまれた文字列の中にある変数とか配列を展開してくれるんですが、これは明らかに正規表現の文字クラス ([abc] とか書くヤツ) とブツかるわけです。 以下のコードは @a に 0-999 まで "x" っていう変数をつっこんでから s/$a[...]/y/; 的なことを実行して、 $_ に入ってる x を y に変えようとするコードをいくつか。 #!/usr/bin/env perl for ($i=0; $i < 999; $i++) { $a[$i] = "x"; } $_ = "x"; s/$a[12]/y/; print "12: $_\n"; $_ = "x"; s/$a[123]/y/; print "123: $_\n"; $_ = "x"; s/$a[-2]/y/; print "-2: $_\n"; $_ = "x"; s/$a[-22]

スタック言語の最小言語ってどんな感じかなぁと考えていて以下のような言語を考えました。 + => スタックトップに 1 を足す - => スタックトップに 1 を引く 0 => スタックに 0 を積む : => スタックトップを取り除き、その値の深さの値をスタックに積む . => スタックトップを取り除き、その値を標準出力に吐く , => 標準入力から 1Byte 受け取り、スタックに積む [ => スタックトップを取り除き、その値が 0 なら対応する ] の次にジャンプ ] => 対応する [ にジャンプ説明が必要なのは : だけでしょうか。 0: がスタックの一番上をコピー、 0+: でスタックから二番目の値をコピー、です。 実装はほとんど BFI.c です。 http://shinh.skr.jp/obf/BSI.c diff はこれだけ。 --- BFI.c 2007-07-14 0

http://shinh.skr.jp/dat_dir/golf_prosym.pdf を置いときました。ほげー。

http://hp.vector.co.jp/authors/VA003988/gpcc/07g1.htm をやろうかなと思ってます。プログラム対戦系好きな人はどうでしょうか。 ちょっとプログラム書いてみた感じ、 全ての可能な指し手が10000手くらいで、1ターンごとの候補数500程度、序盤に1個だけのピースを置くなどの(プログラム的に判断できる)明らかな悪手が結構ある、終盤は可能な手が急速に減る、最大42ターンで普通40ターン切るくらい、などなど、オセロ程度の難易度のゲームなのかなという気がしています。 あとはカンですが、オセロで言うところの可能着手数+それぞれのセルの得点、みたいな適当(だけどそれなりに強い)盤面評価が難しいかなという気はします。あと逆転少ないゲームだし、モンテカルロもそれなりに行けそうな。 ちなみに実物何度かやったことあるけど、デュオはそれなりにできるけど、4人でやる