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

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

:: 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」で1日目ライブコードゴルフの実況解説をやりました.

www.youtube.com

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

esolangサイドの話は後続のbitmathさん,うらさん,くろむのりさんがしてくれるはずなので,主に実用言語サイドの話をしていきたいと思います.

コードゴルフとは

コードゴルフとは端的に言えば要件を満たすコードをより短く書けた方が勝ちという競技です.

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

gyazo.com

TSGでは過去にこのような形式のコードゴルフ大会を開催しており, ここから見れます

esolang.hakatashi.com

今回の盤面はこちらになります

f:id:taiyoslime:20191207182736p:plain

盤面の外周にはesolang(難解プログラミング言語)も存在します.これについては先程述べたとおり後続のお三方が詳しい解説をしてくれるはずなので,この記事では主に真ん中に固まってる実用言語サイドの話をしていきます.

お題

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

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

esolang.hakatashi.com

方針

コードを短くする上で本質となるものの一つにアルゴリズムの選択があります.どのアルゴリズムがえらいというわけではなく言語の機能や特性に即したものを選ぶことが重要です.
ここでは事前準備で思いついたものを4つ紹介します.当日のプレイヤー側の方針も概ねこの4つのどれかに当てはまっていたはずです.

方針① 全列挙

1×1から9×9までいちいち全部計算してそれぞれと等しいかどうか比較すればいいという一番愚直な方法です.

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の範囲に収まるはずです.これを利用して一つのループで書くことができます.

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

シンプルな方針かつ多くの言語で①よりも短く書けるので,本番のプレイヤー側のコードもこれが多かった気がします.

方針③ 符号化

今回の本命です.
今回のお題の入力パターンはたかだか90個しかないので,それをある程度短い形式でコードに持たせることができたならかなり強いんじゃないかという発想をします.

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

00000000000000000010
00000001000000011000
00010100001100100101
00011001010110110011
01011101010000000000

これを16進数に直すと

0x20101814325195b35d400

となり,82~99bit目が0なのが効いてそこそこ短い数となってくれます.

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

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

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

コードの本質部分が数字とbitを見る分だけで済むのでかなり強いアルゴリズムです.問題は符号化した数は64bitを超えてしまうので,多倍長整数がデフォルトで扱えない言語は難しそうです.

方針④ 最強の数式

要するに九九に存在する数と存在しない数で異なる出力をする数式を思いつけば良いという方針です.

実は前回の5月祭のライブコードゴルフでは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]}

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

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

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

55byte

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

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で書けたと仰っていたたので,明日の(僕が遅刻してるので今日なんですが(すみません))記事で多分紹介してくれる気がします.

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', '' ] なのでsplitnの第2引数で要素数を100に制限しています.その他はcとあまり大枠は変わらない気がします.aは全てのiについてe%i>0||e/i>9,即ち九九表に存在しないならば1,それ以外は0となるなるので出力時に!+aと反転させています.全体的に非本質が長いので悲しい.

Python

54byte

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

大正義方針③です.
Pythonは最大の特徴と言っても過言ではないインデントでブロックを表す必要があるという"制約"は勿論,制御構造を用いるには改行が必要だったり,代入は文なので値を返さなかったり等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/

まとめ

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

明日(今日)はうらさんで「多分コードゴルフとかえそらんとか」です