2015年09月

2015年09月19日

デスマコロシアムが終わってしまいました。
デスマコロシアムはコードゴルフとその他諸々の要素を組み合わせて戦うトーナメントです。
詳しくはググればいいと思います。

結果は目標の言語内最短を出すことができました。
そこまでにどうやって縮めていったかを書いていきます。
最終的なコードが見たい人はCodeiqMAGAZINEを見れば大丈夫です。

今回の問題は次のようなものでした。

abCDEfghIjklmnOpQrstuvwxyz
abcDEFghiJklmnoPqRstuvwxyz
abcdEFGhijKlmnopQrStuvwxyz
abcdeFGHijkLmnopqRsTuvwxyz
abcdefGHIjklMnopqrStUvwxyz
abcdefgHIJklmNopqrsTuVwxyz
abcdefghIJKlmnOpqrstUvWxyz
abcdefghiJKLmnoPqrstuVwXyz
abcdefghijKLMnopQrstuvWxYz
abcdefghijkLMNopqRstuvwXyZ
abcdefghijklMNOpqrStuvwxYz
abcdefghijklmNOPqrsTuvwxyZ
abcdefghijklmnOPQrstUvwxyz
abcdefghijklmnoPQRstuVwxyz
abcdefghijklmnopQRStuvWxyz
abcdefghijklmnopqRSTuvwXyz
abcdefghijklmnopqrSTUvwxYz
abcdefghijklmnopqrsTUVwxyZ
abcdefghijklmnopqrstUVWxyz
abcdefghijklmnopqrstuVWXyz
abcdefghijklmnopqrstuvWXYz
abcdefghijklmnopqrstuvwXYZ


を出力。実際にはアルファベット1周ごとの改行は必要ないです。というかしてはいけません(見やすいように勝手にアルファベット1周ごとに改行を追加してます)。
※最後に改行はあってもなくても良い。

内容は以下のとおりです(CodeiqMAGAZINEの記事より引用)。

"はじめは、aからzの文字でcodeiqに一致する文字のみを大文字に変換します。
次にaからzの文字でdpefjr(codeiqの次の文字)に一致する文字のみを大文字に変換します。
という風に、ループする度に大文字に置換する位置をずらす処理をaからzに対して22回繰り返します。"


ちなみにこの"codeiq"に一致したら大文字というルールは45byteの解ができるまで気づかずランダムなパターンだと思ってました。
まあこれが結果的に良かったのかもしれません。


まず考えたのは次のようなコードです。


a=[]
[2,3,4,8,14,16].map{|i|a[i]=1}
22.times{|i|26.times{|j|$><<(a[j-i]?j+56:j+97).chr}}

(改行が2byteとして全部で90byte)
これを動かすと間違った出力になります。
aは
[nil,nil,1,1,1,nil,nil,nil,nil,1,nil,nil,nil,nil,nil,1,nil,1]
となっていてa[j-i]が真(Rubyではnilとfalse以外は真です)だったら大文字、nilだったら小文字を出力です。
この配列の2,3,4,...に入れる値はnilとfalse以外ならなんでも良いですが文字数が短いので1桁の数を入れます(0でも大丈夫です)。
と思ったのですがj-iがマイナスの値になると配列の後ろからアクセスしてしまうためほしくない1が取得されてしまいます。
これを避けるためにa[99]=nilを加えて回避ということもできますが結構長くなりますね。
しかしaを配列ではなくハッシュにするだけで回避できます。
というわけでa={}とすればちゃんと動きます。


次に考えたのはループを二重ではなく1重(?)にする方法です

22.times{|i|26.times{|j|(なんとか)}}

ではなく

572.times{|i|(なんとか)}}

とするとまあ変数の使い方は変わってしまいますが結構ループの構造を短くすることができます。

a={};[2,3,4,8,14,16].map{|i|a[i]=1}
572.times{|i|j=i%26;$><<(a[j-i/26]?j+65:j+97).chr}

(87byte)
と3byte縮めることが出来ました。(と思ったら1つ改行の代わりに;を使っている(なぜ?)ので実質2byteです。←たぶんまだ途中だと思っていたので適当にやっていたんでしょう)


とこんな面倒な方法を考えていたのですが、このコードが何をしているかというとj-iが[2,3,4,8,14,16]に含まれているかどうかを探しているだけという事に気づきました。
というわけで直接探せる
[2,3,4,8,14,16].index(j-i)
を使います。
これなら扱うものはハッシュではなく配列ですがj-i<0でも全く問題ありません。
返ってくる値は先ほどと違いますがnil,falseとそれ以外が判断できればいいので問題ありません。
面倒な配列の宣言や書き換えがなくなって一気に短くできます。
というわけで次のようになりました。

572.times{|i|j=i%26;$><<([2,3,4,8,14,16].index(j-i/26)?j+65:j+97).chr}

(70byte)
ブロックも一つになっていい感じです。ここで満足して1回目の提出をしました。

テキストエディタを見るのも飽きてきたので過去のデスマコロシアムのまとめを読んでいたらputcを使う方法を見つけました。
$><<a.chr



