前回ここで書いたTLEというコンテストですが、ひたすら延期を繰り返していたので、 先月の2回目か3回目延期くらいのところでいい加減な会話が行われ、
TLEの安定感は異常
─ shinichiro hamaji (@shinh) 2015, 2月 11なんか、どうせガチ勢は日本人だけみたいなアレなんだし、もう勝手にやったらいいんじゃないかな。とりあえず FizzBuzz を書いてください。得点は入力を code として Ruby の code.sum で評価されて少ない方が良いです
─ shinichiro hamaji (@shinh) 2015, 2月 11とりあえずHello Worldを書いて下さい。ただしcodeを行:列の二次元配列としたときにcode.transpose==codeになる物だけ解答として認められます #勝手にTLE
─ kinaba (@kinaba) 2015, 2月 12@kinaba どうせなら golf.shinh.org に出題しようかと思います
─ shinichiro hamaji (@shinh) 2015, 2月 12というわけで @shinh さんがゴルフ場にジャッジ作ってくれたので転置不変ハローワールドゴルフ大会遊べるようになりました！ http://golf.shinh.org/p.rb?Hello+transposable+world
─ kinaba (@kinaba) 2015, 2月 12なんだか変則コードゴルフ大会が始まりました。 "Hello Transposable World"、 縦横ひっくり返しても変わらないコードでハローワールドを書いて下さいという問題です。
変則ショートコーディングの一番簡単な抜け方は、変な制約を満たすための部分を全部コメントにしてしまって、 自由に文字列を書けるようにしてしまうことです。この問題なら、一行でハローワールドを書いて、 その後で /* とコメントを始めると、あとは好きな文字が書けます。32x32。
main(){puts("Hello, world!");}/*
a...............................
i...............................
n...............................
(...............................
)...............................
{...............................
p...............................
u...............................
t...............................
s...............................
(...............................
"...............................
H...............................
e...............................
l...............................
l...............................
o...............................
,...............................
...............................
w...............................
o...............................
r...............................
l...............................
d...............................
!...............................
"...............................
)...............................
;...............................
}...............................
/..............................*
*.............................*/自分は最初ずっとこのパターンに引きずられていて、右上にコードを詰め込んで、 最後にコメントアウトして残りを単純に右上の鏡像にして終わり、という方向ばかり考えていました。 一番素直にやると 7x7 の領域にハローワールドを詰め込めるので、6x6 の空白を使って 13x13。
main(){
puts(
"Hello"
", wor"
"ld!");
}/*
略略略
略略略
略略略
略略略
略略略
略略略 *
略略略 */しかし、よく考えてみると、右上パターンは全体の4分の1しか使えないですが、「対角線で行コメントを開始する」 というパターンで左下三角を活用すると、全体の2分の1近くをコード領域として使えます。簡単に 10x10。
//略略略略
//略略略略
//略略略
//略略略
main//略略
(){ //略略
puts( //略
"Hell"//略
"o, wor"//
"ld!");}//という辺りが基本事項で、最短解はここからのさらなる工夫が必要になります。 興味のある方は是非とも挑戦してみて下さい。もしくは、 公開されている解答を是非ともご覧ください。
個人的には、コメントを使わない解が格好いいなーと思いました。 というか、出題した時点ではできると思っていませんでした。
twobitさんのPython解 は、 Pythonの添え字演算で"5文字おきにアクセスする"というヤツを巧く活用したもの。 \\ などを使って見た目の文字数と実際の文字数をずらして衝突を防ぐ技もテクい。
print""""
rHlo oe@"
il@@@\l!"
no@@@\,@[
t @@@@w@3
"o\\@@@r:
"el,w@@d:
"@!@@rd 5
"""[3::5]teebeeさんのPHP解(\x表記の部分は実際にはそのバイナリ値1バイト)はコード中のどこにも world という文字列が登場しない辺りがすごい。PerlやPHPにある文字列と文字列のxor演算という形で、 対角の制約を満たしつつ目的の文字列をピッタリ作り上げるエンコードは見事です。
Hello,<?
echo"*\x1b\x00
lhhx"^ '
lox\x00\x0cIX
o""\x0c
,*^I
<\x1b X
?\x00' ;みんな日記書いてるのでなんとなくつい。 TLE 2015 というコンテストに微妙に参加しました。 コンテスト開催日時が TimeLimitExceed して後ろにずれこむ特徴のあるインドの変則コードゴルフコンテストです。
詳しいことは tanakhさん kikxさん shinhさん mameさん の記事を読んでください。
気づいたら終わりかけていたのと、 AA圧縮とかQuineとかの毎年あまり変わらない系の問題解く気力がなかったのと、 42はバイナリアンに勝てる気が1mmもしなかったのとHalting疲れそうだったので、 前半の簡単な2問だけにトップ狙いで集中して目立とうとしましたが失敗しました。
コード長をN、 コード内に含まれる部分文字列の種類をKとしてK/N2がスコアになる（高い方がよい） という問題。
部分文字列の最大数は全部の文字が違うときでK=N+(N-1)+(N-2)+...+1ですが、 そうはならないとしても、まあ何も考えずコード書いても仮に全く同じ7文字の並びが2回現れることは無いとすると K≧(N-6)+(N-7)+...+1=(N-5)(N-6)/2 なので、Nを大きくすればするほどスコアは0.5に近づく。
というわけで提出上限限界の50000バイトになるまでコメントを適当な文字で埋めて出せば、 前半のコード部分はだいたい誤差になるので 適当な文字で埋めるところをASCII内に限らずバイナリまでくまなく使うと少しスコアがあがります。
ランダムではなくちゃんと部分文字列種類最小になるような埋め字を工夫などするともう少しはあがると思いますが、 たぶんそこまでしても特に面白くはなさそう。
#import <cstdio>
char Q[234];
int N,S,P,I,C,K,D;
main(){
for(; ~scanf("%s",Q); K=K?printf("%d\n",C):5) {
for(C=0,N=1; Q[~-N]; ++N)
for(S=0; Q[S+N-1]; ++S) {
for(P=0; P<S; ++P) {
for(D=I=0; N>I; ++I)
if(Q[S+I] != Q[I+P])
D=1;
if(!D) goto ns;
}
++C;
ns:;
}
}
}
// ...ここにランダムな文字列...
問題を式変形した結果、入力で与えられる十進1000桁くらいの数を2で何回割れるか数える問題として解きました。 ただし +-*/% の字を使ってはいけない、という条件だったですがこれは割と面白かった。
#import <iostream>
char P[3000];
int R,d,p,a;
main(char I[]) {
for(std::cin>>P; std::cin>>P>>&P[999]>>R; std::cout<<(a>>d)<<'\n')
for(d=0,a=1; !(d|a>>R); a<<=1)
for(I=P; p=I[0]; I=&I[1])
I[0] = (d?"56789":"01234")[p>>1&7], d=p&1;
}
%を使えないのは余りが計算できないというよりもscanf/printfが使いにくい。
*を使えないのは掛け算というよりポインタが使いにくい。
かなり終盤までxorとandの再帰で足し算を自前実装してたんですが、
'0'-'4'の文字に5を足す足し算と、ループで配列インデックスを1ずつする足し算しかしていなかったので、
表引きと、I=&I[1] という小技で消せました。