ruby - calculating time in supermarket queue

Question

So suppose there is a queue for the self-checkout tills at the supermarket. I'm trying to write a function to calculate the total time required for all the customers to check out!

Input:

customers: an array of positive integers representing the queue. 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.

Output:

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

queue_time([5,3,4], 1)
# should return 12
# because when n=1, the total time is just the sum of the times

queue_time([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.

queue_time([2,3,10], 2)
# should return 12

There is only ONE queue serving many tills, and the order of the queue NEVER changes. The front person in the queue (first element in the array/list) proceeds to a till as soon as it's free. I tried this, but it doesn't work correctly, I'm not sure how to make the next person go into till when it's open.

def queue_time(customers, n)
  if customers == []
    n=0
  else
    x= customers.reduce(:+) / n 
    if x < customers.max
      customers.max
    else 
      x
    end
  end
end

For example, testing for

customers = [751, 304, 2, 629, 36, 674, 1] 
n = 2
expected: 1461, instead got: 1198

. Thanks :-)

Answer 1

Given an input of:

customers = [751, 304, 2, 629, 36, 674, 1]
n = 2

You could create an array of tills: (each one is an array itself)

tills = Array.new(n) { [] }
#=> [[], []]

Now, for each customer, you add its value to the shortest till:

customers.each do |customer|
  tills.min_by(&:sum) << customer
end

In the end, this gives you:

tills
#=> [[751, 36, 674], [304, 2, 629, 1]]

The first one has a sum of 1,461.

Answer 2

def queue_time(time_required, n)
  remaining_time_by_line = Array.new(n) { 0 }
  curr_time = 0
  time_required.each do |t|
    wait_time, line_assigned = remaining_time_by_line.each_with_index.min_by(&:first)
    curr_time += wait_time
    remaining_time_by_line.map! { |rt| rt - wait_time }
    remaining_time_by_line[line_assigned] = t
  end
  curr_time + remaining_time_by_line.max
end

queue_time([5,3,4], 1)
  #=> 12
queue_time([10,2,3,3], 2)
  #=> 10
queue_time([2,3,10], 2)
  #=> 12 
queue_time([2,3,4,1,2,5], 3)
  #=> 8
queue_time([751, 304, 2, 629, 36, 674, 1], 2)
  #=> 1461

I can most easily explain the calculations by executing the method after have having salted it with puts statements.

def queue_time(time_required, n)
  remaining_time_by_line = Array.new(n) { 0 }
  curr_time = 0
  time_required.each do |t|
    wait_time, line_assigned = remaining_time_by_line.each_with_index.min_by(&:first)
    curr_time += wait_time
    puts "\ntime required, t = #{t}"
    puts "line_assigned = #{line_assigned}"
    puts "wait_time = #{wait_time}"
    puts "curr_time = #{curr_time}"
    remaining_time_by_line.map! { |rt| rt - wait_time }
    remaining_time_by_line[line_assigned] = t
    puts "remaining_times_by_line = #{remaining_time_by_line}"   
  end
    puts "\nremaining_time_by_line.max = #{remaining_time_by_line.max}"
    tot = curr_time + remaining_time_by_line.max
    puts "curr_time + remaining_time_by_line.max = #{tot}"
    tot
end

queue_time([2,3,4,1,2,5], 3)
  #=> 8

The following is displayed.

time required, t = 2
line_assigned = 0
wait_time = 0
curr_time = 0
remaining_times_by_line = [2, 0, 0]

time required, t = 3
line_assigned = 1
wait_time = 0
curr_time = 0
remaining_times_by_line = [2, 3, 0]

time required, t = 4
line_assigned = 2
wait_time = 0
curr_time = 0
remaining_times_by_line = [2, 3, 4]

time required, t = 1
line_assigned = 0
wait_time = 2
curr_time = 2
remaining_times_by_line = [1, 1, 2]

time required, t = 2
line_assigned = 0
wait_time = 1
curr_time = 3
remaining_times_by_line = [2, 0, 1]

time required, t = 5
line_assigned = 1
wait_time = 0
curr_time = 3
remaining_times_by_line = [2, 5, 1]

remaining_time_by_line.max = 5
curr_time + remaining_time_by_line.max = 8

Answer 3

Your question falls in the category of discrete event simulation (DES) modeling. For simple models DES can sometimes be handled by looping and conditioning (as in the other answers provided), but if you plan to extend this model or build simulations with greater complexity, you'll want to use some sort of event scheduling framework as described in this Winter Simulation Conference tutorial. A gem called simplekit provides a Ruby implementation of the concepts from the tutorial. (Full disclosure—I'm the author of the paper and the gem.)

