重複なしで Hello, world! を Ruby だけで
CodeIQ に Hello, world! を3つ以上の言語で書きなさい、ただしそれぞれで使われてる文字種に重複があったらダメ、という問題がありました。
http://nabetani.hatenablog.com/entry/codeiq_hwx3_q766
私の解答は6言語使ったものでした。
http://shinh.hatenablog.com/entries/2014/03/18
今回は Ruby だけを使って、4つの Hello, world! ができました。言語が一つしか無いと複数言語を使うより色々なことをする余地が減るので、当然大変なので6つとかはちょっと無理です。
5つも厳しいかなぁと思っていて、なんらかの文字を出力する方法が4つ以上思いあたらないからです。4つというのは
- puts/putc/print 系
- IO#<<
- eval
- ラムダを使った eval
の4つです。あとは単純に任意文字列を作る手段が足りなくなっていきます。順に見ていきます
ひとつめ puts+putc 使用文字種10種類: " +89;cpstu"
putc 9+9+9+9+9+9+9+9;putc 8+8+8+8+8+8+8+9+9+9+9+9;putc 9+99;putc 9+99;putc 8+8+8+8+8+8+9+9+9+9+9+9+9;putc 8+9+9+9+9;putc 8+8+8+8;putc 8+8+8+8+8+8+8+9+9+9+9+9+9+9;putc 8+8+8+8+8+8+9+9+9+9+9+9+9;putc 8+8+98;putc 9+99;putc 8+8+8+8+8+8+8+8+9+9+9+9;putc 8+8+8+9;puts
色々試しましたが、最終的に丸括弧を消費すると最後で詰むので、丸括弧を使わない、つまり .chr などを必要としない putc がありがたいと判断しました。 8 と 9 だけを使っているのは、後で8進数を使うのでこいつらだけは余るのです。 10 は 8 と 9 では作れませんが、そこは puts で。
ふたつめ IO#<< 使用文字種12種類: "\n$/<=DOSTUz~"
STDOUT<<z=<<SS<<z=/$/=~<<ST SS zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz ST STDOUT<<z=<<SS<<z=/$/=~<<ST SS zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz ST STDOUT<<z=<<SS<<z=/$/=~<<ST SS zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz ST STDOUT<<z=<<SS<<z=/$/=~<<ST SS zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz ST ...
このコードは長いので以降省略。やってることは単純に、長い文字列作って、その長さを /$/=~ で調べて、それが文字コードになってるから文字列に << してその後 STDOUT に << する、と。
二つの << の優先順位が同じなので、なんとかするために = を使ってます。まぁ正規表現の =~ にも使ってるから丁度良い。文字列は <
みっつめ eval 使用文字種16種類: "\t%01234567Q\\aelv"
eval %Q%\160\165\164\163\42\110\145\154\154\157\54\40\167\157\162\154\144\41\12\42%
なんというか、そのまんまです。数字をケチってきたのでラクできます。
よっつめ lambda 使用文字種26種類: "!\"#&()*,-.:>?VW[]^_doqrw{}"
->(__){->(&_){_["",:"#{__[?q.ord^?>.ord]}r#{__[?d.ord^?,.ord]}#{__[?d.ord^?).ord]}#{__[?r.ord^?!.ord]}#{__[?d.ord^?!.ord]}","#{__[?q.ord^?V.ord]}#{__[??.ord^?{.ord]}#{__[?q.ord^?:.ord]}#{__[?q.ord^?:.ord]}o,#{__[?_.ord^?[.ord]}#{__[?d.ord^?&.ord]}#{__[?{.ord^?-.ord]}or#{__[?q.ord^?:.ord]}d!#{__[?_.ord^?[.ord]}#{__[?d.ord^?&.ord]}",?w.ord^?W.ord,?w.ord^?}.ord]}[&:"#{__[?q.ord^?#.ord]}#{__[??.ord^?{.ord]}#{__[?d.ord^?).ord]}d"]}[[*?!..?}]]
知らないと意味不明ですが、 Ruby で記号だけで Turing complete にするための、 ->(&_){_["",:"eval","code..."]}[&:"send"] というイディオムを使ってます。ここに ->()[]{}#: などを残すためにこれまでで苦労してました。
追記。 () 残す必要は無かったでした。
->__{->&_{_["",:"#{__[?q.ord^?>.ord]}r#{__[?d.ord^?,.ord]}#{__[?d.ord^?).ord]}#{__[?r.ord^?!.ord]}#{__[?d.ord^?!.ord]}","#{__[?q.ord^?V.ord]}#{__[??.ord^?{.ord]}#{__[?q.ord^?:.ord]}#{__[?q.ord^?:.ord]}o,#{__[?_.ord^?[.ord]}#{__[?d.ord^?&.ord]}#{__[?{.ord^?-.ord]}or#{__[?q.ord^?:.ord]}d!#{__[?_.ord^?[.ord]}#{__[?d.ord^?&.ord]}",?w.ord^?W.ord,?w.ord^?}.ord]}[&:"#{__[?q.ord^?#.ord]}#{__[??.ord^?{.ord]}#{__[?d.ord^?).ord]}d"]}[[*?!..?}]]
感想とか
どこに何を使うか、割と苦労したんですが、トリッキーなコードを書くとどうしても文字種消費しがちなため、完成してしまうと割とシンプルな4つになりました。難易度的にも言語バラバラ6種の方がやや大変でした。
5つ目は文字を出力する手段さえあれば、かなりキツいでしょうがなんとかなるかもしれません。ずるいですが `` を活用するとかも考えましたが、 1>&2 を使わずに出力できる気がせず。
Perl で同じことをすると、拡張正規表現での eval が使える少し古い Perl でも 3 種類が限度なんじゃないかと思っています。 id:ku-ma-me さんと Perl と Ruby がどっちが強いかみたいな話をしていたのですが、この問題なんかは割と象徴的な気がします。
ppencode 2 - 任意の Perl コードを予約語だけの Perl コードに変換する
@TAKESAKO さんが ppencode を作ってから 10 年経って、私が任意の Perl コードを小文字だけに変換するスクリプトを書いてからでも5年経つらしいですが、なんか任意の Perl コードを予約語だけの Perl コードに変換するスクリプトができました。
http://shinh.skr.jp/obf/ppencode.html
オリジナルの ppencode に敬意を表していろいろ雰囲気を似せておきました。割と色んな予約語が使われるようにしてみたりとか。
これは Perl が予約語だけあれば Turing complete ということなので、副産物として Quine もできました。
http://golf.shinh.org/reveal.rb?Quine/shinh+%28keywords%29_1431106882&pl
なんというか、 ppencode があれば後は print を eval に変えるだけちゃうん?という当然の疑問があると思うのですが、 ppencode より割と大変だったりします。 ppencode は要は
print chr 72 xor print chr 101 xor print chr 121 # Hey
みたいな感じで実現できて、数字の部分は length q q XXXX q とかしてやって XXXX の部分を q を含まないキーワードで適当に埋めてやれば OK です。
ただこれは文字数だけ print を呼べば良いからできる方法であって、 eval みたいに文字列を一旦まとめる必要があるとダメ。
小文字アルファベットしばり PerlやBase64 しばり Perlでは s//something/e を最初に連打することによって、好きな文字列を作ることができましたー、というのがこれまでのあらすじ。
これを予約語だけでやろうとすると、
s XX chr length ????? XYYY xor ... xor eval
の形になるとして、 X は 1 文字の小文字アルファベット、 YYY は e を含む文字列で正規表現の modifier として valid で、かつ、 XX と XYYY は予約語でないといけない、という条件になります。 XX と同じ文字が並んでる予約語は qq しか無く、 q ではじまって e を含む唯一の予約語である quotemeta は t が modifier として不適切です。
ああ、詰んだな、と放置してました。今回気付いたのは、1回の正規表現置換で無理なら2回やれば無理かなーということで、
s qq q s X X chr length ????? XYYY
の形、つまり最初に空白を足しておいてから、その空白を本命の文字に変えれば良いのではないかと。 X が連続してなくて良いので、 X の候補が m, q, s, x, y の5つに増えます。最初、 X = s, XYYY = sleep がうまくいきそうな気がしたんですが、 e が2つあると2回 eval されちゃって扱いにくいったらありゃしないのでもうちょっと眺めてると、 semop がありました。ありがとう POSIX 。まぁ splice とかも該当すると思いますが。
ここまで来るとあとはやるだけーと思ったのですが、空白を含んだスクリプトがうまく変換できません。一番最初にある空白を次の文字で入れ変えていくので、空白を詰めてしまうので。 print "Hey" だと
___________ # 最初に 11 文字空白を確保(_ で空白を示します) p__________ # 1文字ずつ空白が置きかわっていく pr_________ pri________ prin_______ print______ print______ # 空白を空白に置き変えてる print"_____ # 詰められてしまった print"H____ print"He___ print"Hey__ print"Hey"_
というように変換されていく感じ。 JS コード中の ppencode_core がこの変換をしてます。
こういう場合はまあ、空白が無い、評価すると空白を含んだ Perl コードになる Perl コードを作って、 2回 eval すれば良い…とのことで例のごとく version string に活躍してもらいました。
print "Hey" だと
$_="";v112.114.105.110.116.32.34.72.101.121.34
というコードを ppencode_core でエンコードして、これを2回 eval すれば良い、と。最初の $_=""; は $_ をいじってるとあまり厳密な変換じゃないな…と思ったからつけただけです。
長い間、「普通にできんじゃねーの?」→「あれ、できないな。。」を定期的に繰り返してたので解決して良かったと言えます
Base64 decoder/encoder in Perl
http://shinh.skr.jp/obf/b64_dec.pl
dXNlIE1JTUU6OkJhc2U2NDtwcmludCBlbmNvZGVfYmFzZTY0IGpvaW4nJyw8PjsKX19FTkRfXwo+ s//v62/e+s//v60/e+s//v44/e+s//v39/e+s//v39/e+s//join/+s//v32/e+s//base64/ss+ s//v95/e+s//decode/+s//v32/e+s//print/+s//v59/e+s//Base64/+s//v58/e+s//v58/e +s//MIME/+s//v32/e+s//use/s/eval
この Base64 ぽく見える物体は Perl コードで、実行すると引数で指定したファイルに対する base64 デコーダとして機能します。
$ perl b64_dec.pl b64_dec.pl > b64_enc.pl
元々のコードは Base64 でもあったので、 Base64 デコーダによって復元できました。復元されたスクリプトは Base64 エンコーダになってます。よって、
$ perl b64_enc.pl b64_enc.pl dXNlIE1JTUU6OkJhc2U2NDtwcmludCBlbmNvZGVfYmFzZTY0IGpvaW4nJyw8PjsKX19FTkRfXwo+ s//v62/e+s//v60/e+s//v44/e+s//v39/e+s//v39/e+s//join/+s//v32/e+s//base64/ss+ s//v95/e+s//decode/+s//v32/e+s//print/+s//v59/e+s//Base64/+s//v58/e+s//v58/e +s//MIME/+s//v32/e+s//use/s/eval
で元に戻ります。
TLE 2015
http://felicity.iiit.ac.in/contest/tle/
成果物: https://gist.github.com/shinh/64fbd3d43147f6a7bbb4
毎年思ってることだけど、ここ数年は特に脳死しているなーという時に行なわれてる…ので腑甲斐ないのはしょうがないんだよ。
今回は結構神回だったんじゃないかなー実は。たぶん処理速度の問題で SNUSP 問題が消え失せたんじゃないかと思うんだけど、あれ別に面白くなかった気がするから消えて良かったんでないかと思うます。あとたぶんだけどあのへんの問題が決定的な要因になったんでないかな、残っていれば。偶然から生まれた神回感が強い。
あとちなみに初回の延期時から問題は変わってない…気がするので、やろうと思えば2週間以上使えたんじゃないかな実は…僕は延期した日にやったことは SNUSP の仕様読んでたくらいで、他の問題はだいたい忘れて脳死してたので、当日まで準備とかしてないよ…ホントだよ
Distinct Substrings
ゴミみたいな答えができたらゴミを後ろにつけると高得点というすごい問題。主催者が深く考えてない問題が出るのは毎度恒例ではある。トップを取るとかはどうでもいいスコアシステムだったので瞬時に捨てた。
Find the GCD
GCD(P,Q) を求めよただし P,Q には n,m,R を使って色んなことをして作られる。みたいな問題。 P,Q は巨大でかつ問題の制限として四則演算オペレータ使っちゃいけないということなんで、賢いやりかたがあるんだろうなーと思いつつ、はて…としばらく死んでいた。
まさに脳死という感じで。脳死しててもしゃーないんで、とりあえず正の点数取るか、そのうちなんか降ってくるだろ、となるのが私の唯一偉いところだと思ってるので、とりあえず解いた。つまり多倍長整数で mod が計算できる程度のコードを +-*/% 無しで書きました。感想はしんどかった。
手元で通るぽいコードを投げてみると Runtime Error 。これは TLE だろうかなあ…と思いつつデカいケースを喰わせてみると 0.15 秒くらいかかる。 1 秒が TLE の問題でこれだけ時間かかってると、まあだめだろうな…と思いつつ、 gprof とかで最適化するのにムダな時間を使う。本当にムダだ。
本当にムダなので賢いやり方を探そう、まー R てのが与えられてるからこれとなんかすればいいんでしょ?てことで適当に色んなことをやってると、 GCD(P,Q) が GCD(P,2^R) と一致するじゃありませんか…てことで解いた。
翌日 kinaba さんにアレでなんでいいのって聞いたらそんなの当たり前じゃないですか的なこと言われて、いや実際当たり前だった。はい。
Life, the Universe and Everything
数字がいくつか与えられるので、 echo しなさい、で、 42 で出力を止めなさい。ただし -nostdlib ついてるよ、とのこと。
えっとそれは得意分野やんけ…と瞬殺してほったらかしてたけど、普通にゴルフ足りてなかった。
ASCII Weaving
もうこの手の飽き飽きなんだよ…というような、画像圧縮問題。いつも通りとりあえず RLE してそれぽい解ができる。
いつも通りだとこれに huffman かけるんだけど、なんか huffman てやる前からどのくらいのサイズになるか見積れるわけで、はてこれはそういう感じでは mame さんに絶対追いつけないぞ、なんかすごいことが行なわれてる…
ということでやる気が失せて放置。
Halting
C プログラムの停止性を判断せよとの問題。
全部停止するって言えば 4 点入るので、あとは固定解答与えりゃいいやろ…とやってみるとうまくいかないので眺めてみると。出てくる順番が変わってるぽい。
出てくる順番変わってるだけな気がしたけど、まあ限定された C インタプリタとか割とすぐ書けるよね…と思って書きはじめたら全然間に合わなかった。いやまあインタプリタ書けても停止性は判定できないわけだけど、ある程度できたらヒューリスティクス適当に入れりゃ適当に得点高いだろ、って思ってたんだけど…
Reverse Quine
いつも通りの Quine 。 g++ の時は #include のかわりに #import 使うてのは基本中の基本だったはずなのに、脳死しててできなかった。ひどい。
工夫したところは ext/rope を #include すれば stdio.h と string が自動的に手に入る、てことくらいでしょうかね…
まとめ
問題はすごく良かったと思います。が、全体的に脳死してた。そもそも開始時間から大幅に遅れて起きてる時点でアレですね…なんか年々体力とやる気が失われている気がする。それくらいしか取り柄がないというのに…
あとまあ最終版にスコアボード全く見ずに Halting やってたのもひどいなあと思う。自分が1位から落ちてることにすら気付いてたんだっけ…という感じ。もうちょい戦略的にやるべき
GLSL Quine
前から書いてみたいなーと思っていた、 GLSL による Quine です。
http://glslsandbox.com/e#23148.0
マウスカーソルを画面半分より下に送ると拡大して読みやすくなっていきます。 Quine になってるかの確認は困難ですが、ぱっと見た感じあってるような気がします…たぶん。
GPU によっては動かないみたい。 Macbookair だとデータを減らすと動くんで、なんか命令数の上限とか使ってるデータ量の上限とかにかかってるんですかね。 Macbookair で動く程度にデータを減らすのは大変そうと判断。
Tokyo Demo Fest になんか出したいなーと常に思ってるけど今年も何もしなかったので、これでお茶を濁そう…と思ってたらこれも間に合わなかった。
やりゃ動くに決まってるんだけど、 GLSL でまともな速度で動く手順を模索するのが手間でした。なんか頻繁にブラウザが刺さってみたり。
こちらの 4x4 フォントを使わせていただいています。
Exploit and defenses
会社でバイナリの脆弱性を攻撃する方法と、それに対して防御する方法の一般的な簡単な話を適当にしたので、スライドを置いておきます。
http://shinh.skr.jp/slide/exploit/000.html
なにか一般論を書いてたら終わった感。まぁそのぶん基本的なことを網羅できるかもしれません。実際どうやってんの?てのを案外知らなかったりするドメインですし。
CRC32 Quine
Quine Advent Calendar というのがあるのかーと思ったが、特にネタがなかったので一発ネタ。
http://www.adventar.org/calendars/645
$ curl http://shinh.skr.jp/dat_dir/crc32_quine1.txt > x % Total % Received % Xferd Average Speed Time Time Time Current Dload Upload Total Spent Left Speed 100 9 100 9 0 0 344 0 --:--:-- --:--:-- --:--:-- 346 $ crc32 x > y $ diff x y
2種類あります。