Inpakken!
Een oude programmeeropgave bij de Programmeerwedstrijden voor Universiteitsteams luidt als volgt:
Om in het nieuws te komen heeft kunstenaar Christo
besloten een hele stad in te pakken! Om de kosten zoveel mogelijk
te beperken, probeert hij een methode te vinden die
zo weinig mogelijk materiaal gebruikt.
De invoer.
Op de eerste regel staat het aantal gebouwen (1..100).
Vervolgens op iedere regel één gebouw, gegeven door de
plaats van de linkerkant, rechterkant en hoogte.
Dit zijn gehele getallen die liggen tussen 0 en 10000.
De uitvoer.
Op drie decimalen nauwkeurig de lengte van
het touw dat tenminste nodig is om de stad in te pakken.
Er dient een programma geschreven te worden dat, gegeven
de gebouwen van een stad, de hoeveelheid materiaal berekent
die nodig is om de stad in te pakken.
Om het niet al te moeilijk te maken beperkt Christo zich tot
twee-dimensionale steden.
Het inpakmateriaal is dan één-dimensionaal (een touw).
De onderkant van de stad hoeft niet te worden ingepakt.
Bij inpakken trekken we in gedachten het touw van links naar rechts over de gebouwen heen. Op elk moment kijken we vooruit en bepalen we het volgende punt waar het touw de gebouwen zal raken. Dat is steeds het punt dat we onder de grootste hoek vooruit zien.
Bij strak trekken leggen we het touw naar het volgende punt, en kijken dan achteruit om te zien of er geen `kuiltje' ontstaat waaruit we het touw strak kunnen trekken.
Wrapped Reichstag, Berlin 1971-95
Photo: Wolfgang Volz ©Christo
christojeanneclaude.net
Ook de ideeen van andere manieren om het probleem aan te pakken komen aan bod: quick hull een zogenaamde heuristiek die in de praktijk meestal snel werkt, maar niet gegarandeerd eficient rekent, en divide and conquer een algemene aanpak om problemen `recursief' op te lossen die ook hier toepasbaar is.
Het probleem is dan ook geen speelgoed, maar staat in de theorie bekend als convex hull, en is belangrijk in de robotica en de computergrafiek.