Wettbewerb: Parallele Anrufe

Fr, 4. Februar 2022, Ralf Hersel

Wir hatten lange kein Gewinnspiel mehr, bei dem eine Programmieraufgabe gelöst werden sollte. Nun ist es wieder so weit. Zu gewinnen gibt es eine PineTime Smartwatch, für die oder denjenigen, der den elegantesten Algorithmus für das 'Problem der parallelen Anrufe' abliefert. Dabei geht es um eine praktische Fragestellung, die in meinem beruflichen Umfeld entstanden ist.

Stellt euch vor, ihr arbeitet in einer Organisation mit vielen Mitarbeitenden, und habt eine zentrale Telefonanlage. Wie es bei vielen Providern üblich ist, hängen eure Telefonkosten von der Anzahl der parallel geführten Gespräche ab; ihr bezahlt die Anzahl der Kanäle (siehe auch SIP-Trunk). Daher lautet die Aufgabe dieses Wettbewerbs, herauszufinden, wie viele parallele Gespräche während eines Zeitraums geführt wurden. Dann wisst ihr nämlich, wie viele Kanäle ihr buchen müsst.

Als Input liefert eure Telefonzentrale eine Liste mit allen Gesprächen, die während eines Monats geführt wurden. Dabei handelt es sich um eine grosse Menge; im Beispiel sind es 1451 Gespräche. Die Liste enthält Datum und Uhrzeit wann ein Gespräch begonnen wurde und die Dauer des Gesprächs. Hier ein Beispiel:

06.09.2021 12:32:44, 00:00:43
06.09.2021 12:35:48, 00:00:30
06.09.2021 15:15:39, 00:00:36

Die Anfangszeiten sind vollständige Datum/Zeit-Angaben, die Dauer besteht nur aus der Zeit-Angabe ohne Datum. Aus der langen Liste sollt ihr herausfinden, wie viele parallele Gespräche mit welcher Häufigkeit geführt wurden. Damit wir vergleichbare Ergebnisse erhalten, stellen wir euch eine CSV-Datei mit Gesprächsdaten zur Verfügung. Die Auswertung kann beispielsweise so aussehen:

Parallele Gespräche
        20
        19
        17
        10

In diesem Beispiel kam es einmal vor, dass maximal 20 parallele Gespräche geführt wurden.

Hier findet ihr den Link zur CSV-Datei mit den Input-Daten.

Da das Problem schwieriger ist, als es aussieht, gebe ich euch ein paar Tipps für die Lösung:

  1. Erstellt eine Zeichnung oder ein einfaches Beispiel in einer Tabellenkalkulation, in der ihr die Anrufe untereinander auf einem Zeitstrahl darstellt.
  2. Legt euch nicht frühzeitig auf einen Lösungsansatz fest, sondern betrachtet das Problem aus verschiedenen Perspektiven.
  3. Überprüft euren Algorithmus anhand des einfachen Beispiels aus eurer Skizze oder Tabellenkalkulation.

Skizze zur Unterstützung bei der Lösungssuche

Ein mögliches Ergebnis für die Anzahl paralleler Gespräche lautet: 20, 19, 17, 10, 5, ... Die Anzahl der parallelen Gespräche im unteren Bereich könnt ihr euch sparen, weil es uninteressant ist, dass 300 Leute mit einer Parallelität von 1 oder 2 telefoniert haben. Die hohen Zahlen sind spannend, weil diese die zu buchenden Kanäle bestimmen.

Falls irgendetwas an der Aufgabenstellung unklar ist, könnt ihr mich gerne fragen.

Vorschläge für eine Lösung können als Shell-Skript oder Python-Programm eingereicht werden. Bitte schickt euren Code an die E-Mail-Adresse kontakt@gnulinux.ch. Es wäre hilfreich, wenn ihr euren Ansatz erklärt, damit unsere Leser:innen ihn auch verstehen können. Teilnehmen können alle, ausser Mitglieder der CORE-Gruppe. Einsendeschluss für Lösungen ist der 28. Februar 2022. Danach werden wir die Vorschläge auf Funktionsfähigkeit und korrekte Ergebnisse testen und anschliessend den oder die Gewinnerin auslosen.