[Neworleans-pm] Fwd: Perl Quiz-of-the-Week #21

[E. Strade, B.D.]

=====
http://www.brettsbsd.net/~estrabd

__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com

----- Original message -----
From: "Mark Jason Dominus" <mjd at plover.com>
To: perl-qotw at plover.com
Date: Thu, 05 Aug 2004 11:44:43 -0400
Subject: Perl Quiz-of-the-Week #21


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.

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.

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.


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

You will write a program to perform scheduling.  As we all
know, tasks sometimes take longer than expected.  Sometimes
when this happens, the final deadline of the project is
affected; sometimes it isn't.  For example, consider the four
tasks A, B, C, and D.  B and C depend on A, which means that
they cannot be started until A is finished. D depends on B and
C, and cannot be started until both B and C are finished:

      .-> B .
    A        :-> D
      `-> C '

Suppose we expect the four tasks to take the following times:

        A: 1 day
        B: 2 days
        C: 3 days
        D: 1 day

Then we don't expect the project to be finished for at least 5
days: one day to complete A and start C; 3 days to complete C
and start D, and another day to finish D.  Any delay in any of
the three tasks A, C, or D will cause the completion date to
slip.  We say that A, C, and D are on the "critical path".
But B is not on the critical path, because B can go on while C
is going on, and can take up to one day longer than expected
without delaying the start of D.

You will write a program which will calculate critical paths.  The
input to the program will be a file in the following format:

        A 1
        B 2 A
        C 3 A
        D 1 B C
        FINAL 0 D

Each line represents one task.  The first field in each line
is the name of the task.  The second field is the expected
duration.  If there are any other fields, they are the names
of other tasks which must be finished before this task can
start.

The program will find all the tasks on the critical path to
the task named FINAL and will print them out, one per line.

It may happen that the input specifies tasks that cannot possibly be
completed.  For example:

        A 1 B
        B 1 A
        FINAL 0 A B

Here A can't start until B is finished, but B can't start until A is
finished.  In such cases, the program should diagnose an error.

[ ADMINISTRATIVE NOTE: Last week's expert quiz turned out to be more
  subtle than it first appeared.  The report and sample solution will
  be along when it is ready.  Thanks for your patience.  -MJD ]