ICPC2021チーム紹介ドキュメントのメイキング

gist.github.com

https://ideone.com/d43uV5

参考:昨年の記事

kotatsugame.hatenablog.com

今回もアスキーアートQuineを作ってみました。

1. AAを用意する

昨年の経験を活かします。というのも、実行可能なAAかつQuineなんてすごいに決まってるだろという感覚があって、もっとドッカンドッカン話題になってくれるものと期待しながら作っていたのですが、昨年はエゴサしてもほぼほぼ反応がなかったのがちょっとショックだったのでした。そもそもすごくない可能性がありますが、それを置いておくにしてもまた別の理由が考えられます。つまり、昨年のAAは見にくかったのです。

理由は簡単で、チーム紹介ドキュメントの制約である1行75文字が結構厳しく、その結果AAを小さくせざるを得なくなったからです。AAの見にくさに加えて、そもそもコードをAAの形に収めることも難しくなったので、今年はとりあえずイラストをAAにするのは止めました。文字を使います。2行に「Aobayama_」と「dropout」を書くつもりでしたが、これも1行75文字の制約が厳しいので、ただ3文字「青葉山」と書くことにしました。

エクセル方眼紙を使ってAAを作成します。対称性を保つためには1文字の幅が偶数であると都合がいいので、1文字あたり24マス使うことにしました。また縦線を4マス幅、横線を2マス幅にすることにしました。適当なフォントを参考にしつつマス目を塗っていたのですが、このときフォントの縦横比が2対1であることをすっかり忘れて、1対1で作ったマス目を使ってしまったので、正しい縦横比に直すとちょっと縦長になってしまいました。もともと横長に作りすぎたかと思っていたこともあり、結果的にうまくいきました。

f:id:kotatsugame:20220309125033p:plain
いい感じ

2. ランレングス圧縮する

この部分のアイディアは昨年と同じです。空白文字と非空白文字がそれぞれ何連続で出現するか数えて、空白文字から交互に配置した数列を作ると、それを元にAAが復元できるというやつです。数列を文字コードに埋め込んで、文字列として保持するという部分も一緒です。昨年は1行ごとに圧縮していましたが、別に全部まとめて圧縮しても問題ないので、今回はそのようにしています。

うっかり全部完成してから無駄な空白の存在に気付き、修正したところデータ部分の文字列が短くなりました。ただ一度完成したコードを弄るのはさすがに気力が尽きていたので、短くなった分適当な文字を入れてごまかすことにしました。下から5行くらいがそのコードです。文字コード65からいくら増えるかで数列を表現しているので、インデックスの偶奇さえそろっていれば間に文字コード65以下の文字をいくら入れても問題ないのです。

all=gets(nil).gsub(/\n/,"")
a=[]
t=" #"
c=0
all.each_char{|s|
  t[a.size%2]==s ? c+=1 : (a<<c;c=1)
}
a<<c
A=65
puts"WARNING"if a.include?(92-A)
ans=a.map{|e|(e+A).chr}.join
while ans.size<296
  i=rand(0..ans.size)
  ans[i,0]=[0,1].map{[33,35,36,38,43,47,*48..57,60,61,62,63,64,65].sample.chr}.join
end
puts ans

書いているときに気づきましたが、文字コード64を基準にしたほうが素直でした。

3. コードを書く

まず使用するプログラミング言語についてですが、C言語を使うことにしました。RubyによるアスキーアートQuineは昨年のやり方さえ知っていればめちゃくちゃ簡単で、しかもバラバラになった文字列を最後にjoinするという手法から、出来上がったコードにはあまりプログラムっぽさがありません。C言語を使えばもうちょっと難しく、またいかにもプログラムという見た目になることが期待できます。C言語によるQuineの作り方も「あなたの知らない超絶技巧プログラミングの世界」という本に載っています。具体的には3-3-3項(p.127)の、マクロを使う方法を参考にしました。

あなたの知らない超絶技巧プログラミングの世界 | 遠藤 侑介 |本 | 通販 | Amazon

コードの解説をする前に、いったん全体を見やすく整えたものを示します。ここからコードの意味をほぼ変えずに変形したものがQuineになっています。処理系定義や未定義動作がいろいろあるかもしれませんが、このあたり動けばいいだろという精神でやっているのであまり気にしないでください。本当は-Wallオプションをつけてコンパイルしても警告が出ないようなものを目指していたのですが、そもそも#include<stdio.h>を書くのが難しかったので諦めました。

