Challenge 18: Anna's Prerequisites

Anna has made a mistake and she knows it. She really knows it. Instead of listening to her heart and being an English major¹, where she could study everything, and do anything, she decided to do the practical thing and grind through Computer Science and Engineering (with a brief detour through Chemical Engineering²).

Don't get her wrong. She does enjoy coding, learning about how technology works, and solving programming challenges, but... she just would much rather read books³ or write stories. In her mind:

Computer Science and Engineering are interesting, but reading and writing are fun.

Anyway, while reflecting on this mistake during her Epic internship, she decides she just has to see her degree to completion and resolves to make the most of her remaining time left in the program. The only real issue left, of course, is getting into the few interesting and fun classes in the Computer Science and Engineering curriculum.

To help students figure out what courses they can take and when they can take them, the Computer Science and Engineering department provides the following DAG for navigating the number of courses the department offers:

Looking at all the boxes and arrows in the DAG... low-key makes Anna a bit nauseous and kind of crabby. She just wants to know:

Given any course, what are the prerequisites to that course and the order in which she should take them.

For instance, given the ever popular Compilers, she should take the following courses:

Discrete Math
Fundamentals of Computing
Data Structures
Systems Programming

Unfortunately, Anna is a bit busy with her Epic internship and grading your assignments, so she asks that you write a program that reads in a series of courses dependencies and then answers a series of queries about what the prerequisites for each course are as explained below.

Input¶

The input will consist of multiple course dependencies and queries.

For each input test case, you will first be given a series of course dependencies in the following format:

N     # Number of courses
course1: prerequisite1 prerequisite2
course2: prerequisite1 prerequisite2
...

After the course dependencies are listed, you will then get a series of course queries in the following format:

N     # Number of queries
course1
course2
...

Example Input¶

Here is an example of a single test case with course dependencies and queries:

11
ld: fc
sp: fc
ds: dm fc
dic: ld
ca: ld
vlsi: dic ca
pp: sp ds
os: sp ds
tc: ds
cp: tc
al: tc
3
os
vlsi
cp

Output¶

For each input test case, you are to read in the course dependencies, and then process each course query by determining what is the order of the prerequisite courses a student needs to take for the given course:

• Order courses by level or height in the DAG (ie. Logic Design, Data Structures, and Systems Programming are all on the same level).

• Order courses within a level alphabetically (ie. Data Structures comes before Logic Design, which comes before Systems Programming).

For each query, output the prequisites in the following format:

{course}: {prequisite1} {prerequisite2}...

Example Output¶

Given the example input above, here is the expected output:

os: dm fc ds sp
vlsi: fc ld ca dic
cp: dm fc ds tc

Submission¶

To submit your work, follow the same procedure you used for Reading 01:

$ cd path/to/cse-30872-su23-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge19               # Create and checkout challenge19 branch

$ $EDITOR challenge19/program.py            # Edit your code

$ git add challenge19/program.py            # Stage your changes
$ git commit -m "challenge19: done"         # Commit your changes

$ git push -u origin challenge19            # Send changes to GitHub

To check your code, you can use the .scripts/check.py script or curl:

$ .scripts/check.py
Checking challenge19 program.py ...
  Result Success
    Time 0.03
   Score 6.00 / 6.00

$ curl -F source=@challenge19/program.py https://dredd.h4x0r.space/code/cse-30872-su23/challenge19
{"result": "Success", "score": 6, "time": 0.03165841102600098, "value": 6, "status": 0}