見出し画像

【ICFPC 2024奮闘記】いい生活エンジニアチーム『chirijako』が挑んだ72時間！

株式会社いい生活 公式note

こんにちは！いい生活エンジニアのチーム『chirijako』です！
みなさん、ICFPCというプログラミングコンテストをご存じでしょうか！
今年で27回を数えるICFPC2024は、International Conference on Functional Programming(国際関数言語学会)が主催するプログラミング・コンテストです。

今年の公式サイトはこちら！

国内外の腕利きのプログラマーが72時間のなかで「超難問」と言われる問いに挑むコンテストに、いい生活のエンジニアチームは2017年から参加し続けています。今回は、2024年のコンテストでどんな課題が出され挑んだか詳細レポートします！


チーム概要

当社のエンジニアメンバーを中心に『chirijako』 というチームで参加しました。メンバーは変わりつつも2017年からずっと出場しており、今年は過去最多の11人チームで参加しています。

コンテスト概要

International Conference on Functional Programming(国際関数言語学会)が主催するコンテストで、日本時間 6/28(金) 21:00 〜 7/1(月) 21:00の 72時間 で開催されました。最初の24時間時点での順位で競う Lightning と72時間終了時点での順位を競う通称Full の2種類があります。

簡単に解くのは難しい問題がたくさん与えられるので、それを手元で計算して答えを提出し、合計スコアを競います。

2024年の5問

  1. Interstellar Communication Functional Programs (ICFP) というプログラミング言語で問題サーバーと会話します

  2. 問題は大きく5問存在します。問題そのものを取得するにも ICFP を利用する必要があり、これそのものが問題になっています

問題1: hello

以下の ICFP を実行して答えを得る問題です。

? B= B$ B$ B$ B$ L$ L$ L$ L# v$ I" I# I$ I% I$ ? B= B$ L$ v$ I+ I+ ? B= BD I$ S4%34 S4 ? B= BT I$ S4%34 S4%3 ? B= B. S4% S34 S4%34 ? U! B& T F ? B& T T ? U! B| F F ? B| F T ? B< U- I$ U- I# ? B> I$ I# ? B= U- I" B% U- I$ I# ? B= I" B% I( I$ ? B= U- I" B/ U- I$ I# ? B= I# B/ I( I$ ? B= I' B* I# I$ ? B= I$ B+ I" I# ? B= U$ I4%34 S4%34 ? B= U# S4%34 I4%34 ? U! F ? B= U- I$ B- I# I& ? B= I$ B- I& I# ? B= S4%34 S4%34 ? B= F F ? B= I$ I$ ? T B. B. SM%,&k#(%#+}IEj}3%.$}z3/,6%},!.'5!'%y4%34} U$ B+ I# B* I$> I1~s:U@ Sz}4/}#,!)-}0/).43}&/2})4 S)&})3}./4}#/22%#4 S").!29}q})3}./4}#/22%#4 S").!29}q})3}./4}#/22%#4 S").!29}q})3}./4}#/22%#4 S").!29}k})3}./4}#/22%#4 S5.!29}k})3}./4}#/22%#4 S5.!29}_})3}./4}#/22%#4 S5.!29}a})3}./4}#/22%#4 S5.!29}b})3}./4}#/22%#4 S").!29}i})3}./4}#/22%#4 S").!29}h})3}./4}#/22%#4 S").!29}m})3}./4}#/22%#4 S").!29}m})3}./4}#/22%#4 S").!29}c})3}./4}#/22%#4 S").!29}c})3}./4}#/22%#4 S").!29}r})3}./4}#/22%#4 S").!29}p})3}./4}#/22%#4 S").!29}{})3}./4}#/22%#4 S").!29}{})3}./4}#/22%#4 S").!29}d})3}./4}#/22%#4 S").!29}d})3}./4}#/22%#4 S").!29}l})3}./4}#/22%#4 S").!29}N})3}./4}#/22%#4 S").!29}>})3}./4}#/22%#4 S!00,)#!4)/.})3}./4}#/22%#4 S!00,)#!4)/.})3}./4}#/22%#4

