Lab 08: Return of the Cow Overview This lab’s purpose is to provide students with experience in file I/O and C++ exceptions. It is recommended that students use command line tools and editors for this lab (though it is not strictly speaking required). This lab will require students to build on their previous lab experience, in which a version of the cowsay utility was created. Students will need to look up the constructors for some C++ standard objects, such as exceptions, in the C++ documentation to complete this lab. Note that you will need to set the language version to C++17 in your CMakeLists.txt file for this project.SpecificationCowsay Class (Program Driver) Your program must accept command line arguments as follows:cowsay -l Lists the available cows cowsay MESSAGE Prints out the MESSAGE using the default cow cowsay -n COW MESSAGE Prints out the MESSAGE using the specified built-in COW cowsay -f COW MESSAGE Prints out the MESSAGE using the specified file COWNote that this version of the utility handles a special set of Cow-derived FileCow objects. The HeiferGenerator will automatically create FileCow objects (using the FileCow constructor) from files in the “cows” directory. >cowsay -l Regular cows available: heifer kitteh dragon ice-dragon File cows available: moose turkey turtle tuxPrevious Work The following classes, developed previously, are required for this lab to function.Cow public Cow(const string& _name) // Constructor public string& getName() // Returns name of this cow object public string& getImage() // Return image for this cow object public virtual void setImage(const string& _image) // Sets image for this cow objectDragon (extends Cow) public Dragon(const string& _name, const string& _image) // Constructor public bool canBreatheFire() // Defaults to true IceDragon (extends Dragon) public Dragon(const string& _name, const string& _image) // Constructor public bool canBreatheFire() // Returns falseFileCow Class The FileCow class must be derived from the Cow class. In addition, FileCow must add the following behavior:public FileCow(const string& _name, const string& filename)Constructor; creates a new FileCow object with the given name and an image loaded from filename. If the file cannot be loaded, it should throw a new std::ifstream::failure exception object with the message “MOOOOO!!!!!!”. This should be the only public constructor for the FileCow class!public void setImage()Should throw a new std::runtime_error exception object with message “Cannot reset FileCow Image”.Submissions NOTE: Your output must match the example output *exactly*. If it does not, you will not receive full credit for your submission!Files: rotc.zip Method: Submit on CanvasCompressed Archive (rotc.zip)Your compressed file should have the following directory/file structure:rotc.zip rotc (directory) CMakeLists.txt Cow.h Dragon.h FileCow.h IceDragon.h (Other sources / folders)Sample Output>javac Cowsay.java >java Cowsay Hello World! Hello World! ^__^ (oo)_______ (__) )/ ||—-w | || ||>java Cowsay -n kitteh Moew-Moew! Moew-Moew! (“`-‘ ‘-/”) .___..–‘ ‘ “`-._ ` *_ * ) `-. ( ) .`-.__. `) (_Y_.) ‘ ._ ) `._` ; `` -. .-‘ _.. `–‘_..-_/ /–‘ _ .’ ,4 ( i l ),-” ( l i),’ ( ( ! .-‘>java Cowsay -l Regular cows available: heifer kitteh dragon ice-dragon File cows available: moose turkey turtle tux >java Cowsay -n ninja Hello world! Could not find ninja cow! >java Cowsay -f tux Do you have any herring? Do you have any herring? .–. |o_o | |:_/ | // (| | ) /’_ _/` ___)=(___/ >java Cowsay -f alien Earth is ours! Could not find alien cow! >java Cowsay -f kitteh MEOW!!! Could not find kitteh cow!>java Cowsay -n tux How about tuna? Could not find tux cow!
Lab 06: Image ScalingOverview Requirements The program should be driven classless main function and Image class.Standalone Functions (scaler.cpp)int main() When the program is run via the main() method, the program should:1) Fetch ConsoleGfx singleton via ConsoleGfx.getInstance() 2) Display the welcome message 3) Display color test (ConsoleGfx.testRainbow) 4) Display the menu 5) Prompt for inputLoad File Load file via unsigned char *ConsoleGfx.loadFile(string file). Note that loadFile() allocates an array for the file data, but the caller is responsible to deallocation. Success (File was Loaded) Failure (File wasn’t Loaded)Select a Menu Option: 1 Enter name of file to load: logos/uga.gfx File loaded.Scaler Menu ———–Select a Menu Option: 1 Enter name of file to load: foo.png Error: could not load file.Scaler Menu ———–Load Test Image Show Image Properties Loads ConsoleGfx.testImage: Displays the length and width of the current image.Select a Menu Option: 2 Test image data loaded.Scaler Menu ———–Select a Menu Option: 6 Image Dimensions: (14, 6)Scaler Menu ———–Display Image Displays current image by invoking ConsoleGfx.displayImage(unsigned char *imageData) method.Success (Previously Loaded) Failure (No Image Loaded)Enlarge / Shrink Image Prompts the user for orders of magnitude to change (powers of two), then enlarges the image. Select a Menu Option: 4 Select a Menu Option: 5 Enter orders of magnitude for enlargement: 3 Enter orders of magnitude for reduction: 3 Image enlarged! Image reduced!Scaler Menu _Scaler Menu ———– ———–unsigned char *scaledImage(unsigned char *imageData, int orders) Returns a scaled version of the image data based on the orders of magnitude (i.e., powers of two to scale). The number of orders of magnitude should be in the range [-4, 4] (inclusive), which allows scaling down to 1/16 or up by a factor of 16 in each dimension. Do no implement this via recursive or iterative doubling; this takes twice as long as creating a new image one time, and it causes memory fragmentation.This function should never scale any image above 256 in width or height; instead, it should limit scaling such that the image is scaled up by a power of two but remains less than or equal to 256 in each dimension. Likewise, no image should be scaled below a height or width of one. To determine the color for reduced images, the number of colors of each pixel should be counted, and the most common color should be used. If there is a tie, the earliest pixel (by row, then by column) should be used. This function should allocate memory and return it to the caller; the caller is responsible for deallocation.Image Class The Image class will the image data and should be constructed from the raw data.The class must also have the following methods and behaviors (this is mandatory):public Image(unsigned char *imageData) This method should be the only constructor for this class. There should not be a default constructor! Its sole argument is a pointer to an array of raw image data as loaded from the file. The data is formatted as follows:public unsigned char *getImageData() Returns a pointer to the raw image data (not a copy).public unsigned char *getPixelData() Returns a pointer to the raw pixel data (excluding the image property information). Should not be a copy.public unsigned char getWidth() Returns the width of the image.public unsigned char getHeight() Returns the height of the image.public void setImageData(unsigned char *newData) Changes the image data to the new pointer.Building and Testing For this project, students will begin to learn more details about the practical building and testing of C++ programs, including accessing executables built by the compiler from outside of the IDE.Building CLion uses the standardized CMake build system, which is supported across multiple platforms and IDEs (including CLion and Visual Studio) and supports many compilers (GCC, Clang, and MS Visual C.) When you create a CLion project, it will create CMakeLists.txt. The CMakeLists.txt file for this lab might look like this: cmake_minimum_required(VERSION 3.20) project(scaler) C++ versionset(CMAKE_CXX_STANDARD 14) Executable name add_executable(scaler ConsoleGfx.cpp scaler.cpp) Source filesYou should make sure that the CMakelists.txt file correctly lists your source files and the executable. Then, click on the “Build” button (), which is on the toolbar to the left of the “Run” ( ) and “Debug” () buttons.TestingTo open Explorer , open the build folder (e.g, cmake-build-debug), right-click on scaler.exe, and select Open In Explorer. Then, right click in Explorer and select “Open in Windows Terminal”. Once the terminal window is open, you can run your program by typing the executable’s name (e.g., scaler):Submissions NOTE: Your output must match the example output *exactly*. If it does not, you will not receive full credit for your submission!Files: scaler.cpp, Image.cpp, Image.h Method: Submit on ZyLabs
Lab 07: The Cow Strikes BackOverview This lab’s purpose is to provide students with experience in inheritance of classes and working with multiple classes. It is recommended that students use command line tools and editors for this lab (though it is not strictly speaking required). This lab will require students to build on their previous lab experience, in which a version of the cowsay utility was created; however, this lab will be written in C++. Note that you will need to set the language version to C++17 in your CMakeLists.txt file for this project.SpecificationExecutable Specification Your program must accept command line arguments as follows:cowsay ‐l Lists the available cows cowsay MESSAGE Prints out the MESSAGE using the default cow cowsay ‐n COW MESSAGE Prints out the MESSAGE using the specified COWIn addition, this version of the utility handles a special set of Cow-derived Dragon classes (and its subclasses). Whenever a dragon-type cow is selected, the display of the message must be followed by a line stating whether or not the dragon is fire-breathing: finn@BMO:~$ ./cowsay ‐n dragon Fiery RAWR Fiery RAWR |___/| / //|\ /0 0 __ / // | / / /_ / // | _^_’/ /_ // | //_^_/ /_ // | ( //) | // | ( / /) _|_ / ) // | _ ( // /) ‘/,_ _ _/ ( ; ‐. | _ _.‐~ .‐~~~^‐. (( / / )) ,‐{ _ `.|.‐~‐. .~ `. (( // / )) ‘/ / ~‐. _.‐~ .‐~^‐. (( /// )) `. { } / (( / )) .‐‐‐‐~‐. ‐’ .~ `. __ ///.‐‐‐‐..> _ ‐~ `. ^‐` ///‐._ _ _ _ _ _ _}^ ‐ ‐ ‐ ‐ ~ `‐‐‐‐‐’ This dragon can breathe fire. finn@BMO:~$ cowsay ‐n ice‐dragon Ice‐cold RAWR Ice‐cold RAWR |___/| / //|\ /0 0 __ / // | / / /_ / // | _^_’/ /_ // | //_^_/ /_ // | ( //) | // | ( / /) _|_ / ) // | _ ( // /) ‘/,_ _ _/ ( ; ‐. | _ _.‐~ (( / / )) ,‐{ _ `.|.‐~‐. (( // / )) ‘/ / ~‐. _.‐~ (( /// )) `. { } (( / )) .‐‐‐‐~‐. ‐’ ///.‐‐‐‐..> _ ///‐._ _ _ _ _ _ _}^ ‐ ‐ ‐ ‐ ~This dragon cannot breathe fire. Cow Classpublic Cow(const string& _name) // Constructor public string& getName() // Returns name of this cow object public string& getImage() // Return image for this cow object public virtual void setImage(const string& _image) // Sets image for this cow objectDragon Class public Dragon(const string& _name, const string& _image) Constructor; creates new Dragon object with given name and image. This must be its only public constructor!public bool canBreatheFire() This method should exist in every Dragon class. For the default Dragon type, it should always return true.IceDragon Class The IceDragon class must be derived from the Dragon class and must make all its methods available: public IceDragon(const string& _name, const string& _image) Constructor; creates a new IceDragon object with the given name and image. This should be the only public constructor for the IceDragon class!public bool canBreatheFire() For the IceDragon type, this method should always return false.HeiferGenerator Class (Provided)public static vector& getCows() Returns a reference to a vector of cow object pointers from built-in data set. This will call the Cow constructor and setImage() methods of the cow class if needed to initialize new cow objects uniquely for each data set.public static Dragon* getDragonPointer(Cow* candidate) If object pointed to by candidate is a Dragon (including an IceDragon), returns a Dragon pointer to the object. Otherwise, returns nullptr.Submissions NOTE: Your output must match the example output *exactly*. If it does not, you will not receive full credit for your submission! (Note that matching sample output is necessary, but not sufficient, for full credit.)Files: cowsay.cpp, Cow.cpp, Cow.h, Dragon.cpp, Dragon.h, IceDragon.cpp, IceDragon.h, CMakeLists.txt Method: Submit on CanvasSample Output finn@BMO:~$ ./cowsay finn@BMO:~$ ./cowsay Hello World!Hello World! ^__^ (oo)_______ (__) )/ ||‐‐‐‐w | || ||finn@BMO:~$ ./cowsay ‐n kitteh Meow‐Meow!Meow‐Meow! (“`‐’ ‘‐/”) .___..‐‐’ ‘ “`‐._ ` *_ * ) `‐. ( ) .`‐.__. `) (_Y_.) ‘ ._ ) `._` ; `` ‐. .‐’ _.. `‐‐’_..‐_/ /‐‐’ _ .’ ,4 ( i l ),‐” ( l i),’ ( ( ! .‐’finn@BMO:~$ ./cowsay ‐n ninja Hello world! Could not find ninja cow! finn@BMO:~$ ./cowsay ‐l Cows available: heifer kitteh dragon ice‐dragonfinn@BMO:~$ ./cowsay ‐n dragon Firey RAWRFiery RAWR |___/| / //|\ /0 0 __ / // | / / /_ / // | _^_’/ /_ // | //_^_/ /_ // | ( //) | // | ( / /) _|_ / ) // | _ ( // /) ‘/,_ _ _/ ( ; ‐. | _ _.‐~ .‐~~~^‐. (( / / )) ,‐{ _ `.|.‐~‐. .~ `. (( // / )) ‘/ / ~‐. _.‐~ .‐~^‐. (( /// )) `. { } / (( / )) .‐‐‐‐~‐. ‐’ .~ `. __ ///.‐‐‐‐..> _ ‐~ `. ^‐` ///‐._ _ _ _ _ _ _}^ ‐ ‐ ‐ ‐ ~ `‐‐‐‐‐’This dragon can breathe fire. finn@BMO:~$ ./cowsay ‐n ice‐dragon Ice‐cold RAWRIce‐cold RAWR |___/| / //|\ /0 0 __ / // | / / /_ / // | _^_’/ /_ // | //_^_/ /_ // | ( //) | // | ( / /) _|_ / ) // | _ ( // /) ‘/,_ _ _/ ( ; ‐. | _ _.‐~ .‐~~~^‐. (( / / )) ,‐{ _ `.|.‐~‐. .~ `. (( // / )) ‘/ / ~‐. _.‐~ .‐~^‐. (( /// )) `. { } / (( / )) .‐‐‐‐~‐. ‐’ .~ `. __ ///.‐‐‐‐..> _ ‐~ `. ^‐` ///‐._ _ _ _ _ _ _}^ ‐ ‐ ‐ ‐ ~ `‐‐‐‐‐’This dragon cannot breathe fire.
Lab 05: Software Engineering Overview The objective of this lab is to understand the purpose and usefulness of debugging and version control. Debugging is an essential skill needed to be a successful developer. We will use PyCharm’s built-in debugger. We will also practice functions of version control systems to develop familiarity in them. SpecificationDebugging 1) Open your IDE (PyCharm by default) 2) Open your previous solution (or another lab/project if you didn’t complete the previous lab)Git Practice / Setup 1) Complete these exercises: https://try.github.io/levels/1/challenges/1 2) Create a GitHub educational account: https://education.github.com/pack/join 3) Install Git for your OS if necessary. (You can download Git here: https://git-scm.com/downloads)Optionally, you may also want to install a GUI client for Git and a windowed merge tool. You can get SourceTree (https://www.sourcetreeapp.com/) and Meld (https://meldmerge.org/) for free. (Directions for using Meld with SourceTree: https://jaehoo.wordpress.com/2018/05/21/source-tree-resolve-conflicts-with-an-external-tool/)Git Tasks 1) Create an empty repository on GitHub and add a README.md (markdown) file. Each student should clone. 2) Individually convert your Java solution from the previous lab (analyzer.py) into C++ (analyzer.cpp). 3) Add and commit your converted solution to the GitHub repository. Each student should attempt to push. 4) The second push should create a merge conflict. You should work together to resolve this, then push.When you convert to C++, you can use the std::chrono::system_clock::now() function to measure times.If you are unfamiliar with the command line and would like to learn it, this guide will help (for Mac, Linux, and Git-Bash on Windows): http://www.ee.surrey.ac.uk/Teaching/Unix/ Submissions
Lab 04: Time Complexity & ProfilingOverview This project is designed to familiarize students with “Big-O” notation through the algorithm analysis. Algorithms have an associated “Big-O” notation that describes how they run according to the input size. This models how fast the number of calculations grows as the size of the input grows larger. Programs with low growth rates are preferred because, no matter the size of the input, the program will handle it in a timely manner. In this lab exercise, students will compare two different search algorithms by timing them reflecting on how their time complexities compare to their runtimes.Specification You will write a main method and two static methods implementing binary and linear search algorithms. The linear search will step through the elements one at a time until the correct element is found; the binary search will operate on a pre-sorted set and use this knowledge to divide the search space in half at each step. Students are recommended to review the algorithms listed in their textbooks, as they are implemented directly.Provided Implementation Students are provided with the stringdata module. It contains a single data element:dataset: tuple(str) This tuple is the complete set of possible lowercase 5 character strings (containing 17,576 entries).Student Implementation Students will implement the analyzer module with a main entry point and two search methods as follows.Entry Point (main) This module will have a main() function which will execute if the module is directly invoked. The main function should complete the following steps, documenting results and answer questions in the write-up: 1) Access the data set from the stringdata module (via the dataset value). 2) Search for “not_here” using both algorithms. Capture the time each method requires to execute. 3) Search for “mzzzz” using both algorithms. Capture the time each method requires to execute. 4) Search for “aaaaa” using both algorithms. Capture the time each method requires to execute.Search Methods linear_search(container: tuple(str), element: str) -> int Uses linear search to find specified element in container. Returns index of element, or -1 if not found.binary_search(container: tuple(str), element: str) -> int Uses binary search to find specified element in container. Returns index of element, or -1 if not found.Timing your Methods To time your methods, use the time() function in Python’s time module – i.e., time.time(). It reports the time in seconds as a floating-point number. 1) Capture the begin time using time.time(). 2) Run the method. 3) Immediately after running, capture the ending time. 4) Subtract the beginning time from the ending time; display it to the screen.NOTE: You should take a screenshot of the results for each run of each method.Report In your report, include the screenshots (mentioned above) for each run of each method, along with the answers to these questions:1) Why is a search for “not_here” the worst-case for linear search and binary search? 2) Why is a search for “mzzzz” the average-case for linear search? 3) Why is a search for “aaaaa” the best-case for linear search? 4) How do the results you saw compare to the Big-O complexity for these algorithms? 5) Why do the binary search results appear so similar, while the linear search results are so divergent?Submissions Files: analyzer.py, Lab04-Report.pdf Method: Submit on Canvas
Lab 02: Find Four GameWelcome to Find Four! ——————— Enter height of board (rows): 4 Enter width of board (columns): 5 _________ |. . . . .| |. . . . .| |. . . . .| |. . . . .| ———Player 1: x Player 2: oPlayer 1 – Select a Column: _ Overview This lab is designed to introduce students to 2D arrays by recreating the game Find Four (brand name “Connect Four”). This will require students to loop through and manipulate sequential data structures.Specification The program should be driven by the findfour module and its functions. When started, the program should display a welcome message, then ask the user for a width and height of the playing board. Once the user has entered the dimensions, the player’s chips should be displayed, followed by the empty board, and the first player should be prompted for a move.Gameplay Players take turns adding chips to the board, which drop to the lowest open row. Once one player achieves four vertical or horizontal chips in a row (not diagonal), that player wins. Play proceeds as follows. Player 1 – Select a Column: 0 _________ Player 1 – Select a Column: 0 |. . . . .| _________ Player 1 – Select a Column: 0 |. . . . .| |x . . . .| _________ |. . . . .| |x . . . .| |x . . . .| |x . o . .| |o x o x o| ——— |x o x o o| |x o o x x| ——— |x o o o x| Player 2 – Select a Column: _ |x o x o x| ——— The first player selects a column, Player 1 won the game! and the new board is displayed. Play continues to alternate until Draw game! Players tied. The next player is prompted. one player wins… …or until there is a draw.Data Storage Elements in the container should be accessible via row-major indexing (board[row][column]). In addition, the data should be stored so that row zero is the bottom of the board, i.e.:Row 3 x . . . . Row 2 x . . . . Row 1 x . o . . Row 0 x o x o oMake sure you test as you complete this assignment; otherwise, the unit tests used for evaluation will fail! Error Handling This assignment requires students to deal with user error and handle malformed input. The number of columns and rows must be in the range [4, 25]. Note: error handlings should be handled during input, and not in the method proscribed to update the board (see Functions section). The program must handle error cases as follows.Invalid Dimensions Welcome to Find Four! ——————— Enter height of board (rows): 1 Error: height must be at least 4! Enter height of board (rows): -1 Error: height must be at least 4! Enter height of board (rows): 42 Error: height can be at most 25! Enter height of board (rows): _ Welcome to Find Four! ——————— Enter height of board (rows): 5 Enter width of board (columns): 9001 Error: width can be at most 25! Enter width of board (columns): 3 Error: width must be at least 4! Enter width of board (columns): wUT Error: not a number! Enter width of board (columns): _Invalid Column Entry Player 2 – Select a Column: 0 _________ | o . . . .| |x . . . .| |x x o . .| |x o x o o| ———Player 1 – Select a Column: 0 Error: column is full! Player 1 – Select a Column: _ Player 2 – Select a Column: 0 _________ |o . . . .| |x . . . .| |x x o . .| |x o x o o| ———Player 1 – Select a Column: 5 Error: no such column! Player 1 – Select a Column: _ Player 2 – Select a Column: 0 _________ |o . . . .| |x . . . .| |x x o . .| |x o x o o| ———Player 1 – Select a Column: fOo Error: not a number! Player 1 – Select a Column: _Required Functions get_initial_board(rows: int, columns: int) -> list[list[str]] Returns a list of size rows, where each entry is itself a list of size columns, where each entry contains the value ‘.’.print_board(board: list[list[str]]) Prints a copy of the board, where board is a list of list objects, each entry a one-character str object.insert_chip(board: list[list[str]], column: int, chip: str) -> int Places a chip in the column of the board of the chip type. This method should find the next available spot in that column, if any. This method returns the row in which the chip settles.is_win_state(chip: str, board: list[list[str]], row: int, column: int) -> bool This method checks if the player represented by specified chip type has won the game by looking on the board at the position (row, column). If this is a win for the player, returns True; otherwise, returns False.is_board_full(board: list[list[str]]) -> bool This method checks if the board is full. If it is full, returns True; otherwise, returns False.Submission NOTE: Output must match example output exactly. Otherwise, your submission will not receive full credit!Files: FindFour.py Method: Submit on ZyLabs Sample OutputWelcome to Find Four! ——————— Enter height of board (rows): 2 Error: height must be at least 4! Enter height of board (rows): 4 Enter width of board (columns): 5 _________ |. . . . .| |. . . . .| |. . . . .| |. . . . .| ———Player 1: x Player 2: oPlayer 1 – Select a Column: `0 Error: not a number! Player 1 – Select a Column: 0 _________ |. . . . .| |. . . . .| |. . . . .| |x . . . .| ———Player 2 – Select a Column: 5 Error: no such column! Player 2 – Select a Column: 3 _________ |. . . . .| |. . . . .| |. . . . .| |x . . o .| ———Player 1 – Select a Column: 0 _________ |. . . . .| |. . . . .| |x . . . .| |x . . o .| ———Player 2 – Select a Column: -1 Error: no such column! Player 2 – Select a Column: 1 _________ |. . . . .| |. . . . .| |x . . . .| |x o . o .| ———Player 1 – Select a Column: 0 _________ |. . . . .| |x . . . .| |x . . . .| |x o . o .| ———Player 2 – Select a Column: 4 _________ |. . . . .| |x . . . .| |x . . . .| |x o . o o| ———Player 1 – Select a Column: 2 _________ |. . . . .| |x . . . .| |x . . . .| |x o x o o| ———Player 2 – Select a Column: 2 _________ |. . . . .| |x . . . .| |x . o . .| |x o x o o| ———Player 1 – Select a Column: 0 _________ |x . . . .| |x . . . .| |x . o . .| |x o x o o| ———Player 1 won the game!Process finished with exit code 0
Lab 03: The Cow Says… Overview This lab is designed to introduce students to the Bash Command Line Interface (CLI) and the concept of CLI arguments and give them practice writing classes. For (only) this lab, you are not allowed to use any windowed editor (such as IntelliJ, Eclipse, or Notepad++). Instead, you will use a Unix-based command line editor.The cowsay utility is a popular Unix program from the 20th century (see https://en.wikipedia.org/wiki/Cowsay). You will write a slightly simplified cowsay program that takes in several arguments and prints out different text depending on the arguments. You must log in to the school computers using your CISE account to do this lab.Tools Please note that you must use a text editor and the terminal to edit and run your program and its directories. It is advised students learn/review basic Unix shell commands before beginning; a good run-through can be found here: https://linuxjourney.com/lesson/the-shell.Follow these steps to get started on the lab:1) Open a terminal and enter the pwd command to identify the path to the working (current) directory (folder) 2) Enter ls to list the contents of the current directory 3) Use the mkdir command to make a new directory called CowLab. 4) Use ls to see the change, then cd to change to the directory CowLab. 5) Do your lab work in that folder. Use your googlefu skills to find more commands.Recommended text editors include nano and joe. (If you hate yourself, you can use vi or emacs too.) You’ll also need to use the python3 program to execute Python programs. You can also use its interactive shell for testing.You can read more information about some of these commands here: https://www.howtogeek.com/howto/42980/the-beginners-guide-to-nano-the-linux-command-line-text-editor/ https://introcs.cs.princeton.edu/java/15inout/linux-cmd.htmlHistory of Command Line Names (Just for Fun) Students will construct one module which (cowsay) which will contain a main() method as the entry point (for command line execution) and a data class (Cow). Note: heiferfactory.py is provided for you; your code must use this module to create cow objects. All attributes / methods must be private unless noted in the specification! Provided For Students – heiferfactoryget_cows() -> list[Cow] Returns an array of cow objects from the built-in data set. This will call the Cow constructor and set_image() methods of the cow class to properly initialize new cow objects uniquely for each data set. Entry PointThe command line arguments that must be supported are as follows:python3 cowsay.py -l Lists the available cows (this is “dash ell”!) python3 cowsay.py MESSAGE Prints out the MESSAGE using the default COW python3 cowsay.py -n COW MESSAGE Prints out the MESSAGE using the specified COWIf a user calls for a cow that does not exist, the program should print out “Could not find [COWNAME] cow!”Output Samples>python3 cowsay.py I am a potato!I am a potato! ^__^ (oo)_______ (__) )/ ||—-w | || || >python3 cowsay.py -n kitteh I am pritteh.I am pritteh. (“`-‘ ‘-/”) .___..–‘ ‘ “`-._ ` *_ * ) `-. ( ) .`-.__. `) (_Y_.) ‘ ._ ) `._` ; `` -. .-‘ _.. `–‘_..-_/ /–‘ _ .’ ,4 ( i l ),-” ( l i),’ ( ( ! .-‘>python3 cowsay.py -l Cows available: heifer kitteh>python3 cowsay.py -n ninja WUT Could not find ninja cow!Suggested Methods The following methods are suggested to make development easier, but are not required:_list_cows(cows: list[Cow]) Displays the list of available cows from an array of Cow objects._find_cow(name: str, cows: list[Cow]) Given a name and an array of Cow objects, return the Cow object with the specified name.Cow Class The Cow class facilitates the creation and use of cow objects by providing the following methods (which students must implement):__init__(self, name: str) This method should be the only constructor for this class. There should not be a default constructor!get_name(self) -> str Returns the name of the cow.get_image(self) -> str Returns the image used to display the cow (after the message).set_image(self, _image: str) Sets the image used to display the cow (after the message). Submissions NOTE: Your output must match the example output *exactly*. If it does not, you will not receive full credit for your submission!Files: cowsay.py cow.py Method: Submit on ZybooksSample Output>python3 cowsay.py Hello World!Hello World! ^__^ (oo)_______ (__) )/ ||—-w | || ||>python3 cowsay.py -n kitteh Hello World!Hello World! (“`-‘ ‘-/”) .___..–‘ ‘ “`-._ ` *_ * ) `-. ( ) .`-.__. `) (_Y_.) ‘ ._ ) `._` ; `` -. .-‘ _.. `–‘_..-_/ /–‘ _ .’ ,4 ( i l ),-” ( l i),’ ( ( ! .-‘>python3 cowsay.py -l Cows available: heifer kitteh>python3 cowsay.py -n ninja Hello world! Could not find ninja cow!>python3 cowsay.py Hello -n kittehHello -n kitteh ^__^ (oo)_______ (__) )/ ||—-w | || ||
Overview The purpose of this assignment is for you to write a data structure called a Linked List, which utilizes templates (similar to Java’s generics), in order to store any type of data. In addition, the nature of a Linked List will give you some experience dealing with non-contiguous memory organization. This will also give you more experience using pointers and memory management. Pointers, memory allocation, and understand how data is stored in memory will serve you well in a variety of situations, not just for an assignment like this. Background Remember Memory?If you are trying to draw out some representation of memory to help you solve a problem, any of these (or some alternative that makes sense to you) will be fine. Arrays Arrays are stored in what is called contiguous memory. A contiguous memory block is one that is not interrupted by anything else (i.e. any other memory block). So if you created an array of 5 integers, each of those integers would be located one after the other in memory, with nothing else occupying memory between them. This is true for all arrays, of any data type.All of the data in an application is not guaranteed to be contiguous, nor does it need to be. Arrays are typically the simplest and fastest way to store data, but they have a grand total of zero features. You allocate one contiguous block, but you can’t resize it, removing elements is a pain (and slow), etc. Consider the previous array. What if you wanted to add another element to that block of memory? If the surrounding memory is occupied, you can’t simply overwrite that with your new data element and expect good results. someArray[5] = 12; // #badIdea This will almost certainly break. Other MemoryIn this scenario, in order to store one more element you would have to: 1. Create another array that was large enough to store all of the old elements plus the new one 2. Copy over all of the data elements one at a time (including the new element, at the end) 3. Free up the old array—no point in having two copies of the dataOther Memory Newly available memory Someone else’s memory 10 12 This process has to be repeated each time you want to add to the array (either at the end, or insert in the middle), or remove anything from the array. It can be quite costly, in terms of performance, to delete/rebuild an entire array every time you want to make a single change. Cue the Linked List!Linked List The basic concept behind a Linked List is simple: 1. It’s a container that stores its elements in a non-contiguous fashion 2. Each element knows about the location of the element which comes after it (and possibly before, more on that later) So instead of a contiguous array, where element 4 comes after element 3, which comes after element 2, etc… you might have something like this:Each element in the Linked List (typically referred to as a “node”) stores some data, plus some sort of reference (a pointer, in C++) to whatever node should come next. The First node knows only about itself, and the Second node. The Second node knows only about itself, and the Third, etc. In this example the Fourth node has a null pointer as its “next” node, indicating that we’ve reached the end of the data. A real-world example can be helpful as well: Think about a line of people, with one person at the front of the line. That person might know about the person who is next in line, but no further than that (beyond him or herself, the person at the front doesn’t need to know or care). The second person in line might know about the third person in line, but no further. Continuing on this way, the last person in line knows that there is no one else that follows, so that must be the end.So… What are the advantages of storing data like this? When inserting or removing elements into an array, the entire array has to be reallocated. With a Linked List, only a small number of elements are affected. Only elements surrounding the changed element need to be updated, and all other elements can remain unaffected. This makes the Linked List much more efficient when it comes to adding or removing elements. Now, imagine one person wants to step out of line. If this were an array, all of the data would have to be reconstructed elsewhere. In a Linked List, only three nodes are affected: 1) The person leaving, 2) the person in front of that person, and 3) the person behind that person. Imagine you are the person at the front of the line. You don’t really need to know or care what happens 10 people behind you, as that has no impact on you whatsoever.If the 5th person in line leaves, the only parts of the line that should be impacted are the 4th, 5th, and 6th spaces. 1. Person 4 has a new “next” Person: whomever was behind the person behind them (Person 6). 2. Person 5 has to be removed from the list. 3. Person 6… actually does nothing. In this example, a Person only cares about whomever comes after them. Since Person 5 was before Person 6, Person 6 is unaffected. (A Linked List could be implemented with two-way information between nodes—more on that later). The same thought-process can be applied if someone stepped into line (maybe a friend was holding their place):In this case, Person 2 would change their “next” person from Person 3, to the new Person being added. New Guy would have his “next” pointer set to whomever Person 2 was previously keeping track of, Person 3. Because of the ordering process, Person 3 would remain unchanged, as would anyone else in the list (aside from being a bit irritated at the New Guy for cutting in line). So that’s the concept behind a Linked List. A series of “nodes” which are connected via pointer to one another, and inserting/deleting nodes is a faster process than deleting and reconstructing the entire collection of data. Now, how to go about creating that? Terminology Node The fundamental building block of a Linked List. A node contains the data actually being stored in the list, as well as 1 or more pointers to other nodes. This is typically implemented as a nested class (see below). Singly-linked A Linked List would be singly-linked if each node only has a single pointer to another node, typically a “next” pointer. This only allows for uni-directional traversal of the data—from beginning to end. Doubly-linked Each node contains 2 pointers: a “next” pointer and a “previous” pointer. This allows for bi-directional traversal of the data—either from front-to-back or backto-front. Head A pointer to the first node in the list, akin to index 0 of an array.Nested Classes The purpose of writing a class is to group data and functionality. The purpose of a nested class is the same—the only difference is where we declare a nested class. We declare a nested class like this: class MyClass // To create nested classes… { public: // Nested class struct NestedClass { int x, y, z; int SomeFunction(); }; private: // Data for “MyClass” NestedClass myData[5]; NestedClass *somePtr; float values[10]; // Etc… }; // Use the Scope Resolution Operator MyClass::NestedClass someVariable; // With a class template… TemplateClass foo; TemplateClass::Nested bar; /* NOTE 1: You can make nested classes private if you wish, to prevent access to them outside of the encapsulating class. */ /* Why is NestedClass a struct in this case? No reason in particular. Remember a struct is just a class with public access by default. */ /* NOTE 2: Nested classes and templates can make for some ugly code. Be sure to read the section at the end about typename */ Additional reading: http://en.cppreference.com/w/cpp/language/nested_types The nature of the Linked List is that each piece of information knows about the information which follows (or precedes) it. It would make sense, then, to create some nested class to group all of that information together.Benefits and Drawbacks All data structures in programming (C++ or otherwise) have advantages and disadvantages. There is no “one size fits all” data structure. Some are faster (in some cases), some have smaller memory footprints, and some are more flexible in their functionality, which can make life easier for the programmer. Linked List versus Array – Who Wins? Array Linked List Fast access of individual elements as well as Changing the Linked List is fast – nodes can be iteration over the entire array inserted/removed very quickly Random access – You can quickly “jump” to the Less affected by memory fragmentation, nodes appropriate memory location of an element can fit anywhere in memory Changing the array is slow – Have to rebuild the No random access, slow iteration and access to entire array when adding/removing elements individual elements Memory fragmentation can be an issue for arrays—need a single, contiguous block large enough for all of the data Extra memory overhead for nodes/pointers Code Structure As shown above, the Linked List class itself stores very little data: Pointers to the first and last nodes, and a count. In some implementations, you might only have a pointer to the first node, and that’s it. In addition to those data members, your Linked List class must conform to the following interface:Function Reference Behaviors PrintForward Iterator through all of the nodes and print out their values, one a time. PrintReverse Exactly the same as PrintForward, except completely the opposite. PrintForwardRecursive This function takes in a pointer to a Node—a starting node. From that node, recursively visit each node that follows, in forward order, and print their values. This function MUST be implemented using recursion, or tests using it will be worth no points. Check your textbook for a reference on recursion. PrintReverseRecursive Same deal as PrintForwardRecursive, but in reverse. Accessors NodeCount How many things are stored in this list?FindAll Find all nodes which match the passed in parameter value, and store a pointer to that node in the passed in vector. Use of a parameter like this (passing a something in by reference, and storing data for later use) is called an output parameter. Find Find the first node with a data value matching the passed in parameter, returning a pointer to that node. Returns nullptr if no matching node found. GetNode Given an index, return a pointer to the node at that index. Throws an exception of type out_of_range if the index is out of range. Const and non-const versions. Head Returns the head pointer. Const and non-const versions. Tail Returns the tail pointer. Const and non-const versions. Insertion Operations AddHead Create a new Node at the front of the list to store the passed in parameter. AddTail Create a new Node at the end of the list to store the passed in parameter. AddNodesHead Given an array of values, insert a node for each of those at the beginning of the list, maintaining the original order. AddNodesTail Ditto, except adding to the end of the list. InsertAfter Given a pointer to a node, create a new node to store the passed in value, after the indicated node. InsertBefore Ditto, except insert the new node before the indicated node. InsertAt Inserts a new Node to store the first parameter, at the index-th location. So if you specified 3 as the index, the new Node should have 3 Nodes before it. Throws an out_of_range exception if given an invalid index. Removal Operations RemoveHead Deletes the first Node in the list. Returns whether or not the Node was removed. RemoveTail Deletes the last Node, returning whether or not the operation was successful. Remove Remove ALL Nodes containing values matching that of the passed-in parameter. Returns how many instances were removed. RemoveAt Deletes the index-th Node from the list, returning whether or not the operation was successful. Clear Deletes all Nodes. Don’t forget the node count—how many nodes do you have after you deleted all of them? Operators operator[] Overloaded subscript operator. Takes an index, and returns data from the indexth node. Throws an out_of_range exception for an invalid index. Const and nonconst versions. operator= Assignment operator. After listA = listB, listA == listB is true. Can you utilize any of your existing functions to make write this one? (Hint: Yes you can.) operator== Overloaded equality operator. Given listA and listB, is listA equal to listB? What would make one Linked List equal to another? If each of its nodes were equal to the corresponding node of the other. (Similar to comparing two arrays, just with non-contiguous data). Construction / Destruction LinkedList() Default constructor. How many nodes in an empty list? (Answer: 0) What is head pointing to? What is tail pointing to? (Answer: nullptr) Initialize your variables! Copy Constructor Sets “this” to a copy of the passed in LinkedList. For example, if the other list has 10 nodes, with values of 1-10? “this” should have a copy of that same data. ~LinkedList() The usual. Clean up your mess. (Delete all the nodes created by the list.) Template types and the typename keyword The compilation process for templates requires specialization—that is, your compiler essentially copiesand-pastes a version of your template, replacing all the instances of with the type you specified when creating an instance of the class. When dealing with templates within templates, nested template classes, etc… the compiler sometimes needs a bit of assistance when figuring out a type. In order to know how to specialize, it has to know everything about the template class. If that template has some other template, it needs to know everything… before it knows everything… and therein lies the problem. The typename keyword is a way of telling your compiler “Hey, what immediately follows typename is a data type. Treat it as such when you compiler everything else.” For example: template class Foo { public: struct Nested { T someThing; }; Nested SomeFunction(); }; When defining the function “SomeFunction” you might write this: template Nested Foo::SomeFunction() // Error, what is a “Nested”? You could clean that up by specifying that a Nested object is part of the Foo class: template Foo::Nested Foo::SomeFunction() // Error, Foo is a template class, label it as such Okay… how about this? template Foo::Nested Foo::SomeFunction() // This SHOULD work, but… still doesn’t. Why? When the Foo class is being defined, it is referencing a type, Nested. This type is part of the Foo class, but the compiler doesn’t know it’s part of the class until it’s done defining the class… But, since Foo is in the process of being defined… how can something simultaneously be defined not-yet-defined? Answer: It can’t. Solution: using the typename keyword, tell the compiler that Nested IS IN FACT A TYPE, and so the compiler doesn’t have to wait to fully define Foo before finding out what it is. // typename: Yes, compiler, Foo::Nested is a type. Honest. You’ll realize it later. template typename Foo::Nested Foo::SomeFunction() Ugly? You bet! Part of the joy of working with templates? It sure is! Every programming language has quirks like this that you just have to learn over time. Tips A few tips for this assignment: • Start small! Work on one bit of functionality at a time. Work on things like Add() and PrintForward() first, as well as accessors (brackets operator, Head()/Tail(), etc). You can’t really test anything else unless those are working. • Your output is simple: print the data, print newline • Remember the “Big Three” or the “Rule of Three” o If you define one of the three special functions (copy constructor, assignment operator, or destructor), you should define the other two • Make charts, diagrams, sketches of the problem. Memory is inherently difficult to visualize, find a way that works for you. • Don’t forget your node count! Sample Outputs
Lab 01: Scientific CalculatorOverview In this project students will build a command-line scientific calculator. The program will display a menu of options including several arithmetic operations and options to clear the result, display statistics, and exit the program. The project’s goal is to provide students with practice in looping, type conversion, and data persistence.Specification The program must have the main() function as the entry point, which must only run if invoked directly – i.e., by checking __name__. There should be no global variables. All output should go to standard output unless otherwise specified. When the program starts it should display a menu, prompt the user to enter a menu option, and read a value:Current Result: 0.0Calculator Menu ————— 0. Exit Program 1. Addition 2. Subtraction 3. Multiplication 4. Division 5. Exponentiation 6. Logarithm 7. Display AverageEnter Menu Selection: 1If an option with operands (1-6) is selected, the program should prompt for and read floating point numbers as follows:Enter first operand: 89.1 Enter second operand: 42Once the two operands have been read, the result should be calculated and displayed, along with the menu:Current Result: 131.1Calculator Menu ————— … Operational Behavior This calculator includes multiple behaviors that are unique depending on the input and operation specified; they are detailed in this section. Results should be displayed to default precision except where specified.Exponentiation For exponentiation, the first operand should be used as the base and the second as the exponent, i.e.:If the first operand is 2 and the second is 4… 24 = 16Logarithm For logarithms, the first operand should be used as the base and the second as the yield, i.e.:If the first operand is 2 and the second is 4… log24 = 2Displaying the Average As the program progresses, it should store the total of all results of calculation and the number of calculations. Note that this does not include the starting value of 0! The program should display the average of all calculations as follows:Sum of calculations: 101.3 Number of calculations: 2 Average of calculations: 50.15Note that the average calculation should show a maximum of two decimal places. The program should immediately prompt the user for the next menu option (without redisplaying the menu).If no calculations have been performed, this message should be displayed:Error: No calculations yet to average!Extra Credit Using Results of Calculation You can earn 5% extra credit on this project by allowing the user to use the previous result in an operation. To add this feature, allow the user to enter the word “RESULT” in place of an operand; if the user does so, the program should replace this operand with the result of the previous calculation (or zero if this is the first calculation):Enter first operand: 89.1 Enter second operand: RESULTSubmissions NOTE: Your output must match the example output *exactly*. If it does not, you will not receive full credit for your submission!File: calculator.py Method: Submit on ZyLabsDo not submit any other files!Sample OutputCurrent Result: 0.0Calculator Menu ————— 0. Exit Program 1. Addition 2. Subtraction 3. Multiplication 4. Division 5. Exponentiation 6. Logarithm 7. Display AverageEnter Menu Selection: 7 Error: No calculations yet to average!Enter Menu Selection: 1 Enter first operand: 0.5 Enter second operand: -2.5Current Result: -2.0Calculator Menu ————— 0. Exit Program 1. Addition 2. Subtraction 3. Multiplication 4. Division 5. Exponentiation 6. Logarithm 7. Display AverageEnter Menu Selection: 5 Enter first operand: -2.0 Enter second operand: -2.0Current Result: 0.25Calculator Menu ————— 0. Exit Program 1. Addition 2. Subtraction 3. Multiplication 4. Division 5. Exponentiation 6. Logarithm 7. Display Average Enter Menu Selection: 6 Enter first operand: 2 Enter second operand: 0.5Current Result: -1.0Calculator Menu ————— 0. Exit Program 1. Addition 2. Subtraction 3. Multiplication 4. Division 5. Exponentiation 6. Logarithm 7. Display AverageEnter Menu Selection: 7Sum of calculations: -2.75 Number of calculations: 3 Average of calculations: -0.92Enter Menu Selection: -10 Error: Invalid selection!Enter Menu Selection: 0 Thanks for using this calculator. Goodbye!
Contents 1 Overview 3 2 Background 3 2.1 Remember Memory? 3 2.2 Arrays 4 2.3 Linked List 5 2.4 Terminology 6 2.5 Nested Classes 7 3 Benefits and Drawbacks 7 4 Code Structure 8 4.1 Construction / Destruction 8 4.2 Behaviors 8 4.3 Accessors 8 4.4 Insertions 9 4.5 Removals 9 4.6 Operators 9 5 Template types 10 6 Tips 111 Overview The purpose of this assignment is for you to write a data structure called a Linked List, which utilizes templates (similar to Java’s generics), in order to store any type of data. In addition, the nature of a Linked List will give you some experience dealing with non-contiguous memory organization. This will also give you more experience using pointers and memory management. Pointers, memory allocation, and an understanding how data is stored in memory will serve you well in a variety of situations, not just for an assignment like this. 2 Background 2.1 Remember Memory? x y z car r g b a ptr Other memoryThere are other ways to draw this and if you are trying to draw out some representation of memory to help you solve a problem, a visualization that makes sense to you will be best. This pdf will specifically use this horizontal representation, but the same concepts used here will apply to any other representation!2.2 Arrays 2.2 Arrays Arrays are stored in what is called contiguous memory. A contiguous memory block is one that is not interrupted by anything else (i.e. any other memory block). So if you created an array of 5 integers, each of those integers would be located one after the other in memory, with nothing else occupying memory between them. This is true for all arrays, of any data type.All of the data in an application is not guaranteed to be contiguous, nor does it need to be. Arrays are typically the simplest and fastest way to store data, but they have a grand total of zero features. You allocate one contiguous block, but you can’t resize it, removing elements is a pain (and slow), etc.In this scenario, in order to store one more element you would have to: 1. Create another array that was large enough to store all of the old elements plus the new one 2. Copy over all of the data elements one at a time (including the new element, at the end) 3. Free up the old array—no point in having two copies of the data Old Array Create New ArrayLastly, delete the old array Other Memory Newly available memory Someone else’s memory 2 4 6 8 10 12 This process has to be repeated each time you want to add to the array (either at the end, or insert in the middle), or remove anything from the array. It can be quite costly, in terms of performance, to delete/rebuild an entire array every time you want to make a single change. Cue the Linked List! 2.3 Linked List 2.3 Linked List The basic concept behind a Linked List is simple: 1. It’s a container that stores its elements in a non-contiguous fashion 2. Each element knows about the location of the element which comes after it (and possibly before, more on that later) So instead of a contiguous array, where element 4 comes after element 3, which comes after element 2, etc… you might have something like this:Each element in the Linked List (typically referred to as a “node”) stores some data, plus some sort of reference (a pointer, in C++) to whatever node should come next. The First node knows only about itself, and the Second node. The Second node knows only about itself, and the Third, etc. In this example the Fourth node has a null pointer as its “next” node, indicating that we’ve reached the end of the data. A real-world example can be helpful as well: Think about a line of people, with one person at the front of the line. That person might know about the person who is next in line, but no further than that (beyond him or herself, the person at the front doesn’t need to know or care). The second person in line might know about the third person in line, but no further. Continuing on this way, the last person in line knows that there is no one else that follows, so that must be the end. etc… First in line So… What are the advantages of storing data like this? When inserting or removing elements into an array, the entire array has to be reallocated. With a Linked List, only a small number of elements are affected. Only elements surrounding the changed element need to be updated, and all other elements can remain unaffected. This makes the Linked List much more efficient when it comes to adding or removing elements. Now, imagine one person wants to step out of line. If this were an array, all of the data would have to be reconstructed elsewhere. In a Linked List, only three nodes are affected: • the person leaving • the person in front of that person • the person behind that person. Imagine you are the person at the front of the line. You don’t really need to know or care what happens 10 people behind you, as that has no impact on you whatsoever. 2.4 TerminologyIf the 5th person in line leaves, the only parts of the line that should be impacted are the 4th, 5th, and 6th spaces. 1. Person 4 has a new “next” Person: whomever was behind the person behind them (Person 6). 2. Person 5 has to be removed from the list. 3. Person 6… actually does nothing. In this example, a Person only cares about whomever comes after them. Since Person 5 was before Person 6, Person 6 is unaffected. (A Linked List could be implemented with two-way information between nodes—more on that later). The same thought-process can be applied if someone stepped into line (maybe a friend was holding their place)New Guy In this case, Person 2 would change their “next” person from Person 3, to the new Person being added. New Guy would have his “next” pointer set to whomever Person 2 was previously keeping track of, Person 3. Because of the ordering process, Person 3 would remain unchanged, as would anyone else in the list (aside from being a bit irritated at the New Guy for cutting in line). So that’s the concept behind a Linked List. A series of “nodes” which are connected via pointer to one another, and inserting/deleting nodes is a faster process than deleting and reconstructing the entire collection of data. Now, how to go about creating that? 2.4 Terminology Node The fundamental building block of a Linked List. A node contains the data actually being stored in the list, as well as 1 or more pointers to other nodes. This is typically implemented as a nested class (see below). Singlylinked A Linked List would be singly-linked if each node only has a single pointer to another node, typically a “next” pointer. This only allows for uni-directional traversal of the data—from beginning to end. Doublylinked Each node contains 2 pointers: a “next” pointer and a “previous” pointer. This allows for bi-directional traversal of the data—either from front-to-back or back-to-front. Head A pointer to the first node in the list, akin to index 0 of an array.2.5 Nested Classes 3 BENEFITS AND DRAWBACKS 2.5 Nested Classes The purpose of writing a class is to group data and functionality. The purpose of a nested class is the same—the only difference is where we declare a nested class. We declare a nested class like this:The nature of the Linked List is that each piece of information knows about the information which follows (or precedes) it. It would make sense, then, to create some nested class to group all of that information together. A sample hierarchy of how that would work:3 Benefits and Drawbacks All data structures in programming (C++ or otherwise) have advantages and disadvantages. There is no “one size fits all” data structure. Some are faster (in some cases), some have smaller memory footprints, and some are more flexible in their functionality, which can make life easier for the programmer. Array Linked List Fast access of individual elements as well as iteration over the entire array Changing the Linked List is fast – nodes can be inserted/removed very quickly Random access – You can quickly “jump” to the appropriate memory location of an element Less affected by memory fragmentation, nodes can fit anywhere in memory Changing the array is slow – Have to rebuild the entire array when adding/removing elements No random access, slow iteration and access to individual elements Memory fragmentation can be an issue for arrays—need a single, contiguous block large enough for all of the data Extra memory overhead for nodes/pointers 4 CODE STRUCTURE 4 Code Structure As shown above, the Linked List class itself stores very little data: Pointers to the first and last nodes, and a count. In some implementations, you might only have a pointer to the first node, and that’s it. In addition to those data members, your Linked List class must conform to the following specification! (Yes it’s a lot… it’s a big project get started early!) 4.1 Construction / Destruction Default Constructor Default constructor. How many nodes in an empty list? (Answer: 0) What is head pointing to? What is tail pointing to? (Answer: nullptr) Initialize your variables! Copy Constructor Sets “this” to a copy of the passed in LinkedList. For example, if the other list has 10 nodes, with values of 1-10? “this” should have a copy of that same data. Destructor The usual. Clean up your mess. (Delete all the nodes created by the list.) 4.2 Behaviors PrintForward Iterator through all of the nodes and print out their values, one a time. PrintReverse Exactly the same as PrintForward, except completely the opposite. PrintForwardRecursive This function takes in a pointer to a Node—a starting node. From that node, recursively visit each node that follows, in forward order, and print their values. This function MUST be implemented using recursion, or tests using it will be worth no points. Check your textbook for a reference on recursion. PrintReverseRecursive Same deal as PrintForwardRecursive, but in reverse. 4.3 Accessors NodeCount How many things are stored in this list? FindAll Find all nodes which match the passed in parameter value, and store a pointer to that node in the passed in vector. Use of a parameter like this (passing a something in by reference, and storing data for later use) is called an output parameter. Find Find the first node with a data value matching the passed in parameter, returning a pointer to that node. Returns nullptr if no matching node found. GetNode Given an index, return a pointer to the node at that index. Throws an exception of type out_of_range if the index is out of range. Const and non-const versions. Head Returns the head pointer. Const and non-const versions. Tail Returns the tail pointer. Const and non-const versions. 4.4 Insertions 4 CODE STRUCTURE 4.4 Insertions AddHead Create a new Node at the front of the list to store the passed in parameter. AddTail Create a new Node at the end of the list to store the passed in parameter. AddNodesHead Given an array of values, insert a node for each of those at the beginning list, maintaining the original order. AddNodesTail Ditto, except adding to the end of the list. InsertAfter Given a pointer to a node, create a new node to store the passed in value, after the indicated node. InsertBefore Ditto, except insert the new node before the indicated node. InsertAt Inserts a new Node to store the first parameter, at the index-th location. So if you specified 3 as the index, the new Node should have 3 Nodes before it. Throws an out_of_range exception if given an invalid index. 4.5 Removals RemoveHead Deletes the first Node in the list. Returns whether or not the Node was removed. RemoveTail Deletes the last Node, returning whether or not the operation was successful. Remove Remove ALL Nodes containing values matching that of the passed-in Returns how many instances were removed. RemoveAt Deletes the index-th Node from the list, returning whether or not the operation was successful. Clear Deletes all Nodes. Don’t forget the node count—how after you deleted all of them? 4.6 Operators operator[] Overloaded subscript operator. Takes an index, and returns data from the indexth node. Throws an out_of_range exception for an invalid index. Const and nonconst versions. operator= Assignment operator. After listA = listB, listA == listB is true. Can of your existing functions to make write this one? (Hint: Yes you can.) operator== Overloaded equality operator. Given listA and listB, is listA equal to listB? What would make one Linked List equal to another? If each of its nodes were equal to the corresponding node of the other. (Similar to comparing two arrays, just with non-contiguous data). 5 TEMPLATE TYPES 5 Template types The compilation process for templates requires specialization-that is, your compiler essentially copies and-pastes a version of your template, replacing all the instances of with the type you specified when creating an instance of the class. When dealing with templates within templates, nested template classes, etc… the compiler sometimes needs a bit of assistance when figuring out a type. In order to know how to specialize, it has to know everything about the template class. If that template has some other template, it needs to know everything… before it knows everything… and there lies the problem. The typename keyword is a way of telling your compiler “Hey, what immediately follows typename is a data type. Treat it as such when you compiler everything else.” For example:When defining the function “SomeFunction” you might write this:You could clean that up by specifying that a Nested object is part of the Foo class:Okay… how about this?When the Foo class is being defined, it is referencing a type, Nested. This type is part of the Foo class, but the compiler doesn’t know it’s part of the class until it’s done defining the class… But, since Foo is in the process of being defined… how can something simultaneously be defined not-yet-defined? Answer: It can’t. Solution: using the typename keyword, tell the compiler that Nested IS IN FACT A TYPE, and so the compiler doesn’t have to wait to fully define Foo before finding out what it is.Ugly? You bet! Part of the joy of working with templates? It sure is! Every programming language has quirks like this that you just have to learn over time. 6 TIPS 6 Tips A few tips for this assignment: • Start small! Work on one bit of functionality at a time. Work on things like Add() and PrintForward() first, as well as accessors (brackets operator, Head()/Tail(), etc). You can’t really test anything else unless those are working. • Your output is simple: print the data, print newline • Remember the “Big Three” or the “Rule of Three” – If you define one of the three special functions (copy constructor, assignment operator, or destructor), you should define the other two – There are a lot of things to remember when dealing with memory allocation • Make charts, diagrams, sketches of the problem. Memory is inherently difficult to visualize, find a way that works for you. • Don’t forget your node count!
Contents 1 Overview 2 2 Description 2 2.1 Starship Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3 Reading Binary Data 3 4 File Format 3 5 Searches 4 6 Tips 4 7 Sample Outputs 4 1 2 DESCRIPTION 1 Overview 2 Description There are 2 main files that you will be loading in this assignment: • friendlyships.shp • enemyships.shp 2.1 Starship Data The output for a starship would look something like one of these:The data stored for each ship is as follows: 1. A string for the name of the vessel 2. A string for the class of ship 3. The length of the ship, stored as a short 4. The shield capacity, stored as an integer 5. The maximum warp speed of the ship, stored as a float 6. An inventory containing a variable number of weapons, each of which contain a string, integer, and float. If a ship doesn’t have any weapons, the file will still have to indicate a 0. Output-wise, you can just print out “Unarmed” 4 FILE FORMAT 3 Reading Binary Data Reading data in binary is all about copying bytes (1 byte : 8 bits) from a location in a file to a location in memory. When reading data you will always use the read() function, and when writing data you will always use the write() function. For this assignment, you will only need to read() data. Strings are always an exceptional case. In the case of strings, you should read them in a 4 or 5 step process: 1. Read the length of the string from the file. Unless you are dealing with fixed-length strings (in which case you know the length of the string from somewhere else), it will be there, promise. (If someone didn’t write this data out to a file, shame on them, they screwed up.) 2. Dynamically allocate an array equal to the size of the string, plus 1 for the null terminator. If the length already includes the null terminator, do not add one to the count here — you’d be accounting for it twice, which is bad. 3. Read the string into your newly created buffer. 4. (OPTIONAL) Store your dynamic char * in something like a std::string, which manages its own internal memory. Then you can delete your own dynamic array so you don’t have to worry about it anymore. 5. Delete the dynamically allocated array… eventually (unless already done in step 4). If you are planning to use this variable later, be sure to delete it later on down the line. 4 File Format The structure of the file is as follows: 4 bytes An int count of how many ships are in the file4 bytes The length of the name, including the null terminator “Length” bytes The string data for the name, including the null terminator 4 bytes The length of the ship’s class, including the null terminator “Length” bytes The string data for the class, including the null terminator 2 bytes The ship’s length, in meters 4 bytes The ship’s shield capacity, in terajoules 4 bytes The warp speed of the ship 4 bytes A count of the number of weapons equipped on the ship4 bytes The length of the weapon’s name, including the null terminator “Length” bytes The string data for the name of the item, including the null terminator 4 bytes An integer for power rating of the weapon 4 bytes A float for the power consumption of the weapon7 SAMPLE OUTPUTS 5 Searches After you’ve loaded the data, you will perform a few operations on the stored data: 1. Print all the ships 2. Print the starship with the most powerful weapon 3. Print the most powerful ship (highest combined power rating of all weapons) 4. Print the weakest ship (out of ships that actually have weapons) 5. Print the unarmed ships 6 Tips 1. Choices you make at the start of a program can have a big impact on how the rest of the program gets developed. Think about how you want to store the information retrieved from the file, and how you could easily pass that data to various functions you might write. 2. If you have a process for easily loading and accessing the data, the rest of the functionality should be a lot easier to write. Make sure the loading process is all taken care of before worrying about anything else. 3. If you pass containers of data, make sure you pass them by REFERENCE, not by value. Don’t create copies of anything unless you specifically need a copy. 4. Try reading one element at a time. Read the first 4 bytes, try printing it out to the screen. Is the number something reasonable, or something that seems incorrect, like -20? If that works, move on to the next piece of data in the file. 7 Sample Outputs
Contents I Inheritance 2 1 Overview 2 1.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Abstract Base Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Multiple Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 The Diamond Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4.1 How to resolve the diamond problem . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.5 Public and Private Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5.1 Accessing members of base class(es) . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.6 Virtual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.7 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Assignment Specifics 6 2.1 Bank Account . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Checking Account . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Savings Account . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Investment Account . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.5 Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 II Maps… and other 8 3 Overview 8 3.1 Maps in C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Upcasting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3 Functors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4 Assignment Specifics 9 4.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.2 Additional Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1 Part I Inheritance 1 Overview In this part of the assignment, you’re going to create a series of classes to represent bank accounts. While the classes themselves are all simple, you will be using inheritance and the concept of polymorphism to make them functional with the given main code. You will also create classes which make use of multiple inheritance, as well as private inheritance. 1.1 Description The basic idea of inheritance is that you have a base class, and you create new classes which derive from that base class. One common use of inheritance is to reuse data and functions: if a base class defines those things, then the derived class doesn’t have to; it inherits them, so in effect, you get “free” code in that class. Another use of inheritance is to define a class which serves as what other programming languages would call an interface. In C++, the keyword interface doesn’t exist, but some of the classes you create here will serve the same purpose. An interface defines how a class should look on the outside. The first class shown here will serve as interfaces; all the other classes will derive from it. In this way, all classes in this assignment are bank accounts. Some types of inheritance model the “Is-a” relationship. A triangle IS A shape. A circle IS A shape as well. Other types of inheritance model a “has-a” relationship. A car, for example, has an engine—but it isn’t an engine. This type of relationship can still be created, but the process is a bit different. 1.2 Abstract Base Class An Abstract Base Class (ABC) is a class you never want to create an instance of; it doesn’t have enough information to be useful on its own. An ABC could have any number of functions or variables, whether public, protected, or private. You cannot create an instance of an abstract base class. Perhaps you are creating a program that needs to store data about students and faculty members. They share similar data (name, age, email address, etc.), but have their own unique data as well. You might create 3 classes:To create an abstract base class, at least one function in the class must be a pure virtual function. A pure virtual function is one that: 1. Have the virtual keyword before the return type 2. Has = 0 at the end of the prototype 3. Has no function definition (i.e. no body) – the only exception to this is the destructor. You MUST have a body on a destructor, pure virtual or otherwise. For example, our display function is a pure virtual function:1.3 Multiple Inheritance 1.3 Multiple Inheritance While many languages do not allow multiple inheritance, C++ does! The basic concept is the same. You have multiple base classes, and a single class can derive from some or all of them, inheriting the data members and functions of each base class. 1.4 The Diamond Problem An issue with multiple inheritance is the dreaded “diamond problem.” This comes about when a derived class inherits from two base classes, which each derive from the same parent base class. Consider this:Figure 1.1: Diamond Problem In this example, you want FlyingCar to inherit both driving and flying functionality… but you unfortunately inherit Vehicle functionality twice! 1.4.1 How to resolve the diamond problem You can fix the issue of the diamond problem by using virtual inheritance. In the above example, the class declarations might look like this:With virtual inheritance, the “in-between” classes would add the virtual keyword to the inheritance:This ensures that FlyingCar would only inherit ONE instance of anything Car and Airplane inherited from Vehicle. For more information: https://en.wikipedia.org/wiki/Virtual_inheritance https://isocpp.org/wiki/faq/multiple-inheritance#virtual-inheritance-where 1.5 Public and Private Inheritance 1.5 Public and Private Inheritance Perhaps the most common type of inheritance is public inheritance. It represents an “is-a” relationship between classes. The derived class is a base class. For example:We would say that the Car (derived class) IS A Vehicle (base class). A SavingsAccount IS A BankAccount. A Button IS A UIControl, etc. If class inherits from another class using private inheritance, however, it models a “has a” relationship. This is also sometimes referred to as composition. For example:The only thing the Car class can access of the Engine object is public members and functions – here’s where the accessor functions of a class would come into play. 1.5.1 Accessing members of base class(es) To access the functions or variables of a base class, you must specify the name of the class, and then the thing you are trying to access. So in the case of the car and its engine, you would do something like this:Reference: https://isocpp.org/wiki/faq/private-inheritance 1.6 Virtual We’ve gone over different use cases of virtual, that it’s necessary for solving the diamond problem, that ABC’s must have at least one pure virtual function, etc. So what is it? Let’s start with virtual inheritance. This is specifically when you specify a virtual parent class. It would look something like this: “Derrived : virtual public Base”. We’ve already gone over the fact that this is necessary for solving the diamond problem. But why? The reason is that virtual inheritance tells the compiler to only ever include one instance of the class within derived classes. More accurately, it tells the compiler to check if the parent class has already been inherited and to use that instance as the parent rather than making a new one. Let’s move on to virtual methods. In this case we are telling the compiler to make what’s called a vtable for any class with this method. You don’t have to know much about what the vtable does but I do recommend looking into it as it helps with a lower-level understanding. With that said, what you should know is that the result of using a vtable is the ability to override and call overriden behavior from a downcasted parent declaration. This means running the code snippet below will result in the child behavior not the parents!As a take away, the virtual keyword seems ensure that there is only one instance of something in a class. Whether that means one definition for a function (regardless the static dispatch) or one instance of a parent within the child class. 1.7 Polymorphism 1.7 Polymorphism One important concept in object-oriented programming is that a base-class pointer can point to any object which derives from that base class. For example:Following that same concept, we could extend that to something like the following:What polymorphism allows you to do is call a function from one of those objects and depending on what the pointer is pointing to the correct function will be called.Given the previous array, code like the main function bellow would print out “I’m a sports car!”.Polymorphism is the concept that allows you to write code like that, without knowing exactly what type of object you are pointing to. Since cars[1] points to a SportsCar, the call to Identity() will determine that the SportsCar version of the function should be used. The virtual keyword is required on the base class version of the function in order to make this functionality possible. For more on polymorphism: http://www.cplusplus.com/doc/tutorial/polymorphism/2 ASSIGNMENT SPECIFICS 2 Assignment Specifics 2.1 Bank Account BankAccount is an abstract base class. Because at least one of the functions in this class are pure virtual functions (virtual functions with no definition). This base says that all BankAccounts can calculate an amount, display their data, and recieve a deposit. Each derived class can define HOW they do each of these. This class will not require a virtual destructor. A virtual destructor is used to make sure child destructors (if necessary) are called even if the deleted variable is upcasted as a parent class.2.2 Checking Account CheckingAccount derives from the BankAccount class (a CheckingAccount IS A BankAccount). This class, however, is not an abstract base class. This means we now must define any previous virtual functions.2.3 Savings Account 2 ASSIGNMENT SPECIFICS 2.3 Savings Account The savings account class will be treated similarly to the Checking account. All the same virtual functions must be overridden, a new private variable amount must be added as well as a new protected method setAmount(). There is also a new behavioral function to add: CompoundEarnings(), which will return a float (the earned amount). This method should take in a positive float and set the amount in the account to amount*(1+percent). This is how the account will earn interest. While this seems like the same situation as with the Checking account, this function will change in the future investment account. In addition, you must also implement Transfer(). This function will return a boolean representing the operations success. It will take in a checking account object and a float then transfer ’float’ amount from the savings account to the passed in checking account (modifying parameters… where have I heard that before).2.4 Investment Account Now it’s time for the more complicated account class of the 4. The premise of this class is an account that for the most part is a checking account but has a sort of savings account. This savings account will be the investment side of the account. The idea is for any earnings from the investment side to be immediately available in a checking account format as to not have the user worry about transferring money at all. With that said here are a few things to look out for: • getAmount should give the total amount in both! • initial values and any deposits go to the savings account not to the checking! • You will have to override quite a few functions here! • Transfer should only take one ’float percent’ and transfer from this savings to this checking!2.5 Tips A few tips about this assignment: • MOST IMPORTANT: One very necessary distinction to make is that of getAmount() and amount. Specifically because getAmount() is virtual calling it will get the definition of the invoking object which is not necessarily the current class. That is to say calling it within the CheckingAccount class will return the total amount within an InvestmentAccount object if that is the invoking object. • Start with one class at a time. It is important to keep future classes in mind but trying to work from the bottom up can mean a lot of back and forth. 3 OVERVIEW Part II Maps… and other 3 Overview For this assignment, you must write main(int argc, char** argv) and the functor, AccountReader. As long as you implemented everything correctly in part 1 this part will come a lot easier! 3.1 Maps in C++ Thankfully the map class is not one we have to right ourselves! It’s included in the STL specifications meaning all we have to do is #include. There is also the unordered_map which uses hashing functions to have a slightly better performance, but to produce consistent output with options 1 and 2 we will be using the map class. To help get you started here is an example of looping through a map:3.2 Upcasting Upcasting is the process of converting an object which is declared as a parent class into one declared as the child class. Notice that this changes what’s called the static dispatch, you can think of this as what you declare a variable. However, without checking that this object actually is the child class we want to cast to, this is a dangerous thing to do. To safely upcast we will use dynamic_cast in the following format:3.3 Functors We will be using functors in this lab! Functors are a neat way to generalize functions. For example, if you need to have a function that calculates gravitational force you might need different constants for gravity. So instead of having to pass a parameter every time we call the function, we can use a functor! The following code is for this example:4 ASSIGNMENT SPECIFICS 4 Assignment Specifics 4.1 Description You are given a csv file (Comma Separated Values) with rows representing different bank accounts. You must read from these rows and store their information within a new object of it’s respective account class. Then store that object within two maps. You will have store it as a pointer to ensure polymorphism is maintained. The keys you will need to look up with are the account owner’s name and the account’s ID. You will code a functor that takes in the file path of the csv file. To make things easier you should have the following 2 maps in your functor: • Map 1: ID lookup map. This map will use the owners id as the key and the owners Bank Account as a value (BankAccount*) • Map 2: Name lookup map. This map will use the owners name as the key and the owners Bank Account as a value (BankAccount*) The format of the file is as follows: Type Name Amount ID 2 Derek Pearce 1773 1009 1 Ria Marshall 3288 1010 3 Ronan Walker 8971 1011 3 Eric Carr 4762 1012 et c… The type number will be one of the ints 1, 2, or 3 representing Checking, Savings, and Investment accounts respectively The options you will have to read (cin) and implement within your call operator: 1. Display all accounts 2. Display all of account type 2.1. Checking Accounts 2.2. Savings Accounts 2.3. Investment Accounts 3. Find account • Integer input for ID search (use stoi!) • String input for name search (HAS TO BE FULL NAME) • Not Found 4.2 Additional Notes • **IMPORTANT** You are expected to use CLI to get the file path from the main and pass it to the functor. The program will be called in the following format: – ./main.out path/to/accounts.csv • We are using stdin (aka cin) for option selection. HOWEVER, note that cin >> name is NOT the same as getline(cin, name)… this important for when the input has spaces! • Because this part requires you to create new variables and store their pointers in maps, we are working with dynamic memory. As such you are expected to delete the pointers also!
The purpose of this assignment is give you some experience writing classes in C++, the various special functions they make use of (such as copy constructors, assignment operators, and destructors), as well as an introduction to dynamically allocating memory within those classes. Contents 1 New Keywords / Language concepts 2 2 Description 2 2.1 Vehicle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Default values and constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.3 Showroom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.4 Dealership . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 Relevant Reading 4 4 Tips 4 5 Assignment Specifications! 4 5.1 Part 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 5.2 Part 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 5.3 Part 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 5.4 About Codio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 6 Example Output 5 1 2 DESCRIPTION 1 New Keywords / Language concepts • Classes – conceptually similar to other languages • The std::vector class – similar to Java’s ArrayList class, an expandable container • The std::string class – similar in many ways to strings in most every language 2 Description This program will represent a hypothetical car dealership, which consists of showrooms that contain the vehicles for sale. To that end, there are three classes you will be writing: • Vehicle • Showroom • Dealership For this assignment, main.cpp will be mostly provided for you, so you don’t have to worry about the structure of the program. Instead, you can focus solely on the structure of the classes and their interactions. You, however, will have to fill in the //TODO parts! 2.1 Vehicle The Vehicle class is the basic container of this assignment. You will need to store the following data as private data members of the class: • A std::string to store the make of the vehicle (such as Mazda, Toyota, etc) • A std::string to store the model of the vehicle (such as Mustang, Model S, F-150, etc) • An integer to store the year • A float to store the price • An integer to store the number of miles the vehicle has been driven In addition to these data members, you should have the following public functions:2.2 Default values and constructors Make Model Year Price Mileage “COP3503” “Rust Bucket” 1900 0 0 These defaults are chosen arbitrarily for this assignment. For your own projects, you can of course choose anything that you like. 2.3 Showroom 2 DESCRIPTION 2.3 Showroom The Showroom class is a bit more sophisticated. Its purpose is to store a collection of Vehicle objects. Each Showroom that you create could have a different number of Vehicles (depending on its size), so for this assignment we’ll use a vector. Your Showroom should contain variables for the following: • The name of the Showroom • A vector to store Vehicle objects • A maximum capacity of the showroom (we don’t want to add Vehicles beyond this limit) In addition, you should create the following functions:Function Reference Constructor Same as all constructors! Initialize class member variables GetVehicleList Return the vector objects, so other code can access it AddVehicle If the Showroom is already full (numberOfVehicles == capacity), then you should print out “Showroom is full! Cannot add 2015 Mazda Miata”(this will use the GetYearMakeModel() function from the Vehicle class) If there is space in the showroom, add the pass-in Vehicle to the class’ vector. Vector objects can be expanded with the push_back() function. ShowInventory Show all vehicles in the showroom, using the Display() function of each vehicle GetInventoryValue Sum up the prices of all vehicles in the showroom and return that value 2.4 Dealership The Dealership class in some ways is very similar to the Showroom. Instead of Vehicles, it will store a vector of Showroom objects. It will also need a name and a capacity. In addition, you will need functions:Constructor Same as all constructors! Initialize class member variables AddShowroom If the Dealership is already full (numberOfShowrooms == capacity), then you should print out “Dealership is full, can’t add another showroom!” If there is space, add the passed-in object to the vector class member. GetAveragePrice Here you will have to loop through all showrooms, and all vehicles in those showrooms, and get a final average price of all vehicles. (Remember: Average is total / number of values) ShowInventory Show all showrooms stored in this dealership, one at a time, finally displaying the average price of each vehicle stored in the dealership (this sounds familiar…) 5 ASSIGNMENT SPECIFICATIONS! 3 Relevant Reading 1. Chapter 2 and Chapter 3 of Programming: Principles and Practices using C++ (Recommended) 2. Slides: Week 2 : Classes and Week 2 : Classes 3. Slides: Week 2 : Classes and Week 2 : Constructors and Destructors 4 Tips A few tips about this assignment: • You can print out a tab character (the escape sequence ’t’) to help line up the output. • Don’t try to tackle everything all at once. Work on one class at a time. Can’t really have a Dealership without a Showroom, which really needs Vehicles… • An extension of that: work on one function, one class variable at a time. Create a constructor, initialize a single variable, test that out. When that works, move to the next part, and so on. 5 Assignment Specifications! 5.1 Part 1 For this part you will start by solely focusing on the Vehicles class writing a header and source file for the class. • Write the function prototypes and class members in the header. • Give definitions to the functions in the source file (this is where you will use the scope resolution operator, “::”.) • Finally write the final test input following the TODO instructions! 5.2 Part 2 Here we will use our code for the Vehicle class to build our Showroom! • Write the function prototypes and class members in the header (again but this time for the showroom). • Once again give definitions to the functions in the source file (this is where you will use the scope resolution operator, “::”.) 5.3 Part 3 Here we will use our code for the Vehicle and Showroom classes to build our Dealership! This should look very similar to your showroom. 😉 • Write the function prototypes and class members in the header (again but this time for the dealership). • Once again give definitions to the functions in the source file (this is where you will use the scope resolution operator, “::”.) 5.4 About Codio ! This will be the first lab where you have multiple parts. This means you must go to the next part after completing one. There are a total of three! Use the below buttons to navigate between parts. 6 EXAMPLE OUTPUT 6 Example Output Default constructor outputsShowroom output and error message when Showroom is fullDealership output and error message when Dealership is fullCalling just the GetAveragePrice() function of the dealership
Contents 1 Intro and Problem 2 2 Background 2 2.1 Array Declaration and Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.3 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 Specifications 3 3.1 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.2 Methods in Contact class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.3 Required methods: ContactBook class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 Testing and Help 5 5 Helpful links 5 1 2 BACKGROUND 1 Intro and Problem In this lab we will be creating a database for contacts to be stored. Devices having overlapping contacts is inefficient as each device storing duplicate contacts wastes space. So, in this lab all Contact information will be stored in one place, and on each persons device will be a single ContactBook object, a class/struct that you will implement, along with a Contact class/struct you will implement. The ContactBook object will only hold pointers of contacts, to greatly reduce the total amount of memory used for a large database. So now when two devices have the same contact, they will both only hold a pointer to the same contact in memory, instead of there being two copies of the contact. More specifically, a pointer in cpp on a 64 bit device is only taking up 8 bytes, where a contact might be holding way more bytes of information. In our example, there is only two strings for a contact to make it simpler(name and number), but it wouldn’t be difficult to add things like email, profile picture, and more to each contact, which would take up a lot more memory. 2 Background 2.1 Array Declaration and InitializationYou can initialize the array at the time of declaration or later using a loop or individual assignments. In addition, to access specific elements of the array, you can use indexing. For example, to access the third element of the previous array, you can do the following:2.2 Pointers To declare a pointer, use the type followed by an asterisk (*). Pointers can be initialized with the address of a variable. You can use asterisk (*) to access the value stored at the address.Pointers can be set to nullptr when not pointing to a valid address.In C++, the arrow operator (->) is used to access members of a class or structure through a pointer. It provides a convenient syntax for accessing members when working with pointers to objects. The arrow operator is an alternative to the dot operator (.) used with objects directly. Here’s a short example:2.3 References 3 SPECIFICATIONS 2.3 References In C++, references provide a way to work with variables directly, allowing you to pass values into functions and return values from functions. Passing by Reference: Pass variables by reference to avoid unnecessary copying and to allow modification of the original variable.The function modifyValue takes an integer reference as a parameter, allowing it to modify the original variable num. Returning Reference from a Function: You can return a reference from a function, allowing the result to be modified directly3 Specifications 3.1 Structure • Both the name and phone number will be stored as string’s, as an example structure follows:• You must use an array of Contact pointers in your ContactBook Class, an example structure follows:3.2 Methods in Contact class 3 SPECIFICATIONS • When using static arrays in cpp, the size that needs to be allocated must be known at COMPILE TIME, so we must set some kind of max size if we are using static arrays. This is why in most cases, std::vector will be more useful, as it resizes itself. We will learn in the next lab how we can resize dynamically allocated arrays, but know that a static array like this cannot be deleted and resized later. • Note that the Contact and ContactBook class must be made independently of each other, since we will be adding contacts directly to the book by passing an actual Contact object to it. This means that the Contact class can NOT be made inside of the ContactBook class. 3.2 Methods in Contact class • Parameterized Constructor passing two string parameters (Required) • getName, which returns the name of the contact • getNumber, which returns the number of the contact • Display, which will not return anything, and just display the contact info. , 3.3 Required methods: ContactBook class • Default Constructor, Copy Constructor, and Assignment operator • Find – Takes in a string that can either be a phone number or a name and returns the found contact as a pointer. Returns a nullptr if a given string is not a name or a number in the contact system. • Add – Takes in a contact object and stores its memory address in the furthest-most empty position in the array. The current order of contacts in the array must be preserved. (Note: passing by value will result in a garbage pointer). It returns nothing. Also know that there will never be a test case that tries to add a Contact that already exists in the ContactBook, and this applies for all the addition functions, even the operators. • AddContacts – Takes in a vector of contact pointers, and stores all of it’s values in the class’s array, in the same order that they were in the vector. It returns nothing. • Display – Displays each contact in the contact book, in the order that they are stored in the array: Roland, 456-789-0123 Andres, 987-654-3210 George, 234-567-8901 • Alphabetize – sorts the array in alphabetical order based on contact name. Note that in this special case, Albert would come before Alberta. This should be the only function that can alter the order that the contacts are stored in the array. (see page 5 for info on std::sort) • the following operators: ◦ += Contact – Adds a single contact to a ContactBook object. ◦ += ContactBook – Adds all contacts from the passed in ContactBook to this object. Adding them to the back in the order they are in the other ContactBook’s array. ◦ + ContactBook – Adds two contact books together and returns the resulting ContactBook. ◦ -= Contact – Removes the Contact that matches the passed-in Contact. ◦ -= ContactBook – Removes all contacts from a passed in ContactBook from this object. ◦ – ContactBook – Same as above, but returns a new ContactBook object as the result instead of modifying the current one. ◦ != ContactBook – Same as above, but the not equal operator. 5 HELPFUL LINKS 4 Testing and Help 5 Helpful links • A good explanation of pointers • Explanation of → and . dereferencing operators ! While the implementation of any lab or project is entirely up to you (given that it meets our specifications), we recommend using std::sort for this lab! You can find the documentation here. Note that this can mean using functors or lambda which isn’t a topic we cover until later in the course. Knowing your way around the standard template library, especially std::sort, will be extremely helpful!
Objective Give practice with stacks input in C. Give practice with trees in C. Story Well the ship is fixed (sort of). The repair crew just left, but they did something awful. The ship has a completely different interior. Hallways have become blocked off and some walls were removed. You have been in communication with the repair crew. They apparently had to make the ship up to code or something. You are exhausted and want this ship to set sail as soon as possible. Now you are left with the daunting task of determining how many rooms your new ship’s layout can support. The new layout can be thought of as a series of rooms connected by corridors. Each corridor connects 2 rooms; no room is connected to itself via a corridor. There is exactly 1 series of distinct corridors that connects any pair of rooms. You are going to assume that no one should walk through someone’s quarters to reach another room. Because of this you will assume that (with the exception of the ship’s entrance) each possible room will be connected to exactly 1 corridor. You don’t have time to walk through the ship yourself, so you hired an employee to walk through each of the rooms. He came up with a unique room ID for each room they visited. Rather than telling you all the corridors that connect the rooms, your employee walked through all the corridors (each one exactly twice), and they kept a list of the rooms they visited by the IDs in the order in which they visited the room. Additionally each room ID was noted each time they entered the room. This means a room ID can appear multiple times. You are also worried that the rooms might be very far from the main entrance, so you will also track total distance (in terms of number of corridors) from all possible quarters to the main entrance. Problem Given a list of room IDs representing the order in which the employee visited the rooms, determine how many possible sleeping quarters the ship can have an the sum of the distances to each possible quarter. Input Input will consist of a series of integers each one on their own line. The series ends with the integer -1. No earlier integer in the series will be -1. The integer series represents the room IDs visited in the traversal that the employee executed. The employee started in the main entrance. It is guaranteed that the main entrance will be the last room ID before the -1. There will always be at least one ID that is not -1 in the input. Output Output should contain a single line containing 2 integers. The first integer represents the number of possible quarters the second integer represents the total distance (in terms of corridors) from each room to the main entrance. Sample Input Sample Output 1 3 1 10 4 8 4 10 1 5 1 -1 3 5 8 2 4 5 4 6 4 2 8 -1 2 6 Explanation Case 1 There are 6 rooms in the first case. The rooms have IDs, 1, 3, 4, 5, 8, and 10. The main entrance has an ID of 1. The rooms have a layout equivalent to the picture on the following page.The possible quarters are ID’d 3, 5, and 8, since none of them have a room that has to pass through them to reach the main entrance (room ID’d 1). The number of corridors to reach room 5 from the main entrance is 1. The number of corridors to reach room 3 from the main entrance is also 1. The number of corridors to reach room 8 from the main entrance is 3 (1 to 10, 10 to 4 and 4 to 8). The total number of corridors for all possible quarters is 1+1+3 = 5. Thus the output is 3 (number of possible quarters) and 5 (sum of corridors for the possible quarters). Case 2 The layout looks like the followingWith the main entrance being room 8. The number of possible quarters is 2 (room 6 and 5). The number of corridors to get to said quarters is 3 (for room 6) + 3 (for room 5). The total is 6. The output for the case is 2 (number of quarters) and 6 (corridor sum). Hints Reading Input: Use a while loop to process all the rooms. Graph: The input is a graph, where the rooms are the nodes and the corridors are the edges. Tree: The room graph forms a tree, because the number of paths between pairs of distinct nodes is exactly 1. Parents: Track the room that was visited prior (on the path back to the main entrance) to each room. This prior room is the parent node in terms of a rooted tree. When a parent is revisited via the inputted room sequence that means that the employee was heading back to the main entrance and left the current room. Once a room is left (back towards the main entrance) it will never be visited again in the employee’s walk. Possible Quarters: A room can only be a quarter, if the room has no children rooms. Room Distance: DO NOT walk back up the tree to find the distance for a possible quarter to the main entrance. Stack/Depth: Consider using a stack of nodes representing the path from the main entrance to the current room or storing the depth of a node to determine the distance from the main entrance to a possible quarter. The distance would be the size of the stack. The stack would also allow easy access to parent rooms. Grading Criteria ● Read/Write from/to standard input/output (e.g. scanf/printf and no FILE *) ○ 5 points ● Good comments, whitespace, and variable names ○ 15 points ● No extra input output (e.g. input prompts, “Please enter the number of friends:”) ○ 5 points ● Loop until a -1 is read in ○ 5 points ● “Store the depth” for a room ○ 10 points ● Track how many children a room has ○ 5 points ● Track the parent of each room ○ 5 points ● Programs will be tested on 10 cases ○ 5 points each No points will be awarded to programs that do not compile using “gcc -std=gnu11 -lm”. Sometimes a requested technique will be given, and solutions without the requested technique will have their maximum points total reduced. For this problem use a stack or a tree. Without this programs will earn at most 50 points! Any case that causes a program to return a non-zero return code will be treated as wrong. Additionally, any case that takes longer than the maximum allowed time (the max of {5 times my solutions time, 10 seconds}) will also be treated as wrong. No partial credit will be awarded for an incorrect case.
Objective Give practice with brute force and recursion in C. Story Your rescue team arrived at the malfunctioning boat, but they are having difficulties stopping the vessel. The damage is extensive and the engine refuses to cease even when the emergency shut off switch was engaged. There are known steps that can be taken to help stop the engine, and the rescue team has some tools that can also be used to help try to stop the engine. Examples of options include things like spraying the engine with foam, cutting off the air supply to the engine, and disconnecting the power from the engine. We are going to perform all of the actions sequentially. Each one will happen exactly once. The actions can be performed in any order. Currently, the goal is to drop the temperature of the engine enough that the engine will cease. For each action we know how much the engine temperature drops. We also know that an earlier action can increase or decrease the amount the engine temperature drops. Determine the event order that creates the best engine temperature decrease after performing all of them. Problem Given a list of actions that can reduce the temperature of the engine and a list of how much each action impacts the actions that come after it determine the order in which the action should be performed to maximize the temperature reduction. Input Input will begin with a line containing a single integer, n (1 ≤ n ≤ 11), representing the number of actions that can be performed. The following line contains n integers, the i-th representing the amount of temperature changed by the i-th action. The following n lines. The i-th line will contain n integers, the j-th representing the amount of temperature dropped when performing the i-th action strictly after the j-th action. All temperature changes will be in the range of -100,000 to 100,000. Output Output should be a line with n integers representing the order of the index (1 indexed) of the actions that maximizes the engine temperature loss. If there are multiple orders of actions, any one of them can be printed. Sample Input Sample Output 3 -10 -20 3 0 5 9 -13 0 -12 -5 -4 0 1 3 2 4 -1 10 -3 -1 0 4 -3 -6 1 0 3 1 -7 2 0 -1 -10 3 -1 0 1 4 2 3 Explanation Case 1 The first line tells the program that there are 3 actions that could be taken. The next line tells the program the amount that the temperature would drop or increase by for each action. The first listed action would drop the temperature by 10 units. The listed second action would drop the temperature by 20 units. The listed third action would raise the temperature by 3 units. If the first listed action is performed after the second, it would raise the temperature by 5 units. If the first listed action is performed after the third, it would raise the temperature by 9 units. If the second listed action is performed after the first, it would drop the temperature by 13 units. If the second listed action is performed after the third, it would drop the temperature by 12 units. Finally, if the third listed action is performed after the first, it would drop the temperature by 5 units. If the third listed action is performed after the second, it would drop the temperature by 4 units. There are 6 ways the actions can be executed. 1. 1 2 3 The first performed action (first listed action) drops the temperature by 10 units. The second performed action (second listed action drops the temperature by an additional 33 units (20 + 13). The current total units dropped is 43 units. The third performed action (third listed action) drops the temperature by an additional 6 units (-3 + 5 + 4). The final total units dropped is 49 units. 2. 1 3 2 The first performed action (first listed action) drops the temperature by 10 units. The second performed action (third listed action) drops the temperature by an additional 2 units (-3 + 5). The current total units dropped is 12 units. The third performed action (second listed action) drops the temperature by an additional 45 units (20 + 13 + 12). The final total units dropped is 57 units. 3. 2 1 3 The first performed action (second listed action) drops the temperature by 20 units. The second performed action (first listed action) drops the temperature by an additional 5 units (10 – 5). The current total units dropped is 25 units. The third performed action (third listed action) drops the temperature by an additional 6 units (-3 + 5 + 4). The final total units dropped is 31 units. 4. 2 3 1 The first performed action (second listed action) drops the temperature by 20 units. The second performed action (third listed action) drops the temperature by an additional 1 unit (-3 + 4). The current total units dropped is 21 units. The third performed action (first listed action) raises the temperature by an additional 4 units (-10 + 5 + 9). The final total units dropped is 17 units. 5. 3 1 2 The first performed action (third listed action) raises the temperature by 3 units. The second performed action (first listed action) drops the temperature by an additional 1 unit (10 – 9). The current total units raised is 2 units. The third performed action (second listed action) drops the temperature by an additional 45 units (20 + 13 + 12). The final total units dropped is 43 units. 6. 3 2 1 The first performed action (third listed action) raises the temperature by 3 units. The second performed action (second listed action) drops the temperature by an additional 32 units (20 + 12). The current total units dropped is 29 units. The third performed action (second listed action) raises the temperature by an additional 4 units (-10 + 5 + 9). The final total units dropped is 25 units. Dropping the temperature by 57 units is the best possible outcome. Thus the action order is 1, 3, and 2. Case 2 There are 24 possible action orders. The best one is 1, 4, 2, 3. In that order we ● Drop the temperature by 1 unit, ● Drop the temperature by an additional 11 units, ● Raise the temperature by 12 units, ● Drop the temperature by an additional 9 units. Hints BRUTE FORCE: Try every action order. It does not take too long. Use a permutations style recursive method to find all action orders. No Repeat: Don’t allow yourself to try the same action multiple times. Useless Data: The amount the temperature is dropped by an action (without respect to the action order; the second line of input) is not important. Those values are added to each action order attempted. The values can be ignored. Additionally, the values on the diagonal cannot impact your value since no action can be performed before/after itself. It might be worth it to zero them out after reading in the input. Global Values: Consider storing your values in global memory to reduce the amount of values passed into your recursive function. It does not save on runtime, but it might make your code easier to read. You should also consider storing the best order (and the amount of temperature it drops) in global memory as well. Grading Criteria ● Good comments, whitespace, and variable names ○ 15 points ● Use standard input/output ○ 5 points ● No extra input output (e.g. input prompts, “Please enter the number of friends:”) ○ 5 points ● Use a 2D array to hold the temperatures that are affected by action order ○ 10 points ● Create a way to evaluate the temperature some given action order ○ 10 points ● Store the best action order until all orders have been exhausted ○ 5 points ● Programs will be tested on 10 cases ○ 5 points each No points will be awarded to programs that do not compile using “gcc -std=gnu11 -lm”. Sometimes a requested technique will be given, and solutions without the requested technique will have their maximum points total reduced. For this problem use recursion. Without this programs will earn at most 50 points! Any case that causes a program to return a non-zero return code will be treated as wrong. Additionally, any case that takes longer than the maximum allowed time (the max of {5 times my solutions time, 10 seconds}) will also be treated as wrong. No partial credit will be awarded for an incorrect case.
This lab’s purpose is to provide students with experience in inheritance of classes and working with multiple classes. It is recommended that students use command line tools and editors for this lab (though it is not strictly speaking required). This lab will require students to build on their previous lab experience, in which a version of the cowsay utility was created.cowsay.py (Program Driver) Your program must accept command line arguments as follows: python3 cowsay.py -l Lists the available cows python3 cowsay.py MESSAGE Prints out the MESSAGE using the default COW python3 cowsay.py -n COW MESSAGE Prints out the MESSAGE using the specified COW In addition, this version of the utility handles a special set of Cow-derived Dragon class (and its subclasses). Whenever a dragon-type cow is selected, the display of the message must be followed by a line stating whether or not the dragon is fire-breathing:Cow Class __init__(self, name) // Constructor get_name(self) // Returns name of this cow object get_image(self) // Return image for this cow object set_image(self, image) // Sets the image for this cow object to image Dragon Class The Dragon class must be derived from the Cow class and must make all of its methods available. In addition, Dragon must provide the following methods: __init__(self, name, image) Constructor; creates a new Dragon object with the given name and image. can_breathe_fire() This method should exist in every Dragon class. For the default Dragon type, it should always return True. IceDragon Class The IceDragon class must be derived from the Dragon class and must make all of its methods available: __init__(self, name, image) Constructor; creates a new IceDragon object with the given name and image. can_breathe_fire() For the IceDragon type, this method should always return False. NOTE: Your output must match the example output *exactly*. Files: cowsay.py, cow.py, dragon.py, ice_dragon.py Method: Submit on CanvasPROGRAMMING FUNDAMENTALS 1 Lab 8: The Cow Strikes Back>python3 cowsay.py Hello World! Hello World! ^__^ (oo)_______ (__) )/ ||—-w | || || >python3 cowsay.py -n kitteh Moew-Moew! Moew-Moew! (“`-‘ ‘-/”) .___..–‘ ‘ “`-._ ` *_ * ) `-. ( ) .`-.__. `) (_Y_.) ‘ ._ ) `._` ; `` -. .-‘ _.. `–‘_..-_/ /–‘ _ .’ ,4 ( i l ),-” ( l i),’ ( ( ! .-‘>python3 cowsay.py -l Cows available: heifer kitteh dragon ice-dragon >python3 cowsay.py -n ninja Hello world! Could not find ninja cow!>python3 cowsay.py -n dragon Firey RAWRFiery RAWR |___/| / //|\ /0 0 __ / // | / / /_ / // | _^_’/ /_ // | //_^_/ /_ // | ( //) | // | ( / /) _|_ / ) // | _ ( // /) ‘/,_ _ _/ ( ; -. | _ _.-~ .-~~~^-. (( / / )) ,-{ _ `.|.-~-. .~ `. (( // / )) ‘/ / ~-. _.-~ .-~^-. (( /// )) `. { } / (( / )) .—-~-. -‘ .~ `. __ ///.—-..> _ -~ `. ^-` ///-._ _ _ _ _ _ _}^ – – – – ~ `—–‘ This dragon can breathe fire.PROGRAMMING FUNDAMENTALS 1 Lab 8: The Cow Strikes Back>python3 cowsay.py -n ice-dragon Ice-cold RAWRIce-cold RAWR |___/| / //|\ /0 0 __ / // | / / /_ / // | _^_’/ /_ // | //_^_/ /_ // | ( //) | // | ( / /) _|_ / ) // | _ ( // /) ‘/,_ _ _/ ( ; -. | _ _.-~ .-~~~^-. (( / / )) ,-{ _ `.|.-~-. .~ `. (( // / )) ‘/ / ~-. _.-~ .-~^-. (( /// )) `. { } / (( / )) .—-~-. -‘ .~ `. __ ///.—-..> _ -~ `. ^-` ///-._ _ _ _ _ _ _}^ – – – – ~ `—–‘ This dragon cannot breathe fire.
Objective Give practice with binary search in C. Story You will send a team to save them, but the rescue team will only be able to be sent once to a single location and takes 1 hour to arrive, so you must determine the exact location of the ship. Luckily you are able to borrow a satellite that passes over the ocean every hour. It can take a photo of only 1 nautical mile, but you can use this to determine if the ship has passed the location by picking up the traces of a wake, if the ship is at that location by picking up the picture of the ship, or if the ship has not yet reached that location by picking up nothing in the picture. You want to ensure that the ship is not stranded for too long. The ship has to be rescued in 24 hours (at most 23 pictures). Keep in mind that after the last picture the ship will move for a full hour while you launch the rescue team. Finally, your first photo will be exactly 1 hour after the initial distress signal was sent. Problem Write a program that when given the maximum starting speed of the ship and the maximum x coordinate, can ask for information at specific x-coordinates at most 23 times, and can at any point after a query can report the current location of the ship. Input Input will begin with a line containing 2 integers, S and L (1 ≤ S, L ≤ 100), representing the maximum possible speed of the ship in Knots and the maximum possible starting coordinate of the ship, respectively. Following this will be multiple lines. Each line contains a single response to one of your queries. The responses will be one of the following strings ● Wake – The ship has already passed by ● No Wake – The ship has not passed this location as of yet ● Boat! – The ship was captured in the photo The testing system will allow you to read the response only after your program prints the query and flushes the standard output (use fflush(stdout)). Output To make the queries your program should print to standard output. To ask for a photo of a location your program should output “? x” where x is the location to take the photo. To send the rescue team your program should output “! x” where x is the location of the ship. Your program must flush the output (use fflush(stdout)) after each query and after your command to send the rescue team. Sample Input Sample Output 3 3 No Wake Wake Wake Wake Boat! ? 3 ? 1 ? 3 ? 5 ? 10 ! 12 5 2 Wake Wake Wake Wake Wake ? 1 ? 5 ? 11 ? 18 ? 26 ! 32 Explanation Case 1 The boat has a speed of 2. Additionally the boat started at position 0.By the time the first picture happens the boat has moved to position 2.The sample took the picture at position 3. At that location there is no boat and no wake. When the next picture is taken the boat moves to position 4.This picture is taken at position 1. There is no boat, but there is a wake. When the next picture is taken the boat moves to position 6.The next picture is taken at position 3. At that location there is no boat, but there is now a wake. When the next picture is taken the boat moves to position 8.The next picture is taken at position 5. At that location there is no boat, but there is now a wake. When the next picture is taken the boat moves to position 8.The final picture is taken at position 10. At that location there is a boat. The rescue team is now sent out. At this point the boat has moved to position 12. Luckily, the sample requests to send the team to that position.Case 2 The boat started at position 2 with a speed of 5. The ship will be at location 7 during the first picture. The picture is taken at location 1. There is a wake at that point. The ship will be at location 12 during the second picture. The picture is taken at location 5. There is a wake at that point. The ship will be at location 17 during the third picture. The picture is taken at location 11. There is a wake at that point. The ship will be at location 22 during the fourth picture. The picture is taken at location 18. There is a wake at that point. The ship will be at location 27 during the fifth picture. The picture is taken at location 26. There is a wake at that point. The ship will be at location 32 when the sample sends out the rescue team. The rescue team is sent to location 32. There ship is at that location. Hints FLUSH Your Output: After every printf remember to fflush(stdout). Track ALL Possibilities: Keep track of all the possible boats that exist. There should be 1 possibility for every combination of speed and starting location. When your program takes a photo and gets feedback. Eliminate all the boats that would have generated a different output. Possibility Storage: You can store the possibilities in a 2D grid, indexed by the initial parameters of the ship, that contains a 0/1 indicating whether that possibility is still valid. The Midpoint: Your program should guess the “midpoint”. The midpoint is a bit unusual in this problem. At each time the photo is taken there is a list of possible locations that the ship could be (based on the speed/location combinations that have not been invalidated). The midpoint should be the ship location that roughly splits the “search space” (the location of all remaining valid combinations) in half. Midpoint Candidates: Don’t guess random valid ship locations. Instead loop through the list of ship locations and check if that ship location works as a “midpoint”. The midpoints should only be considered from the still valid ships. Extension: This problem was made easier from an alternative version where the max speed and location could be up to 1000. If you finish the version of the problem for homework try to consider how you could efficiently solve the problem for larger bounds. Grading Criteria ● Good comments, whitespace, and variable names ○ 15 points ● Use standard input/output ○ 5 points ● No extra input output (e.g. input prompts, “Please enter the number of friends:”) ○ 5 points ● Flush your output every time your print ○ 5 points ● Track the valid ship combinations ○ 10 points ● Check the effectiveness of a possible midpoint ○ 5 points ● “Move” the ships after each photo ○ 5 points ● Programs will be tested on 10 cases ○ 5 points each ○ 6 of these cases will have fixed values ○ 4 of these cases will be adversarial ■ Without being certain of the location of the ship you will get the case wrong No points will be awarded to programs that do not compile using “gcc -std=gnu11 -lm”. Sometimes a requested technique will be given, and solutions without the requested technique will have their maximum points total reduced. For this problem use a binary search. Without this programs will earn at most 50 points! Any case that causes a program to return a non-zero return code will be treated as wrong. Additionally, any case that takes longer than the maximum allowed time (the max of {5 times my solutions time, 10 seconds}) will also be treated as wrong. No partial credit will be awarded for an incorrect case.
