Hatena::ブログ(Diary)

まめめも このページをアンテナに追加 RSSフィード

2015-07-14

[C][IOCCC] The 23rd IOCCC の結果が公開されました

C 言語のプログラムの汚さで競い合うプログラミングコンテストThe 23rd International Obfuscated C Code Contest (IOCCC 2014) の結果がようやく公開されました。 ようやく :-)

ref: http://www.ioccc.org/years.html#2014

既報の通り、自分は以下の 2 つの賞を貰いました。

紹介はそのうち。

あと、IOCCC 2015 も開催されるようで、ルールのドラフトなど出てます。締切は 10/10 。

2015-04-27

[][] 告知:「超絶技巧プログラミング」の本を書いてます

突然ですが告知です。今までこの日記とかで公開してきた奇妙なプログラムを集めて、本を書くことになりました。今日はエイプリルフールではありません。

コンセプトは、「実務に役立たないプログラミング本」です。誰得?という声が聞こえてきそうですが、手段としてのプログラミングしか知らない人に、一味違うプログラミングの楽しさを知ってもらうきっかけになればいいなとか考えてます。

という建前ですが、内容は完全にアレです。新作を含む30本以上のプログラム紹介と、その開発技法の解説をとうとうと語っています。本当に誰得な本ですが、Qlobe とか Merry Quine-mas とか Quine リレーとか ASCII Fluid とか小文字だけ Ruby プログラムとか放射線耐性 Quine とかについて、ネタバレを知りたい人 (誰?) や自分でも書いてみたい人 (誰?) は必読です。

あと、どんな風にネタを考えてるかとか、IOCCC 勝数歴代 2 位のぼくが教える IOCCC の勝ち方(大げさ)とか、いろいろ書いてます。コンピュータ書籍界の三大奇書を目指します。

ということで、技術評論社から今年中の発売を目指して、現在鋭意執筆中です。ご期待ください。

追記: 正式な書名や価格や発売時期など、もろもろ未定です。決まったらまた告知します。

2015-03-02

Time Limit Exceeded 2k15 参加記録

ref: http://felicity.iiit.ac.in/contest/tle/

変態プログラミングコンテスト TLE に初参加しました。簡単に記録を。

コンテストの概要

インド人がやってる大会。C/C++ 限定。5 〜 10 問程度出題される。多くの問題は、変な制約下でのコードゴルフ

各問題で一番短いプログラムを submit した人が 100 点。二位以下は一位の人の長さとの比で点が決まる。

運営はわりと適当。今回は開催が 4 回くらい延期したり。問い合わせメールを投げても回答は期待できない感じ。あと開催中に問題が減ったとか。自分が参加したのは消滅後だったので、消えた問題のことは知らない。

Distinct Substrings

与えられた文字列の相異なる部分文字列の数をカウントせよ。という問題。

与えられる文字列長が短い(確か最長100)ので、部分文字列を全列挙してカウントするだけ。

Find the GCD

  • P = n - m
  • Q = n^2 - m^2 + 2nm - (2^R + 2)nm
  • 0 < m < n, gcd(n, m) = 1
  • 0 < P, Q <= 10^2000
  • 0 < R <= 16

を満たす P, Q, R が与えられるので、gcd(P, Q) を求めるプログラムを書け。ただし +, -, *, /, % は使用禁止。という問題。

数式が無意味に複雑だけど、P が 2^k を因数に持つとき、gcd(P, Q) = 2^min(k, R) なことはすぐにわかる。というか四則演算禁止だとそんな難しいことできないし。

最初に手を付けたけど、最後までパスしなかった問題。コード。R <= 16 なので P の下 16 桁くらいを取り出して、2 で割り切れるかどうかをシフト演算で見ていく感じ。何が悪いでしょう?*1

自分としては解けたつもりなのにどうしてもパスしないので、半分くらいの時間はこれの問題文解釈と試行錯誤に溶けていった。採点のところに空白を取り除く的なことが書いてあったのが気になり、空白無しでプログラムを書こうとしてみたとか。あと入力例として P = 8017723549, Q = 59173349743176010825 ってあったんだけど、この Q に対して Q = n^2 - m^2 + 2nm + (2^R + 2)nm に解はないので何か出題ミスってんじゃないのかとか。なお P = n + m, Q = n^2 + m^2 + 2nm + 2^Rnm には解がある(n = 8016478423, m = 1245126)。この定義でも解き方は変わらないので、問題作成中に P と Q の定義を変えたけど、入力例は変え忘れたとかそんなんだと思う。

