Stel dat er een verzameling collineaire¹ punten gegeven is. Indien we de afstanden tussen alle punten uit de verzameling willen bepalen, is dit heel eenvoudig. We overlopen elk paar punten en bepalen tussen deze twee punten de afstand.

Veronderstel dat de verzameling met punten {0, 6, 11, 14} gegeven is. Dan kunnen we eenvoudig alle afstanden tussen de punten bepalen.

De afstanden tussen de paren van punten vormen de multiset² met elementen 14, 8, 11, 6, 5 en 3. Hoewel er hier geen dubbels voorkomen, is dat bij bijvoorbeeld de punten {2, 4, 6} met afstanden {4: 1, 2: 2} wel het geval. We noteren een multiset als een afbeelding van een waarde op zijn multipliciteit. Voor een verzameling met \(n\) punten zal het aantal afstanden gelijk zijn aan \({n \choose 2} = \frac{n(n-1)}{2}\).

Moeilijker is om het turnpike probleem op te lossen. Dit is precies het omgekeerde probleem: gegeven multiset van afstanden, construeer een verzameling collineaire punten waartussen de afstanden juist de gegeven multiset vormen. Merk op dat zo’n verzameling niet voor elke multiset bestaat en dat ze zeker niet uniek is.

Indien we bijvoorbeeld de afstanden 14, 8, 11, 6, 5 en 3 krijgen, vinden we naast de oplossing {0, 6, 11, 14} ook de verzameling punten {0, 3, 8, 14}:

Indien we alle punten van de oplossing horizontaal verschuiven, kunnen we een nieuwe oplossing creëren die, op een verschuiving na, identiek is aan de oorspronkelijke oplossing. Door het meest linkse punt op positie 0 te plaatsen, kiezen we één van die oplossingen. Zo zullen alle punten steeds een positieve coördinaat hebben. We kiezen ervoor om steeds deze canonische vorm te gebruiken.

Implementatiedetails

Om het turnpike probleem op te lossen, schrijf je een klasse RecursiveTurnpike die de gegeven interface Turnpike³ implementeert. Deze eist twee methoden:

• public Map<Integer, Long> pointsToDistances(Set<Integer> points); die gegeven een verzameling van punten de bijhorende multiset van afstanden zal berekenen.
• public Set<Integer> distancesToPoints(Map<Integer, Long> distances); die gegeven een multiset van afstanden een overeenkomstige verzameling van punten zal berekenen. Deze verzameling moet het getal 0 bevatten en alle andere elementen moeten strikt positief zijn. Als er geen verzameling van punten bestaat voor gegeven afstanden, geeft de methode null terug.

Maak in de methode distancesToPoints verplicht gebruik van recursieve backtracking om de gezochte verzameling punten te construeren.

Gebruik eventueel de testklasse SimpleTest⁴ om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.