A solution in Ruby to the Codehire Cup Grand Final (Round 3) problem in the second Codehire Cup held across Australia in June and July 2013.

In June and July 2013, Codehire held the second Codehire Cup across Australia. As last year, the contest featured some relatively simple coding problems. Contestants could choose to use C/C++, C#, Java, JavaScript, PHP, Python, or Ruby to submit solutions through a web-based interface.

Contestants were ranked according to the time taken to complete the problem, as well as by an assessment of their approach and coding style by a panel of judges.

The Problem

The Codehire Cup Grand Final (Round 3) problem read:

Elevators

A building has 100 floors (numbered 0 through 99) and 5 elevators (numbered 0 through 4) each with access to all floors.

You are given the following information:

1. The floor on which each elevator is currently situated
2. A list of pending requests by people waiting. Described as the floor on which the request was made and how long for which the request has been pending (the age of the request)

The elevator controller should satisfy the following goals:

1. Always satisfy oldest requests first
2. Minimize wait time after satisfying condition 1

Your program must determine which elevators (numbered 0, 1, 2, 3 or 4) will service each of the requests.

Assumptions

1. A given elevator will only service one request in this exercise
2. When deciding which elevator to send for a request, there will always be only one optimal candidate
3. There will not be more requests than there are elevators
4. All elevators travel at the same speed

Input

The input will be given to you on two lines. The fist line will be a comma separated list of the floors the five elevators are currently situated. eg:

10,5,7,9,1

The second line will be a list of requests containing the floor number and the age of the request in seconds separated by a comma. The individual requests are then separated by semicolons. eg:

7,45;11,10;

In other words, there is a request on level 7 which has been waiting for 45 seconds and a request on level 11 which has been waiting for 10 seconds.

Output

Your program should output the elevator numbers that will service each request in the order that the requests are provided to you.

Input:

0,1,19,9,56
13,15;67,60;68,35;

Output:

3,4,2

The Solution

The solution is simply to sort the requests from oldest to newest. Then, for each request, we find the closest elevator and associate it with that request. After associating an elevator with a request, we set the elevator’s floor notionally to infinity so that the elevator is not used again.

# Parse input
elevators = input.split[0].split(',').map { |e| e.to_i }
requests  = input.split[1].split(';').map { |r| r.split(',').map { |s| s.to_i } }

# Map elevators to requests
requests.sort_by { |r| -r[1] }.each do |r|
  r[2] = elevators.each_index.min_by { |e| (elevators[e] - r[0]).abs }
  elevators[r[2]] = Float::INFINITY
end
output << requests.map { |r| r[2] }.join(',')

The constraints listed in the assumptions section ensure that, at each stage of the computation, there is only one possible outcome. If that were not the case, it would be necessary to perform a more complicated computation where, for example, the total or average wait times are minimised.

More Codehire Cup 2013 Solutions

• Codehire Cup Preliminary (Round 1) Solution
• Codehire Cup Semi-final (Round 2) Solution
• Codehire Cup Grand Final (Round 3) Solution

Codehire Cup 2012 Solutions

• Practice Challenge Solution
• Codehire Cup Preliminary Solution
• Cup Semi-final Solution
• Grand Final Solution