ICFP に実装されている多くの演算子が含まれていて、全て正しく実装されていると `4w3s0m3` という文字列が得られます。`solve language_test 4w3s0m3` という文字列を ICFP 変換して、`S3/,6%},!.'5!'%y4%34}Y7X3U-X` をサーバーに送信すれば正解です。

問題2: lambdaman

効率的にパックマンを操作する問題です。

以下のような盤面が与えられます。 `#` が壁で `.` がエサ、最初は `L` にいます。上下左右に移動して全てのエサを取得するためのコマンドを ICFP で答えます。`ICFP` としての文字数がスコアになり、短いほどよいという問題で、全部で21ケースあります。

############################
#............##............#
#.####.#####.##.#####.####.#
#.####.#####.##.#####.####.#
#.####.#####.##.#####.####.#
#..........................#
#.####.##.########.##.####.#
#.####.##.########.##.####.#
#......##....##....##......#
######.##############.######
######.##############.######
######.##..........##.######
######.##.###..###.##.######
######.##.#......#.##.######
#.........#......#.........#
######.##.#......#.##.######
######.##.########.##.######
######.##..........##.######
######.##.########.##.######
######.##.########.##.######
#............##............#
#.####.#####.##.#####.####.#
#.####.#####.##.#####.####.#
#...##........L.......##...#
###.##.##.########.##.##.###
###.##.##.########.##.##.###
#......##....##....##......#
#.##########.##.##########.#
#.##########.##.##########.#
#..........................#
############################

問題3: spaceship

宇宙船を操作して全ての基地にできるだけ素早く到達する問題です。

以下のような二次元平面に基地が分布。加速度X・Y それぞれに `+1`, `0`, `-1` を入力して宇宙船を操作し、全ての基地の座標ちょうどに到達する速度を競います。早いほどよく、全部で25ケースあります。

問題4: 3d

セルオートマトンになっている独自のプログラミング言語を書いて正解を導きます。ソースコードは以下のような見た目をしていて、例えば

  • `>` は左のセルを右に移動する

  • `-` は上と左のセルの値を消費して引き算し、下と右に書き込む

のような動きをします。できるだけ小さい領域、短い実行ステップが良く、全部で13ケースあります。

. . . . 0 . . . .
. B > . = . . . .
. v 1 . . > . . .
. . - . . . + S .
. . . . . ^ . . .
. . v . . 0 > . .
. . . . . . A + .
. 1 @ 6 . . < . .
. . 3 . 0 @ 3 . .
. . . . . 3 . . .

問題5: efficiency

ICFP が与えられるので実行して出力を答えます。

素数判定や SAT が実装されているので、それを汲み取って効率的なソルバを書くなどすることで解答を導きます。全部で13ケース。

チーム『chirijako』成績概要

以上の難問を72時間解き続けたチーム『chirijako』。
最終的な成績は9月の関数言語学会で発表されるのですが、24時間時点で競う Lightning はおそらく15位前後、最終的な順位はおそらく20位前後ではという感触です。最終発表を待つ！

使った技術、成果物

  • Rust

    • 3人のメイン言語

  • C++

    • 1人のメイン言語

  • Python

    • 各種ツール

  • Next, Firebase

    • ダッシュボード

  • スプレッドシート

    • 3d を手で解く


時系列の詳細レポート

開始まで

今年が初参加の人が多かったので、例年のコンテストの流れを説明します。

6/28 21:00 開始

  • 開始そうそう、「ラムダ計算だー、うわー！」と驚愕。分かる人には2020年 galaxy の再来を思わせます

  • とりあえず ICFP の文字列だけ処理する Python スクリプトを作成してサーバーと会話を開始、hello のスコアを得ます

    • インクリメンタルに進捗が生まれることに気配りされていると感じました

  • ICFP の本格的な eval を3人が独立して作成開始、それ以外の人はサーバーと会話したり休息したり（寝たり）しました

