Google Foobar Challenge を知っていますか？
この記事に来た方は実際に発動したりどこかで見聞きしたかで調べているかと思います。僕はある土曜日の朝、突然 Google 検索の画面がおかしな動きをして初めてその存在を知りました。
Google Foobar Challenge とは
Google Foobar Challenge は Google がプログラミング関連の調べごとをしている人に「ちょっと遊ぼうよ」的な感じで発動するプログラミング問題（ゲーム？）のことです。
「宇宙空間に浮かぶラムダ司令官の悪の組織から、囚われの身になっているウサギちゃんたちを救う」という、どこのAIが考えたのか分からないストーリーを題材に、黒バックのコマンド入力画面の様なUIでプログラミングの問題を解いていきます。
途中まで解くと Google 社に自分の連絡先を送れたりもするので、本気で取り組む価値はあると思いますし、何より面白いです！好奇心旺盛な人にはたまらない時間になると思います。
そして僕はこの度めでたく全問クリア出来たので、記録として記事を書いてます。というか Foobar Challenge は全編英語というのもあって日本語の記事が全然見当たらなかったので書いてます。
問題とコードは GitHub に置いています
下記リポジトリに各問題と自分が作成したコードを載せていますので参考にしてみてください。*参考にしたくない方も Star 等いただけると助かります。。笑
https://github.com/kttyo/google-foobar-challenge
挑戦するには？
URL はこれですが、ページに飛んだところで誰でも挑戦できるわけではなく、Google 検索をしている時に自然発生するのをただただ心待ちにするか、知り合いが頑張って取得した招待用リンクをもらうかの２つしかありません。
必要なスキル
必要なスキルとしては、まずプログラミングの基本的な知識と英語力。そして途中からはアルゴリズムの知識、そして終盤は数学の知識も必要になります。ちなみに言語は Java と Python が使えます。僕は Python で解いていきました。
もちろん初めから全部揃っていたら最高だとは思いますが、後述の通り回答に結構時間をかけられるので必要に応じて調べていくのでも問題ないと思います。
プログラミングの知識よりも発想力＆想像力
プログラミングに関しては特に言語に精通している必要はないです。僕は Python 初心者で、そもそも今回 Google Foobar Challenge が発動した時も try-catch 文の書き方をググってたぐらいです。
それよりも問題を解決する方法を思いつく発想力や、色々な処理パターンを思い浮かべる想像力の方が大切だと思います。あとはそれを元に考えたロジックをコードに落とし込めれば大丈夫で、オブジェクト指向的な知識も全く必要ないです。
各レベルの内容
今後変更があるかもしれませんが、2021年1月時点ではレベル１〜５の全９問で構成されています。レベル１は本当に基本的な内容ですが、徐々に難易度が上がりレベル５はもう訳がわかりませんでした。問題自体は多分いくつかパターンがあると思うので、使うアルゴリズムの種類などは人によって変わると思います！
各レベルの主な内容を紹介します。
レベル１
まずは肩慣らしのような感じ。変数やループ等、プログラミングの基礎の基礎がわかっていれば大丈夫です。
- 問題数：1 問
- 制限時間：48 時間
こんな感じで進捗を確認できます。
レベル２
レベル 1 はプログラミング経験者なら誰でも解けますが、レベル 2 からはちゃんと頭を使う問題になります。このレベルをクリアすると友達に送る用のリンクを一つもらえます。
- 問題数：2 問
- 制限時間：各問題 168 時間（1 週間）
- クリアすると：招待用リンクがもらえる（1 度目）
レベル３
経験者の書き込みをいくつか見ると、Google の採用面接で出されるコーディング問題はこの辺りのレベルだとのこと。このレベルをクリアすると Google に連絡先を送ることもできるので、ここまではがんばりたいですね！
- 問題数：3 問
- 制限時間：各問題 168 時間（1 週間）
- クリアすると：Google に連絡先を送れる
迷路の最短距離の問題など、後になって考えてみればアルゴリズムの知識があればよかったなーと思いますが、想像力一本勝負でがんばりました。この辺りからは処理速度を気にしたプログラムを書かないと普通にタイムアウトでテストケースが Fail になります。
小休止（お勉強タイム）
このタイミングでアルゴリズムの知識を身に付けないとまずいと思い、下記の二冊をポチりました。
まず一つ目
こちらはプログラミング言語関係なくメジャーなアルゴリズムの概要をイラストでひたすら分かりやすく教えてくれます。「アルゴリズムとはそもそもなんぞや」だった僕にとっては最高の入り口でした。
そして二つ目
こちらは、一冊目の「アルゴリズム図鑑」とほぼ同じアルゴリズムを、Python のコードではどう表現するのかを教えてくれます。最高です。
問題と問題の間はいくら時間を開けても良いので、心の準備ができるまで備えると良いと思います！
レベル４
ここからはいよいよ発想力だけではどうにもならなくなり、アルゴリズムが必須になります。そして流石の Google 先生。アルゴリズムを当てはめて終わりではなく、さらに一捻り二捻りする必要があります。
- 問題数：2 問
- 制限時間：各問題 360 時間（15 日間）
- クリアすると：招待用のリンクがもらえる（2 度目）
1 問目は「せっかく学んだし」と思って幅優先探索を使ってみたんですけど処理に時間がかかりすぎたので結局別の方法に切り替えました。2 問目は最短経路を求めるベルマンフォード法を応用したイメージでした。
レベル５
いよいよ最終問題。そして流石の最終問題。もはやただの数学でした。
数学の知識はほぼゼロでしたが調べた内容を書くとするなら、バーンサイドの補題（Burnside’s Lemma）、ポリアの数え上げ問題（Polya’s Enumeration Theorem）、ユークリッドの互除法、順列と組み合わせ（Permutations & Combinations）、などなど。。。
- 問題数：1 問
- 制限時間：528時間（22 日間）
この記事（15.5 Applications of Pólya's Enumeration Formula）を読んでみたり、後述の動画をみたり。とりあえず何か掴めないか模索しました。
人によってはレベル４が一番難しいと感じる人もいるみたいですが、僕にとっては圧倒的にレベル５が一番難しかったです。途中ちょっと心が折れそうになりましたが、12日間かかってやっとクリア。
最終問題で参考にした動画
ポイント
- 「verify solution」が数秒で終わらない場合はパフォーマンス的なところで Fail してる可能性があります。書いたコードの計算数をイメージすることが大事です。
- 問題の細かい条件は読み取るのが難しいので、早めにコードを書いて「verify solution」でテストしながら察していくことが大事だと思います。
- とはいえ問題はなるべく正確に理解する様注意した方がいいです（当然ですが）。自分の場合レベル 4 でコードをしばらく書いた後でどうにも上手くいかないのでよーく問題を読み直してみたら自分で理解していた条件と実際が異なることが分かり、ほぼ丸ごとロジックを考え直しました…。
- ちっちゃいホワイトボードとかあると便利です。iPadとかでも良いのかな？その場で書いて消してを繰り返せるので。
- 参考までに、僕の回答は大体数十行で一番多くても 200 行未満で済んだので（あくまで Python の場合）、もしもやたらと処理が多くなっている場合は考えすぎているかもしれません。
まとめ
コロナでのステイホーム中に突然始まった Google Foobar Challenge。思いの外夢中になってとてもエキサイティングな数週間になりました。初めは全てクリアできるとも思っていなかったので、最終的には自信を得られたことが一番良かったことかもしれません。
皆さんももし挑戦する機会があったら週末など出来るだけ時間を取れる期間を見つけて、思い切り没頭してみてください。きっと素敵なおうち時間になると思います。
繰り返しになりますが、下記リポジトリに各問題と自分が作成したコードを載せていますので、参考にしたくない方も Star 等いただけると助かります。。笑