putc a

と書く方法です。この例だと3文字しか短くなりませんが今回の場合は()も減らせるので5byte短縮です。
というわけでこうなりました

572.times{|i|putc (j=i%26)+(([2,3,4,8,14,16]&[j-i/26])[0]?65:97)}

65byteで提出です。
a.index(n)と(a&[n])[0]が同じ文字数だったので適当に書き換えてみました。
その他にも色々(jの宣言とか)違いますが5byte縮めた要素はputcを使っただけです。
これを出した直後にもう1つ縮める要素を見つけました。
出した直後に改善案が見つかるのはマーフィーの法則からすれば妥当なところです。

jはわざわざ宣言する必要はなくi%26をそのまま使えばよかったのです。
というわけでjに関するところをi%26に書き換えれば1byte短くなります。
というわけで64byteで提出しました。


ここで1回目の集計です。
できれば言語内最短、あわよくば全言語内最短という目標でしたが後者は達成できず(Perlで60がいた)、前者だけ。まあ目標が達成できたので良しとします。


次の目標はPerl(60)です。なんとか4文字短くしてみましょう。

とりあえずいまのコードを短くする方針を考えます。
なんとかPerl(60)に追いつこうと色々考えていたらちょっと短くする方法が見つかりました。

([2,3,4,8,14,16].index(i%26-i/26)?65:97)



([i%26-i/26,97,65]-[2,3,4,8,14,16])[1]

に置き換えます。配列の引き算を使います。
i%26-i/26が右側の配列に含まれるときはその要素が消え[97,65]という配列が返り、含まれない場合は[i%26-i/26,97,65]になります。この配列の(0から数えて)1番目の要素を取れば97か65の欲しい方が取得できるわけです。
これで2byte縮まります。62byteでまだ目標の60byteには届きません。
なんかすごい綺麗になったと思ったのですが意外と縮まらないものですね。
綺麗なアルゴリズムでコードが縮んだと思った時に限って文字数はあまり変わらない法則の発動です。

次に気になるのはi%26が2回出てるということです。できれば1文字の変数でなんとかしたいですね。
jを用意するのは失敗だったのでループ内変数のiを破壊してなんとかする方法にします。
次のループでは新しく正しい値が生成されるので破壊してもあまり問題無いです。
i%=26とすれば次にiを使うときには最初でいうi%26と同じになります。
というわけでこれらを用いるとループの中身は

putc ([i%26-i/26,97,65]-[2,3,4,8,14,16])[1]+i%26

から

putc ([-i/26+i%=26,97,65]-[1,2,3,7,13,15])[1]+i

になりました(1byte短縮で61byte)。

ちなみに-i/26は-(i/26)ではなく(-i)/26なので探す数は1つずれます。
"a"を出力するときだけずれないので問題ありそうですが今回はaが大文字になるケースが無いので問題無いですね。
60byteが目標でしたがここで力尽きてこの日はこれで提出。

ここで2回目の集計です。
Perlは(59)になり、Rubyは全言語最短の(56)になりました。言語内最短も陥落です。


ボツネタ
1,2,3,7,13,15って,使いすぎなので文字列にしてつないだらどうだろう?

"12371315".index(n.to_s)

と.to_sが長いためアウトです。しかもこれn==5で引っかかってしまいます。ダメ。
10進数を使うからダメなんだというわけで16進数を使います。幸いRubyでは16進数とかに簡単に変換できます。

"1237df".index(n.to_s 16)

1文字長くなってしまいましたがこれなら通ります。しかし
[1,2,3,7,13,15].index(n)
のが短いです。ダメでしたね。

"0111000100000101"[n]
を使ってみる。
→返ってくる値は"1","0"の文字列です。このまま使うのは厳しそうですね。to_iすれば使えますが長いですね。
"0"や"1"は数値と四則演算はできません。
あとn<0の時は逆からアクセスしてしまうのでダメです。

ここで一つひらめきました

このビットパターンを持つ数値とビット演算すればいいじゃん。


上の2進数の文字列は左から数えているので逆にしないといけませんがその2進数で表される数値を使います。
というわけで上の文字列を逆順にした物を10進数の数値に変換してみましょう。
irbを使って計算してみました。

#1と0で書かれた文字列を2進数と見て数値に変換する
"1010000010001110".to_i(2)
=>41102

というわけでこの数値を使います。
これの右からnビット目が1か0を調べたら良さそうです。というわけで
41102&(2**n)>0?

とかでしょうか。9byteも縮めることができます。やったぜ。と思ったらn<0でエラーですね。

41102&(1<<n)>0?

なら問題なく動くのでこれで良いようです。
ここまでかと思いましたがRubyにはもっと便利なメソッドがありました。Integer#[]というメソッドがあり、これは右から(0から数えて)nビット目の数値(返ってくるのは0または1の数値)を取得することができます。
さらにnがマイナスの場合は常に0が返ってきます。というわけで

41102[n]>0?

と更に短くすることができました。

572.times{|i|putc (41102[-i/26+i%=26]>0?65:97)+i}

