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

2024年7月30日 15:00

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

lambdaman

問題概要

lambdaman では迷路とスタートマスが与えられ、上下左右への移動を繰り返して全ての . マスを1度以上通るような操作を求める課題でした。# のマスや盤面の外側に出ることはできません。そのような操作をしようとした場合その場に留まります。
例えば、以下のような迷路に対しては、LLLDURRRUDRRURR(左左左下上右右右上下右右上右右)と回答することで正解となります(Lがスタート位置を表すマスです)。

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

lambdaman は全部で21問出題されました。問題ごとに様々な特徴があります。

lambdaman は efficiency とは異なり、ただ正解すればよいというわけではなく以下のような特殊なルールが設定されていました。

提出は、文字列をそのまま送ってもよいし、迷路を解く文字列を生成する宇宙言語のコードを提出してもよい
正解の中でも、より短いコード量で正解できたほうが高順位になる
出力される文字列の長さは100万文字以下に収めること

具体的な問題で説明しましょう。
問題6 は以下のような迷路でした。

L...........(略)...

. の数は省略した部分も含めると199個でした。これを迷路と呼んでいいのかは謎ですが、何はともあれ右に199回(以上)移動すれば正解できます。
したがって、最も簡単な正解方法は R を 199 個繰り返した文字列をそのまま出力することですが、これだと 199 文字かかってしまいます。
しかし宇宙言語を使って例えば以下のようなコードを書くと 74 字で R を 200 個繰り返した文字列を生成することができます。

B$ L' B. v' B. v' B. v' B. v' v' SLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL

宇宙言語に精通されていない読者のために JavaScript に変換したコードを添えると以下のようになります。
「同じ文字列を5回繰り返す関数」を作ってそこに「Rを40回繰り返した文字列」を代入する、ということですね。

((v1) => v1 + v1 + v1 + v1 + v1)("RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR")

ちなみに、実際のこの問題を解く最も短いコードはこのようになります。

B$ L" B$ v" B$ v" B$ v" SLLLLLLLL L! B. v! B. v! v!

JavaScript で書くと以下のようになります。もはや JavaScript にしても難読ですね。
ざっくり説明すると、「Rを8回繰り返した文字列に”ある操作”を3回繰り返す」という関数に「文字列を3回繰り返す」という操作を代入することで R を 216 回繰り返した文字列を生成しています。

((v1) => v1(v1(v1("RRRRRRRR"))))((v2) => v2 + v2 + v2)

問題へのアプローチ

efficiency で「宇宙言語を読む」ことはある程度できるようになっていた我々ですが、ここで2つの大きな問題に直面しました。

宇宙言語を自分たちで書かないといけない
自分で書いた宇宙言語が正当であるかを確かめるために、実行できる環境が欲しい

yunix の貢献により宇宙言語をJavaScriptに変換することはできていましたが、前述の通り再帰関数を実行しようとすると落ちてしまうなどの問題があり、機能としては不十分でした。
そこで、tempura0224 がJavaScriptで遅延評価を実装することで再帰関数の実行を可能にし、さらに JavaScript のコードを宇宙言語に変換する逆トランスパイラを追加で開発しました。これにより、「JavaScript で迷路を解くコードを作成し、手元で実行結果を確認しつつ、宇宙言語で提出する」ということが簡単に行えるようになりました。
(tempura0224 がこれの実装に手こずっている間に terry_u16 が「94進数整数を4進数に変換する関数を作成することで回答文字列を圧縮する」という方針のコードを宇宙言語を直接書くことで完成させていて目と耳を疑ったのですがそれはまた別のお話です。)

最初、私たちのチームでは、「ランレングス圧縮した文字列を埋め込んで復元するコードを作成すると短くなるのではないか」「ランレングス圧縮を前提としたときに、短くなるような経路を見つける必要がある？」といったことを考えていましたが、ここで terry_u16 が閃きました。
「100万回も移動して良いならランダムな移動を繰り返すとわりとうまくいくのでは？」
通らないといけないマスの数は最も大きい問題21(約4万マス)を除けば数千マス程度、小さい問題だと数百マスしかないので、確かに100万回も移動すればいけそうな気もします。
早速線形合同法を用いてランダムな文字列を生成するプログラムを書くことにしました。宇宙言語でのコードは割愛しますが、以下のような再帰関数を実装しました。


