Terwijl je buur vrolijk geniet van haar computerspel, richt je je aandacht op de open datapoort naast het kleine schermp op de stoel voor je.

Hoewel het geen standaard poort is, slaag je erin om hem op je computer aan te sluiten door slim gebruik te maken van een aantal paperclips. Na het aansluiten komt er uit de poort een reeks cijfers.

De gegevens blijken versleuteld te zijn met het eXchange-Masking Addition System (XMAS) dat — handig voor jou — een oude codeersleutel is met een belangrijk zwak punt.

XMAS begint met het verzenden van een preambule van 25 getallen. Daarna moet elk getal dat je ontvangt de som zijn van twee van de getallen die er onmiddellijk aan voorafgaan. De twee getallen hebben verschillende waarden en er kan meer dan één paar getallen zijn die als som het getal opleveren.

Stel bijvoorbeeld dat de preambule bestaat uit de getallen 1 tot en met 25 in een willekeurige volgorde. Om geldig te zijn, moet het volgende getal de som zijn van twee van die getallen:

• 26 zou een geldig volgend getal zijn, omdat het de som is van 1 en 25 (en veel andere paren, zoals 2 en 24).
• 49 zou een geldig volgend getal zijn, omdat het de som is van 24 en 25.
• 100 zou niet geldig zijn; geen twee van de vorige 25 getallen zijn samen 100.
• 50 zou ook niet geldig zijn; hoewel 25 in de vorige 25 getallen voorkomt, moeten de twee getallen in het paar verschillend zijn.

Stel dat het 26e getal 45 is en het eerste getal (dat niet langer in aanmerking komt, omdat het meer dan 25 getallen geleden is) was 20. Opdat het volgende getal geldig zou zijn, moet er tussen 1-19, 21-25 of 45 een paar getallen voorkomen die als som het getal opleveren:

• 26 zou nog steeds een geldig volgend getal zijn, omdat 1 en 25 nog steeds voorkomen in de vorige 25 getallen.
• 65 zou niet geldig zijn, omdat het niet de som is van twee van de voorgaande 25 getallen.
• 64 en 66 zouden beide geldig zijn, omdat ze respectievelijk het resultaat zijn van \(19 + 45\) en \(21 + 45\).

Hier is een groter voorbeeld dat enkel rekening houdt met de vorige 5 getallen (en dus een preambule heeft van lengte 5):

35
20
15
25
47
40
62
55
65
95
102
117
150
182
127
219
299
277
309
576

In dit voorbeeld is na de preambule van 5 getallen bijna elk getal de som van twee van de voorgaande 5 getallen. Het enige getal dat hier niet aan voldoet, is 127.

Opgave

De eerste stap om de zwakte in de XMAS-gegevens uit te buiten, is het eerste getal in de lijst te vinden (na de preambule) dat niet de som is van twee van de \(m\) getallen ervoor, met \(m\) de lengte van de preambule. Wat is het eerste getal dat deze eigenschap niet bezit? Hiervoor ga je als volgt te werk:

• Schrijf een functie find_error waaraan twee argumenten moeten doorgegeven worden: i) de padnaam (char*) van een tekstbestand met een lijst van getallen (één getal per regel) en ii) de lengte \(m\) (int) van de preambule. De functie moet het eerste getal (int) in de lijst (na de preambule) teruggeven dat niet de som is van twee van de \(m\) voorgaande getallen.

Voorbeeld

In deze interactieve sessie gaan we ervan uit dat het tekstbestand numbers.txt¹ zich in de huidige directory bevindt.

> find_error("numbers.txt", 5)
127