In our prior story about allocating people with the power of window aggregation, we saw our valiant hero and heroine trying
to sort people into elevators
to ensure that each elevator ride was not over capacity. All was good in the world until someone named Frank came along and spoiled the party.
Frank rightfully pointed out that our algorithm was flawed because should Charlie double his weight, then we could have one elevator ride over capacity.
We have a plan.
What was wrong with our first try? Well we failed to realize that while the number of rides
you need at each increment of weight has to be at least the ceiling of the sum divided by the capacity of the car, it can exceed that number. This approach we think
works fine if you are simply counting people. If we had normally weighted people instead of some dwarfs and giants that may work fine. So if we wanted to fit at most 5 people per car we would do this. Note we also changed our window to something that
is a bit shorter but equivalent in meaning.
To test this idea out lets recreate our table of characters (Charlie being a little fatter now). We want at most 5 people per car run.
Of course this is not the problem we were trying to solve. We want to ensure that our car weights are at most 750 kg with giants in mind. So what to do.
Sadly the power of window aggregates in PostgreSQL appears to fail us here but we can write a recursive query AKA (Recursive common table expression (CTE) with PostgreSQL 8.4. Sorry it looks
kind of convoluted. The translation to this into spoken tongue is actually closer to what we said we were doing in the first place.
If anyone can come up with a simpler way of achieving this, we'd like to know. I think there is a way to do this with a self-join, but haven't
thought that far into it.
WITH RECURSIVE p1 As
(SELECT 1 As carriage, passenger_name, weight_kg, weight_kg As car_weight
ORDER BY passenger_name LIMIT 1
SELECT carriage, passenger_name, weight_kg, car_weight
SELECT np.carriage, np.passenger_name, np.weight_kg, np.car_weight
(SELECT CASE WHEN c.car_weight + p2.weight_kg <= 750
THEN c.carriage ELSE c.carriage + 1 END As carriage,
CASE WHEN c.car_weight + p2.weight_kg <= 750
THEN c.car_weight + p2.weight_kg
ELSE p2.weight_kg END As car_weight
FROM passengers As p2 INNER JOIN
(SELECT carriage, passenger_name, weight_kg, car_weight
FROM congregation ORDER BY passenger_name DESC LIMIT 1)
As c ON (p2.passenger_name > c.passenger_name)
ORDER BY p2.passenger_name LIMIT 1) As np
SELECT carriage, COUNT(passenger_name) As cnt_pass,
array_agg(passenger_name) As passengers, SUM(weight_kg) As car_kg
GROUP BY carriage;