const solve = () => {
   const start = 23;
   const end = 1;
   const a = 23;
   const m = 799999;

   const rec = (x) => {
      if(x === end) {
         return "";
      }
      const next = a * x % m;
      return "LURD"[x % 4] + rec(next);
   }

   return func(start);
}

一般的な線形合同法は ax + b の形を用いますが、+ b に使う文字数も惜しいので a 倍するだけの簡易実装です。
このコードを宇宙言語に書き直して提出すると数百マス程度の迷路は全て解くことができました。
数千マス以上の問題はこのままでは厳しかったのですが、以下のような努力をすることで結果的にはほぼ全ての問題を線形合同法によって解くことができました。

単にLURDをランダムに繋げるのでなく、問題に応じて、同じ文字が連続しやすくなったり、左折/右折が連続しやすくなったりするような工夫を加えました。
マシンパワー(180コア360スレッドのGCEインスタンスを借りました)を信じて、迷路を解くことのできるパラメータ(start、end、a、m)の組み合わせを探索しました。コード長が短いほうがよいというルール上、ただ迷路が解けるだけでなく各種パラメータの桁数が短いほうが良いので、必死に探索しました。

最終的に、僕たちのチームの解法の内訳は全21問中

迷路が小さく文字列をそのまま出力するのが最短だったもの: 3問
線形合同法などランダムな文字列を出力することで解いたもの: 13問
それ以外の方法(問題6のようなルールベースなど)で解いたもの: 5問

となりました。多種多様な迷路があるにも関わらず半分以上の問題が線形合同法で解けてしまうというのは少し切ない気持ちにもなりつつ衝撃的で面白かったです。

余談ですが、コンテスト終了後に各問題の最短解法が公開されており、そこでは僕たちがランダム解法を採用しなかった3問を含めた実に16問がランダム解法で更なる衝撃を受けました。
僕たちのチームは、lambdaman 単独では、順位表凍結時点では5位とまずまずの結果となりました。上位に食い込めた理由は線形合同法でうまく解けるパラメータを見つけることに成功していたからですが、逆に最上位に入れなかったのは、線形合同法のそもそもの実装が良くなかったからでした。再帰関数を実装するのにYコンビネータをそのまま使用していたのですが、実は一工夫加えることでより短いコード長で再帰関数を実現できたようです。
「実は再帰関数をもっと短く書ける」以外のほぼ全ての要素をクリアしていただけに悔しさの残る結果とはなってしまいましたが、最後まで楽しく向き合うことができました。
最後に、線形合同法以外の方法で面白く解けた問題を2問紹介してこの章を締めくくりたいと思います。

問題5

中央から渦巻きのような形で外側に出ていく問題です。
「LLRDDDLLUUULLULLRUURUDRDRRRURDLD という文字列を27回繰り返す」という解法で上位に入ることができました。LLRDDDLLUUULLULLRUURUDRDRRRURDLD という文字列は山登り法によって見つけられました。こういった設定でも山登り法で解けるのは面白かったです。

問題19

フラクタルのような形状になっています。マス目の数や行き止まりが多く線形合同法などの解法では解くことが難しい問題でしたが、Jirotech がこのフラクタルの構造を解析し、以下のような再帰関数を実装しました。
この問題では全体で単独1位(順位表凍結前時点)のコード長を達成することができました。

const solve = () => {
  const func = (n, idx) => {
    if (idx === 0 || n === 0) {
      return "";
    }
    return (
      "UDDULRRL"[idx / n] +
      (idx % (2 * n) === n ? func(n / 2, 4 * n - 1) : "") +
      func(n, idx - 1)
    );
  };
  return func(64, 511);
};

To be continued….パート3に続く
いよいよ最終章、次回もお楽しみに🎉

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