Google Foobar Challenge に挑戦しました

Google Foobar Challenge とは

Googleでコンピューター関連の検索をしている人にランダムでインビテーションが表示され、Googleから出題されるプログラミングの問題を解くことができます。
検索履歴に基づいてGoogleのAIが何か判断しているのでしょうが、私の場合はなぜ表示されたのかはわかりません。Pythonのライブラリをググっていた時に急に出てきました。

ちょっと調べたら英語の記事ばっかりだったので、言語設定を英語にしていないと出ないのかもしれません。

インビテーション

こんな風に検索結果がパカっと向こうに倒れて、隙間にこんなボタンが出てきます。

"You're speaking our language." あなたは我々の世界の言葉(=プログラミング言語)を話しているようですね、といった感じのお誘い。
ここで赤いボタンを押すと二度と表示されないようです。やりたい人は青いボタンを押します。

ログイン

コンソール画面に移ったら、まずはSign In のボタンを押しましょう。
これを押しておくと、一度ブラウザを閉じても継続してチャレンジすることができます。
レベル5までを一度に解くのはかなり難しいと思うので、必ず押しておきましょう。

チャレンジ内容

これからやる人もいると思うので、問題の内容については詳しく触れません。悪しからず。
問題の内容は人によって違うみたいです。

ストーリー

一応ストーリーがあり、各レベルの問題はこのストーリーに沿って進んでいきます。
ウサギ(Bunny)の惑星を破壊しようとする悪の組織の宇宙船に潜入し、計画を阻止しつつ宇宙船のウサギちゃんたちを救出していくというストーリーです。
クルーに扮してタスクをしたり、ドアロックを解除するためにプログラミングで問題を解いていくといった感じでストーリーが進んでいきます。

問題を解く流れ

問題のリクエスト

問題のリクエスト、閲覧、提出はすべて画面上のコマンドで行います。
requestコマンドで問題をリクエストすると、カレントディレクトリに問題のディレクトリが作成されてそこに問題文などが格納されます。
readme.txtというファイルにストーリーと問題、テストケースが書いてあります。
また、同じフォルダにsolution.pyとSolution.javaというテンプレートのファイルがあるので、それを編集する形でコードを書きます。

テストケースの実行

一通りのコードが書けたら、verifyコマンドでテストケースを実行できます。
このように結果が表示されます。

readme.txtに書かれているテストケースに加えて条件が開示されないテストケースが複数あり、それも評価されます。これがけっこう厄介です。何がダメだったのか一切分からないので、自分で手元のコードだけを見て欠陥がないか調べる必要があります。
失敗の原因が分からない時は改めて問題の条件を整理し、考慮の漏れているパターンがないかを調べるといいでしょう。また、一定時間が経ってからFailになる場合は処理に時間がかかりすぎて打ち切られている可能性もあります。

提出

すべてのテストケースに通ったら、コードを提出します。
submitコマンドでコードを提出したら問題のディレクトリは削除されます。

各レベルの内容

レベル1

問題数：1
制限時間：7日

まずは練習問題みたいな感じでした。
ここはプログラミングをしたことがある人ならサクっとできるかと思います。
十数行のコードを書いて簡単に終わりました。

↓ レベル1と5だけ演出でウサギのAAが出ます (動きます)

レベル2

問題数：2
制限時間：各7日

ここからはちゃんとロジックを考えて解く必要が出てきます。
1問目は並び替えの問題。特定の条件に従って並び替えをする関数を書きます。
2問目は並び替えではないですが似たような問題でした。

このレベルをクリアすると他の人を招待できるURLがもらえます。
ぜひ友達を誘ってみましょう。

レベル3

問題数：3
制限時間：各7日

整数の組み合わせの数を調べるコードや迷路の経路探索をするコードを書きました。

1問目は組み合わせを求める問題。数列から条件に沿って数字を取り出す方法が何通りあるかを調べます。
2問目はこれも整数の問題。与えられた条件に沿って数字を計算したら何回の計算で別の数字にできるか、みたいな。
3問目は経路探索的な問題です。迷路の最短経路を求めました。

レベル3からはちゃんと処理効率を考慮して書く必要が出てきます。何も考えずに安易にループをネストしたり関数を再帰しまくるとループ回数が簡単に億や兆単位になり処理が終わりません。
最初、非表示のテストケースがFailになる理由が良くわからなかったのですが、色々なパターンを手元で試しているうちにタイムアウトであることがわかり、コードを改善してパスできました。

ストーリー的にはここまで解くとウサギの惑星を破壊する計画は阻止成功です。
この後はウサギちゃんの救出と宇宙船からの脱出に移ります。

レベル4

問題数: 2
制限時間: 各15日

さらに難しくなります。
レベル3まではパズルのような感じでしたが、少し数学チックになってきます。
問題文を読み解くのがだんだんと難しくなってきます。じっくり読んで条件を理解しましょう。

1問目はグラフ理論みたいな問題で、ノードと重みづけされたエッジが提示されてそれに関する計算をしました。
このあたりの数学的な予備知識が全くなかったので一生懸命ググりながら進めました。
数学の解説サイトで定理などを調べてやり方を考えて、それをコードに落とし込む感じでした。

2問目

またグラフの問題です。
あるノードからスタートして所定のルールで移動する場合、時間切れまでに最大でいくつのノードを回れるかということを計算するプログラムを書きます。
こちらは1問目とは違って特に数学の理論を調べたりすることなくパズル感覚で解けました。

これを解き終わると招待リンク(2回目)が貰えます。

レベル5

問題数 1
制限時間 22日

数字が入った任意の大きさの碁盤を並べ替える方法がいくつあるのかを計算します。
こう聞くと簡単そうですが、こういう場合は同じとみなすという条件が設定されていて、一筋縄にはいきませんでした。

ここで正月が終わってしまいあまりまとまった時間を取れないまま期限が来てしまいました。
最後の最後にバーンサイドの補題というのを応用すれば解けそうだということが見えたのですが、もう時間がなくなってしまいました。

チャレンジを終えて

ロジックをじっくり考えながらプログラムに落とし込んでいくのは純粋に楽かったです。普段アプリなどを作る時ってけっこう単純な処理が多くて、ロジックをじっくり考える部分って少ないないです。

また、テストケースが非表示だったことで、問題の条件を読み込んで着実にロジックを組み立てていくことが必要でした。私はインフラ系なので仕事でプログラムを書くことはないですが、この考え方は何の業務でも大切にしなければと思いますね。

最後解けなかったのは残念ですが、コロナ禍+年末年始の楽しいチャレンジとなりました。