Lab 4: Planning Programs on Lists

This lab is strongly recommended for those who struggled with the Rainfall or MaxTripleLengths programs on the homework, or those who feel they need more practice programming with lists.

If you had problems with those problems, try to work with the planning and diagramming approach that we showed you in class on Tuesday. Grab paper, draw pictures, and try to figure out how to set up these problems. Spending a bunch of time working on paper, rather than writing code, could help you a lot on these problems.

If you work with diagrams for this week, we would like you to turn them in (on paper) at the end of lab. You aren’t being graded on them. Rather, we want to look to see where you might be struggling so we can try to help.

1 Problems

1.1 Nearest Point Distance

Imagine that you had an application that was tracking devices as they moved around (such as tracking phones, flying drones, etc). You need a program to figure out how close the nearest tracked device is from some specified point. Because of limitations in your tracking application, rather than have a list of locations, your program will get a list of all the locations, but flattened out into a sequence like

device1-x device1-y device2-x device2-y ...

(where device1-x and device1-y are the x and y coordinates of device1, and so on. We’ll work with just 2-dimensional coordinates and check the distance to the origin (0,0) to keep things simple).

Write a program nearestPointDistance that takes a LinkedList of integers for the locations as shown above and returns the distance (a double) of the closest point to the origin (the coordinate at (0,0)). For example:

nearestPointDistance([3, 4, 0, 2, 5, 12]) should return 2

How do we get 2? The distance from (3,4) is 5, the distance from (0,2) is 2, and the distance from (5,12) is 13. The smallest of these distances is 2.

As a reminder, given a point (x,y), its distance to the origin is given by the formula

sqrt(x*x + y*y)

in Java, you get the sqrt of a number num by writing Math.sqrt(num). This function returns a double. To use it, include the following import in your file:

import java.lang.Math;

1.2 Revisit Adding Machine from Yesterday’s Lecture (Optional)

If you didn’t finish addingMachine yesterday, you could go back and try to get that working (or skip to the next problem). Here’s the problem statement again:

Design a program called addingMachine that consumes a list of numbers and produces a list of the sums of each non-empty sublist separated by zeros. Ignore input elements that occur after the first occurrence of two consecutive zeros.

1.3 Least-Healthy Teams

A company maintains records on its employees. For each, it stores the person’s name, which team they are on on, and how many days they have been out sick. The company tracks the health of each team by totalling the number of sick days across all members of the team.

Write a function leastHealthy that takes a list of employees and returns a list of the team names in order from the one with the most to the one with the least sick days. Here’s a class of Employee to get you started.

  class Employee {
    String name;
    String team;
    int missedDays;
  }

Note that, at least here in class, it is more important that you figure out how to break the problem down into tasks than necessarily get the code written. Planning out your code before you write too much can be a useful way to make progress without getting overwhelmed by the code.

1.4 Shopping Cart

An online clothing store applies discounts during checkout. A shopping cart is a list of the items being purchased. Each item has a name (a string like “shoes”) and a price (a real number like 12.50). Design a program called checkout that consumes a shopping cart and produces the total cost of the cart after applying the following two discounts:

if the cart contains at least 100 worth of shoes, take 20% off the cost of all shoes (match only items whose exact name is "shoes")
if the cart contains at least two hats, take 10 off the total of the cart (match only items whose exact name is "hat")

Use the following classes for items and carts:

  class CartItem {
    String name;
    double price;

    CartItem (String name, double price) {
      this.name = name;
      this.price = price;
    }
  }

  // A sample cart in your Examples class
  LinkedList<CartItem> cart;

2 What to Turn In

In addition to submitting your code files in InstructAssist as usual, if you did any diagrams on paper, please write your name on the paper and hand that in to your lab staff.