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

2024年7月31日 15:00

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

spaceship

問題概要

SpaceShipは宇宙言語を読み解く他の問題とは異なり、ヒューリスティックコンテストに出てくるような形式の問題でした。※ただし、入出力は宇宙言語を変換する必要があります。

ルールは以下のようなものです:

ゲームは2次元座標上で行われ、次のように進行します。
宇宙船は最初、原点 (0, 0)に位置し、速度は (0, 0) からスタートします。各ターンで宇宙船は以下のように行動します。
1. 速度のx座標、y座標をそれぞれ±1だけ変化させるか、そのままにする（3×3=9通りの操作）。
2. 宇宙船の位置を現在の速度分だけ移動させる。
訪問する必要のある地点のリストが与えられるので、なるべく少ないターン数でそれら全ての地点を訪問する手筋を見つけてください。

速度と加速度を使って目的地に移動していく問題なので、第一回マスターズ決勝にどこか似ていますね。

速度は毎ターン高々1のみ変化する
速度にノイズが加わることはない

という点がマスターズ決勝と異なっています。決定的に位置・速度が決まるので、工夫すればターン数の理論値が出せそうな雰囲気が感じ取れます。

例

訪問する地点として、(1,-1), (1,-3), (2,-5), (2,-8), (3,-10)が与えられた場合を考えてみます。
原点からスタートして与えられた順番で地点を訪問してみます。各地点から次の行き先までの座標の差分は、(+1, -1), (0, -2), (+1, -2), (0, -3), (+1, -2) になります。
さて、速度は各ターンに±1だけ変化させることができるはずです。上記の隣り合う差分どうしはx,y座標ともに±1以内で増減しています。各ターンの速度を上の差分の通りに変更すれば、1ターンごとに次の地点の座標に移動することができそうです。
実際に宇宙船を移動させてみると、以下のようになります。

宇宙船が全ての地点にうまく到達しました！ 5箇所の地点を5ターンで訪問することができたので、このケースの最適な経路を見つけることができました。

問題ケース

Spaceshipの問題ケースは全部で25個あります。実は、先ほどの例題はこのうちの1つ目のケースであるspaceship01でした。
spaceship01のように地点数が数個のケースもあれば、地点数が数万個に及ぶケースも存在します。ケースによって解法を変える必要がありそうです。
それぞれのケースには特徴があって、大きく分けて以下の3種類に分類できます。実際のケースを見ながら紹介・考察をしていきます。

(1)地点が一筆書きされたケース
まず1つ目です。この種類のケースは端から端へと一筆書きのように並べられた地点が入力で与えられるのが特徴です。spaceship06、spaceship09を例として見てみます。

spaceship06は地点が緩やかな曲線状に並べられています。地点間の間隔に多少差はありますが、どちらかの端から出発して、まだ訪問していない最も近い地点を順に辿っていくことで全地点を周ることができそうです。

spaceship09は一筆書きの要領で地点が並べられてはいるものの、2つの経路が交差する箇所や集中的に地点が入り混じっている箇所が見られます。spaceship06のように最も近い地点を辿っていく方針では厳しそうです。
経路が交差する箇所は2つの経路がなだらかになるように、交差している地点を2つに分類することで、うまく経路を切り分けられそうです。
地点が集中している箇所は、宇宙船の速度が急激に変化しないように経路を決めてあげると良さそうです。速度は毎ターン1のみ増減する制約上、速度の急激な変化はターン数をより消費してしまうためです。

(2)地点が模様を描くケース
次に2つ目です。この種類のケースは特定の模様の形に並べられた地点が入力で与えられるのが特徴です。spaceship21を例として見てみます。

spaceship21は渦巻き模様に地点が並べられています。中心から渦が4つに分かれているので、それぞれを辿ることで効率よく訪問できそうですが、画面端で見切れているのが問題です。例えば、左下、右下、右上で見切れた同じ渦はこれらをそのまま辿るよりも、近くにある別の渦の端と繋げることでより短いターンになると考えられます。
宇宙船は左上の点から始まるので、このスタート地点から模様を辿りつつ、渦の端と端を繋いで一筆書きの経路を作ります。「どの端と端を繋げるか」、「ゴール地点をどこに定めるか」をうまく決める必要があります。

(3) 地点が散在するケース
この種類のケースは地点が無作為に散りばめられているのが特徴です。
1,2つ目では貪欲に近い地点から選んでいくことで効率の良さそうな経路を決められましたが、このケースではその方針は難しそうです。
巡回セールスマン問題（TSP）の要領で経路を決めるとそれなりに効率の良い経路が求められそうです。ただし、本問題では宇宙船は速度を急激に変化させることができないため、速度がなだらかに変化するような経路が理想的です。

