Description
2 Amazon
Congratulations, you have just been hired by Amazon ! They would like to
automate their warehouses and are asking you to code the basic outline they
will be using.
Automation in real-life There was automation far before computers were
invented. For instance, John Kay invented the flying shuttle (he received the
patent for his invention in 1733) that enabled the automation of looms (used
to weave cloths). This was one of the great contributors to the industrial
revolution. Nowadays, automation is expanding very quickly. Some striking
examples include an almost fully automated plant in the delivery industry in
Tianjin (China), receptionists who are replaced with robots or screens or the
treatment of information that is done by facebook, google etc (or the grading
of this course).
We won’t be discussing here the societal changes (both positive — automation of tedious or dangerous tasks — or negative — removal of jobs)
that will come with these changes.
Structure of the code that is provided to you You have five files that
are provided to you.
There are four classes.
First there are Box and its subclass UrgentBox. A Box has a unique
identifier, a height and a length. They also have two fields next and previous
that will be useful to construct linked lists.
A Shelf is where you store Boxes. A Shelf has a length and a height.
You can only store a Box on a Shelf if it fits the remaining space (in height
and in length). Boxes are stored in a two-way linked list.
Finally, a Warehouse contains an array of Shelf and two linked lists
which correspond to Boxes and Urgentboxes that need to be shipped. We
assume that a Warehouse contains at least one Shelf.
The class Warehouse contains two methods print and printShipping
that are useful to test your code. We have only provided a very scarce testing
framework in Tester.java and you should expand it.
Sort storage The height field is really important : you cannot put a box
that is 10 high into a spot that is 5 high. But at the same time, you do
not want to put a box that is 10 high onto a shelf that is 30 high if there is
some space left on a shelf 15 high. To make it simpler to place a box on the
3
optimal shelf, you are first going to organize (sort) the shelves by increasing
order of height.
Question 1. Implement merge sort in Warehouse to sort all shelves by increasing order of height. You will have to code mergeSort (divide part of
merge sort) and merge (merging part). You can refer yourself to the slides of
lecture 9 for the detailed algorithm (be careful, the indices in an array start
at 0 in java). You can assume that the maximal height of a Shelf is 1000.
For the other methods that you are going to implement, you can assume
that storage is already sorted.
Add Boxes Your warehouse is now ready ! You are starting to get boxes.
You need to put them on the shelves : each box on its optimal shelf. This
is what you are going to code now : first how to add a box on a shelf and
second decide which shelf from the warehouse to put the box onto (and do
it).
Question 2. Implement addBox in Shelf. Here you can assume that the
box given in argument fits both in height and length so you don’t need to
check it in this function. You will have to add it to the last position on the
Shelf.
Question 3. Implement addBox in Warehouse : find the smallest shelf with
enough space available for the box given in argument, add the box on this
shelf and return the noProblem message. If there is no such shelf, do not do
anything to the warehouse and return the problem message.
Shipping Boxes Ultimately, you want to send to each customer what he
ordered from Amazon. You are going to implement this part now. First, you
are going to implement the method that removes a box from the shelf it was
on, then you are going to implement an auxiliary method that puts a box
into the appropriate shipping list and finally you are going to implement the
method that finds the box with a given id, removes it from its shelf and put
it into the corresponding shipping list.
Question 4. Implement removeBox in Shelf. The argument is the id String
of a box. If you can find a Box with that identifier, remove it from the
Shelf and return the box you have found. Do not forget to update all the
fields that need to be. If there is no Box on that Shelf, return null.
Question 5. Implement addToShip in Warehouse. The argument given is
a Box. If that box is an Urgentbox, it is added to the beginning of the
4
toShipUrgently list. Otherwise it is added to the beginning of the toShip
list. Do not forget to update all the fields that need to be. The method
returns noProblem if everything was done successfully, problem otherwise.
The method addToShip is an auxiliary method for the method shipBox
that you will code next.
Question 6. Implement shipBox in Warehouse. The argument given is
the identifier of a Box. If a Box with such identifier exists, remove it from
its corresponding Shelf and add it to its corresponding shipping list, then
return noProblem. If no such Box exists in the entire warehouse, return
Problem.
Moving Boxes around Your warehouse is now fully functional : each day
you receive and ship boxes. But the placement of the boxes may become non
optimal. Let us see why on an example : there are two shelves with height
15 and 20 respectively and length 10 for both. You receive a first box of
height 15 and length 10. You place it on the first shelf (of height 15). You
now receive a second box of height 15 and length 10, so you place it on the
second shelf. And then you ship the first box. So the first shelf is empty and
the second shelf has the box of height 15. Now if you receive a third box of
height 16, you have to send it back saying “sorry, no room left”. But if you
had moved the second box on the first shelf, you could have stored the third
box on the last shelf !
You are going to implement this reorganization of the warehouse, first for
a single box, then for the entire warehouse.
Question 7. Implement moveOneBox in Warehouse. The arguments are a
Box and a number of Shelf corresponding to the Shelf on which the Box sits.
If there is a Shelf with a smaller height where the Box would fit, move the
Box to the end of that new Shelf (and don’t forget to update all the fields
that need to be)
Question 8. Implement reorganize in Warehouse. Start with the lower
Shelf and the first Box on this Shelf and go on until the last Box on the last
Shelf. You can optimize this procedure, but this is the order we are looking
for.
5
