$ :(){ :|:& };:

$ :(){ :|:& };:

:: fork failed: resource temporarily unavailable

2019年駒場祭ライブコードゴルフ（実用言語編）

プログラミング

これは TSG Advent Calendar 2019 の6日目の記事です．

昨日12/5は もらさんのCTF Zone Quals 2019 Writeup でした．

先日11/22-24に行われた駒場祭にて，私が所属しているサークルTSG（東京大学理論科学グループ）の企画「TSG LIVE! 4」の一つとしてライブコードゴルフ大会が行われ，私はその実況解説をやらせていただきました．

www.youtube.com

事前に実況解説側で各言語の模範解答的なものを作成したのですが時間の都合上放送内で紹介できなかったのでそれの供養もしつつ企画の紹介もできればなあと思いつつこの文章を書いています（現在(12/7)日付を勘違いして絶賛遅刻中)．詳細は上のアーカイブを観て頂けると嬉しいです．

コードゴルフとは

コードゴルフとは端的に言えば要件を満たすプログラムをより短いbyte数で書けた方が勝ちという競技です．

今回の企画「ライブコードゴルフ」は，プログラミング言語とマスを対応せた盤面で2名 × 2チームがこのコードゴルフで陣取り合戦をするというもの．
プレイヤーは，各言語のマスについて相手の提出されたコード長さより短いコードで正解を得ることができたならばその言語のマスを獲得することができます．どちらのチームも取っていないマスであれば，その言語を用いて正解するだけでマスを得られます．ただし，プレイヤーが提出できるマスは初期マス / 自チームが獲得したマスに隣接しているマスのみです．
制限時間内に獲得できたマスの合計数をチーム間で競います．

gyazo.com

TSGでは過去にこのような形式のコードゴルフ大会をいくつか開催しており， その様子はここから見ることができます．

esolang.hakatashi.com

そして，今回の盤面はこちらになります．

f:id:taiyoslime:20191207182736p:plain

盤面の外周にはesolang（難解プログラミング言語）も存在します．これらについては後続のうらさん，くろむのりさんがしてくれるはずなので，本記事では主に真ん中に固まってる実用言語サイドの話をしていきます．

追記: n4o847.hatenablog.com

kuromunori.hatenablog.com

お題

2桁の整数が100個改行区切りで与えられるので，それぞれについて九九表に存在する数のとき1，そうでないとき0を出力せよ

詳しい問題文や制約は以下になります．

esolang.hakatashi.com

方針

コードを短くする上で本質となるものの一つにアルゴリズムの選択があります．特定のアルゴリズムが絶対的に優れているということは基本的には無く，言語の機能や特性に即したものを選ぶことが重要です．
ここでは事前準備で運営サイドが思いついたものを4つ紹介します．当日のプレイヤー側は方針も殆どが方針①，②に収まっていたと思います．

方針① 全列挙

1×1から9×9まで全部計算して与えられた入力がそのどれか1つと等しいかどうか見れば良いという一番愚直な方法です．

Rubyでゴルフせずに書くとこんな感じ．

100.times do |n|
    input = gets.to_i
    output = 0
    9.times do |i|
        9.times do |j|
            if (i + 1) * (j + 1) == input
                output = 1
            end
        end
    end
    puts output
end

2重ループがどうしても長くなってしまうため今回これが最短になる言語は恐らく無いように思えますが，例えばPerl6だと配列の直積 / ある要素が配列に含まれるかどうか 等が極めて短く書けるのでこの方針が恐らく最短です．

方針② 1~9で割った余りと商

九九にある数ならば，1~9で割った余りのうちどれかが0になる かつ それらについてその商が1~9の範囲に収まるはずです．これを利用すれば1つのループで書くことができます．

Rubyでゴルフせずに書くとこんな感じ．

100.times do |n|
    input = gets.to_i
    output = 0
    9.times do |i|
        if input % (i + 1) == 0 && input / (i + 1) <= 9
            output = 1
        end
    end
    puts output
end

シンプルな方針かつ多くの言語で①よりも短く書けるので，本番のプレイヤー側のコードもこれが多かったように思えます．

方針③ 符号化

今回の本命です．
今回のお題の入力パターンである10から99までの自然数はたかだか90個しかありません．そこで，この入力に対する出力の対応関係をある程度短い形式でコードに埋め込んでしまえば良いのではないかという発想をします．

