CSci 1301: Takehome 2

Due: Saturday, November 21st at 11:59pm by e-mail (no late work accepted)

Total: 40 points

This is individual work. You are not allowed to spend more than 8 hours on this test. This includes any reading that you do to help you solve the problems.

Use helper functions as needed. All your functions must have documentation with the signature (contract) showing the types of parameters and results and a function description. All functions must have check-expect tests.
When defining your own structures, clearly explain what all the fields mean.
The problems provide some test cases, but you need to write at least two more for each problem.
Comments, helpful variable names, and good code style and formatting are a very important part of your grade. You don't have to look for the shortest solution, but you should eliminate unnecessary code repetition if possible (use helper functions).

Important: you may not use list functions append and length. You may use any of the following higher-order functions map, filter, foldr, foldl, sort, as well as anonymous functions. However, all of the problems may be solved using direct recursion (some problems require recursive helper functions).

The problem description: shipping boxes

A trucking company moves containers (boxes) filled with products. A simplified structure that describes a box is:

      (define-struct box [length width height price destination])
  

      (make-box 4 3 5 200 "New York, NY")
  

describes a box 4ft long, 3 ft wide, and 5ft tall that needs to be shipped to New York, and the company will get $200 once the box is shipped.

The following list will be used in the check-expects below:

      (define boxes (list (make-box 4 3 5 200 "New York")
                    (make-box 2 10 1 300 "Philadelphia")
                    (make-box 5 5 6 250 "New York")
                    (make-box 4 2 4 170 "Chicago")))
  

You need to write the following functions on lists of boxes:

1. Write a function total-amount that, given a list of boxes, computes the total amount that the trucking company will get by shipping the boxes:

     
         (check-expect (total-amount boxes) 920)
       

2. Write a function max-height that, given a non-empty list of boxes, returns the height of the tallest box in the list:

     
         (check-expect (max-height boxes) 6)
         

   If the list has only one box, the height of that box is returned. Don't worry about an empty list for this problem.
3. Write a function largest-box that, given a non-empty list of boxes, returns the box with the largest volume (obtained by multiplying the length, the width, and the height together):

     
         (check-expect (largest-box boxes) (make-box 5 5 6 250 "New York"))
         

   If the list has only one box, that box is returned. Don't worry about an empty list for this problem.
4. Write a function same-destination that takes a list of boxes and a city and returns a list of all boxes that are going to that city:

     
         (check-expect (same-destination boxes "New York") (list (make-box 4 3 5 200 "New York") (make-box 5 5 6 250 "New York")))
       

5. Write a function that produces an image corresponding to a list of boxes. Each box is shown as rectangle length-by-height (ignore the width) and shows its price. 1 ft = 20 pixels. Use beside/align to align the boxes to the bottom.
   The result for the given list of boxes looks like this:
   
6. Write a function fit-by-width-height that takes a list of boxes and the width and height of a truck, and returns #true if each box fits into the given dimensions, and #false otherwise. For example, if the width of the truck is 8 and the height is 7, the list above should return #false since one of the boxes has width 10 which is larger than 8.
7. Write a function fit-by-length that takes a list of boxes and the length of a truck and returns #true if the combined length of the boxes is not larger than the length of the truck, and #false otherwise. For instance, if the given length is 12, the given list of boxes doesn't fit since its total length is 15.
8. Suppose you are given a truck of a particular length and a list of boxes that all are going in the same direction and fit into the truck be height and width. You cannot put two boxes behind each other or on top of each other, so you are putting them in a row.
   Your goal is to try to maximize the profit, i.e. fit the boxes that give you the maximum total amount and fit into the truck. If you want to find a perfect solution, you would have to consider all possible combination of boxes, but that's a long process, and we are not doing it.
   Instead we will try to approximate the solution: first we will sort the boxes by their profit per foot of length (in decreasing order, so more profitable ones first), and then we will start putting them into the truck until the length is filled up. If a box is longer than the remaining space in the truck, it will be skipped, and the next (less profitable) box will be attempted. The process continues until we have filled up the truck or have no more boxes in the list.
   Your goal is to write two functions (with check-expect tests):
   1. sort-by-price-per-length that takes a list of boxes and orders them in decreasing order by price per unit of length. If two prices-per-length are equal, the boxes may appear in any order. In our list of boxes the first and the third boxes have the same cost, so they can go in any order. This is a check-expect that keeps them in the same order as in the given list:

      
      	    (check-expect (sort-by-price-per-length boxes)
      	       (list (make-box 2 10 1 300 "Philadelphia")
      	             (make-box 4 3 5 200 "New York")
                           (make-box 5 5 6 250 "New York")
                           (make-box 4 2 4 170 "Chicago")))
      	

   2. fill-up-truck takes the sorted list of boxes and the length of the truck and fills it up as described above. For instances, if sorted-boxes is the sorted list above, and the capacity is 10, then we can put the first two boxes, then we have remaining space of 4, and the next box doesn't fit since its length is . However, the one after it has the length of 4, and fots, so we get:

      
      	    (check-expect (fill-up-truck sorted-boxes 10)
      	      (list (make-box 2 10 1 300 "Philadelphia")
      	            (make-box 4 3 5 200 "New York")
                          (make-box 4 2 4 170 "Chicago")))
      	

Happy programming!

What to submit

Submit all your files as attachements in an email to me. The subject of the email must be Midterm 2. Please include your name and a task number at the beginning of the file, in a comment. In your email message please include any comments about what works and what doesn't, as well as thoughts on how you would've continued if you had more time (if you run out of time). Also please include the total time you spent on the test.

CSci 1301 course web site.