char a[]="圧縮された文字列";
b=1,c,d,e,f;
#define Q(k)char*l=#k,m[202203];k
Q(
    main(){
        sprintf(m,"...",l);
        for(;d=a[c];c++)for(;--d>='A';b++%71!=0||puts("")){
            for(;m[e]==' ';)e++;
            putchar(...);
        }
    }
)

マクロQがQuineの重要なポイントで、本からコードを引き写してきた部分です。引数にそのままコードが書かれていますが、マクロの展開時、この引数はまず文字列化演算子#を用いて文字列にされ、次に直接コードとして解釈されるようになります。こうして作った文字列に適切な加工を施し、Quineとして出力すべきものを作り出すということです。同じコードを2回書かなくてよいという点で、今回のようなコード長に制限がある状態で有利だと考え採用しました。マクロ定義の上2行も引数に含めようと思えば含められますが、AAにした状態でdefineという6文字が連続している必要があり、その前も意味のあるコードで埋めるために外に出しました。

全体的な注意点として、空白文字の扱いに気を付ける必要があります。文字列化演算子は強力で、特殊な意味を持つ文字はエスケープしてくれますが、それとは別にマクロという性質上改行を含む連続した空白文字が1つのスペースに置き換えられます。そのため、そのまま出力するとAAの空白が中途半端に影響し、謎に穴が開いたボロボロのコードが出来上がってしまいます。このコードでいえば、char*l=#kの部分で穴あきの文字列が生成されます。sprintf(m,"...",l)で出力すべき文字列を構築した際にもその穴は引き継がれ、さらにフォーマット文字列に入り込んだ空白も混入します。

出力前にfor(;m[e]==' ';)e++;とすることでその穴を読み飛ばしていますが、代わりにsprintfで構築する文字列に意味を持つ空白文字が存在しないようにする必要が出てきました。そのような空白文字は、インデントを無視すれば、何か所かの改行とchar a[]=#define Q(k)m[e]==' 'の3つです。順に対処していきましょう。

まず改行については、使用しない変数の宣言を増やすことでAAに埋め込んだ時の位置を調整しました。配列長がm[202203]のように意味深な数字になっているのもその一環です。AA化したコードの12、13行目が該当します。次にchar a[]=は、たまたま最初からAAに埋め込んだ時に勝手に区切れてくれます。#define Q(k)はどうしようもないですが、/**/とコメントを書いておくとその部分がコンパイル時に空白文字とされる仕様を使い、#define/**/Q(k)とすることで回避できます。最後のm[e]==' 'は簡単で、文字リテラルの代わりに直接文字コードを書いておけばよいです。

それ以外の部分を順に見ていきましょう。まず1行目に、先ほどランレングス圧縮して出来上がった文字列を埋め込んでいます。間に何も書かず並べられた文字列リテラルは連結されるという仕様があるので、適切に"で囲むことでこの部分は好き放題分割することができます。2行目は使用する変数です。型がありませんが、この場合int型だと解釈されます。3行目は先ほど解説したマクロです。char*lがコードのデータになり、これに加工を施した後の文字列を保存する用途でchar m[]も宣言しています。

マクロの引数に入ります。6行目で出力すべき文字列を構築し、7行目で1文字ずつ出力するためのループを回します。AAを圧縮した文字列を先頭から見て、その文字コードから'A'を引いた回数だけ文字を出力します。さらに出力した文字数をカウントして、71文字に1回改行を出力します。8行目は先ほど説明した通り、空白文字を読み飛ばす部分です。

9行目で実際に文字を出力します。...で省略した部分に三項演算子を詰め込み、いろいろ場合分けを施しています。長いので下に抜き出しておきました。

c%2==1?f==2?f=1,'"':f==5&&b%71==0?'\\':f==1&&(d=='A'||b%71==0)?f=2,'"':(f=m[e]!='"'?f:f<1?1:f+2,m[e++]):' '

変数cの偶奇によって、出力する文字が空白文字か非空白文字か決まります。ここで非空白文字を出力すると分かったからと言って、すぐさまm[e++]を出力してはいけません。更なる場合分けがあります。まずコード冒頭の圧縮された文字列部分について、AAに変換する際好き放題分割できたのは適切に"で囲んでいたからなので、これを再現する必要があります。さらにsprintfのフォーマット文字列はどうしても2行以上にわたるため、改行の直前にエスケープ文字を入れる必要があります(よく考えればここも"で分割してよかったですね)。

