Een reuzachtige walvis¹ heeft besloten dat jouw onderzeeër zijn volgende maaltijd wordt, en hij is veel sneller dan jij. Je kan nergens meer heen!

Plots snelt er een zwerm krabben (elk in zijn eigen kleine onderzeeër - anders is het hier veel te diep voor hen) ter hulp! Ze lijken zich klaar te maken om een gat in de zeebodem te schieten. Sensoren geven aan dat er zich een massief ondergronds grottenstelsel bevindt onder de plek waarop ze aan het mikken zijn!

De krabbenonderzeeërs moeten allemaal netjes uitgelijnd zijn voordat ze genoeg kracht hebben om een gat te schieten dat groot genoeg is voor je onderzeeër om doorheen te komen. Het ziet er echter niet naar uit dat ze daarin zullen slagen voor de walvis je vangt! Misschien kun je hen helpen?

Er is echter een valstrik - de onderzeeërs van de krabben kunnen alleen horizontaal bewegen.

Je maakt snel een lijst met de horizontale positie van elke krab (de invoer van de opgave). Krabbenonderzeeërs hebben een beperkte hoeveelheid brandstof, dus moet je een manier vinden om hun horizontale posities uit te lijnen, terwijl daar zo weinig mogelijk brandstof voor moet gebruikt worden.

Neem bijvoorbeeld de volgende horizontale posities:

16,1,2,0,4,2,7,1,2,14

Dit betekent dat er een krab is met horizontale positie 16, een krab met horizontale positie 1, enzovoort.

Elke verandering van 1 stap in de horizontale positie van één enkele krab kost 1 brandstof. Je zou elke horizontale positie kunnen kiezen om alle krabben op één lijn te krijgen, maar degene met de minste brandstofkost is horizontale positie 2:

• Ga van 16 naar 2: 14 brandstof
• Ga van 1 naar 2: 1 brandstof
• Ga van 2 naar 2: 0 brandstof
• Ga van 0 naar 2: 2 brandstof
• Ga van 4 naar 2: 2 brandstof
• Ga van 2 naar 2: 0 brandstof
• Ga van 7 naar 2: 5 brandstof
• Ga van 1 naar 2: 1 brandstof
• Ga van 2 naar 2: 0 brandstof
• Ga van 14 naar 2: 12 brandstof

Dit kost in totaal 37 brandstof. Dit is de goedkoopst mogelijke positie om alle krabben uit te lijnen. Je krijgt bijvoorbeeld een duurdere uitlijning op positie 1 (41 brandstof), positie 3 (39 brandstof), of positie 10 (71 brandstof).

Opgave

Bepaal de horizontale positie waarop de krabben zich kunnen uitlijnen met zo weinig mogelijk brandstof. Hoeveel brandstof moeten ze verbruiken om zich op die positie uit te lijnen? Bepaal dit op de volgende manier:

• Schrijf een functie fuel waaraan de padnaam (str) moet doorgegeven worden van een tekstbestand met de horizontale posities van alle krabben in een zwerm. De functie moet teruggeven hoeveel brandstof (int) er minimaal nodig is om alle krabben op dezelfde horizontale positie uit te lijnen.

Voorbeeld

In deze interactieve sessie gaan we ervan uit dat de tekstbestanden positions01.txt² en positions02.txt³ zich in de huidige directory bevinden.

>>> fuel('positions01.txt')
37
>>> fuel('positions02.txt')
347011