Child pages
  • Yixuan's CS231 Project 5: Checkout Lines
Skip to end of metadata
Go to start of metadata

1. Summary

In this project, I used my Queue to simulate shoppers picking check-out lines. A queue is a First In First Out sequence where we add a thing only at the tail and remove a thing only at the head. It has three key methods—offer, poll, and peek. For the project, I used a node-based doubly linked list to implement a queue.

With the simulations, I compared the performance of three different strategies for selecting a line which are random, pick2, and picky.

The results are overall as expected and relatable to our daily life.

2. Tasks

Customer Class

The Customer class is an abstract class from which I derive three classes that implement their own chooseLine methods.

CheckoutAgent Class

The CheckoutAgent class incorporates a queue of customers. The draw method draws the CheckoutAgent as a rectangle, but I later modified it so that the simulation becomes visually attractive and informative. I also added a getNumItemsInQueue method that returns the total number of items in a queue for one of my extensions. In the updateState method, I used if else statements and a for each loop.

Landscape Class

The Landscape Class uses ArrayList and LinkedList. In the draw method, I used a for each loop to loop through the CheckoutAgent ArrayList, calling each CheckoutAgent's draw method.

RandomCustomer Class

The RandomCustomer extends the Customer class and implements the random line-choosing strategy. Its chooseLine method returns an integer randomly chosen from the range 0 (inclusive) to the length of the list (exclusive). I used the Random package to generate a random integer.

PickyCustomer Class

The PickyCustomer class extends the Customer class and implements the strategy in which the customer chooses to join the shortest queue. In the chooseLine method, I initialized a large integer named 

shortest and an integer with the initial value 0 that represents the index of the shortest line. And then I used a for loop to in which I compared the number of Customers in each checkout line with the variable shortest, and update the value of shortest if necessary. Finally, I returned  the index of the CheckoutAgent with the shortest line.

Pick2Customer Class

The Pick2Customer class extends the Customer class and implements the strategy in which the customer randomly chooses two lines, then joins the shorter of those two. In the chooseLine method, I first generate two random integers in the range of [0, 5). To ensure that there are two different lines chosen, I use a while loop to renew one of the integers if the two integers are the same. Then I use an if else statement to compare the two different integers and return the index accordingly.


I made three new classes--RandomCustomerSimulation, PickyCustomerSimulation, and Pick2CustomerSimulation. And I added an updateCheckouts method in the Landscape class that loops through all of the CheckoutAgents, calling updateState.

Evaluate the strategies 

Initially, each Customer has 1 to 10 items. The lines grow over time, which means that 1 to 10 items is too many. So I adjust the maximum number of items to find a situation where the queues don't grow over time. 

In all the simulations, I add one Customer every one time step.


The lines grow too long with [1, 10] items per Customer:
Short lines with [1, 9] items per Customer:

The lines grow too long with  [1, 10] items per Customer:
Short lines with  [1, 8] items per Customer:


The lines grow too long with  [1, 10] items per Customer:

Short lines with  [1, 7] items per Customer:

I added a method printFinishedCustomerStatistics() to the Landscape to compute and print the average and standard deviation of the time-to-leave for all of the Customers in the finished customer list. 

I ran each simulation with 1000 customers and print out the statistics once every 100 time steps. 

The results of the three strategies are as below:

 PickyCustomerSimulation                                  Pick2CustomerSimulation                                  RandomCustomerSimulation

Picky Customers spend the longest time in average because they need to scan all of the checkout stations.

Pick2 Customers spend the shortest time in average because they only compare two lines and choose the shorter one.

Random Customers spend the shortest time on choosing to join a line, but the line they choose may be very long. So the time they spend is not the shortest overall.

In terms of standard deviation, the time spent varies little among each Picky Customer.

Pick2 is the most stable strategy.

Random is unpredictable and thus unstable, so its standard deviation is the largest.

3. Extensions

1) Re-implement your Queue using an array-based method instead of a Node-based method and show the functionality is identical. 

I made my ArrayQueue generic and implemented an iterator and a reverse iterator.

The result of testing is shown below:


2) Allow each agent to choose one of the three strategies randomly. Then calculate the statistics for each strategy in the mixed situation. Which strategy does the best?

In the Landscape class, I added another three LinkedList fields which are randomCusLLpick2CusLL, and pickyCusLL

And in my addFinishedCustomer method, I used if else statements and the instanceof operator to add three different kinds of customers into the three linked lists respectively. 

I made a new ChooseRandomStrategySimulation class in which I allowed each Customer to choose a random strategy. In the for loop, I randomly generate 0, 1, or 2, and each of them is related to a condition of the if else statements. For example, if the integer generated is 0, I add a new RandomCustomer and increment a variable numRandomCust that represents the number of RandomCustomers. Since the integers are randomly generated, each Customer's strategy is also randomly chosen. 

In order to calculate the statistics, initializing three variables(numRandomCust, numPick2Cust, and numPickyCust) aside, I created a new printFinishedCategorizedCustomerStatistics method in the Landscape class that calculates the average and standard deviation of the time-to-leave for all of the 3 types of Customers in their respective finished customer list.

I added 1000 customers in total to the five checkouts and I kept the maximum number of items (which is 9) the same for each customer.

In one simulation, the numbers of each kind of customers are printed in the terminal, as shown below: 


