本記事は、はてなエンジニア Advent Calendar 2020 の17日目の記事です。昨日は id:papix さんでした。
AWSの資格試験を受けようとして失敗した話と、その副産物であるAWSしりとりについて書きます。
AWS認定資格試験の、Solutions Architect Associateを受験しようとしていました。受験には試験会場まで行く方法と自宅でオンラインで受ける方法があり、出かけるのが面倒だった私はピアソンVUEのオンライン受験を予約しました。
PCの要件は満たしていてシステムチェックも通ったけど、実際受けたら失敗したので、その体験談です。
1回目
監督者の方とチャットが繋がり、「それでは試験を送ります」と連絡をもらったところまでは順調でした。
試験案内のページに移り、チャットで「ページは切り替わりましたか？」と確認されましたが、文字を入力しようとすると虹色がくるくる回り出し、一文字入力するのに5秒くらいかかるようになってしまいました。それに気づかぬまま十数文字ほどタイプしてしまっていたため、その入力がゆっくりと処理されていくのをひたすら見守ることしかできません。
返答がないことで異常に気づいたのか、監督者が2人に増え、様子を尋ねてくれました。私は質問に少しでも早く返事をするために、タイプ数を節約して「hai」「no」などと返答していましたが、それでも監督者が次の質問を被せてくる方が早くて、会話が全く成り立ちませんでした。もはや紙にメッセージを書いてカメラに見せた方が早いと思ったけど、試験中は机の上に物を置けないので無理でした。
結局、質問を全部無視して「trouble」と送ったところ、「パソコンを再起動してみてください」と案内してもらえたので、再起動しました。
2回目
再起動してもう一度チェックインをやり直すと、無事チャットが繋がり、「さっきはすみません、再度チェックインできました」「よかったです」などとやりとりをすることができました。直後にチャット欄が消え、「試験が開始されるまでお待ちください」という案内だけが残されました。
何か試験開始の条件を満たしていないのだろうかと思って確認すると、OnVUE（受験のためのアプリケーション）以外の全てのアプリケーションを閉じないといけないところがChromeだけ残っていました。しかも応答なし状態になっていて、強制終了しても終了する気配がありません。今回はチャット欄がないためトラブルを伝えることもできず、独断でパソコンを再起動しました。
3回目
今回も一瞬チャットが繋がりましたが、すぐに消えてしまい、「試験が開始されるまでお待ちください」のまま進まない状態となりました。それでも1時間は粘ろうと思ってじっと待っていましたが、カメラから離れると失格とされる可能性があるし、他のアプリケーションも開けず、机の上にはなにもなくて、ただただ虚無の時間でした。頭の中でAWSしりとりをするなどして時間をつぶしました。
1時間経っても変化がなかったので、OnVUEを強制終了し、諦めることとしました。
その後サポートの方とメールでやりとりして、今回の試験結果の取り消しなど対応していただけました。
原因
後から調べてみると、Karabiner-Elementsが原因でOnVUEを使った受験に失敗することがあるそうです。私もKarabiner-Elementsを使っているので、これが原因だったのかもしれません。
この体験談を社内で共有したところ、私が待ち時間にやっていたという「AWSしりとり」とは？という話になりました。
AWSしりとりとは、AWSに関連する用語（主にサービス名）を使ったしりとりです。
サービス名に使われるアルファベットは偏っていることもあり、なかなかうまく続けられませんでした。せっかくなのでもっと長いしりとりを作りたいと思い、「最長しりとりを組合せ最適で解く」のコメント欄の方法を試してみました*1。
手順を以下に書きます。
1. 文字をノード、単語をエッジとするグラフを作る
使える単語を全部使って、文字をノード、単語をエッジとするグラフを作ります。例を挙げると、
こういう感じです。
実際にAWSのサービス名（AWSのプロダクト一覧やglossaryから取った）でやってみると、こうなります。
このグラフからは、「Cで始まるサービス名が多い」「Rで終わるサービス名が多い」などの特徴が読み取れます。
さらに、startノードとendノードを作ります。AWSしりとりは「AWS」の「S」から始めたいので、startノードは「S」ノードにのみ繋ぎます。どこでしりとりが終わってもいいように、endノードは他の全ての文字ノードと繋ぎます。
2. 解きたい問題を定義する
しりとりの長さを最大化するということは、以下の問題を解くのと同義です。
- 上のグラフで、startノードからendノードまでを辿る
- エッジはそれぞれ最大1回ずつ通れる
- なるべく多くのエッジを通りたい
上記の条件をコードで定義しやすいように、以下のようなテーブルを作ります。
すると、解きたい問題は
- それぞれのエッジを通るかどうかを 0 か 1 で表す
- startから出るエッジ、endに入るエッジはそれぞれ1本ずつ通る
- 通ることになったエッジの中では、fromノードとtoノードの文字の種類と数が一致しなければならない（startとend以外）
- 例えば、「A」から出るエッジを2回通るなら、「A」に入るエッジも2回通らなければならない
- エッジを通るかどうかの値の合計（テーブルの水色の部分の合計）をなるべく大きくする
という条件の下でそれぞれのエッジを通るかどうかを決める（テーブルの水色の部分の値を決める）ということになります*2。
3. 最適化問題として解いてもらう
いろいろ制約がある中で、ある値を最大・最小にするにはどうすればいいかというのを考えるのは、最適化問題と呼ばれています。その中でも線形計画問題は、PuLPというPythonライブラリで扱うのが定番のようです。PuLPを使って上記の問題を定義し、ソルバーに解いてもらうことで、どのエッジを通ると経路を長くできるのかを求めることができました。
4. 解答からルートを組み立てる
最適化問題を解いて、それぞれのエッジを通るか否かは決まりましたが、通る順番までは決まっていません。
どのように経路を求めるかというと、使うことに決まったエッジのみを使ってグラフを作り、startノードとendノードも繋いでから、startノードを起点とするオイラー閉路を求めます*3。networkxのeulerian_circuit()などが使えます。
こうして、73個のサービス名を使ったAWSしりとりを作ることができました。
AWS → SES → SNS → SQS → Step Functions → SWF → FreeRTOS → Shield → Direct Connect → Timestream → MQ → QuickSight → Textract → Trusted Advisor → RoboMaker → RAM → Managed Blockchain → Network Firewall → Lightsail → Lambda → AppFlow → WAM → Macie → ECR → Rekognition → Neptune → EBS → Snowmobile → EKS → Snowcone → ECS → Snowball → Lumberyard → DataSync → Config → GovCloud → DeepLens → Sumerian → NLB → Braket → Transcribe → Elastic Beanstalk → Kinesis Video Streams → Secrets Manager → RDS → Systems Manager → Redshift → Translate → Elastic Inference → ElastiCache → EventBridge → Elasticsearch Service → ELB → Batch → Honeycode → EFS → Security Hub → Backup → PrivateLink → Kendra → A2C → Cloud Map → Panorama → A2I → Inferentia → Aurora → Athena → AppSync → Cognito → Organizations → SSO → Outposts → SageMaker → Route 53
意外とまともなしりとりができてしまった。
EBS → Snowmobile → EKS → Snowcone → ECS → Snowball
このあたり、リズム感があって好きです。
話が逸れてしまいましたが、Solutions Architect Associateの試験を受けたかったのでした。近いうちに再挑戦しようと思います。
アドベントカレンダーの明日の担当は id:onk さんです。
*1:調べてみて初めて知ったけど、最長しりとり問題はかなり昔からある話題で、最長しりとりを作ってくれるwebサイトもあります。この記事で自分で実装することにしたのは、始める文字縛りやグラフの可視化など、追加でやりたいことがあったからです。
*2:厳密には、この条件だけではstartからendまで一筆で辿れる保証はありません。下の非連結グラフについての注釈参照。
*3:非連結グラフになってしまった場合（飛び地ができてしまった場合）はそのままではオイラー閉路を求められませんが、そのときの対処法も参考記事のコメント欄に書いてくれてあります。その解よりも長いしりとりを探しに行きたい場合はこの記事のような工夫をする必要があるようです。
