【参加記】頭脳のオリンピックに挑戦！ICFPC2024に挑んだ物語パート1

2024年7月29日 15:00

ALGO ARTISでは多くのエンジニアがプログラミングコンテストに参加しています。2024/6/28~7/1に開催されたICFP Contest 2024(ICFPC)というチーム戦のプログラミングコンテストに、社内有志でチーム"Heuristic Artis（ヒューリスティックアーティス）"として参加しました。
コンテストの面白さ、社内のメンバーの工夫、何よりもメンバーがコンテストを楽しんでいるさまを伝えたく、参加記を3部作でお送りします。
プログラミングコンテストの経験が豊富な方も、プログラミングコンテストって何？という方も楽しめる記事に仕上げましたので、ご一読いただければ幸いです。

ICFPCとは?

ICFPという国際会議が主催するプログラミングコンテストで、毎年7月頃に開催されます。今年は27回目の開催で、前世紀から続くとても歴史のあるプログラミングコンテストです。
特徴としては、

人数制限なしのチーム戦
コンテスト時間が72時間とマラソン系のコンテストとしては中間的な長さ
問題の形式やジャンルは毎年様々に変わり、AHCのようなヒューリスティックコンテストのような問題、手で解くパズルのような問題、果ては折紙を折るソルバーを作るなどの超難問が出されたことある

というもので、普段のマラソンコンテストとは一風変わったコンテストになっています。
今年はALGO ARTISとして初めてチームを組み、チーム”Heuristic Artis”で参加しました。

チーム紹介

総勢11名の競技プログラマーが参加しました(敬称略):
threecourse, terry_u16, G4NP0N, tempura0224, Jirotech, plcherrim, KawattaTaido, nrvft, yunix, yochan, takumi152
AHCレーティング合計28,484、平均約2590のなかなか強そうなチームになりました。
メンバーの得意分野もヒューリスティック・アルゴリズム・ゲームAI・パズル・フロントエンドと、多方面に隙のないチームを作ることができ、どのような問題が来ても良い成績を残してやるぜ!という気持ちで参加しました。
今年はメンバー間のコミュニケーションを円滑にして問題に集中して取り組むために、箱根にホテルの部屋を借りて4泊5日の合宿をしました。

余談ですが、AtCoderの社長のchokudaiさんも参加しているレジェンドチーム、Unagiと宿がかち合ってしまうハプニングがありました(しかも部屋が隣でした…)。
大浴場で考察を聞いてしまわないように、Unagiとの間にお風呂を使う時間の協定が結ばれました。
コンテスト中は、世界で一番ICFPCが強い宿じゃん、みたいな冗談をチーム内で言っていました。

隣の部屋でしたｗｗｗｗｗｗ
コンテスト中の温泉を利用する時間は、偶数時がUnagi、奇数時がALGO ARTISにしよう、って話になりました。そんなことあるんだねえ……ｗhttps://t.co/bhfEm25htS
— chokudai(高橋直大)@AtCoder社長 (@chokudai) June 28, 2024

今年の問題概要

問題の設定は以下のようなものでした:

“Cult of the Bound Variable”という宇宙文明が見つかった(2006年度のICFPCの問題設定に登場したものと同じらしい)
宇宙文明は関数型の言語(以下宇宙言語)を使ってコミュニケーションをしており、ICFPコミュニティは言語の仕様を概ね解読することに成功した
- 宇宙言語は関数型の言語で、string, integer, boolean, 単項演算子, 二項演算子, ラムダ式などが定義されている
宇宙文明は宇宙で生きていくために必須なスキルについて、オンラインコースで訓練を提供している
コンテスタントは各コースのテストにおいて良い点数を取ることが求められる

このような設定で、

hello
efficiency
lambdaman
spaceship
3d

という5つのコースで出題される問題に取り組んで回答をすることが求められました(各々のコースは10~20程度の小問題から構成されます)。
順位は以下のようにつきます:

全体の順位は、各コースの順位の合計値が小さい方から上位
各コースの順位は、コースの中の小問題ごとの全体順位の合計値が小さい順
小問題は答えが1つに定まっているもの(hello, Efficiency), 条件を満たす答えの中から良いスコアを求めるもの(Lambdaman, Spaceship, 3d)がある

このコンテストのユニークなところは、宇宙人のオンラインコースなので、宇宙言語のstring型の値で問題が出題され、宇宙言語のstring型の値で問題を回答しなければいけない点です。

[宇宙言語の問題文] SB%,,/}!.$}7%,#/-%}4/}4(%}M#(//,}/&}4(%}</5.$}P!2)!",%_~~<%&/2%}4!+).'}!}...

[英語に翻訳された問題文] 
Hello and welcome to the School of the Bound Variable! ...

宇宙言語のstringと英語の間の変換は規則が与えられており、翻訳の規則自体は単純です(変換規則が既知の単一換字暗号)。
spaceshipと3dは英語にすると普通のヒューリスティックな問題とパズルになり、宇宙言語についてあまり気にしなくて済みました。一方で、efficnecyとlambdamanについては宇宙文明が使用している関数型言語に真面目に取り組む必要がありました。
以下ではhello以外の各コースの問題の概要、解法のアプローチや面白かったところについて、各コースを担当していたメンバーが解説をします。