I used three variables in the if else statements to count the numbers.

I printed out the stats every 100 time steps.


I also plotted four charts:



The three strategies take approximately the same amount of time to be checked out, specifically, random < pick2 < picky. Theoretically, pick2 should be the most temporally efficient strategy. But in this case, the maximum number of items(9) is relatively large, which could affect the results to some extent.

Additionally, Picky is the most reliable strategy due to its small standard deviation.

3) Make the simulation visually interesting or more informative.

I modified my draw method in CheckoutAgent class.

Firstly, I draw checkout stations represented by black round rectangles at the bottom of the window.
Secondly, I used the Random package and a fill3DRect method of Graphic to draw randomly colored and positioned customers scattered on the top of the window. To have the customers appear less frequently, I used Random and made an if statement in which I draw a customer with a 5% probability.
Thirdly, I made the visualization more informative by showing how many items each Customer has. The longer a rectangle is, the more items a customer has. As time goes by, the length of a red rectangle in the front of a queue decreases, which indicates that the first customer's items are being checked out. 
In order to do so, I added a get() method that takes in an index as a parameter in MyQueue class so that in the for loop I could use a loop index i to get the number of items each Customer has in a queue.
Fourthly, I indicate the customer in the front, back, and middle with three different colors–red, green, and pink--using if else statements.
Last but not least, I used a drawString method of Graphics in Landscape's draw method to display the total number of customers and the total number of items in the window.

Below are some snapshots:

4) Analyze different aspects of the performance. For example, keep track of the average line length.

In my RandomCustomerSimulationPick2CustomerSimulationPickyCustomerSimulation classes, I calculated the average line length every 100 time steps using a for each loop.

The average line length refers to the average number of customers in a line.

I fixed the maximum number of items to be 8 for all three strategies.

To have a clearer idea of the average line length, I display the output statistics in a dialog box. 


In the LandscapeDisplay class, I created an output method using the showMessageDialog() method of JOptionPane.


In the RandomCustomerSimulation class, I call the output method that takes in avrLineLength as a parameter on LandscapeDisplay.
When I ran the simulation, a dialog box would pop up, informing me of the average line length every 100 time steps.

For example:


5) Analyze different aspects of the performance. For example, see if the amount of time a Customer spends in line is related to the number of items he has.

In order to analyze the relationship between the amount of time and the number of items, I created a chooseNumItems() method using JOptionPane in LandscapeDisplay and assigned the result of calling chooseNumItems() to a variable maxNumItems in my ChooseRandomStrategySimulation class. 




From the statistics, we can observe that the fewer items each customers has, the less it takes a customer to be checked out.


6) Try other strategies for checking out, such as choosing a line based on how many items are in the line (rather than how many customers). Be sure to choose an initial time-step value that reflects the amount of time it would take to make the line choice. The item-counting example should take significantly more time steps than the one that chooses the shortest line.

Firstly, I added a getNumItemsInQueue method in CheckoutAgent class that loops through each Customer in a CheckoutAgent's queue to get the sum of items in the queue and returns the total number of items.

I also created CountItemsCustomer and CountItemsCustomerSimulation classes.

The CountItemsCustomer class extends Customer, and the constructor takes in the total number of items as the time steps. 

Based on the PickyCustomer's chooseLine method, I modified the chooseLine method for CountItemsCustomer. I initialized a variable fewest and assigned to it a large integer. In a for loop, I used an if statement to compare the total number of items in each checkout line with fewest and update the value of fewest if necessary. Finally, I return the index of the CheckoutAgent with the fewest items in its line.

In the CountItemsCustomerSimulation class, before I create a new CountItemsCustomer in the for loop, I initialized a variable totalNumItems and then used a for each loop to call each CheckoutAgent's 

getNumItemsInQueue method so that I can add the total number of items in all five lines together and pass it in as the second parameter which represents the initial time steps to the CountItemsCustomer's constructor.

Another small extension I did in my CountItemsCustomerSimulation class is using Scanner to allow user to determine the maximum number of items each Customer has.


The average time is around or above 20. Since the customers count the number of items, they spend significantly more time in a line.

7) Gaussian distribution

Inspired by Professor Maxwell, in my Pick2CustomerSimulation class, instead of choosing the max number of items from 1 to 8 uniformly, I chose 6, 4, and 2 recurrently, simulating a Gaussian distribution.

To do so, I used a modulo operator: 2 + (j / 10) % 6.
(j / 10% 6 gives 4, 2, 0, and the whole expression gives 6, 4, 2.

The simulation is shown below:


The variation of average time is little.


In order to see the pattern more clearly, I changed the modulo operator to 3 + (j / 10% 6 so that it generates 7, 5, 3.

Now we can see the interesting pattern:

4. Reflection

At the end of the project, I became more familiar with data structures such as doubly-linked lists, arrays, array lists, and queues. I also learned a lot of GUI functions like showMessageDialog and showInputDialog. Additionally, I tried to improve the visualization using functionalities of Graphics. Besides, I learned how to design a new strategy and facilitate the process of user controlling variables and receiving information. I also spent a lot of time collecting and analyzing data. Overall, the project was super fun.

5. Acknowledgements

Professor Taylor

Professor Maxwell and his lecture notes

Professor Layton and his lecture notes

Ethan Pullen

Tia Zhang