作成サイト: http://timetable.torimari.site:8080/
コード: https://github.com/moririn2528/timetable

背景

学校の先生は急な出張が入ることがあります。その出張と授業が被っていたとき、その授業を時間割変更する必要があります。この時間割変更を自動的に行うアプリがこちらです。
これはある学校においてかなり難しいことです。その理由は以下の 2 つです。

クラス分けが複雑であること。
ある高校の 3 年 A 組の授業は、数学の授業は A 組と I 組合同、英語は A 組、国語は 2 次試験に必要かどうかで分かれ A 組と I 組合同、理科は物理か生物どちらを取るかで分かれて A 組と I 組合同、社会は地理、日本史、世界史、倫理政経どれを取るかで分かれて A,B,C 組合同という風にかなり複雑です。
研究日、非常勤講師など、授業できない時間帯が多いこと。
ある高校では、非常勤講師が 1/3 くらいいます。また、常勤講師においても週 1 で研究日があり、その日は休みです。さらに、出張日など授業できない時間帯がもともと存在します。

これらの理由によって、外注しても断られる状態であったと聞いています。ほとんどの人ができないようなことをやりたいと思っている私からしたらとてもやりがいのある製作だと感じ、挑戦することにしました。

技術選定

バックエンド

時間割変更において、計算量が結構大きくなると推定されるため、実行速度が速い言語がよいです。今まで使ってきた言語、学習コストも考慮して Go 言語を使うことにしました。
構造はクリーンアーキテクチャのように作成、長く使うことを考えて標準ライブラリ以外を極力使わないようにしました。
時間割などデータを蓄積する必要があるためデータベース、mysql を用いました。

フロントエンド

型がついている方が好きなため、typescript を用います。また、時間割部分は生徒にも利用してほしく、その際に ios, android アプリ化するため、React を用いました。

アルゴリズム

クラスの包含関係をグラフ化します。ある高校の高 3 のクラスすべてをグラフ化した図が以下です。¹

時間割変更するクラス自身とそのクラスの祖先に対して、そのクラスで時間割をまとめられるかどうかを判定し、まとめられるもので動かして変更できるかを考えます。あるコマ、そのクラスでまとめられる、というのは、そのクラスに対応する生徒は、そのクラスの子孫となるクラスの授業を受けているコマのことを指しています。動かして変更できるかどうかは、ダイクストラを用います。動かすルートは最後の辺を除けばパスになるという性質から使うことができます。また、状態は、現在のパスの最後となるコマとパスの長さとして実装します。パスの長さを状態として含める理由は、動かすコマ数はクラス構造のためある程度(10 個以内くらい) は許せるが、それ以上は許さないようにしたいため、動かすコマ数に対して追加するコストを変えるためです。
このとき、最初から 1 人の先生が同じコマで 1 つのクラスの授業を持つという制約を付けていると 1 割ほどが時間割変更できなくなります。ですので、最初この制約を緩和してコストに入れ、複数クラス持ってしまう先生がいた場合、最初から時間割として入っていた方のクラスを上記制約を入れた時間割変更をするという仕組みにしています。