A quick summary is that an "event" occurs at a discrete point in time and updates the system state. It can also schedule further events. A DES framework maintains a set of pending events as a priority queue, so that events occur in the correct sequence despite the time delays between when an event gets scheduled and when it will be executed. All of this is handled relatively transparently by methods provided by the framework.

Here's an implementation of your model with different parameterizations, heavily annotated:

require 'simplekit'

class MyModel
  include SimpleKit

  # Constructor - initializes the model parameters.
  # param: service_times - An array of service times for each customer
  # param: max_servers - The total number of servers in the system.
  def initialize(service_times, max_servers)
    @service_times = service_times.clone
    @max_servers = max_servers
  end

  # Initialize the model state and schedule an initial set of events.
  def init
    @num_available_servers = @max_servers
    # As long as servers remain available and there are customers
    # remaining, schedule the end_service for the next customer
    # to occur after a delay equal to the customer's service time.
    # The number of available servers gets reduced by one.
    while @num_available_servers > 0 && !@service_times.empty? do
      schedule(:end_service, @service_times.shift)
      @num_available_servers -= 1
    end
  end

  # Every time there's an end of service, see if there's another customer
  # waiting in line.  If so, schedule their end_service (and the current
  # server remains tied up), otherwise the current server gets freed up.
  #
  # This model will terminate when there are no more events scheduled,
  # which happens when all the end_services have completed.
  def end_service
    if @service_times.empty?
      @num_available_servers += 1
    else
      schedule(:end_service, @service_times.shift)
    end
  end
end

model_params = [
  [[5,3,4], 1],
  [[10,2,3,3], 2],
  [[2,3,10], 2],
  [[2,3,4,1,2,5], 3],
  [[751, 304, 2, 629, 36, 674, 1], 2]
]

# SimpleKit models track and update the model_time automatically for you,
# so the current_model's model_time reflects what time it was in the
# model when the last event occurred.
model_params.each do |svc_times, servers|
  current_model = MyModel.new(svc_times, servers)
  current_model.run
  puts "#{svc_times}, #{servers} => #{current_model.model_time}"
end

which produces the following output:

[5, 3, 4], 1 => 12.0
[10, 2, 3, 3], 2 => 10.0
[2, 3, 10], 2 => 12.0
[2, 3, 4, 1, 2, 5], 3 => 8.0
[751, 304, 2, 629, 36, 674, 1], 2 => 1461.0

Answer 4

Essentially the same as the answer of Stefan. The difference being that this answer only tracks the sum's running total for each checkout till, instead of keeping track of the customers and re-summing their values each time a new customer arrives.

def queue_time(customers, n)
  till  = Struct.new(:sum)
  tills = Array.new(n) { till.new(0) }

  customers.each do |customer| 
    tills.min_by(&:sum).sum += customer
  end

  tills.map(&:sum).max
end

Answer 5

I really liked Stefan's answer and this one works much the same but without using a nested array.

Start by creating an array of the number of tills, each with a value of 0.

tills = [0] * 3

Then, iterate over the customer array adding each customer item to the till item with the lowest value, found by referencing the index of the minimum value.

customers.each { |customer| till[till.index(till.min)] += customer }

And implicitly return the till item with the max value.

till.max

The complete code:

def queue_time(customers, n)
  till = [0] * n
  customers.each { |customer| till[till.index(till.min)] += customer }
  till.max
end