Harvard XのCS50 2021 Week3 のプロブレムであるTidemanがようやく終わった。
CS50は無料のオンライン講座で、Harvard大学が実施しているCS50という講義をedXというプラットフォームで無料配信している。CSはComputer Science の頭文字をとったものらしい。50というのは講座番号らしいのだけれど、なぜ50なのかは調べてもよくわからなかった。CS50はIntroduction to Computer Scienceという正式名称で、Introductionというのが信じられないぐらい難しい（けど楽しい。）オンライン講義でなければ、つまりハーバード大学に入学していればCS51(Introduction to Computer Science 2)とかCS60というのも履修できるような情報も見つけたけど、ちょっと情報がふるいのでCS51はともかくCS60がまだ存在するのかがわからなかったし、入学しなければいけないのはハードルがかなり高いなあ。
CS50は無料というのが信じられないほど素晴らしい内容で、2時間半程度の講義と講義で扱った内容をもう少し詳しく説明するショートビデオ(Short)、練習問題(Lab)と課題(Problem)で成り立っている。講義の内容はまとまってサイトに上がっているし、講師であるDavidが話した内容がすべて文字に起こされていて、講義の英語がよくわからなかったり、講義のあの部分だけもう一度確認したいといった時に非常に便利。講義も工夫されていて、お金もかかっている様子。なんでも毎年講義内容を更新して講義も撮り直ししているらしい。もともとはハーバード大学で実際に行われている講義を録画したものなので、当然と言えば当然だけど、内容が変わっていくのも素晴らしいと思う。
12週間分の講義を自分のペースで進めていけるのだが、最初はScratchを使ってプログラミングはこんなものですよという紹介から始まって、C言語、Python, HTML+CS＋Javascriptを順番にやっていく。盛りだくさんのボリューム。講義を見た後、練習問題や課題をこなして身に着けていく。
練習問題や課題はCS50 IDEというクラウド上のサービスを使って解いていくのだけれど、このCS50 IDEがとてもよくてプログラムの勉強時にありがちな開発環境を整えるだけで時間がかかってしまう、もしくは開発環境構築に挫折してしまうといった事態を避けられる。それにCS50 IDEを使ってエラーのチェックや、課題の提出、さらには採点までされるという、なぜこれが無料で使用できるのかと不思議に思うレベル。何十時間も触っていくことになるので、画面のデザインがシンプルでクールなのもいい。
ターミナルで操作したときの反応が若干遅い気がするのはサーバーが地球の裏側（アメリカ）にあるせいかな。
ここからCS50について確認できます。いつまでリンクが生きているかわからないので、「CS50 Harvard」とかで調べた方がいいかもしれない。
CS50（https://pll.harvard.edu/course/cs50-introduction-computer-science?delta=0）
さて、Tidemanについて。TidemanはWeek 3(Week 0から始まるから4週目)の課題。同じくWeek 3のRunoffと同様、選挙時の投票システムをつくる課題なのだけれど難易度が桁違いだった。自分はRunoffは3時間ぐらいで終わったが、Tidemanは1日3時間から4時間を5日間かかった。土曜日に始めて水曜日までの5日間。これは作業時間で、起きている間は通勤しているときも、ご飯を食べているときも、お風呂に入っている間も、仕事の会議中でも、とりあえず時間があれば考え続けての5日間です。本当に本当に大変だった。何とか終わってホッとしている。
ネットで「Tideman hard」とかを調べると、いろいろな掲示板で苦しんでいる人の書き込みを見つけられる。お互いに励ましあっていたり、問題が難しすぎると文句を言う人がいたりと反応は様々。ハーバード大学のオンラインショップで「I finished Tideman」というTシャツを売っているぐらい、難しいと有名なある意味名物課題なんだろう。
解き方としては、6個のプログラムを順番に作成していくもので、一つ一つが結構複雑で時間がかかる。それでも一つを除いてはまあ何とかなる。問題は「再帰(recursion)」を使うことにある「lock_pairs」というプログラム。再帰という概念自体が難しいし、選挙システムもややこしい。ここでかなり時間をつかった。
自分はここの部分を考えるのにExcelでマトリックス表を作って、場合分けをしながら、別のファイルにこのプログラムだけを抜き出して、それが想定通りに動くかを1行1行確認していった。再帰の概念を理解するのに「Merge sort」を実装してみたりもした。急がば回れで、こういったちょっと余計な手間をかけるのがよかったのだろうと思う。あと、debug50の使い方を習熟してからこの箇所に臨むと結果的に時間節約になるかな。
lock_pairsをどう考えればいいかはネタバレになるので書かないけれど、あらかじめ準備されているlockedという二次元配列を使うのがポイントになるかな。Candidateが3人とか4人の場合を想定して、Excelに表を作ってコードに合わせて記入をしていくことで自分のコードをよく理解できると思う。
check50を使ってチェックをかけてしまうのもよいと思う。プログラム単体でチェックしてくれるようなので、6つのプログラムそれぞれをつくり終わる都度チェックをかけていけば確実に進んでいるのを実感できるし、精神的な支えになるはず。
Tidemanのアルゴリズム自体がよくわからなければ「シュルツ方式」で検索をかけるとWikipediaで同じような投票方式の説明がある。このサイトは課題を終えた後に見たのであまり詳しく確認していないけど、なんとなくなじみのある矢印とか、「コンドルセ方式」という言葉があるので、参考になるんじゃないだろうか。
混乱をしたのはStrength of Victoryの考え方で、サイトにある説明とBrianの説明、check50の表示が少し違う気がする。サイトにある説明は明確なのだけど、Brianとcheck50ではMargin
of strengthという言葉が使われていて、これだと2つの候補者の得票数の差を計算することになるのだけど、結果がかわってくるんじゃないだろうか。
あと、lock_pairsで票の順番によって結果が変わってくることがある気がする。英語のサイトでこれはTidemanアルゴリズムのバグのようなものなので気にしなくていいとあったけど、少しもやもやする。
細かいところではWalkthroughビデオのBrianはティーダマンと言っているが、英語の発音の法則からはタイドマンが本来は近いのではないかという疑問はある。
気になるところはありつつもようやく終わってよかった。5日間の苦労が報われた。記念に「I finished Tideman」Tシャツを買ってもいいかなと思うぐらいには頑張ったと思う。
ちなみにハーバード大学のオンラインショップにはCS50の特設ページがあってDDB（Duck DeBugger）が売っている。講義の中でDavidの前にずっと置いてあるやつ。これは欲しいなあ。
全ての項目にパス！記念スクショ