2015年03月06日

【ですころ10】Javaゴルフ講座とか

9回は特に書くことなかったので飛ばしましたけど、10回目のデスコロ

またもやJavaで最短ですよ!
今回は
treetreetreefiregoldtreetreetreetreegoldtreegoldtreegoldtreegoldtreegoldtreetreegoldtreegoldtreetreetr
eegoldtreetreetreewaterwatertreetreewatergoldgoldtreegoldtreegoldtreegoldtreegoldtreetreegoldtreeg
oldtreetreetreegoldtreetreefiregoldgoldwatermoontreemoontreegoldgoldtreewatergoldgoldtreetreegold
goldtreetreemoonwatergoldgoldwatergoldtreetreemoongoldgoldmoon

という文字列を出力しろ、というのが課題です。
さて、この文字列はtree,fire,gold,moon,waterという5つの文字で出来ています。
月に代わっておしおきですね!
これを数字に当てみると0001200002020202020020200020004400422020202020020200020012243030220422002200342242003223みたいな数列になります。
この数列は5進数なので、これをn進数に圧縮して/=5しつつ%5で値を取れば答えが求まります。
ところで、Javaで扱えるn進数は最大幾つかご存知でしょうか。
16までと思う人は甘いです。なんと無駄に36進数なのです!
上の数字を逆順に(reverse)して36進変換すると4k8orvt45xfetts7f5f7w9flurp2bmks14vsoi6rと、強烈に圧縮されます。
では36進数変換した文字列を使って回答してみましょう。

この[]xはArrays.toListに変えて

とすると、若干短くなりますが、永杉さんです。ていうか、BigIntegerが長すぎるのですよ!
もう余計な処理は辞めてシンプルに書きましょう!

あら短い。

これを基準に、この長い数字列を圧縮することを考えます。
この数字を全角文字コードに直し、ビット演算で0〜4の数字化すれば圧縮できるはずです。
Javaで使用される文字コードはUTF-8。UTF-8の全角文字は通常3バイトです。
UTF-8で3バイト全角文字はE2****〜E6****にありますので、ちょうど5種類ですが、問題はE2系。これってрニか→とかLあたりが扱われているのですが、ほぼ全部CodeIQですと「機種依存文字」として弾かれます。
そのため、E2系は実質使えません。
また実際にはサロゲートペアという拡張文字があって、これを使うと4バイトになりますが、扱える文字数が少なくて使いづらい上に、機種依存文字の可能性が高く、怖くて使えません。

そこで、文字として出現率の低いfireを1バイト文字(つまり半角ASCII文字)で表すことにして、E3〜E6系だけを使いました。
もともとの数字を3バイトあるいは1バイトに切ったとき、最短となるのは(0〜4をa〜eと置き換えて)
aaa,b,caa,aac,aca,cac,aca,aca,caa,aca,aae,eaa,ecc,aca,cac,aca
,aca,caa,aca,abc,ced,ada,cca,ecc,aac,caa,dec,cec,aad,ccd
と分割した時です。
そして、これ上手い具合にdで始まるのがdecしかないので、あえて
aaa,b,caa,aac,aca,cac,aca,aca,caa,aca,aae,eaa,ecc,aca,cac,aca
,aca,caa,aca,abc,ced,ada,cca,ecc,aac,caa,d,ecc,eca,adc,cd
と分割し、dも先頭から外してしまいます。これでも後述の理由により文字数は変わりません。
あとはUTF-8文字コード表とにらめっこしながら、&7で2〜6になるような文字列を作り上げ、-2を引いてあげれば0〜4の数字に戻せます。
実際の文字列は
伜C億伽佼包佼佼億佼伶挌捕佼包佼佼億佼仕冊交兄捕伽億B捕杜井備
となります。
この中で重要なのは最後の「備」。こいつは0xE58299なので、バイトごとに&7かけると5,2,1となります。最後の1文字が2〜6ではありませんので、-2すると-1となってしまいます。
これぞデスマ名物Exception抜けです。デスマコロシアムではExceptionが出ても無視されることになっているため、ArrayOutOfBoundsExceptionを起こして終了させて構わないのです。このテクニックを使って、元の数字の3を使わないようにしたほうが、全角文字を当てるときに便利というわけ。
こうして出来たのが

