Her følger et utdrag av resultatlisten:
Sortert etter n=18 bnavn/program n=18 n=19 n=20 83 263 591 621 012 754 583 699 512 løsninger kjetimh/dronning 008m35.550s 65m25.710s 581m48.710s kjetimh/rekursivdronning 008m59.350s 64m16.710s 531m42.810s eglccapr/Dronning 009m39.360s 75m25.640s 602m58.360s johnco/Dronning 016m53.910s 124m01.700s 1080m54.820s kimr/Dronningopt 028m33.550s 230m29.680s 1814m41.120s runeval/Dronningoppgave 032m16.860s 252m39.890s runeval/Dronning 039m02.770s 294m10.100s zhiguanj/Oblig2 049m16.000s 377m44.530s kevinu/D 052m24.800s kimr/Dronstandard 058m22.760s ... bmmender&richar/nqueens 074m25.590sFor å studere de enkelte bidrag, følg disse lenkene: johnco, kimr, kjetimh, kevinu, eglccapr, runeval, bmmender. Flere legges til etter hvert som samtykke til offentliggjøring mottas.
Tidene fra kjøring med unixkommandoen time, jf. man time.
Juryen består av en student som tar INF1010, to gruppelærere i emnet og en tidligere foreleser i «Algoritmer og datastrukturer» og sjakkspaltist i Aftenposten, Rune Djurhuus (juryleder). Undertegnede er sekretær og legger fram forslag om rangering og premiering.
Juryen møttes første gang tirsdag 19. april kl 1215. Andre gang for å kåre vinnerne tirsdag 26. april kl 1300.
Det er levert inn 35 programmer fra 28 studenter (Antall e-post med deltagerprogrammer).
Alle program er testet for n=8,9,10,11,12
Første tidssammenligning for n=16.
De fleste (bortsett fra de tregeste er testet for n=18). De 6 beste fra n=18 testet for n=19.
Juryen ba om ytterligere testing av kandidatene som ser ut til å vinne kategori 1 og 3.
For å kåre en vinner i kategori 2 («matematisk») trengs mer dokumentasjon. Noen deltagere har levert god dokumentsjon som beskriver det de har gjort og hvilke avskjæringer som er lagt inn og hvorfor. Andre har skrevet svært lite.
For å kåre en vinner her, trengs i det minste en skisse av algoritmen med forklaring og logisk argumentasjon for de avskjæringer man gjør. Argumentasjonen må gjerne inneholde beregninger for hvor mange kandidater til løsninger man reduserer med.
Dette er litt uklart og det er vasnkelig for dere å vite om dere har levert tilstrekkelig dokumentasjon. Her er et utdrag fra en e-post til en av deltagerne:
| Hei
|
| Jeg hadde satt pris på om dere kunne sendt ut et semiindviduelt
| varslingsmail til deltagerene i kategori 2 som fortalte om de var i
| kategorien "god dokumentasjon" eller "svært lite". Dette for å unngå at
| folk som allerede har god nok dokumentasjon for sikkerhets skyldskriver
| en skikkelig mikro t-skje avhandling på bekostning av infoblig ogandre
| viktige ting.
|
| Selv regner jeg meg som et sannsynlig gråsone tilfelle mellom "nok" og
| "for lite" dokumentasjon. Samtidig har jeg to obliger til fredag, og på
| den andre siden har jeg lagt såppass med arbeid i det at jeg ikke vil bli
| diskvalifisert for en liten filleting som at "det er noe litt uklart i
| dokumentasjonen", eller "Jeg hang ikke helt med på hva han mente med
| /"verdi/"".
|
| Det som står på siden kan riktignok tolkes som at ALLE må levere
| tilleggsdokumentasjon, men hvis dette er tilfelle, vær så snill å skrive
| det i litt mer klartekst.
Takk for nyttig reaksjon og tilbakemelding. For å informere andre som opplever samme dilemma, tillater jeg meg å legge en kopi av denne e-korrespondansen på «resultater.html».
Tilstrekkelig dokumentasjon vil være programkommentarer (eller sidedokument) som forklarer hvordan man har tenkt i forbindelse med avskjæringer. Dette kan gjøres på mange måter, men en oversikt over hvor mange avskjæringer, et argument for den enkelte avskjæring og forsøk på å beregne hvor mye man sparer (uttrykt vha. n) , hjelper juryen til å forstå hva som er gjort. En «matematisk» god løsning har en estetisk side også, men jeg vil ikke anbefale at juryen legger særlig vekt på det. Jeg vil anbefale at den algoritmen som unngår å generere flest «overflødige» løsninger - og som forklarer hvordan - kåres som vinner i denne kategorien.
Bakgrunnen for denne måten å tenke på, er at en algoritme helt uten avskjæringer genererer alle kandidater til løsninger (rekursjonen når bunnen) før man ser på om rotasjon/speiling er funnet før. En «god» algoritme begrenser rekursjonen så tidlig som mulig.
En annen ting som kanskje kan gjøres - og kommenteres - er å hoppe over visse permutasjonsgrener ved å hoppe over bestemte verdier i p[k] på bakgrunn av kunnskap om p[0:k-1]? Kan man bruke «springeravstand»?
Leveringsfrist for tillegsdokumentasjon settes til fredag kl 1500. Det kan ikke gjøres forandringer i innlevert program.
Juryen vil på dette grunnlag forsøke å kåre en vinner også i denne kategorien til neste forelesning.
--
Stein Michael