そこで，整数Nが九九表に存在するかどうかの判定結果(0/1)をNbit目に持つような数を考えます．後々アクセスしやすいように0<=N<=99とすると次のような数(2進数表記)になります．

00000000000000000010
00000001000000011000
00010100001100100101
00011001010110110011
01011101010000000000

これを16進数表記に直すと

0x20101814325195b35d400

となり，この数をx,入力をnとすると，(x >> n) & 1 を出力すればお題を満たすプログラムになります．

ゴルフせずに書くとこんな感じ．

100.times do
    n = gets.to_i
    puts 0x20101814325195b35d400 >> n & 1
end

コードの本質部分が数字とbitを見る分だけで済むのでかなり強力なアルゴリズムです．符号化した数が64bitで表現できる範囲を超えてしまうので，多倍長整数がデフォルトで扱えない言語は（短く書くという点では）難しいかもしれません．

方針④ 最強の数式

要するに九九に存在する数と存在しない数で異なる出力をするような（コードとして書き下した時にそこそこ短い）数式を思いつけば良いという方針です

実は前回の5月祭のライブコードゴルフ(じゃんけんの手を表す0~2の整数を2つ受け取り勝敗を出力する)ではn%8%3<2という数式が最強で，今回も同じように式を作るという発想自体はありました．が，前回は入力パターンが6個（あいことなる入力は存在しないことが保証されていた）しかないのに対して今回は90パターンと数が大きく，流石に他の方針が強いんじゃないかと殆ど検討せずにいました．

この話を本番前日のリハーサル帰りの電車で数学つよつよ部員であるところのナンにしたところ，その夜に彼から突然数式が送られてきました．

99225%n*(60480%n)+n/60*(n&51)%17

2桁の自然数が九九に存在する時に0，存在しない時に1以上になります．
ラマヌジャンか？

彼の言葉を借りつつ解説をすると，

  • 基本的なアイデアは与えられた自然数nがある自然数集合Nに含まれるかの判定をNの全要素の最小公倍数をnが割り切るかどうかでするというもの
  • 99225%nは 九九に含まれる奇数の集合，60480%nは偶数の集合をそれぞれ判別しており，どちらかの値がnで割り切れるなら99225%n*(60480%n)は0になり，そうでないなら1以上となる．
  • {60, 70, 75, 80, 84, 90, 96}が例外として九九にしないにも関わらず割り切れてしまう．
  • これらの数は全て60以上なので，60以上で九九表に存在する{63, 64, 72, 81}とそれ以外を判別できないかを考える．徐にnを51とbitwise andをとって17で割った余りを見ると前者は0，後者は1以上になる．
  • これを後ろに連結させて99225%n*(60480%n)+n/60*(n&51)%17となる．

実際のコード(実用言語編)

以下各言語ごと実況解説側が事前準備で用意していたコードです

Ruby

44byte

$<.map{|e|p 0x20101814325195b35d400[e.to_i]}

方針③です．Integer#[]でnビット目がとれるので更に短くなります．えらい．自信作です．
36進数にすると符号化した数自体のbyte数は減るんですがprefixがないので結局"".to_s(36)分が嵩んでしまうため結局これが最短になりました．
また，0~99までではなく10~99，9~99までで符号化するという方針も考えられますが，結果的に同じ44byteなりました． 

$<.map{|e|p 0x80406050c94656cd75[e.to_i-10]}
$<.map{|e|p 0x10080c0a1928cad9aea[e.to_i-9]}

ちなみに方針②でもEnumerable#all?等を使ってまあまあ短くなります

55byte

$<.map{|n|p (1..9).all?{|i|n.to_i%i>0||n.to_i/i>9}?0:1}

これは余談ですが，本年度中にリリースされる予定のRuby 2.7の機能であるNumbered Parameterを使うと更に2byte短く書けます(42byte)

$<.map{p 0x20101814325195b35d400[_1.to_i]}

C(gcc)

78byte

i;main(n,s){for(;i||~scanf("%d",&n,s=48,i=9);i||putchar(s))s|=!(n%i|n/i-->9);}

方針②です．あんまり短くならずに悩んでいたらsatosさんが颯爽と現れて数byte縮めてくれたのでそのコードを紹介させていただきます．
宣言で型を省略した場合はint型となる，int型の関数で返り値を省略した場合は0を返すので最後のreturn 0;は不要，mainの引数で変数宣言すると短くなる，gccはデフォルトでlibcとリンクしてくれるので出力のための"""おまじない"""（#include <stdio.h>）は不要等のおなじみののテクを使ってかなり殺風景になっています．

