dev.to staff

Posted on

# Daily Challenge #126 - The Supermarket Line

There is a line for the self-checkout machines at the supermarket. Your challenge is to write a function that calculates the total amount of time required for the rest of the customers to check out!

input
`customers` : an array of positive integers representing the line. Each integer represents a customer, and its value is the amount of time they require to check out.
`n` : a positive integer, the number of checkout tills.

rules
There is only one line serving many machines, and
The order of the line never changes, and
The front person in the line (i.e. the first element in the array/list) proceeds to a machine as soon as it becomes free.

output
The function should return an integer, the total time required.

examples

```queueTime([5,3,4], 1)
// should return 12
// because when there is 1 machine, the total time is just the sum of the times

queueTime([10,2,3,3], 2)
// should return 10
// because here n=2 and the 2nd, 3rd, and 4th people in the
// queue finish before the 1st person has finished.

queueTime([2,3,10], 2)
// should return 12
```

Good luck, happy coding!

This challenge comes from mattlub on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Jon Bristow • Edited

Kotlin semi-functional solution:

``````sealed class Cashier
data class Occupied(val timeleft: Int) : Cashier()

fun queueTime(shoppers: List<Int>, cashiers: Int) =
simulate(0, shoppers, generateSequence { Ready }.take(cashiers))

tailrec fun simulate(elapsed: Int, shoppers: List<Int>, aisles: Sequence<Cashier>): Int {
val (nextShoppers, nextCheckout) = aisles.fold(shoppers to emptySequence<Cashier>()) { (s, co), aisle ->
when {
aisle is Ready && shoppers.isNotEmpty() -> s.drop(1) to co + Occupied(s.first() - 1)
aisle is Occupied && aisle.timeleft == 1 -> s to co + Ready
aisle is Occupied -> s to co + Occupied(aisle.timeleft - 1)
else -> shoppers to co + aisle
}
}
return when {
nextShoppers.isEmpty() && nextCheckout.all { it is Ready } -> elapsed + 1
else -> simulate(elapsed + 1, nextShoppers, nextCheckout)
}
}

fun main() {
println(queueTime(listOf(5, 3, 4), 1))
println(queueTime(listOf(10, 2, 3, 3), 2))
println(queueTime(listOf(2, 3, 10), 2))
}
``````

This is a cool puzzle! Without going into spoilers, last year's Advent of Code had a similar puzzle, but with a few layers of complication on-top.

Jon Bristow

As an additional challenge, I added a record of the order shoppers finish.

``````
internal sealed class Cashier
internal data class Occupied(val timeleft: Int, val shopper: Shopper) : Cashier() {
constructor(shopper: Shopper) : this(shopper.time - 1, shopper)
}

data class Shopper(val id: Int, val time: Int)

private fun queueTimeAndFinishOrder(shoppers: List<Int>, cashiers: Int) =
simulateWithOrder(
Moment(
waitingShoppers = shoppers.mapIndexed { i, it -> Shopper(i + 1, it) },
aisles = generateSequence { Ready }.take(cashiers).toList()
)
)

private data class Moment(
val waitingShoppers: List<Shopper>,
val aisles: List<Cashier> = emptyList(),
val finishedShoppers: List<Shopper> = emptyList(),
val tick: Int = 0
)

private tailrec fun simulateWithOrder(
moment: Moment
): Moment {
val nextMoment =
moment.aisles.fold(
Moment(
waitingShoppers = moment.waitingShoppers,
finishedShoppers = moment.finishedShoppers,
tick = moment.tick + 1
)
) { (waiting, aisles, finished, tick): Moment, aisle ->
when {
aisle is Ready && waiting.isNotEmpty() -> Moment(
waitingShoppers = waiting.drop(1),
aisles = aisles + Occupied(waiting.first()),
finishedShoppers = finished,
tick = tick
)
aisle is Occupied && aisle.timeleft <= 1 -> Moment(
waitingShoppers = waiting,
aisles = aisles + aisle.tickDown(),
finishedShoppers = finished + aisle.shopper,
tick = tick
)
aisle is Occupied -> Moment(
waitingShoppers = waiting,
aisles = aisles + aisle.tickDown(),
finishedShoppers = finished,
tick = tick
)
else -> Moment(
waitingShoppers = waiting,
aisles = aisles + aisle,
finishedShoppers = finished,
tick = tick
)
}
}
return when {
nextMoment.waitingShoppers.isEmpty() && nextMoment.aisles.all { it is Ready } -> nextMoment
else -> simulateWithOrder(nextMoment)
}
}

private fun Occupied.tickDown() = when (timeleft) {
else -> Occupied(timeleft - 1, shopper)
}

fun main() {
val momentA = queueTimeAndFinishOrder(listOf(5, 3, 4), 1)
println("time: \${momentA.tick}, order: [\${momentA.finishedShoppers.joinToString { "\${it.id}" }}]")

val momentB = queueTimeAndFinishOrder(listOf(10, 2, 3, 3), 2)
println("time: \${momentB.tick}, order: [\${momentB.finishedShoppers.joinToString { "\${it.id}" }}]")

val momentC = queueTimeAndFinishOrder(listOf(2, 3, 10), 2)
println("time: \${momentC.tick}, order: [\${momentC.finishedShoppers.joinToString { "\${it.id}" }}]")
}
``````

Idan Arye

Rust solution. This is easy when you use the right data structure - in this case, a heap.

``````use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn queue_time(customers: &[usize], n: usize) -> usize {
assert!(0 < n, "can't serve anyone without registers");

let mut customers = customers.iter().copied().fuse();

// The first n customers start at 0 and finish at their serving time.
let mut finish_times: BinaryHeap<_> = customers.by_ref().take(n).map(Reverse).collect();

for serving_time in customers {
// `finish_times.pop()` returns the next time a customer finishes.
let Reverse(current_time) = finish_times.pop()
.expect("finish_times should not be empty here - we add a new entry for each one we take");
// This register was cleared at `current_time`, and will be cleared again after
// serving_time passes.
finish_times.push(Reverse(current_time + serving_time));
}

// No more pending customers - so just wait for the last one in the registers.
finish_times.drain().map(|Reverse(time)| time).max()
// `finish_times` can only be empty if customers was empty to begin with.
.unwrap_or(0)
}

fn main() {
assert_eq!(queue_time(&[5,3,4], 1), 12);
assert_eq!(queue_time(&[10,2,3,3], 2), 10);
assert_eq!(queue_time(&[2,3,10], 2), 12);
}
``````

morgana

Ruby solution: It's not the prettiest, but it works. I'm a Ruby newb so this was some good practice and I won't say no to any pointers or suggestions if I am doing something that's not very "Rubyish" (What word do they use for poorly used Ruby? In Python they say "that's not very "pythonic").

``````  1
2 def queueTime(line, till_count)
3     empty = false
4     in_progress = []
5     time_spent = 0
6     while !empty do
7         # remove finished customers from in_progress
8         in_progress = in_progress.reject{ |x| x <= 0 }
9
10         # add more customers to in_progress
11         while in_progress.length < till_count and line.length > 0 do
12             in_progress.push(line.shift)
13         end
14
15         # check if done, otherwise, keep tracking progress
16         if in_progress.length == 0 and line.length == 0
17             empty = true
18         else
19             min = in_progress.min
20             in_progress = in_progress.map{|x| x - min }
21             time_spent += min
22         end
23     end
24     time_spent
25 end
``````

dillan teagle • Edited
``````def queue_time(customers, n):
tills = [0]*n
for i in customers:
tills[0] += i
tills.sort()
return max(tills)
``````