efficiency

問題概要

efficiencyは宇宙言語で書かれたプログラムが与えられ、その実行結果を解答として提出することが求められる問題でした。
例えば、以下のような文字列が問題として与えられます:

B$ B$ L# L$ v# B. SB%,,/ S}Q/2,$_ IK

上記のプログラムを宇宙言語の仕様に則ってHaskell風に変換すると、以下のようになります:

((\v2 -> \v3 -> v2) ("Hello" . " World!")) 42

この場合には実行結果が”Hello World!”になります。

問題へのアプローチ

宇宙言語をそのまま理解するのはかなり辛そうだったので、まずは見覚えのある形式のプログラムに変換することを目指しました。yunixが徹夜で字句解析器、パーサー、プリンタを書いて、宇宙言語からJavaScriptの無名関数を使った記述に変換するツールを作りました。

[宇宙言語]
B$ B$ L# L$ v# B. SB%,,/ S}Q/2,$_ IK

[変換した式]
((v2)=>((v3)=>(v2)))("Hello"+" World!")(42)

変換した式はJavaScriptの記法になっていて、実際にJavaScriptの式として実行することもできます。
トランスパイラができたのであとは楽勝だぜ、などと思っていたのも束の間、実際に出題される問題を変換してみると見通しが甘かったことがわかりました。
efficiencyの3問目の内容を見てみましょう:

[宇宙言語]
B+ I7c B* B$ B$ L" B$ L# B$ v" B$ v# v# L# B$ v" B$ v# v# L$ L% ? B= v% I! I" B+ I" B$ v$ B- v% I" I":c1+0 I"

[変換した式]
2134 + ((v1) =>(((v2) =>(v1(v2(v2))))(((v2) =>(v1(v2(v2)))))))
(((v3) =>(((v4) =>(v4 == 0 ? 1 : 1 + v3(v4 - 1))))))(9345873499) * 1

変換した式を見ても何が何だかさっぱりわかりません。この式はJavaScriptの文法としては有効ですが、実際に実行しようとするとスタックオーバーフローが起きてしまいます(この事情はlambdamanでのtempura0224の解説にも書いてあります)。再帰と無名関数が多すぎて意味が不明です。

頭を抱えていたら、関数型言語の処理を調べていたterry_u16が颯爽と現れ、このプログラムの読み方を教えてくれました。

"((v1) =>(((v2) =>(v1(v2(v2))))(((v2) =>(v1(v2(v2))))))) "の部分はYコンビネータというもので、後続の無名関数を再帰的に処理できるようにするもの
- https://en.wikipedia.org/wiki/Fixed-point_combinator
"(((v3) =>(((v4) =>(v4 == 0 ? 1 : 1 + v3(v4 - 1)))))) "の部分をYコンビネータと組み合わせると

const g = (v) => {
  if (v==0) return 1;
  return g(v-1)+1;
}

というような再帰的な処理をする関数になる。(細かいことは今でもよくわかっていませんが、Yコンビネータ部分をうまく読み飛ばして後続の関数を再帰的に処理するものとして理解すれば良い)

terry_u16の教えてくれた通りに問題を解いて(というか全部解いてくれたのですが)、9345873499 + 1 + 2134 = 9345875634が答えになりました。

他の問題でも同様のアプローチでterry_u16が解きました(以下は5問目をJavaScriptに変換したもの):

((v6) =>
  ((v7) =>
	  // Yコンビネータ部分
    ((v1) => ((v2) => v1(v2(v2)))((v2) => v1(v2(v2))))(
	    // 以下の箇所を再帰的に実行する
	    // 初期値2を1つずつincrementして、v4>1000000 && v6(v4) && v7(v4+1)を満たす最初の数を返す
      (v3) => (v4) => v4 > 1000000 && v6(v4) && v7(v4 + 1) ? v4 : v3(v4 + 1)
    )(2))(
	   // v7部分
    ((v1) => ((v2) => v1(v2(v2)))((v2) => v1(v2(v2))))( //v7のYコンビネータ
      (v3) => (v4) =>
        // v4が1だったらtrue, 奇数だったらfalse, 偶数だったら2で割って再帰的に実行
        v4 == 1 ? true : v4 % 2 == 1 ? false : v3(parseInt(v4 / 2))
    )
  ))((v5) => // v6部分、素数の判定をしている
  ((v1) => ((v2) => v1(v2(v2)))((v2) => v1(v2(v2))))(
    (v3) => (v4) => v4 == v5 ? true : v5 % v4 == 0 ? false : v3(v4 + 1)
  )(2)
);

terry_u16の教えに従って読むと、

1000000より大きい
1をプラスしたものが2の累乗
素数

つまり、100万より大きい最初のメルセンヌ素数を返せば良いことになります。

順調に問題を解いていたのですが、terry_u16でもアプローチの仕方がわからない問題がありました。それは次のような問題でした(長いので一部省略):

