Perl 'Expert' Quiz-of-the-Week #16

IMPORTANT: Please do not post solutions, hints, or other spoilers
        until at least 60 hours after the date of this message.
        Thanks.

IMPORTANTE: Por favor, no enviéis soluciones, pistas, o cualquier otra
        cosa que pueda echar a perder la resolución del problema hasta
        que hayan pasado por lo menos 60 horas desde el envío de este
        mensaje. Gracias.

IMPORTANT: S'il vous plaît, attendez au minimum 60 heures après la
        date de ce message avant de poster solutions, indices ou autres
        révélations. Merci.

WICHTIG: Bitte schicken Sie keine Lösungen, Tipps oder Hinweise für
        diese Aufgabe vor Ablauf von 60 Stunden nach dem Datum dieser
        Mail. Danke.

BELANGRIJK: Stuur aub geen oplossingen, hints of andere tips in de
        eerste 60 uur na het verzendingstijdstip van dit
        bericht. Waarvoor dank.

VNIMANIE: Pozhalujsta ne shlite reshenija, nameki na reshenija, i
        voobshe lyubye podskazki v techenie po krajnej mere 60 chasov
        ot daty etogo soobshenija.  Spasibo.

Qing3 Zhu4Yi4: Qing3 Ning2 Deng3Dao4 Jie1Dao4 Ben3 Xin4Xi2 Zhi1Hou4 60
        Xiao3Shi2, Zai4 Fa1Biao3 Jie3Da2, Ti2Shi4, Huo4 Qi2Ta1 Hui4
        Xie4Lou4 Da2An4 De5 Jian4Yi4.  Xie4Xie4.


----------------------------------------------------------------

Today's quiz and next Monday's solution come courtesy of Pr. Shlomi Fish.
Thank you, Shlomi!


        You will write a program that schedules the semester of courses at
        Haifa University.  @courses is an array of course names, such as
        "Advanced Basket Weaving".  @slots is an array of time slots at which
        times can be scheduled, such as "Monday mornings" or "Tuesdays and
        Thursdays from 1:00 to 2:30".  (Time slots are guaranteed not to
        overlap.)

        You are also given a schedule which says when each course meets.
        $schedule[$n][$m] is true if course $n meets during time slot $m, 
        and false if not.

        Your job is to write a function, 'allocate_minimal_rooms', to allocate
        classrooms to courses.  Each course must occupy the same room during
        every one of its time slots.  Two courses cannot occupy the same room
        at the same time.  Your function should produce a schedule which
        allocates as few rooms as possible.

        The 'allocate_minimal_rooms' function will get three arguments:

          1. The number of courses
          2. The number of different time slots
          3. A reference to the @schedule array

        It should return a reference to an array, say $room, that
        indicates the schedule.  $room->[$n] will be the number of the
        room in which course $n will meet during all of its time
        slots.  If courses $n and $m meet at the same time, then
        $room->[$n] must be different from $room->[$m], because the
        two courses cannot use the same room at the same time.

        For example, suppose:

            Time slots
            0  1  2  3  4

  Courses        
        0   X  X                (Advanced basket weaving)
        1      X  X     X       (Applied hermeneutics of quantum gravity)
        2   X        X          (Introduction to data structures)


        The @schedule array for this example would contain

        ([1, 1, 0, 0, 0], 
         [0, 1, 1, 0, 1],
         [1, 0, 0, 1, 0],
        )

        'allocate_minimal_rooms' would be called with:

                allocate_minimal_rooms(3, 5, \@schedule)

        and might return

        [0, 1, 1]

        indicating that basket weaving gets room 0, and that applied
        hermeneutics and data structures can share room 1, since they
        never meet at the same time.

        [1, 0, 0]

        would also be an acceptable solution, of course.