Back when I competed in programming contests, problems would be wrapped up in “real-world” stories, with the goal of making the problem easier to comprehend and more digestible for larger audiences. Following such tradition (hopefully), I present a story about a common problem developers deal with here at Acceleware.

In recent years, AxIsland has become quite a tourist destination, and hotel companies have been flourishing. Sixteen different hotel chains exist on the island, each with multiple accommodation offerings and courtesy taxi service. The high cost of beach property forced the local airport onto a nearby island, thus arriving tourists must first hop onto a taxi vehicle (run by their choice of hotel chain) before taking a small ferry across to AxIsland. The ferry service is a joint service run by the sixteen hotel chains, and has exactly sixteen spots for taxi-vehicles, reserved exclusively for its respective hotel chain. It used to be that single-passenger taxi-cabs were the only taxi-vehicles on AxIsland, but recently taxi-vans capable of holding up to sixteen passengers (all headed to the same hotel) were introduced to accommodate large families and business-retreat visitors.  Unfortunately, the introduction of taxi-vans also introduced logistical problems. The ferry can still carry sixteen taxi-vehicles at once, however due to the ferry’s size and slot restrictions there is only room for at most one taxi-van. Due to this constraint, hotel-chains began bickering over who could operate the taxi-van, before it was finally decided that taxi-van destination hotel would be that of the first tourist waiting in line for transportation. This solution is far from ideal, and can lead to tourists sitting around waiting a long time for their turn on the ferry.

Given a list of tourists and their destination hotels, your job is to assign them to one of the daily flights headed to AxIsland in such a way that minimizes the worse-case total number of ferry transfers needed.  (Worst-case due to the fact that you have no control over which tourist gets in line for the ferry first).

In the examples below, sixteen passengers have lined up for the ferry.  Color is used to symbolize the hotel chain they are staying at, while the shape represents the destination hotel.  The ferry has 16 smaller squares for taxi-cabs with their respective hotel-chain color pattern, along with one large square to accommodate a single taxi-van.  In the first configuration, two ferry transfers are required.  The second configuration has the same passengers as the first, but due to the way they lined up for the ferry, it will take 4 transfers.

Start: