TSG LIVE4!ライブコードゴルフ大会＋α Aheui , Tetris , Golfscript , ><>
この記事はTSG Advent Calender 2019の9日目の記事です(今日が12日なことは内緒です)。
adventar.org
2019年の駒場祭で私の所属する情報系サークルTSGでは、TSGLIVE4!という企画をしてました。
90分の放送枠の中で、ゲーム作ったり、競技プログラミングやCTFの大会をしたりしたんですが、今回はコードゴルフの紹介です。
LIVEの動画は下から見れます。
コードゴルフってな～に？
上のYoutubeのサムネに「人間お断りプログラミングコンテスト」と書いてあるのですが、人間でも楽しめます。(私は楽しんでいる人間です)
与えられた問題を解く、なるべく短いソースコードを書く！というのがコードゴルフ大会の趣旨です。
読みやすさとか、デバッグのしやすさとか、そういうものはかなぐり捨てて、ただただ短いことが正義の大会です。
C言語やPythonなど、いわゆる実用言語たちを縮めるには、言語の仕様を深く深く理解してないと書けません。膨大な知識が必要なので、私は苦手です。
その辺りは、他のTSGメンバーの記事、
達をご覧ください。
私が紹介するのは、難解プログラミング言語、通称エソラン達です。
難解プログラミング言語とは、風変わりな特徴を持った言語たちで、例えば韓国語だったり(Aheui)、プログラムが二次元平面状をくるくる動いたり(><>)、テトリス(Tetris)だったりします。
こういった言語たちは、可能な命令の数が少なかったりして、言語仕様を完全に把握するのが楽なため、知識要素はだいぶ減ります。今回はAheui,Tetris,Golfscript,><>の4言語の解を紹介をします。
今回の問題の紹介
2桁の整数が100個改行区切りで与えられるので，それぞれについて九九表に存在する数のとき1，そうでないとき0を出力せよ
詳しい問題文は以下をご覧ください
GolfScript
名前にGolfとある通り、短く書くことを目標に作られた言語です。
いろんな関数が1文字で用意されており非常に便利ですね。
ソースコードは以下
n/{~[10.,*.$]zip{~*}%?0>}%26Bytesでだいぶ偉いですね。
やっていることは
n/ 入力を改行区切りで分割
{
~ 入力を文字列から数字に変換
[
10 10をスタックにプッシュ
. 10をもう一つ複製
, 10から、[0,1,2,3,4,5,6,7,8,9]という配列の作成
* もう一つの10と[0,1,2,3,4,5,6,7,8,9]を演算、配列を10回繰り返し、[0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,....,8,9]という要素数100の配列を作る
. 上記配列をもう一つ複製
$ 上記配列をソート[0,0,0,..,0,1,1,1,...,1,2,2,2,...,2,...,9]という配列にする
]zip []内で作った2つの配列をzip[[0,0],[1,0],[2,0],...,[9,0],[0,1],[1,1],...,[9,1],[0,2],....,[8,9],[9,9]]という配列を作る
{~*}% 上記配列の各項を掛け算してmap[0,0,0,0,..,0,1,2,3,4,5,6,7,8,9,2,4,6,8,10,..,72,81]という九九と0が含まれた配列をゲット
? 入力が上記配列の何番目に含まれてるかを返す。含まれない場合は-1が返る
0> 直前の値が0より大きければ1、小さければ0を返す
}% 入力全てにmap
という感じです。
出力はいちいち書かなくても、最後にスタックに残ったものを順次出力してくれます。えらい。
><>(fish)
まずは><>の紹介です。右向きのお魚の形をしているため、fishと読みます。
いわゆる二次元言語というやつで、1文字が1命令に対応し、ソースコードの上を上下左右に動き回りながら各文字のコマンドを実行していく言語です。
縮める前のソースコードがこちら
aa*v<
v >i68*-a*i68*-+:a
>1-:}%?!v:{
v0v?(a,{<
<1<;v?~i:-1nfishでは、通常右向きに進むのですが、<>v^に出会うことで、読む方向を左右下上にそれぞれ切り替えます。
そのため、最初はこの順番で読んでいきます。
ここまででスタックにaa*で100を積み、
>i68*-a*i68*-+:二桁の数字入力を2回積み、
aで10を積んでいます。
fishでは文字コードしか読めないため、「０」を読み込むと、その文字コードである48として返されてしまいます。
同様に「１」を読むと49,「9」を読むと57が返されます。
そこで、入力から48を引き、10の位を10倍して一の位と足すことで二桁の数字を読んでいます。
入力が56だった場合、ここまでで、スタックには100,56,56,10が積まれています。
そして、このまま右へ読み進めていくのですが、><>の世界はドラクエと同様に、右端と左端、上と下が繋がっています。
よって、2行目の右端に到達した命令ポインタは、2行目の左端から右向きに出てきます。
そして同様に折れ曲がり、3行目へと進みます。
3行目ではループが回っており、9から順番に入力を割り、割り切れたら4行目へ移動します。
1-でスタックの1番上の10から1を引き、9にします。
:で複製し、100,56,56,9,9に
}でスタックを右に一つ回転させ、9,100,56,56,9にします
%で割った余りを計算、56は9×6あまり2なため、スタックは9,100,56,2になります
?はスタックのトップを取り出し、0だったら次の命令をスキップします。今回は2のためスキップしません。
!は次の命令を必ずスキップします。vがスキップされました
:で複製、}でスタックを左に一つ回転させ、100,56,56,9にします。
右端に到達したため、左端から出てきます。
同様に>1-:}まですると、8,100,56,56,8となります
%で余りを計算すると、今度は56=8*7あまり0より、スタックは8,100,56,0となります
スタックのトップが0なため、?で!がスキップされ、vが実行されることで4行目へ移動します。
4行目では<で受けているため、左向きに読み進めます。
{でスタックを左に1つ回転させ、100,56,8となります。
,で割り算を実行し商を獲得します。スタックは100,7になります。
(aで商が10より大きいか比較をしています。大きければ0小さければ1が獲得されます。
ここで、九九に含まれているかを判定しています。
(つまり、9以下の数で割り切れても、その商が10以上であれば九九には含まれていません。例:88=8*11)
そして?でスタックのトップが0だった場合ジャンプし、黄色矢印の経路を、
0でなかった場合はジャンプせずに青矢印の経路を取ります。
そして、赤の矢印に統合され、nで数字として直前に積んだ0,1をそれぞれ出力
:-1で100から1を引いて99がスタックに残り、それが複製されます。
~iは入力を1文字読み、それを捨てています。これは改行文字を読み捨てています。
;v?で、スタックのトップが0だったら;を実行しプログラムを終えます。
つまり、100回実行したら終了する処理です。
0でない場合はvで下に移動し、下の図のように次の入力を処理し始めます。
これが><>の縮める前のコードです。二次元プログラミング言語、楽しいですよね。
しかしお気づきの通り、<>^vといった読む向きを変える文字は、情報処理を何もしていないため、無駄です。
本質的に必要な改行は、3行目の9から順番に割り算を繰り返すループだけです。
この行では、右端に到達すると左端から再度実行されることを基にループ構造を書き、
割り切れた時にだけvで次の行へ移動することで、ループから抜け出しています。
つまり、理論上2行にまとまるはずなんですね。
というわけで2行にまとめたのが以下です。
aia*i+68*b*-\i,)n
(?;:{1-:}%?!\:0aia*i+で10と入力の(10の位の数+48)*10+(1の位の数+48)をスタックに積んでいます。
その後、68*b*-で48*11をいっぺんにひくことで、入力を正しい値にしています。
\の文字は、読む方向の反射で、右から来た場合は下へ、下から来た場合は右へ、上から来た場合は左へ、左から来た場合は上へ読む方向を切り替えます。
今回は下へ読む方向を切り替え、直後の\で2行目を右方向へ読んでいきます。
2行目は基本的に縮める前のプログラムの3行目と一緒なんですが、0:(?;が余計に挟まっています。
これは実は終了判定です。
fishでは、入力文字がなくなると、iを打った時に文字コードの代わりに-1が降ってきます。
つまり、入力がない状態で通常通りの手順で二桁の数を読もうとすると-1*10-1-48*11=-539が入っています。
そこで、入力の値が0以下だったら終了するというコードを書くことで、100回をいちいち数えなくても終了判定を5文字で実装できます。
割り切れた後の処理も少し違いますね。
割り切れると1行目の\i,)nにたどり着きます。
まず、iで入力を読んでいます。ここで読まれるのは改行文字なのですが、改行文字の文字コードは実は10です。
九九判定に10、めっちゃ使えそうですよね。
この時、スタックには与えられた入力と、それを割り切った9以下の最大の数が入っています。
例えば入力が88だった時、スタックは8,88となっています。
ここにiで10を読み取り、,で割り算をすると、8,8.8となります。
最後に)nで8と8.8を比較し、8.8の方が大きいため0を出力しています。
これは何をしているかというと、88÷8が10未満かを確認する代わりに、
88÷10が8未満かを確認しています。
こうすることで、スタックの順番を入れ替えたりする操作を省け、文字数を減らすことができます。えらいですね。
Aheui
韓国語の文字である、ハングル文字を用いて行われるプログラミング言語です。
放送時間中に解きたかったけど、制限時間後3分とかでやっと動いて、非常に悲しい気持ちになりました。
これは短くする努力をしていません。ソースコードがこちら。
삲뷔아까가가아아까카짜가쭈 삼바반빠빠빠빠빠빠아아우카 우어어번벚법벌벖벍벓벑석오 삭싿삳빠빠빠빠빠빠빠빠술쪼 초섬어어어어쑫썽뻐선썽부쪼 숞카아빠쑻코삳따쌏술뽀분고 분쪼솜쿠섳쏯너벅벗차솓뿌코 두봉뷰라꺄쿠처박밧누노뿌꼬 까솜쬬거쿠껴쪄꺼섳썿뽀뿌쪼 숞머멍어커밦발밤받반뽀뿌쪼 빠밙밚밣뚜볽벓벑선뻐뻐뻐꼬 ㅇㅇㅇ카땨훠차카짜카아까꼬
解説はちょっとしんどいのですが、ハングル文字は素晴らしい文字なのでハングル文字の素晴らしさだけはお伝えしようと思います。
この言語も二次元プログラミング言語で、読む方向がfish同様に上下左右に変わります。
ハングル文字のえらいところは、1文字で読む方向とコマンドの両方を表せることです。
各文字のパーツにㅏ, ㅓ, ㅗ, ㅜが入ってると思うのですが、これがそれぞれ右左上下に次進むことを表しています。
また、コマンドも偉くて、図として分かりやすいんですよね。
たとえばスタック値を追加するpushと呼ばれる命令はㅂで表わされます。
そして、値を2つに複製する命令はㅃで表わされています。
すごい直感的で偉いですね。
(僕はハングル文字はスタック型二次元プログラミング言語を作るために生まれた文字だと思ってます)
そんなこんなで結構読みやすいので皆さんもぜひ学んでみてください。
AheuiChemがめちゃめちゃ便利なエディタでえらいです。
ぜひ使ってください。
Aheuiを学ぶとこんな感じでハングル文字が読めるようになりますよ
日本の鉄道がハングル表記してるのと同様に、韓国の鉄道も日本語表記つけてくれてるんだけど、ハングルをカタカナに置き換えただけなので、日本人からすると親切なのはわかるんだけど日本語表記より中国語表記の方が意味がわかるというよくわからない事態になってるんだよな pic.twitter.com/AO4nthYLp9
— マルベリー公 (@dominus_clavem) 2019年11月26日
これくらいのハングル文字なら読めるようになった
— Cr (@kuromunori) 2019年11月27日
1つ目の駅名は足し算を無限に繰り返すんですが、スタックに値を積んでいないので無限に無をします。
Tetris
テトリスです。
KMCのmurataさんが作った自作エソランです。
Tetris Esolangから遊べますので遊んでみてください。
私はこの言語が大好きで、TSGLIVEのオープニングでも紹介したので、ぜひそちらも見てください
【東京大学駒場祭】オープニングトーク【ライブプログラミングショーTSG LIVE! 4】
テトリスで九九、書いたんですけど、ソースコード長すぎてアレなので解説を加えて一番最後に貼ります。
コードの下には何もありません。興味ない人はスクロールしなくて大丈夫です。
Tetrisは基本的には、データ構造として一時変数一つと、配列と、現在配列の何番目を参照しているかというポインタが与えられたチューリングマシンライクな言語です。
存在する命令を列挙しておくとこんな感じ
- I: 標準入力から1文字取ってRをそのユニコード値にする。EOFではR=-1となる。
- O:標準出力にRの値をユニコード値として出力。
- J:ラベル R にジャンプ。複数同じラベルがある場合はプログラム実行前にエラーをだす。ラベルが存在しない場合はジャンプしない。
- Z: P = 0 . Zero.
- P: P += R. ポインタを動かす。Pointer.
- L: R = A[P] .Load.
- S: A[P] = R. Store.
- +-*/= : よくある二項演算 (=は宇宙船演算)。R = R op A[P]
- M: R = -R . Minus.
- B: テトリスフィールドをすべて削除し、以降の命令は実行されない。Bomb.
厄介なのが、ポインタの移動が1増やす、1減らすというものではなく、一時変数の値分だけずらすというものなんですよ。
P[0]にある値をP[1]に移動させようと思った時、めちゃめちゃしんどい。
P[0]の値を一時変数に読み取る。OK。
P[1]に移動するには、一時変数の値をまず1にセットする必要がある。
P[1]に移動後、移動するために一時変数を1で上書きしてしまったため、P[0]の値はもはや残っていない。完。
一応、Zというポインターの値を0に戻すというコマンドがあるため、複数の保存した値を演算したければP[0]を上手に使えという話ではあります。
それとJump命令が一時変数の値に応じたJumpで、数字以外に特徴がないため、地味に大変です。
値が0だったら飛ぶみたいな命令を1カ所で書くと、もう他の個所では値が0の時に飛ぼうとするとコンフリクトを起こします。
特にループから抜ける処理としてジャンプ命令を使う場合、ループの中で現れうるループを抜けるべきでない値は全てジャンプ命令として使えなくなります。
しんどいですね。
まぁ頑張りました。
まずは=ISを実行し、1文字目の文字コードをP[0]へ代入します。
文字コードなので、数字には+48されていることを覚えておいてください。
次に、L++++SBを実行し、値を4回足すことで5倍する
次に、L+Sを実行し、値を2倍する。
これで1つ目の値が10倍された
次にI+SBを実行し、1の位も追加する。
これでP[0]に入力すべき二けたの数＋48*11の値が格納された
次にこの値をP[1]へ移す。この時、全て移し切らずに、528残して移すことで入力から48*11の値を引くことを同時にしている。
①まず、LM/+JSでP[0]の値を1引き算し、保存する
この時、残りが527になったら次の処理へジャンプする
次にL/P+S-=PBを実行する。
L/で自身で割ることで1を作り、PでP[1]へ移動
- SでP[1]の値を1増やす
- =で-1を作っている。ここでの=は宇宙船演算子で、2つの値の比較結果により1,0,-1のどれかを返す。
その後PでP[0]へ移動。Bでテトリスフィールドを削除している。
その後JBで①へジャンプする(図は省略)
こうしてP[1]に正しく入力の値が保存されるまでループを繰り返す。
ジャンプを抜けた後は、=ISBを実行することで、P[0]に改行の文字コードである10を格納している。
②その後、LM/+JSBを実行する
これでP[0]の値を1減らして保存し、値が4になったらジャンプしている。
そしてLPSPSPSPSを2回実行したのち、
LPS/MZJBを実行している。(図は横着して一気に書いたが、実際はそろった行から逐次に消えていく)
現在、Pの値はP[0]の10を1減らして9であるため、LPSPSPSPSPSでポインターを9増やしその場所に値9を保存を繰り返している。
全部でこれを9回行っているため、P[9]=P[18]=P[27]=...=P[81]=9となっている。
その後、/Mで一時変数の値が-1になり、Zでポインターの参照位置を0に戻し、Jでラベル-1がある②へ飛んでいる
これを繰り返すことで、次に②から下の流れが行われるとき、P[0]は8であるため、同様にP[8]=P[16]=P[24]=...=P[72]=8となる。
ちなみに配列の初期値は0でリセットされているため、こうすることである整数xについて、xが九九表に存在するならP[x]≠0、存在しないならP[x]=0という構造を作ることができた。
次に、なんやかんや頑張ってP[0]=-48にします。
一列消えると手に入る100を2で割って2から引いたりするとできます。
48は0の文字コードであるため、作らないと数字の出力が難しいです。
次にL/PLZPLJをします。
L/で1を作りPでP[1]にアクセスします
P[1]に保存しておいた、入力の二桁の数字をLでLoadしたのち、ZでP[0]に移動
PでP[1]でLoadした値xに対応するP[x]に飛びます。
そしてLJでP[x]の値に応じてジャンプをします。
具体的には0の時だけジャンプし、P[0]に保存された-48を基に0の文字コードである48を出力します。
それ以外の時はP[0]に保存された値をさらに-1して1の文字コードである49を作ったのち、P[0]と合流して出力してもらいます。(図省略)
そして最後に、2行消しつつJBコマンドを打つことで、ソースコードの先頭にある200のラベルへ飛び、次の入力に対して全く同じ処理を繰り返します。
こうして、テトリスでも九九判定が書けました。
ループを抜けるジャンプの範囲が被らないように上手にループを組む必要があり、思ったよりしんどかったです。
各ジャンプラベルの範囲をまとめると以下になります。
528~536:入力をP[0]からP[1]へ移すループ終了判定で参照されるため、ラベルが存在してはいけない
527:入力をP[0]からP[1]へ移すループ終了判定のラベル
100:入力P[0]をP[1]へ移すループの作成に使用
200:全体の繰り返しに使用
5~9:九九表づくりのループの終了判定で参照されるため、ラベルが存在してはいけない
4:九九表づくりのループの終了判定のラベル
- 1:九九表づくりのループの作成に使用
5~9:与えられた入力が九九に含まれるかを調べるために参照されるため、ラベルが存在してはいけない
0:与えられた入力が九九に含まれないことを示すラベル
例えば、入力を最初から48引いた形で作成し、P[0]に二桁の数字を作り、それをP[1]へ移す場合、1~99のラベルが存在してはいけないことになり、さらに0のラベルが使用済みになります。これはだいぶ困る話で、48を引かない形でやった方が使えなくなるラベルの数が少なくなります。
九九表作りや九九に含まれるかチェックのところも結構繊細です。
二桁以上の九九に含まれる数は、全て5の段から9の段に登場します。例えば4*3の12は6*2として6の段に登場します。
よって5の段まで作り、数字が4になったら4の段は作らずに九九表づくりを終了しています。
ここでもし、5の段を作り終えたのち、数字を1減らす前の5を見て終了するか否かの判定をしていたとします。
すると、終了ラベルとして5が存在することになり、九九に含まれるかを調べる際に0の場合だけジャンプしたいのに5の場合も変なところへジャンプしてしまいます。
このあたりの被りを上手に回避するのが大変でした。
200: #入力をそのまま読み取る I:<<< T.> Z.>>> S:A>>>> ##10の位を5倍 L:A<<<< T:B<< T:B T:A<<< T:A< S:>> Z:>>>> Z.A> #2倍 #1の位を追加 L:<<< T: J.B>>>>> S:AA>>> I:<<< T:> S:A>> Z:A>>>> #####横に移動 100: L:A<<<< J:A<< L:BB<< J:B> T:A S:B>>> T.>>>> # L:A<<<< J:<< S:B<< S:B> T:A< I:A>> Z:B>>>>> S:B>>>> T:B>> J:<<< Z:< T.>>>> Z:> 527: #p[0]=10 Bomb I:<<< O.>> S:A Z:>>>> ## -1: L:A<<<< J:A<< L:BB<< J:B> T:A S:B>>> Z:B>>>>> O.>>> # L:A<<<< S.B<<< L:B<<< S:A<< S:A S:A>> S:A>>>> S:A<< S:A S:A>> S:A>>>> S:A<< S:A S:A>> S:A>>>> # L:A<<<< S:A<<< S:A<<< L.> J: L:A Z:>>> S:A>>>>> 4: ##p[0]=-48 J:B< S:AA<<< T:>>> S:AA> S:A>>>> J:<<< L.>> I. S:AA<< Z:>>>> J:<<< T: J.<< S:A J.AA>>>> Z:A>> ## L:A<<<< J:<< S:B<< L:B< S:A> Z:B> J:B>>>>> L:>>> ## Z:<<< L:B<< J: L:A L:B>>>> T:A>> S:A>>>> 0: Z:<<< L: L:< I:>>> O:>> I.<<< L:B> Z:>>>> # L:A<<<< J:<< S:B<< L:B< Z:B>>>> S:>> T:A I.A>>>> I.> J:> Z:>>>> I.A>>>> O.<<<< O.<< -12: I.
