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.
CREATE TABLE passengers(passenger_name varchar(20) PRIMARY KEY, weight_kg integer);
INSERT INTO passengers(passenger_name, weight_kg)
VALUES ('Johnny', 60),
('Jimmy', 120),
('Jenny', 50),
('Namy', 20),
('Grendel', 500),
('Charlie', 400),
('Gongadin', 400),
('Tin Tin', 10),
('Thumb Twins', 10),
('Titan', 600),
('Titania', 550),
('Titan''s Groupie', 55) ;
SELECT carriage,COUNT(passenger_name) As cnt_pass,
array_agg(passenger_name) As passengers
FROM (SELECT passenger_name, weight_kg,
ceiling(COUNT(passenger_name)
OVER(ROWS UNBOUNDED PRECEDING)/5.0) As carriage
FROM passengers) As congregation
GROUP BY carriage
ORDER BY carriage;
The result looks like
carriage | cnt_pass | passengers
----------+----------+--------------------------------------------------
1 | 5 | {Johnny,Jimmy,Jenny,Namy,Grendel}
2 | 5 | {Charlie,Gongadin,"Tin Tin","Thumb Twins",Titan}
3 | 2 | {Titania,"Titan's Groupie"}
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
FROM passengers
ORDER BY passenger_name LIMIT 1
),
congregation AS
(
SELECT carriage, passenger_name, weight_kg, car_weight
FROM p1
UNION ALL
SELECT np.carriage, np.passenger_name, np.weight_kg, np.car_weight
FROM
(SELECT CASE WHEN c.car_weight + p2.weight_kg <= 750
THEN c.carriage ELSE c.carriage + 1 END As carriage,
p2.passenger_name, p2.weight_kg,
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
FROM congregation
GROUP BY carriage;
Result
carriage | cnt_pass | passengers | car_kg
----------+----------+---------------------------------------------------+------
1 | 1 | {Charlie} | 400
2 | 1 | {Gongadin} | 400
3 | 5 | {Grendel,Jenny,Jimmy,Johnny,Namy} | 750
4 | 4 | {"Thumb Twins","Tin Tin",Titan,"Titan's Groupie"} | 675
5 | 1 | {Titania} | 550
Tracked: Oct 05, 19:03