De bug die mij een 10 heeft gekost

Afgelopen woensdag, tijdens de fijne tijden van 18:15 tot 21:15, had ik mijn final exam for imperative programming. Eindstand: 9.85. Dat is natuurlijk een prima cijfer! Maar wat mij wrang zit, is dat ik 1 fout had gemaakt, en als ik die niet had gemaakt, ik een 10 had gehad. En ik weet precies welke fout ik heb gemaakt.

Het begon heel goed: eerst een aantal opdrachten van een wat algebraïschere aard, waar je een symbolische begin- en eindwaarde krijgt voor wat variabelen, en je uit moet vogelen wat voor assignments er plaats hadden gevonden om dat zo te maken. Nou waren de antwoorden multiple choice dus het was een kwestie van simpelweg natrekken, maar er zat ook een weggever bij, met begin{x=A, y=B} en eind{x=B, y=A}. Dan weet je al dat het A^=B, B^=A, A^=B, of A-=B, B+=A, A-=B moet zijn. Waar je nu aan denkt mag niet, want nieuwe variabelen waren buiten de spelregels.

De tweede opdracht was wederom geen raketwetenschap: je moest de runtime complexity van een aantal willekeurige "algoritmen" bepalen. Dit kon je heel makkelijk doen door gewoon even te ademen, een pen en papier te pakken, en de inductievariabelen van de loops per loop na te lopen, dan werd het wel duidelijk wat de afgeleide ervan was, waarmee je een soort van differentievergelijking op kon lossen. Als de loop begint met i=0, en i<n moet zijn en elke iteratie i+=i, dan groeit i kwadratisch en is de loop dus O(sqrt(n)) bijvoorbeeld. Groeit hij exponentieel (i*=2) dan is het O(log(n)). Enzovoorts.

Toen kwamen de echte programmeeropdrachtjes. Daar begon ik wat stroef, maar het was eigenlijk gewoon prima te doen. Je moest iets tellen qua hoe veel unieke sommen er bestonden genomen uit n input arrays gelijk aan een input getal, daar gebruikte ik eerst een soort aangepaste insertion sort (O(n²)) om duplicates te verwijderen, met een voorspelbare timeout als gevolg. Toen brak ik het op in 2 stappen, eerst quicksort, dan O(n) deduplicatie, en klaar was kees. Verder had je er dynamic programming voor nodig, iets wat we ruimschoots hadden geoefend. De derde opdracht weet ik niet eens meer.

Maar er zat 1 opdracht tussen die me een beetje liet zweten. Je moest het Goldbach conjecture, dat elk getal>4 te schrijven is als de som van 2 priemgetallen a en b waarbij a<b, numeriek bewijzen door te tellen hoe veel van zulke sommen er bestonden voor een bepaald input getal. Nou had ik dit redelijk snel gekraakt door eerst een array met priemgetallen te genereren, daar doorheen te loopen, en het tweede getal uit te kiezen met b=n-a gevolgd door count += isprime(b).

Alleen één klein probleempje! Twee willekeurige testcases gaven een fout antwoord. Een hoger getal dan verwacht. Het leuke is dat het systeem dan hints gaf. De eerste hint luidde "this test case is nothing special". Oh-oh. De tweede hint was "the input number is greater than 5000000". Maar de eerste hint was belangrijker: het ging hier om een soort vreemde bug. Al gauw genoeg kwam ik erachter dat mijn isPrime voor sommige niet-priemgetallen toch beweerde dat het een priemgetal was.

Toen ging ik de sommen debuggen, en controleerde ik met de hand een paar honderd priemgetallen (nou oké, met de hulp van openssl prime dan). Dit had ik eigenlijk direct al anders aan moeten pakken door gewoon een heel dom priemgetalalgoritme te maken en ze zij aan zij te leggen. Maar goed. Ten eerste ontdekte ik dat getallen met een factor 17 niet goed werden beoordeeld, dus daar voegde ik een handmatige check voor toe: if (x%17==0) {return x==17}. Dit leverde mij een extra testcase in het groen op. Nu nog die tweede.

Ik kwam er maar niet achter. Ik wist dat mijn algoritme niet deugde, maar waarom wist ik niet. Ik kreeg nog een cryptische hint, van iemand die schijnbaar graag zag dat ik die 10 haalde: "17*17". Ik pikte hem niet op. "17 heb ik al", dacht ik. Hier is de code, spot de bug:

int isPrime(int n) {
  if (n < 2) {
    return 0;
  }
  if (n%2 == 0) {
    return n==2;
  }
  if (n%3 == 0) {
    return n==3;
  }
  if (n%5 == 0) {
    return n==5;
  }
  // all possible primes are 5+6x or 7+6x
  for (int i=5; i*i<n; i+=6) {
    if (n%i == 0 || n % (i+2) == 0) {
      return 0;
    }
  }
  return 1;
}

Mocht je die formule nog nooit eerder gezien hebben, hier heb ik hem vandaan: youtube video, rond 16:39. In ieder geval, er zit een bug in. Nou wat blijkt, stel n=289. Dat is niet priem, wat 289 = 17*17. Maar wat is er nou, die for loop stopt vóórdat i*i==n, dus 17*17=289 wordt nooit getest! En hij springt naar return 1! De loop condition had moeten zijn i*i<=n. Een bug van 1 character dus, die mij een 10 heeft gekost.

2022-11-04 in blog