Life, the Universe and Everything

入力の数列をそのまま出力しつつ、42 を見つけた時点で終了するプログラムをできるだけ短く書け。ただしプログラムは -nostdlib オプション付きでコンパイルされる。という問題。

コード。標準ライブラリが一切使えないので、インラインアセンブリでread/write/exitシステムコールを呼び出す。ひと目で「この問題では勝てない」って思ったので、あまり頑張らなかった。1 位の kikx さんにダブルスコアにならなかっただけで十分満足。

ASCII Weaving

指定されたアスキーアートを出力するプログラムをできるだけ短く書け。という問題。

コード。これまでの変態プログラミングの経験から、こういうデータは境界線だけ保持しといてプログラム的に境界内を塗りつぶすと短く書けることを知ってたので、過去のコードを再利用しつつあっさり書いたら、2 位(たしか shinh さん)に倍近くの点差で勝てて驚いた。その後 RLE から LZ78 に置き換えたら更に半分くらいになった。

Halting

与えられた C プログラムが停止するかしないかを答えるプログラムを書け。という問題。唯一ゴルフではない。

気づかなかったんだけど与えられる C プログラムは決まっているらしく(順番は変わる)、入力プログラムを適当にハッシュ化して正解データと対応つける感じで満点が取れるらしい。全く思いつかなかったので、やる気なく全部 yes と答えるプログラムを投げておいた。

Reverse Quine

自分自身を反転させた文字列を、自分自身の長さの回数だけ出力するプログラムを書け。という問題。

これで高順位を取れなかったのが一番残念。いやあ、恥ずかしながら C で繰り返しのない Quine は書けないと思ってた。ほうぼうで「C ではできない」って言ってきた気がするなあ。IOCCC とか。

まとめ

とてもおもしろかったです。みんなもっと参加するといいと思うよ。

あと全然関係ない余談ですが、大会中に IOCCC 2014 の勝者レビュー用 tarball がついに届いた!今月中にはソースコードが公開される見込みとのこと。

*1:答え:P = 10000000000000000000000 みたいな入力に対して無限ループする。kikx さんありがとう

2015-01-01

あけましておめでとうございます 2015

あけましておめでとうございます。日本のプログラマには古来より「正月はフラクタル」という習わしがあります。正月はフラクタルに触れて心穏やかに過ごそうというものです。

今年は L-system で遊んでみました。以下でススキっぽいのが描けます。

$ ruby 2015-fractal.rb 7 20 X X:A-[[X]+X]+A[+AX]-X A:AA

出力には Sixel を使ってみました。mltermで動作確認。

コッホ曲線

$ ruby 2015-fractal.rb 4 90 A A:A+A-A-A+A

ドラゴン曲線。

$ ruby 2015-fractal.rb 16 90 AX X:X+YA+ Y:-AX-Y

C 曲線。

$ ruby 2015-fractal.rb 13 45 A A:+A--A+

ヒルベルト曲線。

$ ruby 2015-fractal.rb 6 90 X X:-YA+XAX+AY- Y:+XA-YAY-AX+ A:A
$ ruby 2015-fractal.rb 4 90 X X:XAYAX+A+YAXAY-A-XAYAX Y:YAXAY-A-XAYAX+A+YAXAY A:A

シェルピンスキーのギャスケット。

$ ruby 2015-fractal.rb 9 60 X X:YA-XA-YA Y:XA+YA+XA A:

ペンローズ・タイル

$ ruby 2015-fractal.rb 4 36 [N]++[N]++[N]++[N]++[N] M:OA++PA----NA[-OA----MA]++ N:+OA--PA[---MA--NA]+ O:-MA++NA[+++OA++PA]- P:--OA++++MA[+PA++++NA]--NA A:

Sixel 初めて使ってみましたが、簡単でいいですね。何か作りたくなった。

# 2015-fractal.rb

# read L-system definition
if ARGV.size < 4
  puts "usage: ruby #$0 <iteration> <angle> <init> <rules...>"
  exit 1
end
Iteration = ARGV.shift.to_i
Angle     = ARGV.shift.to_i
Init      = ARGV.shift
Rules = {}
ARGV.each do |s|
  pre, post = *s.split(":",2)
  Rules[pre] = post
end

# generate a program by L-system
s = Init
Iteration.times { s = s.gsub(/\w/) {|c| Rules[c] } }
s = s.gsub(/[B-Z]/, "")