6/29 深夜

  • ICFPの eval が2セットでき始めます

  • `language_test` を評価すると何か文字列が得られる！と喜んでいたが、よくみると `application is not correct` と書いてある

  • その後も気合いで実装すると `4w3s0m3` が得られてこれが正解

    • 6/29(土) 深夜1時なので開始から4時間

    • Rust

  • `get index` と `get lambdaman` や `get spaceship` が実行されて「どうやら個別の問題がいくつかあるタイプらしい」

6/29 昼まで

  • lambdaman と spaceship を解くフェーズに

  • lambdaman の問題盤面を得るためには ICFP の実行が必要ですが、特に lambdaman21 では 10進数で13226桁 の整数を評価する必要がわかり急遽多倍長整数の対応を始めました

  • lambdaman と spaceship を適当に解いていきます

  • 朝5時半に 3d 解放

  • 「lambdaman って ICFP 的に答えを圧縮する必要があるのでは？」と気づく

  • シミュレータもないのに 3d を手で解き始めます。結局最終日までシミュレータはなかった

  • 昼頃 efficiency 解放

  • この頃

    • lambdaman: 一人が焼きなましを書く

    • spaceship: 二人が焼きなましを書く

    • 3d: 二人が手で解き続ける

6/29 21:00 まで

  • 6人で手分けして色々やっていきます

  • efficiency が解かれ始めます。結局 Lightningh 時点では13ケース中7ケースが解けていました

  • efficiency をやる中で ICFP の eval が改良されて Y コンビネーターが正しく実行できるようになり、lambdaman の残りの盤面も得ることができました（ここまで2つくらい実行されていなかった）

  • lambdaman も spaceship も半端に焼きなました解を出してお茶を濁しておきます

  • 3人が 3d を手で解くことにハマっており、順位的には 3d が最も良い

6/30

  • ダッシュボードや提出用のツールなどが出揃い、ケースごとのスコアの確認や現在のベストがわかりやすくなりました

  • efficiency が完了

  • lambdaman はどうやら焼きなましではなくて ICFP 的な圧縮こそが本質だと気づきますが、最後までよくわからないまま終わりました

  • spaceship をクソデカビームサーチするとベスト解が出ることがわかったのでビームサーチを頑張っている

  • spaceship の探索順序を人が調整する必要がありチューニング

7/1 (最終日)

  • 引き続き 3d を手で解くのにハマっている人が多い

  • 3d を全ケースで正解

  • lambdaman はトップのスコアを見る限り我々が知らないことをやっているなと、あきらめの境地に

    • 終了後に線形合同法の乱数生成を ICFP で実装して、seed などを探索していたことが判明し気づけたなと後悔しています

  • 人が調整した spaceship の探索順序を追加で焼きなますことでベスト解をいくつか得られました

総評、感想など

問題そのものやコンテストの構成がよくできており、常にインクリメンタルな進捗が生まれて楽しいコンテストでした。成績や個々の動きには反省が多いのですが、その時々にはベストを尽くせていたと思っており、やり切った感があります。

チーム『chirijako』は例年15位付近で順位の上下はあるものの、今年は lambdaman の乱数生成に気づいていれば10位くらいになれたのでそれが悔しいです。

3d のシミュレーターがほとんど作成されることなく最後まで初期盤面から実行を脳内シミュレーションしている人ばかりで、（3d に取り組んでいない筆者としては）凄みを感じました。毎年のことですが、その瞬間だけなら難解プログラミング言語であっても読み書きができてしまうのが不思議だなと思っています。

計算機と人が融合して問題を解いていく ICFP の醍醐味を今年も感じ、来年も出場したいと考えています！

終わりに

チーム『chirijako』の72時間の奮闘を時系列含めてレポートしてきましたがいかがでしょうか。

いい生活のプロダクトを支えるエンジニアは、プログラミングコンテストだけでなく、日々の開発現場においても開発力を高める努力をしています。

お客様はもちろん、その先の社会において課題となっていることをプロダクトによって解決していきたい。そんな想いを持ちながら、いい生活のエンジニアは日々開発しています。

「そんなエンジニア気になる！」「話してみたい！」という方、ぜひお話ししましょう✨

いい生活では、新卒・中途ともに積極採用中！ 採用サイトもぜひご覧ください。

採用サイト
募集職種確認はこちらから