この-2を先頭に持っていくと

で、1文字だけ減ります。
しかし、これ以上縮まりません。
たとえば順序を工夫して~i&7で処理することで文字列を縮めようとしても、2〜6→5〜1となってしまい、ノイズ除去の""を入れて

とすると、かえって長くなってしまいます。

Javaで最短に挑戦した人はたぶんこのあたりで投了しているはずです。
バーも投了しかけました。

たとえばListではなく配列にすれば.get()ではなく[]が使えて文字が削れますが、Javaで変数代入なしで配列作るにはnew String[]{,,,}という書式になります。

長い、長いよママン。
もはや諦めるしかと思ったとき、突然閃きました。
CSVファイルを処理する場合、Javaで使うメソッドがあるじゃないの!
String.split()!
new String[]{"","water","gold","tree","fire","moon"}

",water,gold,tree,fire,moon".split(",")
と等価!
これで一気に縮まり

という最短解が求まりました。

やったー!





まだまだ終わらんよ……
じゃあ、本当にこれ以上の最適解はないのでしょうか?
実はUTF-8には2バイトコードが存在しています。
いわゆるC2/C3系で、÷とか×とかが、それに当たります。
これを上手く利用すれば、ひょっとして…!

文字列を2バイトと3バイトできれいに分けてみます。
aaa,bc,aaa,aca,cac,aca,caa,cac,aaa,caa,aee,aae,cca,cac,aca,caa,cac,aaa,caa,bc,ced,ada,cca,ecc,aac,caa,dec,cec,aad,ccd
おお、2バイトがbcだけじゃないですか!
あとは色々と数式を試してみて、最適な解がないか求めてみます。
バーが出した最適数式は「-i%5」
-i%5対象バイト
083,88,8d,92,97,9c,a1,a6,ab,b0,b5,ba,bf,c4,c9,ce,d3,d8,dd,[e2],e7,ec,f1,f6,fb
182,87,8c,91,96,9b,a0,a5,aa,af,b4,b9,be,[c3],c8,cd,d2,d7,dc,e1,[e6],eb,f0,f5,fa,ff
281,86,8b,90,95,9a,9f,a4,a9,ae,b3,b8,bd,[c2],c7,cc,d1,d6,db,e0,[e5],ea,ef,f4,f9,fe
380,85,8a,8f,94,99,9e,a3,a8,ad,b2,b7,bc,c1,c6,cb,d0,d5,da,df,[e4],e9,ee,f3,f8,fd
484,89,8e,93,98,9d,a2,a7,ac,b1,b6,bb,c0,c5,ca,cf,d4,d9,de,[e3],e8,ed,f2,f7,fc

bcがc2かc3になりますが、cが先頭文字として多用されることから、c3b7(÷のUTF-8コード)を選択します。
先頭がaとcは多用されていますが、dはdec、eはeccしかありません。
この中でe2系をどうしても使う必要があり、e2系の中で使えそうな文字を探したところ、e28099(’)が見つかりました。
これを当てはめると、e=e2,c=80/99となります。そうするとdecはe38380(ダ)が当てはまりますので、結果として
上の表の-i%5の結果は0=e,1=b,2=a,3=c,4=dと決まりました。
それぞれに文字を当てはめていきます。


前人未到の110文字最短解。
posted by バー at 09:22| Comment(0) | TrackBack(0) | CodeIQ | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
この記事へのトラックバックURL
http://blog.seesaa.jp/tb/415130177
※ブログオーナーが承認したトラックバックのみ表示されます。
※言及リンクのないトラックバックは受信されません。

この記事へのトラックバック
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。