Daily Challenge #126 - The Supermarket Line

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

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

  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)