The Supermarket Queue

Task description

There is a queue for the self-checkout tills at the supermarket. Your task is write a function to calculate the total time required for all the customers to check out!

Input:
customers: An integer array representing customer estimated processing times.
tillCount: An integer representing available tills.

output:
An integer representing the maximum time required to process all customers.

Examples:
queueTime([5,3,4], 0) returns 12
queueTime([10,2,3,3], 2) returns 10
queueTime([2,3,10], 2) returns 12

Task solution

Tests

For this Kata I have chosen to implement the functionality in JavaScript, this being the case, I will use jest as the test runner for our test cases.

We have need to test the following failure cases:

1. If the customers parameter is not an array
2. If the customers parameter is an array containing non-integer types
3. If the tillCount parameter is not an integer

We then continue on to implement our happy path cases:

1. If noone is in line, no wait time should be expected
2. If customers are in line, total their wait times based on the tills available

describe("example tests", () => {
  it("Should throw if invalid inputs provided", () => {
    expect(() => queueTime(1, 1)).toThrow(/InvalidArgumentException/);
    expect(() => queueTime(["test", 2, null], 1)).toThrow(/InvalidArgumentException/);
    expect(() => queueTime([], null)).toThrow(/InvalidArgumentException/);
  });

  it("Should have no queue time if no customers are in line", () => {
    expect(queueTime([], 1)).toBe(0);
  });

  it("Should calculate the correct queue time for valid customers", () => {
    expect(queueTime([5,3,4], 0)).toBe(12);
    expect(queueTime([1,2,3,4], 1)).toBe(10);
    expect(queueTime([2,2,3,3,4,4], 2)).toBe(9);
    expect(queueTime([1,2,3,4,5], 100)).toBe(5);
  });
});

Implementation

function queueTime(customers, tillCount) {
  if(!Array.isArray(customers)) {
    throw new Error(`InvalidArgumentException: Parameter 1 must be an array, received: ${typeof customers}`);
  } else if(!customers.every(time => Number.isInteger(time))) {
    throw new Error(`InvalidArgumentException: Parameter 1 must be an array of integers. Atleast one element in the array does not conform to this, received: ${customers}`);
  } else if(!Number.isInteger(tillCount)) {
    throw new Error(`InvalidArgumentException: Parameter 2 must be an integer, received: ${typeof tillCount}`);
  }

  let tills = Array(tillCount <= 0 ? 1 : tillCount).fill(0);
  customers.forEach(customer => {
    const fastest = tills.indexOf(Math.min(...tills));
    tills[fastest] += customer;
  });
  return Math.max(...tills);
}

We begin by running our checks as usual. Then we then begin to hit an edge case just as we begin our happy path implementation, consider this:

The tillCount is 0 but the customer wait times are existing and valid. This being the case, we are to assume based on the task description that alternative arrangements have been made to account for these customers such as a person manually doing the work 🤷‍♂️. This being the case, the wait times should be processed as if 1 till is actually active, thus, a tillCount of 0 resolves the same result as a tillCount of 1.

This being the case, we check if tillsCount is 0 or less and if it is, we assume it to be equivelant to 1, otherwise we use whatever tillsCount is actually set to. We also have this case covered in our TDD flow on this line:

expect(queueTime([5,3,4], 0)).toBe(12);

The reason for this is simple, if we were to set new Array(0).fill(0), we would get a -Infinity value returned every time from the queueTime function. The reason for that is quite silly but also kind of makes sense. Basically, the array, if it had been created as new Array(0) would have no elements and thus the .fill(0) populates no indicies since none exist, it's an empty array afterall. From here as we run the loop for getting our customer times validated. At this point, the indexOf call returns -1 since no index is found, since none exist. So far things make sense but here is where it gets silly. As we execute the tills[fastest] += customer; line, JavaScript will allow us to set an index of -1 on the array and assign it a value, in this case, NaN. Thus, our tills array after the loop is finished will always be [-1: NaN]. You might rightfully be thinking "how is that even a thing?", well it gets slightly worse because in Javascript, an array with negative indexes is invalid and thus, when we call Math.max(...tills); JavaScript interperets that as Math.max(...[]) and the default return value in such cases of using Math.max is -Infinity. Before you ask, the flipside case of using Math.min will return Infinity under the same conditions, so atleast there's a predictable and consistent implementation 👀.

So, understanding these quirks, we move onto the loop itself which simple checks what the till with the lowest wait time is and adds the current customer in the loop to it. Lets imagine the following pseudo-code:

customers: [1, 2, 3]
tills: [0, 0]
loop customers
 1st iteration -> tills = [1, 0]
 2nd iteration -> tills = [1, 2]
 3rd iteration -> tills = [4, 2]
Maximum wait time -> 4

This being the case, we simply return the maximum value in the tills array to finish things.

Conclusions

This was quite a fun Kata to work with, I remember completing it a couple of weeks back and finding the quirks with Math.min and Math.max that I hadn't come across in almost 8 years of development with JavaScript but it is one of these things you come across and you just think to yourself "that's pretty cool but also... why?". I guess that is one of the reasons JavaScript continues to be such a popular language, it is powerful in and of itself but it is so quirky that you learn something new almost every day 😂.

I experimented with using a reducer as the final return value like so:

// code removed to keep this snippet short
let tills = Array(tillCount === 0 ? 1 : tillCount).fill(0);
return customers.reduce((maxTime, customer) => {
  const fastest = tills.indexOf(Math.min(...tills));
  tills[fastest] += customer;
  return Math.max(...tills);
}, 0);

This works just the same as the implementation above but personally, I don't like the use of tills inside the reducer function since it is not explicitely passed in. Perhaps this is just me but either way I settled on the implementation we went over in the section above and I am pretty happy with the outcome.