Als je op het vliegtuig wil stappen, ontdek je een nieuw probleem: je hebt ergens je instapkaart laten vallen! Je weet niet zeker welke stoel van jou is, en het cabinepersoneel heeft het veel te druk met de stroom mensen die plotseling door de paspoortcontrole gekomen zijn.
Je schrijft snel een programma om de camera van je telefoon te gebruiken om alle instapkaarten in de buurt te scannen. Misschien kan je je stoel wel vinden door middel van eliminatie.
In plaats van zones if groepen1 gebruikt deze luchtvaarmaatschappij een binaire indeling van de ruimte om mensen te laten zitten. Een stoel wordt aangeduid als FBFBBFFRLR, waarbij F staat voor “vooraan”, B voor “achteraan”, L voor “links” en R voor “rechts”.
De eerste zeven tekens zijn ofwel F of B, en duiden één van de 128 rijen in het vliegtuig aan (genummerd van 0 tot en met 127). Elke letter zegt je in welke helft van een regio de gegeven stoel zicht bevindt. Begin met de volledige lijst van rijen. De eerste letter geeft aan of de stoel zich in het voorste deel (0 tot en met 63) of in het achterste deel (64 tot en met 127) bevindt. De volgende letter geeft aan in welke helft van die regio de stoel zich bevindt, enzoverder, totdat je precies één rij overhoudt.
Neem bijvoorbeeld enkel de eerste zeven tekens van FBFBBFFRLR:
0 tot en met 127.F betekent dat je de onderste helft moet nemen, waardoor je rijen 0 tot en met 63 overhoudt.B betekent dat je de bovenste helft moet nemen, waardoor je rijen 32 tot en met 63 overhoudt.F betekent dat je de onderste helft moet nemen, waardoor je rijen 32 tot en met 47 overhoudt.B betekent dat je de bovenste helft moet nemen, waardoor je rijen 40 tot en met 47 overhoudt.B behoudt de rijen 44 tot en met 47.F behoudt de rijen 44 tot en met 45.F behoudt de kleinste van de twee, rij 44.De laatste drie tekens zijn L of R. Deze geven duiden juist één van de 8 kolommen van de stoelen in het vloegtuig aan (genummerd van 0 tot en met 7). Je kan opnieuw hetzelfde proces als hierboven doorlopen, maar deze keer zijn er slechts drie stappen. L betekent dat je de onderste helft moet nemen, terwijl R betekent dat je de bovenste helft moet nemen.
Neem bijvoorbeeld enkel de laatste drie tekens van FBFBBFFRLR:
0 tot en met 7.R betekent dat je de bovenste helft moet nemen, waardoor je kolommen 4 tot en met 7 overhoudt.L betekent dat je de onderste helft moet nemen, waardoor je kolommen 4 tot en met 5 overhoudt.R behoudt de grootste van de twee, kolom 5.Dus, als we FBFBBFFRLR decoderen dan weten we dat de stoel te vinden is op rij 44, kolom 5.
Elk stoep heeft ook een unieke stoel-ID: vermenigvuldig de rij met 8 en tel daar de kolom bij op. In ons voorbeeld heeft de stoel ID 44 * 8 + 5 = 357.
Hier zijn nog enkele instapkaarten:
BFFFBBFRRR: rij 70, kolom 7, stoel-ID 567.FFFBBBFRRR: rij 14, kolom 7, stoel-ID 119.BBFFBBFRLL: rij 102, kolom 4, stoel-ID 820.Loop bij wijze van controle door de lijst van instapkaarten. Wat is de hoogste stoel-ID io een instapkaart? Bepaal dit op de volgende manier:
row waaraan een stoel (String) wordt doorgegeven. De functie moet teruggeven op welke rij (Int) de gegeven stoel zich bevindt.column waaraan een stoel (String) wordt doorgegeven. De functie moet teruggeven op welke kolom (Int) de gegeven stoel zich bevindt.seatId waaraan een stoel (String) wordt doorgegeven. De functie moet de stoel-ID (Int) van de gegeven stoel teruggeven.highestSeatId waaraan de padnaam (String) moet doorgegeven worden van een tekstbestand met een lijst van instapkaarten: elke regel bevat de stoel van een instapkaart. De functie moet de hoogste stoel-ID (Int) teruggeven op de gegeven lijst van instapkaarten.In deze interactieve sessie gaan we ervan uit dat het tekstbestand boarding_list.txt2 zich in de huidige directory bevindt.
> row "FBFBBFFRLR"
44
> row "BFFFBBFRRR"
70
> row "FFFBBBFRRR"
14
> row "BBFFBBFRLL"
102
> column "FBFBBFFRLR"
5
> column "BFFFBBFRRR"
7
> column "FFFBBBFRRR"
7
> column "BBFFBBFRLL"
4
> seatId "FBFBBFFRLR"
357
> seatId "BFFFBBFRRR"
567
> seatId "FFFBBBFRRR"
119
> seatId "BBFFBBFRLL"
820
> highestSeatId "boarding_list.txt"
820