Eindelijk kan je het bericht van de Elfen ontcijferen. HI, zegt het bericht. Je gaat verder met zoeken naar de sleutels van de slee.

Voor je doemt iets op wat lijkt op een grote diepzeetrog¹. Zouden de sleutels daarin kunnen gevallen zijn? Je kunt beter een sonde op onderzoek uitsturen.

Je onderzeeër heeft een lanceerplatform die sondes kan afvuren met elke gehele² snelheid in de x (vooruit) en y (naar boven, of naar benden indien negatief) richtingen. Zo zou een x,y-beginsnelheid zoals 0,10 de sonde bijvoorbeeld recht omhoog schieten, terwijl een beginsnelheid zoals 10,-1 de sonde naar voor zou schieten met een kleine neerwaartse hoek.

De x,y-positie van de sonde begint bij 0,0. Daarna volgt hij een bepaald traject door in stappen te bewegen. Bij elke stap vinden deze wijzigingen plaats in deze volgorde:

De x-positie van de sonde verhoogt met zijn x-snelheid.
De y-positie van de sonde verhoogt met zijn y-snelheid.
Door wrijving verandert de x-snelheid van de sonde met 1 in de richting van de waarde 0. Dat wil zeggen dat de snelheid met 1 afneemt als hij groter is dan 0, met 1 toeneemt als hij kleiner is dan 0, of niet verandert als hij al 0 is.
Door de zwaartekracht neemt de y-snelheid van de sonde met 1 af.

Om de sonde met succes in de diepzeetrog te mikken, moet hij een traject afleggen waarin hij zich tijdens één van de stappen in een doelgebied bevindt. De computer heeft dit doelgebied reeds berekend (de invoer van deze opgave). Bijvoorbeeld:

target area: x=20..30, y=-10..-5

Dit doelgebied betekent dat je x,y-beginsnelheden moet vinden waarvoor tijdens één van de stappen de x-positie van de sonde minstens 20 en hoogstens 30 is, en de y-positie van de sonde minstens -10 en hoogstens -5 is.

Voor het gegeven doelgebied is een 7,2 beginsnelheid die ervoor zorgt dat de sonde zich tijdens één van de stappen binnen het doelgebied bevindt:

.............#....#............
.......#..............#........
...............................
S........................#.....
...............................
...............................
...........................#...
...............................
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTT#TT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT

In dit diagram is S de beginpositie van de sonde, 0,0. De x-coördinaat neemt naar rechts toe en de y-coördinaat naar boven. Rechtsonder worden de posities binnen het doelgebied weergegeven als T. De positie van de sonde na elke stap (totdat het doelgebied bereikt is) wordt aangeduid met #. (De # rechtsonder is zowel een positie op het traject van de sonde en een positie binnen het doelgebied.)

Een andere beginsnelheid die ervoor zorgt dat de sonde zich na een bepaalde stap binnen het doelgebied bevindt is 6,3:

...............#..#............
...........#........#..........
...............................
......#..............#.........
...............................
...............................
S....................#.........
...............................
...............................
...............................
.....................#.........
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................T#TTTTTTTTT
....................TTTTTTTTTTT

Nog een andere is 9,0:

S........#.....................
.................#.............
...............................
........................#......
...............................
....................TTTTTTTTTTT
....................TTTTTTTTTT#
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT

Een beginsnelheid waarvoor de sonde zich tijdens geen enkele stap binnen het doelgebied bevindt, is 17,-4:

S..............................................................
...............................................................
...............................................................
...............................................................
.................#.............................................
....................TTTTTTTTTTT................................
....................TTTTTTTTTTT................................
....................TTTTTTTTTTT................................
....................TTTTTTTTTTT................................
....................TTTTTTTTTTT..#.............................
....................TTTTTTTTTTT................................
...............................................................
...............................................................
...............................................................
...............................................................
................................................#..............
...............................................................
...............................................................
...............................................................
...............................................................
...............................................................
...............................................................
..............................................................#

De sonde lijkt door het doelgebied te gaan, maar bevindt zich er na geen enkele stap binnen. In plaats daarvan gaat hij verder naar beneden en naar rechts - alleen de eerste paar stappen worden weergegeven.

Als je een zeer wetenschappelijke sonde vanaf het supercoole lanceerplatform wil afvuren, dan kun je het net zo goed in stijl doen. Hoe hoog kun je de sonde laten gaan, terwijl die nog steeds binnen het doelgebied passeert?

In het voorgaande voorbeeld is de beginsnelheid 6,9 de beste die je kan kiezen, omdat de sonde daarmee een maximale y-positie van 45 bereikt. (Elke hogere y-beginsnelheid zorgt ervoor dat de sonde volledig voorbij het doelgebied schiet.)

Opgave

Zoek de beginsnelheid die ervoor zorgt dat de sonde de hoogste y-positie bereikt en tijdens een bepaalde stap nog altijd binnen het doelgebied passeert. Wat is de hoogste y-positie die de sonde op dit traject bereikt? Bepaal dit op de volgende manier:

Schrijf een functie shoot waaraan de padnaam (str) moet doorgegeven worden van een tekstbestand dat een doelgebied vastlegt. De functie moet de hoogste y-positie (int) teruggeven die de sonde kan bereiken op een traject dat tijdens één van de stappen binnen het doelgebied passeert.

Voorbeeld

In deze interactieve sessie gaan we ervan uit dat de tekstbestanden target01.txt³ en target02.txt⁴ zich in de huidige directory bevinden.

>>> shoot('target01.txt')
45
>>> shoot('target02.txt')
4753

Epilogue

Gambuzzi Roberto (@gbinside⁵) animeerde zijn oplossing.