((v1) =>(((v2) =>(v1(v2(v2))))(((v2) =>(v1(v2(v2)))))))
(((v2) =>(((v1) =>(((v11) =>(((v12) =>(((v13) =>(((v14) =>
(((v15)=>(((v16) =>(((v17) =>(((v18) =>(((v19) =>(((v21) =>
(((v22) =>(((v23) =>(((v24) =>(((v25) =>(((v26) =>(((v27) =>
(((v28) =>(((v29) =>(((v31) =>(((v32) =>(((v33) =>(((v34) =>
(((v35) =>(((v36) =>(((v37) =>(((v38) =>(((v39) =>(((v41) =>
(((v42) =>(((v43) =>(((v44) =>(((v45) =>(((v46) =>(((v47) =>
(((v48) =>(((v49) =>(((v51) =>(((v52) =>(((v53) =>(((v54) =>
(((v55) =>(((v56) =>(((v57) =>(((v58) =>(((v59) =>(((v61) =>
(((v62) =>(((v63) =>(((v64) =>(((v65) =>(((v66) =>(((v67) =>
(((v68) =>(((v69) =>(((v71) =>(((v72) =>(((v73) =>(((v74) =>
(((v75) =>(((v76) =>(((v77) =>(((v78) =>(((v79) =>(((v81) =>
(((v82) =>(((v83) =>(((v84) =>(((v85) =>(((v86) =>(((v87) =>
(((v88) =>(((v89) =>(((v91) =>(((v92) =>(((v93) =>(((v94) =>
(((v95) =>(((v96) =>(((v97) =>(((v98) =>(((v99) =>
(!v11 == v12 && !v11 == v13 && !v11 == v14 && !v11 == v15 && 
!v11 == v16 && !v11 == v17 && !v11 == v18 && !v11 == v19 && 
!v11 == v21 && !v11 == v22 && !v11 == v23 && !v11 == v31 && 
!v11 == v32 && !v11 == v33 && !v11 == v41 && 
...(省略)... 
&& !v95 == v98 && !v95 == v99 && !v96 == v97 && !v96 == v98 && 
!v96 == v99 && !v97 == v98 && !v97 == v99 && !v98 == v99 
? v1 : v2(v1 + 1)))
(1 + parseInt(v1 / 1) % 9)))(1 + parseInt(v1 / 9) % 9)))
(1 + parseInt(v1 / 81) % 9)))(1 + parseInt(v1 / 729) % 9)))
(1 + parseInt(v1 / 6561) % 9)))(1 + parseInt(v1 / 59049) % 9)))
...(省略)...
(1 + parseInt(v1 / 21847450052839212624230656502990235142567050104912751880812823948662932355201) % 9))))))(1)

変数が多すぎる & 条件式が多すぎる & 謎の大きな数値で割り算をしていて意味が不明な問題で、これが一体何の問題なのか困っていました。
そこに通りかかったtempura0224がこの問題は数独じゃないかと言い出しました。初めに聞いた時には何を言っているかわからなかったのですが、

変数がv11からv99までの81個ある
- v11は(1, 1)マスに対応する変数
v11 ≠ v12 && v11 ≠ v13… のように数独特有の9マス内で同じ数値が重複しないような条件式が書かれている
変数として1が与えられて、条件に合わなかったらインクリメントされている
最後の(1 + parseInt(v1 / 81) % 9))) のような箇所は数独の各マスの数値を9進数で表している

ということらしく、言われてみれば確かに…となりました(なぜ気付けるのかわからないですが、efficiencyを全部正解していたチームはたくさんいたので、わかる人にはわかるものだったのでしょう…)
従って、辞書順で最小の数独の答えを返せばよく、「そんなものOEISにないわけがない」というtempura0224の言葉通りhttps://oeis.org/A114288 が答えでした。

最後に

上記以外の工夫としては、

処理内容をLLMに問い合わせて、処理内容をエスパーする
小さな数値を関数の入力にあたえて実行結果を見て、処理内容をエスパーする

なども行いました。
各メンバーの協力もあって、コンテスト開始から24時間くらい経つ頃にはefficiencyの問題は全て討伐できました。

efficiencyはコンテスト序盤に取り組んでいた問題だったので、関数型言語のプログラムを読むことに慣れておらず手間取ったところもあります。このあとterry_u16とtempura0224はlambdamanでさらに宇宙言語に手を焼くことになります。
最終的にterry_u16は宇宙言語をそのまま読み書きできるようになりました。terry_u16を見かけたらSB%,,/と挨拶してみましょう。

To be continued…..冒険はパート2に続く
次回もお楽しみに🎊

良かったら、SNSやHPをチェックしてみてください。最新情報をお送りしています。

ALGO ARTISについて：https://www.algo-artis.com/

https://www.algo-artis.com/

最適化ソリューション『Optium』：https://www.algo-artis.com/service

https://www.algo-artis.com/service

化学業界DXソリューション『Planium』：https://planium.jp/

https://planium.jp/

X：https://twitter.com/algo_artis

https://twitter.com/algo_artis

Linkedin: https://www.linkedin.com/company/algo-artis/