n%i|n/i>9はnが九九表に存在するとき0, それ以外のとき1になり，C言語では0はfalsy / 0以外はtruthyなのでnotを取ることでそれぞれtrue, falseとなります．
この結果をiが1~9までについてsとbitwise orを取ってあげるとtrueは1，falseは0として評価されるため，一つでも!(n%i|n/i>9) がtrueのときsの下位1bitは1になります．asciiコードで"0"は48(下位1bitは0), "1"は49(下位1bitは1)なので，それぞれお題を満たすようなの値が出力されるという仕組みになっています．
i||~scanf("%d",&n,s=48,i=9), i||putchar(s)は短絡評価がうまく使われていて，左のiの評価がfalseの時は右のscanfとputcharが評価されることを利用してi==0，つまり割り算のループが終了したときにこれらが実行されるようになっています．

ところで下は方針④をそのままcに移植してきたものも方針②と同着の78byteになりました．見た目がかなりいかつい．

main(n){for(;~scanf("%d",&n);)puts(99225%n*(60480%n)+n/60*(n&51)%17?"0":"1");}

Perl

54byte

print(99225%$_*(60480%$_)+($_>59)*($_&51)%17?0:1)for<>

golfの王様言語です．入力<>を後置forで回し$_で取っています．perlの割り算はfloatを返してくるので式を少し変形して$_>59としています
どう考えても方針②でこの方針④より短く書ける気しかしないがPerl力も無いし準備時間がねえ〜〜〜これで許してくれ〜〜〜〜〜〜といいながら書いたコードです．

後日駒場プレイヤーのうら氏が39byteで書けたと仰っていたたので，明日の（僕が遅刻してるので今日なんですが（すみません））記事で多分紹介してくれる気がします．

追記: 紹介してくれました n4o847.hatenablog.com

Node.js

109byte

(""+require("fs").readFileSync(0)).split(`
`,100).map(e=>{for(a=i=1;i++<9;)a&=e%i>0||e/i>9;console.log(+!a)})

方針②です
readFileSyncの第一引数はファイルディスクリプタなので0(標準入力）とし，普通は第2引数にエンコーディング方式を渡すんですが，何も渡さないとインスタンスが帰ってきちゃうので雑に空文字と結合して文字列を得ます．JSゴルフ必須テク．
"1\n".split(/\n/) => [ '1', '' ] なので split の第2引数で要素数を100に制限しています．その他はcとあまり大枠は変わらない気がします．aは全てのiについてe%i>0||e/i>9，即ち九九表に存在しないならば1，それ以外は0となるなるので出力時に!+aと反転させています．全体的に非本質が長いので悲しい．

Python

54byte

while 1:print(0x20101814325195b35d400>>int(input())&1)

大正義方針③です．
Pythonは最大の特徴と言っても過言ではないインデントでブロックを表す必要があるという制約は勿論，制御構造を用いるには改行が必要でインデントと合わせてbyte数が嵩んだり代入が文なので値を返してくれなかったり等golf的には大変厄介なんですが，かなりすっきりと書くことができました．
whileで無限ループになっていますがinputは入力が枯れるとEOFで例外を吐いて異常終了してくれるのでこれを利用します．

一応参考程度に方針②で雑に書いてみたものがこちらになります．84byte．長い．

while 1:
 n=int(input());i=9
 while n%i or n/i>9 or print(1) if i else print(0):i-=1

これは終わってから気付いんたんですがリスト内包表記とinがえらくて現状の方針②よりも①の方が短くなります．盲点．

a=range(1,10)
while 1:print(int(int(input())in[i*j for i in a for j in a]))

余談ですが，2ヶ月ぐらい前にリリースされたPython3.8.0ではセイウチ演算子というゴルフ的にも大変うれしい代入式が追加されました． https://www.python.org/dev/peps/pep-0572/

まとめ

ゴルフ初心者なので多分まだまだ短くなる気がします．こっちのほうが短いぞ〜〜みたいなのあったらぜひぜひコメントとか引用とかで教えて頂けると楽しいです．

明日(今日)はうらさんで「TSG LIVE! 4 ライブコードゴルフ大会 writeup + 解き直し ( Perl, sed, Haskell )」です