Motivated by solving the ancient mystery you are going to figure out exactly what the fox says from a transcript of a recording of animal sounds from the forest. You are working with a team of scientists who have already figured out what sounds all of the other animals make. Your task is to filter out the known forest sounds to determine once and for all, what does the fox say?

Input

The input consists of one line of forest noises given as a series of words separated by spaces. The next line of input is a number n describing how many known animal sounds there are. The next n lines describe n animal sounds given in the format "[animal name] goes [noise]".

Output

The output consists of two lines, the first is the list of sounds in order uttered by our shy, sly fox. The last line lists the names of any other animals heard in the recording in the order in which they were first heard with no animal repeated (the scientists asked you for this for research purposes). The first line should be formatted "what the fox says: [whatever the fox did say]". The last line should be formatted "also heard: [space separated list of animals also heard in order they were heard]". There should be NO spaces following the last thing the fox says and the last animal name (just a new line character).

Sample Input

Sample Output

toot woof wa ow ow ow pa blub blub pa toot pa blub pa pa ow pow toot
5
dog goes woof
fish goes blub
elephant goes toot
seal goes ow
horse goes neigh

what the fox says: wa pa pa pa pa pa pow
also heard: elephant dog seal fish

Your Task

Your task is to implement two versions of the program solving the code above. The first version (cs412_foxsays_list.py) should only use list data structures. The second version (cs412_foxsays_dict.py) must utilize maps/dictionaries and set data structures to speed up your code as much as possible.

Gradescope is checking for dictionaries to NOT be in the first version and for a dictionary to be in the second version.

Test Cases

Example input/output:

Test #1:

Input file: foxsays_t1_in.txt
Output file: foxsays_t1_exp.txt

Test #2:

Input file: foxsays_t2_in.txt
Output file: foxsays_t2_exp.txt

There is a unittest file that you can download (foxsays_unittest.py) and use to test your program. See the programming guidelines (located here in canvas: CS412_CodingAssignmentGuidelines.pdf) which specifies how to structure your program and also how to use the unittest file.

You can use a diff program to compare your output to these examples before submitting to Gradescope.

Code Templates for this class

Your python code must utilize this template: cs412_code_template.py

Turning it in

Turn in these two files (cs412_foxsays_list.py and cs412_foxsays_dict.py) to Gradescope. Here are some larger test files to see how fast your program runs:

foxsays_tleader_in.txt and foxsays_tleader_exp.txt

Leaderboard/Speed Check

Your code will be checked for speed and a leaderboard posted within Gradescope.

Acknowledgments

Problem from Kattis are used under their educational license.

Lab 3: Empirical Analysis with Profiling

This lab is intended to be started in class, where additional background information may be provided.

Requirements

You will need to use a UNIX based system can run shell scripts. STU would be a good resource.

Goal

Utilize run-time profilers to identify poorly performing sections of a program and then potential these areas.

Process

Part 1

Utilize the two programs from your "What does the Fox Say" homework. Run each of these with the profiling information from the lecture slides (cs412_03_EmpiricalAnalysis.pdf) and gather/analyze this information. For the dict version of the program, identify and try and to improve the portions of your program that take up the most time.

Part 2

Using the large examples files from "What does the Fox Say" homework and the split, wc, and head UNIX commands, create input files of size 200K, 400K, 600K, 800K. To find out more about these UNIX commands, you can use Google or the man pages from stu.

Write a shell script that performs this work and then runs the dict version of your program capturing the execution time using the time UNIX command. Create a plot of this run time where the Y axis is the run time and the X axis is the input size. The shell script only needs to run your work and produce the plots (it does not need to do the file manipulation, you can do that on your own).

An example python script for creating the plot is here: line_plot.py

Deliverables

A PDF (described below)
Python script to create your plot
Shell script to run your test cases

Eclypse's Note: Did not need to submit a Shell script

Create a single PDF that contains the following information with two separate sections (one for your list and one for your dict versions of the HW 1). Each section must showcase the results/output of 2 cProfile runs. Then create a 3rd section within the PDF that discusses the slowest portions of the dict program. This discussion must include steps you tried in order to improve the run time performance of your program.

For the 4th and final section, show the plot of your run times and discuss what type of growth rate is experienced by your program and what portion of the program you believe is responsible for this.