Description
CmpE 250 Project 1 : Datalonya Student Houses Simulator
1 Introduction You are going to be implementing a Java program for simulating the distribution of student houses. You are going to be running this simulation by using the Java Collections Framework. 2 Details of the Project The University of Datalonya offers houses for the students. All houses are for one student only. But they can be in various conditions: old, new, needs renovation, broken oven, broken shower, new kitchen, new bed etc. According to these conditions each house has a rating point between 0 and 10. Students study at the university up to 8 semesters. If they are located at a house, they stay until graduation. But each student has his/her own criterion on house selection. This criterion is a threshold on the house’s rating. For example, if the student wants a house with minimum rating 4, then he/she is not located at houses with rating 2 or 3 (any rating below 4) even if they are the only available houses. New allocations are made at the beginning of each semester. House and student lists are checked for new allocations if possible. Now you are enrolled at the University of Datalonya Dormitory Office. The current list of houses and students are transferred to you. From now on, you are responsible for the allocation of the houses. 1 You are supposed to arrange the lists of houses and students in collections of your choice and simulate the allocations until all students in the list graduate. In your simulation, check for matching houses and students at every new semester. The output of your simulation is the list of students who cannot stay at any house. 3 Input/Output Format 3.1 Input Format The input will be given as a file argument. There are two types of input lines: house lines and student lines. The input lines will be in mixed order. You can assume that the input file is error free. You don’t have check for data. A typical line for a house is like this: h There are 4 parts which are single-space separated in a line for a house. The first part, the letter h, is the house indicator. The second part, , is the id of the house. The third part, , is the duration as the number of semesters that the house is full. If the duration is 3, then this house will be available after 3 semesters. The last part, , is the rating which shows the good or bad condition of the house. A typical line for a student is like this: s There are 5 parts which are single-space separated in a line for a student. The first part, the letter s, is the student indicator. The second part, , is the student id. The third part, , is the name of the student. The fourth part, , is the duration as the number of semesters that the student will study at the University of Datalonya. For example, if the duration is 3, then this student will graduate after 3 semesters. Of course, max duration can be 8 for a student. The last part, , is the rating which shows the minimum rating criterion of the student to accept a house. For example, if the rating parameter for a student is 3.2, then this student can only stay at houses with rating equal to or greater than 3.2. Your simulation program should read the input file and create appropriate 2 collections for students and houses. Then process these collections until all students graduate. Your program should process houses and students in their id order. For example if there are two houses with ids 1 and 3 that are available at the moment, first the house with id 1 is allocated if possible. For students, if there are two students with ids 123 and 126 whose rating criterion holds for a house, the student with id 123 gets the house. 3.2 Output Format Your program should end when the waiting student list is empty. The output of your program is the list of students that couldn’t stay at any of the houses. You should create a .txt file and print one student name at a line. The output student list must be in ascending order of student id but only names will be printed in output file. 3.3 Java Project Outline Your java project will be named Project1. Your entry class for the project will be named project1main. All your .java files will be under folder Project1\src. Your project should be compatible with Java 17. Your program will be compiled with below command: javac Project1/src/*.java -d Project1/bin -target 17 The input and output files can be at any folder. Design your code in order to accept full path for file arguments. Your program will be run with below command: java project1main For example: java project1main input.txt output.txt java project1main somepath/input.txt someotherpath/output.txt 3 4 Examples For the input data: h 1 0 8 s 10 Ali 3 9 h 2 0 4 h 3 0 7 s 11 Melis 3 9 s 12 Ayse 5 4 h 4 6 9 s 13 Selim 5 3 h 5 5 5 The correct result is: Ali Melis 5 Grading Grading of this project is based on the automatic compilation and run and the success of your code in test cases. If your code compiles and runs with no error, then you will get 10/100 of the project grade. The rest of your grade will be the sum of collected points from each test case. Each test case will have equal weight. Maximum project grade is 100. 6 Warnings 1. This is an individual project. 2. All source codes are checked automatically for similarity with other submissions and exercises from previous years. Make sure you write and submit your own code. Any sign of cheating will be penalized and you will get -50 points for the project and you will get F grade in case of recurrence in any other project. 3. There will be time limit on test cases, so it is important to write your code in an efficient manner. 4 4. You can add as many files as you can as long as they are in the src folder and your project can be compiled as above. But the entry point of your program should be project1main.java. 5. Make sure you document your code with necessary inline comments and use meaningful variable names. Do not over-comment, or make your variable names unnecessarily long. This is very important for partial grading. 7 Submission Details You will zip up your project folder and submit on Moodle as a single .zip file. The name of the zip file is Cmpe250 Project1 .zip No other type of submission will be accepted. 5
CmpE 250 Project 2: ExcelFed
1 Introduction Heraclitus once said “The only constant in life is change”. Heraclitus was a wise man, indeed, but he missed an exception: if you take CMPE 250, you solve a Discrete Event Simulation (DES) project! Well, but what is DES? Enter, Wikipedia: “A discrete-event simulation (DES) models the operation of a system as a (discrete) sequence of events in time. Each event occurs at a particular instant in time and marks a change of state in the system. Between consecutive events, no change in the system is assumed to occur; thus the simulation time can directly jump to the occurrence time of the next event”. In other words, DES is the representation of a certain process by simulating certain events which occur at certain times. Hence, time is not continuous in DES and progress according to the events. As a demonstrative example, a process of taking a coffee can be simulated as follows: • TIME: 09:00 Go into the checkout queue. • TIME: 09:05 Order your coffee and make your payment. • TIME: 09:10 Go into the serving queue. • TIME: 09:15 Wait for the preparation of your coffee and enjoy your free time. • TIME: 09:20 Grab your coffee and enjoy! Note that in DES the only things that count are events and everything else is ignored. In the case of the customer, until 09:20 only 5 things happened. Additionally, the time progressed in a discrete fashion (i.e. jumped from one event to the next one). 1 In this project, you are expected to simulate training procedure of ExcelFed, which is a tennis club founded by his excellency 1For further reading about DES you can visit here or Wikipedia 1 2 Details of the ExcelFed Do you know his excellency? This is not even a question, everyone knows him. Yes, I am talking about Roger Federer2 who is the best tennis player ever! He has decided to retire since he is not young enough to continue his career. However, he wants to transfer his great experience to the new generation. That’s why, he has founded ExcelFed. Roger is very experienced so he knows almost everything that plays a huge role in the development of the tennis player. He has already hired great nutritionists and chefs. Additionally, he has a consulting team consists of Rafael Nadal and Novak Djokovic. Furthermore, he has rent nice tennis courts. His aim is to train children in very good conditions so that there are better tennis players. There is one “little” problem though. He needs great training coaches, masseurs, and physiotherapists but he does not know how many he needs. He may hire many staffs but this would be a waste of money and there are not many outstanding staffs. Therefore, he decided to simulate the training procedure of ExcelFed with fictional players and staffs to find how many of them would be enough. However, his relationship with simulation tools and coding is terrible so he needs your help! Let Roger provide more detail. • There might be multiple training coaches, masseurs and physiotherapists depending on the simulation configuration. In this case, every physiotherapist has his/her own service time and training, and massage duration depending on the player’s need. • There are exactly three queues in the system: one for training, one for massage and one for physiotherapy. So, each coach shares a common queue and similar for the others. • The training queue works in first-come-first-served fashion. Thus, the first player to enter the queue is served before the others. If two players arrive at the same time, the one with the lower ID is served first. When the training of the player is finished, he/she enters the physiotherapy queue, immediately. • Since more training time requires more urgent rehabilitation, physiotherapy queue works in a prioritized manner. Therefore, in this queue, the more the training time, the higher the priority. If there are more than one player that have the same training time, then the one that arrived earlier is served before. If they arrived at the same time as well, then the one with the lower ID is served first. Note that, one player may come to the training more than one time, for the prioritization, you should consider only the current training time not the cumulative. • Because massage is an advanced service, players should deserve them by their skills. Hence, in the massage queue, the higher the skill level, the earlier the service. If there are more than one player that are in the same skill level, then the one that arrived earlier is served before. If they arrived at the same time as well, then the one with the lower ID is served first • For all of the services, players visit the first available staff for the service (the available staff with the smallest ID) when they leave the queue. 2A video to enjoy the talent of Roger Federer. 2 • Each player is allowed to take at most 3 massage service. Hence, whenever a player attempts to enter the massage queue 4th time, this is called an “invalid attempt”. • Since it is hard for the players to estimate how much time they spend in the queues, there could be some cases such that players may try to come to the training or massage when they are already in the training, physiotherapy or massage process. These attempts should be “canceled” so they are called “canceled attempts”. • One can enter the physiotherapy queue only after the training, no direct entrance is possible. Below, is a schematic description of the training procedure of his excellency. Figure 1: A schema of the queues Therefore, for our purposes, there are two types of events triggered by the players: coming to the training and massage request. Keep also in mind that internal events, such as leaving the training, should also be triggered by the simulation. Roger Federer expects you to simulate the training procedure of ExcelFed using these external and internal discrete events and collect some statistics. 3 Input & Output 3.1 Input Roger provides all simulation configuration files in the following format: • The first line contains an integer N that denotes the total number of players in ExcelFed. • Each of the next N line contains two integer: the ID of the player and his/her skill level. These players will be given in sorted order by ID. • The next line is the line of an integer A that denotes the total number of arrival to the training and massage. 3 • Each of the next A lines contains a character At denoting the type of arrival (either “m”(massage) or “t”(training)), an integer denoting the ID of the player, the second T that denotes the arrival time, and d duration of the process. These events will not be given in sorted order. • The next line comprises an integer Sp that denotes the number of physiotherapists and a list of floats of size Sp. The i th element of the list denotes the service time of the i th physiotherapist. • The last line contains two integers: Sc that denotes the number of training coaches and Sm that denotes the number of masseurs. Table 1 demonstrates an example input provided by Rafael Nadal, the best consultant in the consultancy team. Sample Input File Explanations 3 There are 3 players. 0 2 The player with ID 0 has a skill level 2. 1 3 The player with ID 1 has a skill level 3. 2 1 The player with ID 2 has a skill level 1. 9 There 9 arrivals in total. t 0 1 1.2 The player with ID 0 arrives for the training at second 1 and the training will take 1.2 seconds. t 1 1.2 2 m 0 6 3 The player with ID 0 arrives for the massage at second 6 and the massage will take 3 seconds. m 1 6.3 1.8 m 0 10 1.2 t 2 10.1 4 m 0 15 1.2 m 2 16 1.5 m 0 20 3 1 2 There is 1 physiotherapist and her service time is 2 seconds. 1 1 There are 1 training coach and 1 masseur. Table 1: Sample Input with Explanations 3.2 Output Roger needs you to collect the following statistics to evaluate the configuration and output them in separate lines, in the order they are given. Please round the statistics to exactly 3 decimal points. In case you cannot report any of the following 15 statistics, print -2 for each of them in order to adhere the output format. 1. Maximum length of the training queue. 2. Maximum length of the physiotherapy queue. 3. Maximum length of the massage queue. 4. Average waiting time in the training queue. 5. Average waiting time in the physiotherapy queue. 4 6. Average waiting time in the massage queue. 7. Average training time. 8. Average physiotherapy time. 9. Average massage time. 10. Average turnaround time (Turnaround time: Total time passed from the training queue entrance until leaving the physiotherapy service.) To compute, sum all turnaround times and divide it by the number of turnarounds, which is also equal to the number of total training arrivals. 11. ID of the player who spent the most time in the physiotherapy queue and the waiting time of that player in seconds. If more than one player spent the same amount of time, choose the one with the smallest ID. 12. ID of the player who spent the least time in the massage queue and the waiting time of that player in seconds, among the ones who took three massage services. If more than one player spent the same amount of time, choose the one with the smallest ID. If there is no player that took three massage services, print -1 for both. 13. Total number of invalid attempts to get a message service. 14. Total number of canceled attempts including both training and massage attempts. 15. Total seconds passed during the whole simulation. Nadal also showed the courtesy to share the expected output for the input in Table 2 with explanations. He also showed the progress of queues and services in Table 3 where the numbers in the parenthesis in the“service” columns represent the number of remaining seconds to finish the process. 3.3 Java Project Outline Your java project will be named Project2. Your entry class for the project will be named project2main. All your .java files will be under folder Project2/src. Your project should be compatible with Java 16. Your program will be compiled with below command: javac Project2/src/*.java -d Project2/bin –release 16 The input and output files can be at any folder. Design your code in order to accept full path for file arguments. Your program will be run with below command: java project2main Make sure that your final submission compiles and runs with these commands. 5 Output File Explanation 1 Between seconds 1.2 and 2¸c2 Player 1 waits for the training. 0 No one waits for the physiotherapist. 1 Player 1 and Player 0 waits for the massage but not together so the length of the queue is at most 1. 0.333 In total, there are 3 training events and only Player 1 waits for 1 second so the answer is 1/3. 0 No waiting for the physiotherapy queue. 0.7 Player 1 waits for 2.7 seconds and Player 0 waits for 0.8 seconds so in total 3.5 seconds waiting. Also there are 5 valid massage attempts so 3.5/5. 2.4 Total training time is 1.2+3+4 so 7.2 and the answer is 7.2/3. 2 Since there is 1 physiotherapist and her service time is 2 seconds average is also 2 seconds. 1.44 Total massage time is 3+1.2+1.2+1.8 so 7.2 and the answer is 1.44. 4.733 Player 0 arrives at 1 and leaves the physiotherapy service at 4.2. Player 1 arrives at 1.2 and leaves the physiotherapy service at 6.2. Player 2 arrives at 10.1 and leaves the physiotherapy service at 16.1. 0 0 No waiting in physiotherapy queue so the smallest ID is chosen. 0 0.8 Only Player 0 takes 3 massage services. 1 Player 1 attempts to take 4 massage services 1 of which is invalid. 1 Massage attempt by Player 2 at 16 is canceled. 20 It is the end of the last event which is the invalid massage attempt by Player 0. Table 2: Expected Output File and Explanation of each Statistic Second Training Queue Training Service Physiotherapy Queue Physiotherapy Service Massage Queue Massage Service 1 – Player 0 (2.2) – – – – 1.2 Player 1 Player 0 (2.2) – – – – 2.2 – Player 1 (4.2) – Player 0 (4.2) – – 4.2 – – – Player 1 (6.2) – – 6 – – – Player 1 (6.2) – Player 0 (9) 6.2 – – – – – Player 0 (9) 6.3 – – – – Player 1 – 9 – – – – – Player 1 (10.8) 10 – – – – Player 0 Player 1 (10.8) 10.1 – Player 2 (14.1) – – Player 0 Player 1 (10.8) 10.8 – Player 2 (14.1) – – – Player 0 (12) 12 – Player 2 (14.1) – – – – 14.1 – – – Player 2 (16.1) – – 15 – – – – – Player 0 (16.2) 16.1 – – – – – Player 0 (16.2) 16.2 – – – – – – Table 3: Step by step progress of the queues and services. Numbers in the parentheses denote the exact second to leave the service. 4 Grading Grading of this project is based on the automatic compilation and run and the success of your code in test cases. If your code compiles and runs with no error, then you will get 10/100 of the project grade. The rest of your grade will be the sum of collected points from each test case. Each test case will have equal weight. However, each statistic may not contribute to the overall point for the test case equally. We haven’t decided about their weights, as soon as 6 we decide, we will share with you. Maximum project grade is 100. If your submission is not auto-runnable, then you will receive 0 at first and then have to issue an objection. 5 Warnings 1. This is an individual project. 2. All source codes are checked automatically for similarity with other submissions and exercises from previous years. Make sure you write and submit your own code. Any sign of cheating will be penalized and you will get -50 points for the project and you will get F grade in case of recurrence in any other project. 3. There will be time limit on test cases, so it is important to write your code in an efficient manner. 4. You can add as many files as you can as long as they are in the “src” folder and your project can be compiled as above. But the entry point of your program should be “project2main.java”. 5. Make sure you document your code with necessary inline comments and use meaningful variable names. Do not over-comment, or make your variable names unnecessarily long. This is very important for partial grading. 6 Submission Details You will zip up your project folder and submit on Moodle as a single .zip file. The name of the zip file is Cmpe250 Project2 .zip No other type of submission will be accepted. Some tips regarding the project 1. First, ensure to understand the project with all definitions and concepts before implementing. DO NOT START CODING RIGHT AWAY!. When you are comfortable with project in every aspect, it is highly recommended to simulate some test cases by hand and think of edge cases. Then, you will be ready to start coding. Otherwise, you might end up like in Figure 2 2. We do think that this project is one of the most important ones in this course. Therefore, we suggest starting this project early(not on the last day!). 3. For a more clean and understandable code, try to code object-oriented. Think about the classes that you can use. An object-oriented design will make the code easier to develop and to debug. 7 Figure 2: Starting to Code Right Away 8
CmpE 250 Project 3: A Love Story
1 Introduction As Shakespeare once said “i am to wait, though waiting so be hell…”, it is an obvious fact that waiting is the worst thing in the world. Do not worry!!! Our hard-working team works really hard and saves you the burden of waiting for the next project. No thanks needed, we are here for you. Mecnun and Leyla are two lovers who live in the Anatolian country. They try to come together but Leyla’s father is preventing them from doing so. Recently Leyla has tried to convince her father and she eventually manages to do. But her father offers a condition for Mecnun that he has to reach their town in time less than or equal to a threshold. The father sets the threshold and writes it to a piece of paper and hides the paper. Mecnun will be informed about the challenge but he will not be provided any information about the time that was set. The countdown for Mecnun will start at the moment he departs from his city and if he can arrive in time Leyla’s father will let them marry. Mecnun has a map of the Anatolian country which demonstrates all land routes over the country and their lengths. The country is divided into two regions by a river. Leyla and Mecnun are in the same region of the country but in different cities. Leyla’s city is the only city in the country where there are bridges for crossing to the other side of the country. For this reason, anyone who wants to cross over to the other side should visit this city. Two cities can be considered neighboring cities if there is a road between them. The roads of the country are one-way for the vehicles and two-ways for the pedestrians. Mecnun will take a bus while going to Leyla to be able to reach fast. Each road has a bus service of its own and there is always a bus service available at any given time. Every bus has the same constant velocity. Mecnun and Leyla are planning a honeymoon in which they would be traveling on foot to all the cities of the other side of the country. But each pedestrian has to pay a sidewalk-tax which is equal to the length of the road. If they can’t find a decent travel route for their plan, 1 they will have to stay in the city where Leyla lives. According to the legend, if they can’t get together, Mecnun will disappear. 2 Details • For each case output consists of a list of integers and one integer, list1 and int1 . List1 indicates the output generated for Mecnun’s path to reach Leyla. int1 indicates the output generated for the Honeymoon path. • Mecnun does not know the time set by the father, so he must take the shortest possible route. The shortest route to be used in list1 should be containing the IDs of the cities passed starting from Mecnun’s city to Leyla’s city. If there is no route from Mecnun’s city to Leyla’s city, list1 should contain only -1 • When Mecnun tries to reach Leyla’s city, he cannot get over the bridge. On the honeymoon, they can only visit Leyla’s city + cities of other side of the country.(For the sample map illustrated in Schema 1, only c7, d1, d2, d3, and d4 cities can be visited on the honeymoon.) • If Mecnun can reach Leyla, Leyla’s father will compare the time he arrived with the time on the paper and come to a decision. Since the speed of the buses is 1br/second, the arrival time is equal to the total length of the path. • Mecnun and Leyla are planning to walk around all the cities of the other side of the country and have the walkthrough honeymoon with the lowest sidewalk-tax. The roads traveled are subject to a sidewalk-tax proportional to their length, and after the tax is paid once, subsequent uses of the road are free of charge. In this case, the length of the path they walk does not matter. The sidewalk-tax paid must be the lowest and the route must include all cities of the other side of the country. The tax paid by Mecnun will be the int1 part of the output. • If there is no such honeymoon route, Mecnun stays in Leyla’s city and int1 should be -2. • If they cannot get married, Mecnun disappears as per the legend. In this case int1 should be -1. 3 Input & Output 3.1 Input • The first line represents the time set by Leyla’s father. • The second line represents the total number of cities in the Anatolian country. • The third line represents the ID of the city where Mecnun lives and the ID of the city where Leyla lives, respectively. 2 • Each next line will give the ID of a city of Anatolian country and the IDs and lengths of the cities that can be reached by vehicle from that city in pairs. For example: If there is a way from c1 city to c2, c3, and c4 cities of length 1, 2, and 3 respectively. Input line will be c1 c2 1 c3 2 c4 3 If there is no way from c2, input line for c2 will be c2 Sample Input File Explanations 8 Time limit determined by Leyla’s father is 8. 11 The country has 11 cities. IDs start with c represents the cities of the side where Leyla and Mecnun lives and IDs start with d represents the cities of the other side of the country. c1 c7 The ID of the Mecnun’s city and the ID of the Leyla’s city respectively. c1 c2 1 c3 3 c5 5 The city with ID 1 has a way to c2, c3 and c5 with length of 1,3 and 4 respectively. c2 c4 6 c5 3 c6 5 The city with ID 2 has a way to c4, c5 and c6 with length of 6,3 and 4 respectively. c3 c4 2 c6 2 The city with ID c3 has a way to c4 and c6 with length of 2 and 2 respectively. c4 c7 3 The city with ID c4 has a way to c7 with length of 3. c5 c7 2 The city with ID c5 has a way to c7 with length of 2. c6 c7 1 The city with ID c6 has a way to c7 with length of 1. c7 d1 2 d2 3 d4 5 The city with ID c7 has a way to d1, d2 and d4 with length of 2,3 and 5 respectively. d1 d2 4 d3 2 d4 3 The city with ID 8 has a way to d2, d3 and d4 with length of 4,2 and 3 respectively. d2 d3 1 The city with ID d2 has a way to d3 with length of 1. d3 d4 4 The city with ID d3 has a way to d4 with length of 4. d4 d2 4 The city with ID d4 has a way to d2 with length of 4. Table 1: Sample Input with Explanations d1 d2 d3 d4 c7 c1 c2 c3 c5 c4 c6 4 2 1 3 4 4 2 3 5 1 3 5 6 3 5 2 2 3 2 1 River Schema 1: A schema of the sample Anatolian country 3 3.2 Output 1. For each case there will be two lines of output. First line will be list1 and second line will be int1. 2. List1, Mecnun’s path of reaching Leyla (if he cannot reach -1 should be written) should be written. 3. Int1, the tax paid on the Honeymoon route if it is possible. (If Leyla and Mecnun don’t marry -1 should be written but if they did not find a suitable honeymoon route -2 should be written.) 4. If there is more than one possible output for a test case, you can use any. The program used for grading will test their accuracy. Output File Explanation c1 c2 c5 c7 or c1 c3 c6 c7 The path that Mecnun used to reach Leyla. Since there are two paths with the same minimum length of 6, one of them should be on the output file. 16 The side-walk tax paid on the Honeymoon route. (c7,d1), (d1,d4), (d1,d3) and (d2,d3) ways are used so (2+3+2+1)*2=16. Table 2: Expected Output File and Explanation of each Statistic 3.3 Java Project Outline Your java project will be named Project3. Your entry class for the project will be named project3main. All your .java files will be under folder Project3/src. Your project should be compatible with Java 16. Your program will be compiled with below command: javac Project3/src/*.java -d Project3/bin –release 16 The input and output files can be at any folder. Design your code in order to accept full path for file arguments. Your program will be run with below command: java project3main Make sure that your final submission compiles and runs with these commands. 4 Grading Grading of this project is based on the automatic compilation and run and the success of your code in test cases. If your code compiles and runs with no error, then you will get 10/100 of the project grade. The rest of your grade will be the sum of collected points from each test case. Maximum project grade is 100. If your submission is not auto-runnable, then you will receive 0 at first and then have to issue an objection. 4 5 Warnings 1. This is an individual project. 2. All source codes are checked automatically for similarity with other submissions and exercises from previous years. Make sure you write and submit your own code. Any sign of cheating will be penalized and you will get -50 points for the project and you will get F grade in case of recurrence in any other project. 3. There will be time limit on test cases, so it is important to write your code in an efficient manner. 4. If the entire path you find is not suitable, you cannot get points for that route. Please don’t object like ”but my route is correct except for the last two cities” 5. Again, if the tax amount is not equal to correct tax amount you cannot get points. Please don’t object like ”but my amount is just one less than the correct one” 6. You can add as many files as you can as long as they are in the “src” folder and your project can be compiled as above. But the entry point of your program should be “project3main.java”. 7. Make sure you document your code with necessary inline comments and use meaningful variable names. Do not over-comment, or make your variable names unnecessarily long. This is very important for partial grading. 6 Submission Details You will zip up your project folder and submit on Moodle as a single .zip file. The name of the zip file is Cmpe250 Project3 .zip No other type of submission will be accepted. 7 Some tips regarding the project 1. You need to know how the minimum weighted path on a directed graph is found for the first part of the project. 2. You should also know what a minimum spanning tree is to solve second part of the problem. 3. We do think that this project is one of the most important ones in this course. Therefore, we suggest starting this project early(not on the last day!). 5 Figure 1: Pseudo code for implementation of MST Figure 2: When someone says ”I love you” 6
CMPE 250 Project 4: Help the Santa Claus!
“As the year draws to a close, I have lots of gifts to give but I don’t have an optimal arrangement to distribute them. Let’s try together not to leave empty under the Christmas tree as much as possible. All I want for the new year, Cmpe students who make everything easier with their algorithms.” 1 Introduction Hi, there! Firstly, thank you all in advance for helping me on distributing the gifts. But it won’t be that straightforward because I have various gifts to distribute to different regions. I will explain the properties of gifts and how we will distribute them. Santa Claus Expresses and Santa Claus’s reindeers will help us but unfortunately, they can carry gifts as much as their capacities. Therefore, in some cases, it will be impossible to deliver all gifts to their owners. At this point, I need your help. Can you help me to figure out the minimum number of gifts that can’t be delivered? 2 Details There are two kinds of regions, which we call the green region and the red region. Therefore, trains and reindeers can be classified as those going to the green region and the red region. Our gifts are in the bags, and we should distribute them to trains and reindeers according to the properties of the bag. You can consider that the same type of gifts is in the same bag, and we want to distribute them properly. Properties of bags are as follow, remark that one bag has more than one property a. Each of the gifts in this bag type should be distributed through different vehicles, i.e. there are no 2 gifts from the same bag on the same train or reindeer. b. Each of the gifts in this bag type should only be distributed to green regions. c. Each of the gifts in this bag type should only be distributed to red regions. d. Each of the gifts in this bag type should only be distributed by train. e. Each of the gifts in this bag type should only be distributed by reindeer. If it’s not specified, assume that gifts can be distributed to all regions, and both by train and reindeer. Let’s look at some examples of bag types. o bd can be distributed only by trains which go to green regions o ace can be distributed only by reindeers which go to red regions and there are no 2 gifts from this bag on the same reindeer o c can be distributed only to red regions, both by trains and reindeers o d can be distributed only by trains, to both the red and the green regions o a only constraint is that there are no 2 gifts from this bag on the same vehicle o bc invalid, it won’t be given as an input to you because it is a contradictory o de invalid, it won’t be given as an input to you because it is a contradictory 3 Input & Output 3.1 Input • The first line represents the number of Santa Claus Expresses that are going to the green region. • The second line will give the capacities of each of these trains. • The third line represents the number of Santa Claus Expresses that are going to the red region. • The fourth line will give the capacities of each of these trains. • The fifth line represents the number of Santa Claus’s reindeers that are going to the green region. • The sixth line will give the capacities of each of these reindeers. • The seventh line represents the number of Santa Claus’s reindeers that are going to the red region. • The eighth line will give the capacities of each of these reindeers. • The ninth line represents the number of bags. • The tenth line will give the type of bags and number of gifts in it. 3.2 Output • For each test case, there will be one line output that gives the minimum possible number of gifts that can’t be distributed. 3.3 Java Project Outline Your java project will be named Project4. Your entry class for the project will be named project3main. All your .java files will be under folder Project4/src. Your project should be compatible with Java 16. Your program will be compiled with the below command: javac Project4/src/*.java -d Project3/bin –release 16 The input and output files can be in any folder. Design your code in order to accept the full path for file arguments. Your program will be run with the below command: java project4main Make sure that your final submission compiles and runs with these commands. Sample Input File Explanations 1 3 2 1 9 0 1 2 4 ac 6 be 3 cd 4 ad 8 The number of trains go to green region Capacity of each train The number of trains go to red region Capacity of each train The number of reindeers go to green region If there is no such reindeer this line will be empty The number of reindeers go to red region Capacity of each reindeers The number of gift types i.e number of bags Types of bags and numbers of gifts in them respectively The maximum possible number of gifts that can be distributed is 9. The total number of gifts is 21. Therefore, the minimum possible number of gifts that cannot be given is 12. Sample Output File Explanations 12 The number of gifts that cannot be distributed 6 3 4 3 1 ac be cd 9 2 8 ad 1 1 1 1 1 1 4 Remark that it exceeds capacity of the train, only one of them can be taken 4 Grading The grading of this project is based on the automatic compilation and run and the success of your code in test cases. If your code compiles and runs with no error, then you will get 10/100 of the project grade. The rest of your grade will be the sum of collected points from each test case. The maximum project grade is 100. If your submission is not autorunnable, then you will receive 0 at first and then have to issue an objection. 5 Warnings 1. This is an individual project. 2. All source codes are checked automatically for similarity with other submissions and exercises from previous years. Make sure you write and submit your own code. Any sign of cheating will be penalized and you will get -50 points for the project and you will get an F grade in case of recurrence in any other project. 3. There will be a time limit on test cases, so it is important to write your code in an efficient manner. 4. You can add as many files as you can as long as they are in the “src” folder and your project can be compiled as above. But the entry point of your program should be “project4main.java”. 5. Make sure you document your code with necessary inline comments and use meaningful variable names. Do not over-comment, or make your variable names unnecessarily long. This is very important for partial grading. 6 Submission Details You will zip up your project folder and submit on Moodle as a single .zip file. The name of the zip file is Cmpe250_Project4_.zip No other type of submission will be accepted. 23.55 and after New Year’s Day Submission Day
