Discussion on: Daily Challenge #126 - The Supermarket Line

View post

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