これらの場合分けを処理するために、今出力しようとしている文字が文字列リテラルの内部なのかそうでないのかを知る必要があります。これは変数fで管理していて、f=m[e]!='"'?f:f<1?1:f+2の部分で状態を更新しています。今見るとさすがにもうちょっと単純なやり方があったかと思いますが、場当たり的に書いていたのでこうなってしまいました。f==1の場合は圧縮された文字列内で、f==5の場合はフォーマット文字列内です。またちょっとした影響として、フォーマット文字列の文字列リテラル自体に直接"が出現すると嬉しくないので、この部分は%cにしてsprintfで埋め込むようにしました。

fを利用した場合分けを行います。改行の直前であることはb%71==0で、空白文字の直前であることはd=='A'でわかります。これらを適切に組み合わせて条件を作り、合致した場合は出力すべき文字を直接埋め込みます。文字列リテラルを分割する"を出力した際は、次の非空白文字も"にする必要があるので、これまたフラグ管理にfを使いf==2f==1を行き来しています。

以上でひとまず完成です。sprintfのフォーマット文字列は、出来上がったコード全体を再現するように文字列alを埋め込むだけなので省略します。

4. AAにする

コードに細かい調整を施し、AAとして仕上げます。すでに動くコードが手に入っているので、それを実行したときの出力を見つつ調整していく感じでした。上から手を入れていきます。

まず無意味な変数を増やして、#defineが行頭に連続して現れるようにします。またこの時増やした変数のいくつかは適切な値で初期化しておいて、文字リテラルの代わりに使います。マクロ名がQQQに伸びているのは、この後との兼ね合いです。

          char                a[]=    "KE"                "QE"         

                                (中略)

    ">9";b=1,c,d,e,f      ,g=+                   34,h     =66,     i,j;
    #define/**/QQQ(k      )char*l=#k,m[202203]   ,n,o     ,p,*     q;k;

以降はマクロの引数です。この部分も後から直接コードとして評価されるので、sprintfなりputcharなりのキーワードが分割されないようにしなくてはなりません。幸い最初からかなりうまくいっていたので、数値リテラル+を前置するとか、演算子&&&に置き換えるとか、そういう小手先のテクニックだけでコードの形を大きく変えることなく実現することができました。

    QQQ(        main      (){for(sprintf(m,"ch   ara[     ]=%c     %s%\
    c;b=1,c,d,e,f,g=              +34,           h=66     ,i,j     ;#d\
    efine/**/QQQ(k)c     har*l=#k,m[%d],n,o,p,*  q;k;     QQQ(     %s)\
    ",g,        a,g,     11*91*202+1,l);d=a[c];  c++)     for(     ;d--

2つ目のfor文の途中までを切り出しました。mainをこの位置に置くためにマクロ名をQQQにしたということです。sprintfをfor文の第1項に入れましたが、ただの好みです。フォーマット文字列の内容は、確かに先ほど増やした変数まで再現するようなものになっています。配列長の202203という数値リテラルが2回も出現するのはあからさまな気がしたので、11*91*202+1として隠しています。

残りの部分はかなりバラバラになってしまいましたが、幸い三項演算子を連打する部分は連続しているべき文字が少なかったので何とかなりました。

    >=h;b++%71||puts          ("")){for(;+       32==     m[e]     ;)0>
    e++;putchar(c%2?         f==2 ?f=1 ,g:f      ==5&     b%71     <=+0
    ?+92        :f==        1&(d  <h|b  %71<     1)?f     =2,g     :(f=
    m[e]        -g?f       :f<1   ?1:f   +2,m    [e++     ]):+     32);

まだ2行ほど残っています。この部分を;なりで埋めてしまうことも可能ですが、それでは面白くありません。ここは昨年同様、Aobayama_dropoutTohoku_Universityという文字列を埋め込むことにしましょう。

    }int    Aobayama      ;for    (;b<    -h;)   for(;f-->c+e*f;)d+++d;
    char    _dropout     ;q<&     p+d;     char  **Tohoku_University;})

かなりうまくいきました。特に「青」の跳ねの部分を8文字+8文字でAAにしたのは我ながら天才的でした。右上のあたりをどう埋めようか迷って、実行されることのないかなり謎な式を書いてしまいましたが、それ以外特に思いつかなかった僕の精一杯です。

5. 完成!

f:id:kotatsugame:20220310111713p:plain
実行結果とともに

f:id:kotatsugame:20220310112012j:plain
届いてみると

見える!見えるぞ!