解法

私たちの解法は2つの手順に分けられます。

(1)経路を決める

一筆書きのケース
- 両端のうち、宇宙船のスタート地点から近い方の端を始点として、貪欲に近い地点を辿っていく
模様のケース
- 地点の中からスタート、ゴールを決めて、見切れている模様の端同士を手作業で繋げて一筆書きの経路を作成する
地点が散在するケース
- 巡回セールスマン問題（TSP）の要領で経路を求める
  - 焼きなまし法を使って、以下の2つを評価して経路を作成した
    1. 経路の長さ
    2. 経路で隣り合う地点間の速度変化の大きさ
      - 経路の連続する3地点について、1つ目→2つ目の速度ベクトル、2つ目→3つ目の速度ベクトルの変化量に注目する
  - 他にも、後述するDP解法の結果を評価値とした

(2)経路から少ないターン数の手筋を求める

経路に対して最短のターン数を求める動的計画法（DP）を使用
- 具体的には、「経路のi個目の地点に速度が(vx,vy)の状態で到達した時の最短ターン数」を管理する
  - 地点数が多いと実行時間が長くなるため、以下の枝刈りを使用
    - 速度の上限・下限を設定
    - 途中経過でのdpの最短ターン数+αを閾値として、遷移する候補を絞る
    - ある地点から別の地点まで到達するためのターン数に上限を設定
- dpの遷移では、以下の問題を解けば良い。
  現在の地点での速度がv1の時、次の地点に速度v2で到達することは可能か？また、可能な場合は最短ターン数とその手筋を求めよ。
  これは実際に解くことができる（詳細は省略）。

結果

前述したケースごとの方針と解法をふまえて、実行結果を確認します。

(1)地点が手動で一筆書きされたケース

spaceship06

スタート地点から近い方の端から順番に地点を辿ることができていますね。
動的計画法を使うことで最短ターン数も達成しています。

spaceship09

経路がなだらかになるように地点を振り分けたことで、宇宙船が不自然な挙動をせずに交差する地点を辿ることができています。
地点が集中している箇所では右往左往することなく宇宙船が動くことができていそうです。

(2)地点が模様を描くケース

温かみのある手作業で模様の端を繋ぎ合わせて効率の良さそうな経路を作成しています（こだわりポイントは画面右下）。
この経路で順位表凍結前まで全体1位を達成することができました。

(3)地点が散在するケース

宇宙船が緩やかにカーブしながら経路を辿っている様子がわかると思います。

感想

とても面白い問題でした！
3日間でSpaceshipの全てのケースに対して解答を提出することができました。
最終日にはSpaceship部門で瞬間的に1位になることができました。
順位表凍結前の時点で、ケースの7割は単独1位か1位タイのスコアで、残りのケースもTOP10以内のスコアでしたが、Unagiチームにリードを許す結果となりました。
チームで協力して解法を組み合わせることで、様々なケースでスコアを改善することができました。特に、ビジュアライザのおかげで一筆書きされたケースや、模様が描かれたケースの経路を工夫して考えることができました（yunixさんありがとうございます！）。
チームHeuristic Artisの名に恥じず、ヒューリスティック形式の問題で良い結果を残せたのではないかと思います。

3d

問題概要

3dでは、問題タイトルにもなっている3d言語というオリジナルの難解プログラミング言語を使って、3d1から3d12の12問の問題を解くことを要求されます。この言語は名前の通り、X軸,Y軸,そして時間軸という3次元空間上で動作するプログラミング言語です。

まずは、実際に3d言語で書かれたプログラムを見てみましょう。

. B .
A + .
. . .

AとBが入力として与えられ、+ は加算を表す演算子です。
例えばA=1,B=2を与えると、上のプログラムは以下のように動作します。

(0ターン目)
. 1 .
2 + .
. . .

(1ターン目)
. . .
. + 3
. 3 .

演算子の左と上に数字がある場合、演算子はそれらを消去し、代わりに演算結果を右と下に吐き出す動きをします。同様の二項演算を行う演算子として、四則演算,一致判定演算,不一致判定演算が用意されています。
また、移動演算子として>,v,<,^が用意されており、これは数字を上下左右に移動させることができます。

(0ターン目)
0 > . . < 1
2 . . . . .
v . . . . ^
. . . . . 3

