DEV Community

Daily Challenge #126 - The Supermarket Line

dev.to staff on November 27, 2019

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 r...

Read full post

Jon Bristow • Nov 27 '19 • Edited

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.

Jon Bristow • Nov 27 '19

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

Idan Arye • Nov 28 '19

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 • Nov 30 '19

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 • Nov 30 '19 • Edited

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