As usual, Selina is having tummy troubles. Maybe she ate dairy despite having an intolerance1. Or maybe she ran around the lake despite not having eaten2. Or maybe she is stressed out because the instructor hasn't written that sixteenth letter of recommendation yet3. Or maybe she simply just ate at the dining hall4. Either way, her stomach is not happy and she needs to find some medicine to calm it down.

Unfortunately, Selina takes a lot of medication. Like, a lot. Perhaps too many. In fact, her backpack is a portable pharmacy5... a mini St. Liam's. Because she has so many medicine bottles, she decides to organize them according to the following rules.

  1. Each bottle has three attributes: medication name, bottle size, and pill type.

    • size: can be small, medium, or large
    • type: can be gel or tablet

  2. She wants to group all the bottles of the same type together with gel pills coming before tablet pills.

  3. Within each type she wants to arrange the bottles in ascending order alphabetically by medication name.

  4. If any of the bottles have the same medication name, then she wants to order them by in ascending order according to size (i.e. small, medium, then large).

Of course, she is too busy girlbossing to actually do the organization herself. Instead, she wants you to do the work for her so she can go socialize, take care of ducks, or play with Indy.

Input

You will be given a series of input test cases, in a stream, each representing a collection of bottles you need to arrange according to the rules described above.

Each input test case will consist of two parts. The first line is an integer n which denotes how many bottles there are in the collection. This is then followed by a series of n bottles in the following format:

MEDICATION_NAME BOTTLE_SIZE PILL_TYPE

Here is an example input:

10
Omeprazole large gel
Metoprolol small gel
Clopidogrel medium tablet
Clopidogrel large tablet
Oxycodone large gel
Clopidogrel small tablet
Furosemide large tablet
Clonidine large tablet
Simvastatin medium tablet
Amoxicillin medium tablet

Note: As described above, each bottle can be one of three sizes: small, medium, or large. Likewise, each bottle can be one of two types: gel or tablet.

Output

For each input test case, you are to order the bottles as described above and then display a silhouette of the bottles in the cabinet in the ordered arranged.

For each bottle size, use the following letter to represent the bottle based on its size in the silhouette:

small .
medium :
large |

Here is the output for the example input above:

.||:|.:||:

Arranging the input of bottles by the rules described above, would give the following sequence of bottles:

Medication Size Type Letter
Metoprolol small gel .
Omeprazole large gel |
Oxycodone large gel |
Amoxicillin medium tablet :
Clonidine large tablet |
Clopidogrel small tablet .
Clopidogrel medium tablet :
Clopidogrel large tablet |
Furosemide large tablet |
Simvastatin medium tablet :

As can be seen, the bottles are arranged by pill type, then alphabetically medication name, and then by bottle size.

Once arranged properly, simply combine all the letters corresponding to the bottle sizes into a single line to form the silhouette and print that out.

Algorithmic Complexity

For each input test case, your solution should have the following targets:

Time Complexity O(Nlog(N)), where N is the number of bottles for each input test case.
Space Complexity O(N), where N is the number of bottles for each input test case.

Your solution may be below the targets, but it should not exceed them.

Submission

To submit your work, follow the same procedure you used for [Reading 02]:

$ cd path/to/cse-30872-fa23-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 challenge04               # Create and checkout challenge05 branch

$ $EDITOR challenge04/program.cpp           # Edit your code

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

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

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

$ .scripts/check.py
Checking challenge04 program.cpp ...
  Result Success
    Time 0.62
   Score 6.00 / 6.00

$ curl -F source=@challenge04/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa23/challenge04
{"result": "Success", "score": 6, "time": 0.6157994270324707, "value": 6, "status": 0}

Pull Request

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the teaching assistant.


  1. Me too :| 

  2. Negative feedback loop. 

  3. Never again. 

  4. True story. 

  5. Just Kidding. Maybe. Not really.