(1ターン目)
. > 0 1 < .
. . . . . 3
v . . . . ^
2 . . . . .

そして最後に、この言語の大きな特徴である、タイムワープ演算子@があります。
これは、以下のような記法で命令を出します。

. a .
x @ y
. t .

これは、”盤面をtターン遡り、@ 演算子から見て相対位置が(-x,-y)の場所にaを上書きする”という挙動をします。
とは言われてもピンと来ないと思うので、実際に問題を解くコードを動かしてみましょう。

問題例

【3d1】
入力Aが与えられる。Aの階乗を求めよ。

解答コードが以下になります。Aに入力が与えられ、Sで回答を出力します。

. . . 1 > . .
. . . v . v .
. . . . . . .
A > . * . = S
v 1 . . . . .
. - . v . . .
. . . . > . .
. v . . 2 @ 7
. . > . . 4 .
. . 3 @ 6 . .
. . . 4 . . .

これは以下のようなコードを実行しています。最上部にある1がproductで、ループごとに上書きすることで積を更新していきます。

product = 1
while(true){
	if(A * product == product) return product;
	product *= A;
	A -= 1;
}

入力としてA=3を与えた時の実際の挙動を見てみましょう。

なんとなくループしている感じが伝わったのではないかと思います。プログラミング言語というよりはピタゴラスイッチみたいですね。

実行環境

後から振り返るとコーディング環境やビジュアライザを作成するべきではあったのですが、実際のところ3dを担当したほとんどのメンバーはExcelコーディング・脳内エミュレータ実行という力業で解決していました。なんとか可読性を上げようと、色分けを行ったりコメントを付けたりと、各自工夫を凝らしていたようです。
途中でtakumi152が最低限動くシミュレータを作成してくれたので、デバッグはそちらで行っていました。

コードゴルフ

さて、3dの各問題のスコアは、以下で算出されます。スコアは小さければ小さいほど良いです。

(使用した空間の幅) x (使用した空間の高さ) x (使用したターン数)

問題1の解答コードを改めて確認してみましょう。

. . . 1 > . .
. . . v . v .
. . . . . . .
A > . * . = S
v 1 . . . . .
. - . v . . .
. . . . > . .
. v . . 2 @ 7
. . > . . 4 .
. . 3 @ 6 . .
. . . 4 . . .

幅が7、高さが11、ターン数は5ターン必要なので、このコードのスコアは385点となります。もう少し上手く配置することで、スコアを減らせないでしょうか？
Excel上で色々並び替えてみます。人力焼きなましです。

 . . . . 1 > . 
 . . < A * . = 
-1 + . . . v S
 . . . . . . .
-2 @ 3 . 1 @ 4
 . 2 . . . 2 .

お、これはよさそうです！
幅が7、高さが6、ターン数が3なので、126点となります。スコアを1/3にできました！
こんな感じで、ただでさえ読みにくい3d言語を、なるべく小さな空間内にうまく詰め込むことを求められます。難しいですね。

感想

めちゃめちゃ面白かったです！！！
難解言語でコードゴルフをさせるという取り組み自体はMAOなどいくつか先例がありましたが、3d言語はタイムワープという概念を導入した結果として驚くほどの自由さと複雑さを実現しており、3日間考え続けても新しいアイデアが尽きることがありませんでした。
最終日までUnagiと1位争いをし続けることができましたが、副作用としてしばらくは夢の中に3d言語が登場する羽目になりました……。

最後に

参加したメンバー一同、ICFPCを非常に楽しむことができました。
大量の興味深いタスクが与えられて、非常に充実したコンテストでした。始まる前には、やることがなくなったら箱根観光に行くかw、などと言っていたのですが、宿から外に出る暇がありませんでした。

成績も初参加にしてはかなり健闘できて、順位表凍結直前には全体で4位となかなかの位置にいました(これは人海戦術が効く回だったことが大きいですが… これだけのメンバーをこの人数揃えたのは少しずるいような気もします笑)。

もしこの記事を読んで興味を持った方がいたら、来年はぜひ参加してみてください!　個人でも参加できますし、Xなどでチームメンバーを募集しているチームもあるようです。
弊社チームは来年も参加予定です! 対戦よろしくお願いします!

最後まで読んで頂きありがとうございます。参加した弊社メンバーの活動はXで確認できます。ぜひみてみてください。それではまた次の記事でお会いしましょう。

良かったら、ALGO ARTISの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/

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

spaceship

問題概要

例

問題ケース

解法

結果

感想

3d

問題概要

問題例

実行環境

コードゴルフ

感想

最後に

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