impl/typescript.ts

import { type TimetableClash, type TimetableSession } from "./education_timetable_clash_types.ts";

function shared(a: readonly string[], b: readonly string[]): string[] {
  const out: string[] = [];
  for (const x of a) {
    if (b.includes(x) && !out.includes(x)) out.push(x);
  }
  return out;
}

/**
 * Every pair of sessions that overlap on the same day and share a room,
 * teacher or group. Times are half-open: a session ending at 600 does not
 * clash with one starting at 600.
 */
export function timetableClashes(sessions: readonly TimetableSession[]): readonly TimetableClash[] {
  const ids = new Set<string>();
  for (const s of sessions) {
    if (ids.has(s.id)) throw new RangeError(`session id "${s.id}" appears twice`);
    ids.add(s.id);
    if (!Number.isInteger(s.day) || s.day < 1) {
      throw new RangeError(`day must be a whole number of 1 or more, received ${s.day} for "${s.id}"`);
    }
    if (!Number.isInteger(s.start) || s.start < 0 || s.start > 1439) {
      throw new RangeError(`start must be a whole minute from 0 to 1439, received ${s.start} for "${s.id}"`);
    }
    if (!Number.isInteger(s.end) || s.end <= s.start || s.end > 1440) {
      throw new RangeError(`end must be a whole minute after start and no later than 1440, received ${s.end} for "${s.id}"`);
    }
  }
  const found: { clash: TimetableClash; i: number; j: number }[] = [];
  for (let i = 0; i < sessions.length; i++) {
    for (let j = i + 1; j < sessions.length; j++) {
      const a = sessions[i];
      const b = sessions[j];
      if (a.day !== b.day) continue;
      const start = Math.max(a.start, b.start);
      const end = Math.min(a.end, b.end);
      if (start >= end) continue;
      const rooms = shared(a.rooms, b.rooms);
      const teachers = shared(a.teachers, b.teachers);
      const groups = shared(a.groups, b.groups);
      if (rooms.length + teachers.length + groups.length === 0) continue;
      found.push({ clash: { first: a.id, second: b.id, day: a.day, start, end, rooms, teachers, groups }, i, j });
    }
  }
  found.sort((x, y) => x.clash.day - y.clash.day || x.clash.start - y.clash.start || x.i - y.i || x.j - y.j);
  return found.map((f) => f.clash);
}