# run the generated program
mod = 180 / Angle
lines  = {}     # drawn lines
pos = [0] * mod # current position (represented by polynomial)
dir = 0         # current angle
stack = []
s.each_char do |c|
  case c
  when ?A
    npos = pos.dup
    npos[dir % mod] += dir < mod ? 1 : -1
    line = [pos, npos].sort
    lines[line] = true if !lines[line]
    pos = npos
  when ?+ then dir = (dir + 1) % (mod * 2)
  when ?- then dir = (dir - 1) % (mod * 2)
  when ?[ then stack << [pos, dir]
  when ?] then pos, dir = *stack.pop
  end
end

# translate polynomials to the actual point
lines = lines.keys.map do |line|
  line.map do |point|
    point.map.with_index do |mag, i|
      Complex.polar(mag, Math::PI * Angle * i / 180)
    end.inject(&:+)
  end
end

# render it to the buffer
S = 450
l, r = lines.flatten.map {|p| p.real }.minmax
u, d = lines.flatten.map {|p| p.imag }.minmax
scale = S / 1.1 / [r - l, d - u].max
translate = Complex(r + l, d + u) / 2
fine = [(scale / 3).round, 4].max
image = (0 ... S / 6).map { [0] * S }
lines.each do |p1, p2|
  fine.times do |i|
    p = ((p1 * i + p2 * (fine - i)) / fine - translate) * scale
    x = (S / 2 + p.real).round
    y = (S / 2 + p.imag).round
    image[y / 6][x] |= 1 << (y % 6)
  end
end

# output the buffer as Sixel
r = (100 * rand).round
g = (100 * rand).round
b = (100 * rand).round
print "\eP0;0;0;q#0;2;0;0;0#1;2;#{ r };#{ g };#{ b }#1"
image.each do |line|
  print line.map {|c| (c + 0x3f).chr }.join + "-"
end
print "\e\\"

2014-12-29

CRC32 Quine を Z3 で解く

ref: http://shinh.hatenablog.com/entry/2014/12/25/013926

おー。

Z3 で再現してみた。

$ time python crc32.py 
86319a79    
58a8a1b9

real    151m1.375s
user    151m7.607s
sys     0m0.179s

1 つめは 3 分くらいで見つかるけど、2 つめは 2 時間くらい、チェック完了までは 3 時間弱かかった。

単純に 2^32 個を全チェックする方法なら、秒間 100 万個調べられるとして 1 時間ちょっとという計算。まあ、こんなもんなのかな。追記:shinh さんによると 1 分でできるらしい。残念。

ソースはこんな感じ。もっと綺麗に書けそう。

# coding: utf-8
from z3 import *

# CRC-32 の生成多項式(の反転)
POLY = 0xedb88320 * 2 + 1

# BitVec(1) の 0
ZERO = BitVecVal(0, 1)

# 求めたい CRC-32
answer_crc32 = BitVec("answer", 32)

# answer_crc32 をテキスト化する
text_crc32 = []
for i in range(8):
    d = ZeroExt(4, Extract(31 - i * 4, 28 - i * 4, answer_crc32))
    d = If(d < 10, d + 48, d - 10 + 97) # [0-9a-f] の ASCII コードに変換する
    text_crc32.append(d)
text_crc32.append(10) # 最後の改行
# テキスト化をしない場合はこっち
# for i in range(4):
#    d = Extract(31 - i * 8, 24 - i * 8, answer_crc32)
#    text_crc32.append(d)

# テキスト化したものの CRC-32 を求める
crc32 = BitVecVal(0xffffffff, 32)
for d in text_crc32:
    n = ZeroExt(32, Extract(7, 0, crc32) ^ d)
    for i in range(8):
        n = If(Extract(i, i, n) == ZERO, n, (POLY << i) ^ n)
    crc32 = Extract(39, 8, n) ^ ZeroExt(8, Extract(31, 8, crc32))
calculated_crc32 = ~crc32

# 元の CRC-32 と求めた CRC-32 が一致するケースを全列挙する
s = Solver()
s.add(calculated_crc32 == answer_crc32)
while s.check() == sat:
    found_crc32 = s.model()[answer_crc32].as_long()
    print("%08x" % found_crc32)
    s.add(answer_crc32 != found_crc32)

他のソルバでもやってみたかったけど、Z3 でも 3 時間かかるんじゃ無理かな。

追記:

テキスト化しない場合は 30 秒。これなら他のソルバとベンチマークできそうですね。

$ time python crc32.py 
cc4fbb6a
ffffffff

real    0m29.339s
user    0m29.327s
sys     0m0.032s