CMPE Project 4: Help the Santa Claus! Solution

:


“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 <inputfile> <outputfile>

Make sure that your final submission compiles and runs with these commands.
Sample Input File
Explanations


1
The number of trains go to green region
3
Capacity of each train
2
The number of trains go to red region
1 9
Capacity of each train
0
The number of reindeers go to green region

If there is no such reindeer this line will be empty
1
The number of reindeers go to red region
2
Capacity of each reindeers
4
The number of gift types i.e number of bags
ac 6 be 3 cd 4 ad 8
Types of bags and numbers of gifts in them respectively



ac
1
3








6



1

be
2





3


1

cd
1

1

4

1

4
9
ad
1


























Remark that it exceeds
capacity of the train,
only one of them can
be taken


8



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



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 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 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_<studentid>.zip No other type of submission will be accepted.










23.55 and after













New Year’s Day    Submission Day