(49byte)
というわけで50byteも切って大満足です。最高記録です。

ここでまた一つ気付きました。
返ってくるのは0,1(数値)なので配列のインデックスとして使えばいいじゃんということです。

572.times{|i|putc [97,65][41102[-i/26+i%=26]]+i}

(48byte)
短くなりました。すごく綺麗になったと思うのですが綺麗になった割には1byteしか縮まってないですね。
まだ括弧が多いような気がしますね。
さらにもう一つ気付きました。
0,1は配列のインデックスじゃなくて計算式に突っ込めるじゃん。
というわけで最終的に出来たのが次のコードです。

572.times{|i|putc 97-41102[-i/26+i%=26]*32+i}

(45byte)
48byteのコードのほうが美しいと感じますが短くなったので正解です。
もうこれ以上はムリだろうと思って提出しました。
ここで3回目の集計。
集計時点で全言語最短を達成です(この時点では単独1位でした)。
目標の(途中経過での)全言語最短の達成です。
オツカレサマデシタ。

ちなみにこの全言語最短記録は一晩でRubyで追いつかれ、数日でPerlによって抜かされてしまいました。
残念でしたね。
Rubyが全言語最短になれる問題だと思ったのに…


時は流れ…
最終結果はこちら
というわけで結果はRuby内最短でした(トーナメントはいきなり負け)。
目標の言語内最短と途中集計で全言語最短ができたので良かったです。


おまけ
1.Ruby(45)の別解
別解というほどでもありませんが

572.times{|i|putc 41102[-i/26+i%=26]*32^97+i}

としても同じ結果になります。中身がどうなっているかは簡単なビット演算の問題なので自分で考えてみましょう。


2.Cに移植してみる
なんか行けそうだったのでCにも移植してみました。
で、コードはこれ

i;main(){for(;i-572;putchar(i%26+(82204&1<<i%26-i++/26?65:97)));}

ループの中でiを破壊できなかったりするのでちょっと長いですが65byteでまあまあです。
ideoneで動かしてみました。
http://ideone.com/PuAQ0X

なんと最後の方で無駄に大文字変換されてしまっています。
どうやら32bitでループしてるようです。
適当にビットシフトでテストした結果がこちら。
http://ideone.com/TAgqBw
シフトしているわけではなく2のn乗をかけているのでしょうか。
オーバーフローしているように見えます。
もう少し詳しく調べてみたくなりますね。

(03:32)

2015年09月08日

デスマコロシアムが最終回ということで参加中です。
最終回だからという理由ではなくちょうどCodeIQとコードゴルフを始めたのでちょうどよかっただけですが。

現在開催中のデスマコロシアムはもうこれ(Ruby(45))以上短くできそうにないので過去問を解いてみました。
今回解く問題はデスマコロシアムの第9回です。

問題は

AbcdefghIjklmnopQrstuvwxYzabcdefGhijklmnOpqrst...

という文字を出力(a..zを8回繰り返し、8個ごとに大文字に変換)するという問題です。

Rubyだと簡単に

208.times{|i|putc (i%8<1?65:97)+i%26}

(37byte)
こういう解答ができますね。意外と簡単に思いつきますがなかなか縮められそうに無いですね。
Rubyの最短解もこれとほぼ同じでした。
なんとか削れそうなのはカッコと三項演算子でしょうか。
三項演算子を使う限りは短くできそうに無いのでビット演算でなんとか削る方法を考えます。

幸いなことに(?)大文字と小文字の整数コードの差は32で、a..zの間に6ビット目は変化しないのでここのビットをオン・オフすることでなんとかする方針を考えます。

i%8が0の時とそれ以外の時で6ビット目を切り替えられるようにします。
どこか一つのビットだけを見て0か1~7を判断する方法はありませんが一つ方法があります。
0と1~7の判断は難しいですが0と-1~-7は比較的簡単にできます。
-1~-7は4ビット目以上は1が並びます。当然6ビット目も1です。
というわけで
(-(i%8)&32)==(i%8>0?32:0)
はtrueになります
-i%8の結果は0~7になってしまうので-(i%8)とします。
というわけで-(i%8)&32でiが8の倍数の時は0、そうでなければ32になる計算式が出来ました。
これを使うと

208.times{|i|putc -(i%8)&32^65+i%26}

(36byte)
というわけで1文字縮まりましたね。大勝利ですがここで終わりではありません。
実はもう少し削れます。-i%8とカッコを消すと違う結果になってしまって使い物になりませんがi%-8とすることで(計算結果の値は違いますが8の倍数かそれ以外かを判断する上では)同じ結果を得られます。ということで。

208.times{|i|putc i%-8&32^65+i%26}

(34byte)
こうなりました。というわけでここで終了です。3文字縮まりましたね。i%-8&32と65+i%26はそのまま足し算しても大丈夫なのですが+を使うと演算の優先度の関係で違う結果になってしまう(もしくはカッコが必要)ので排他的論理和の^を使ってます。^じゃなくても|でも同じ結果になりますね。

(21:30)