loading...

Daily Challenge #126 - The Supermarket Line

thepracticaldev profile image dev.to staff ・1 min read

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!

Posted on by:

thepracticaldev profile

dev.to staff

@thepracticaldev

The hardworking team behind dev.to ❤️

Discussion

pic
Editor guide
 

Kotlin semi-functional solution:

sealed class Cashier
data class Occupied(val timeleft: Int) : Cashier()
object Ready : 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.

 

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)
}

internal object Ready : Cashier()

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) {
    1 -> Ready
    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}" }}]")
}
 

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);
}
 

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
 
def queue_time(customers, n):
    tills = [0]*n
    for i in customers:
      tills[0] += i
      tills.sort()
    return max(tills)