Lösningar till uppgifterna i
Kvalet till Programmeringsolympiaden 2005.

Lösningarna är skrivna i C och en del av dem är tyvärr okommenterade. Tillsammans med kommentarerna nedan hoppas jag ändå att de kan vara till hjälp.

Kom ihåg att alla sätt att lösa en uppgift är rätt utom de som är fel!
Skriv gärna om ni har frågor, kommentarer, tips om andra lösningar m.m. Kolla också gärna in träningssajten.
Pär Söderhjelm, par.soderhjelm@teokem.lu.se
Uppgifterna (PDF)  Rättelse: svaren på testexemplen i uppgift 4 ska vara KALLI och PIKTU.
Testdata (PDF) (tillgängligt inom kort)

Uppgift 1 - Tomater

Här simulerar man helt enkelt förloppet dag för dag med hjälp av en array som talar om huruvida varje tomat är mogen eller ej. Varje dag kollar man för varje omogen tomat om någon av dess grannar är mogna. I så fall markerar man den som mogen. En liten knepighet är att en "nymogen" tomat inte får påverka sina omogna grannar under samma dag som den själv mognade. Detta kan lösas antingen genom att ha två olika arrayer för tomatstatusen före respektive efter den aktuella dagen, eller genom att, som i mitt lösningsförslag, spara vilken dag som varje tomat mognade och då endast låta dem som mognade tidigare påverka.

Lösningsförslag

Uppgift 2 - Tvåvalsfrågorna

Eftersom antalet frågor (nf) är begränsat till 12 finns det högst 2^12=4096 olika facit. Därför kan vi gå igenom alla dessa möjliga facit tills vi hittar ett som för var och en av deltagarnas svar ger det angivna antalet rätt. Att generera alla facit kan göras rekursivt genom att ha en funktion som för en viss fråga sätter först svaret 'j' och sedan anropar sig själv för nästa fråga, därefter sätter 'n' och anropar sig själv för nästa fråga. När funktionen anropar sig själv med alla frågor redan ifyllda kollar man om facit stämmer. Om man är lite lat kan man istället använda sig av att varje tal mellan 0 och (2^nf)-1 direkt ger ett facit om man översätter det till binär form. Exempelvis, för nf=2, erhålls 00, 01, 10 och 11, vilket naturligtvis kan översättas direkt till 'nn', 'nj', 'jn' och 'jj'. Med bitvisa operatorer blir det hela mycket enkelt, vilket visas i lösningsförslaget.

Lösningsförslag

Uppgift 3 - Gräsklippning

En lite udda typ av uppgift som bygger på att även om gräsklippningen tar helt olika lång tid varje gång, så får man samma svar om man tar ett medelvärde över många klippningar. Praktiskt sett utgör detta inget problem, man låter en loop gå 10000 gånger, utför en klippning varje gång och lägger ihop antalet minuter som varje klippning tar. På slutet delas denna summa med 10000 för att få medelvärdet. Själva klippningen görs enklast i en loop där varje iteration innebär ett (tillåtet) steg för gräsklipparen. Notera att varje steg ska tas oberoende av  var gräsklipparen har varit innan, men programmet måste ändå hålla reda på vilka rutor som gräsklipparen har varit på för att kunna avgöra när klippningen är klar. När man tar ett slumpmässigt steg kan det vara bekvämt att använda en konstant array med två tal (förflyttning i x- och y-led) för var och en av de fyra riktningarna.

Lösningsförslag

Uppgift 4 - Namn

Denna olycksaliga uppgift är inte så svår egentligen, den blev dock besvärligare eftersom det var fel på de givna testfallen. Jag passar på att be om ursäkt för detta misstag.

Man börjar lämpligtvis med att översätta personnumret till ett ordningstal som anger numrets plats i listan. Detta kan göras genom att loopa över årets 365 dagar med en dagräknare. När man kommer till det givna födelsedatumet multiplicerar man dagräknaren med 1000 och lägger till de tre sista siffrorna i personnumret. Den andra delen av uppgiften är att hitta det namn som korresponderar mot detta ordningstal. Namnsorteringen som nämns i uppgiftstexten behöver naturligtvis inte göras i praktiken, det är bättre att generera namnen i bokstavsordning och sluta när man har kommit till rätt plats i listan (och helst INTE ett steg för tidigt!). För genereringen kan man  använda ett rekursiv funktion som för en viss bokstavsposition går igenom alla möjliga bokstäver (de 9 vokalerna om det är position 2 eller 5, de 20 konsonanterna i övriga fall) och för varje sådan bokstav anropar sig själv för nästa position. Man inser lätt att om bokstäverna gås igenom i alfabetisk ordning i varje steg, så blir namnen automatiskt sorterade. När funktionen anropas för position 6 har ett helt namn genererats och en räknare ökas. Om räknarens position överensstämmer med det sökta ordningstalet är det bara att avbryta och skriva ut namnet.

Lösningsförslag

Uppgift 5 - Vända

Detta är ett typiskt "sökningsproblem", ganska vanligt förekommande på programmeringsolympiaden, läs vidare på vår träningssajt. Typiskt så finns det en startposition och en slutposition som det gäller att uppnå med så få "drag" som möjligt. Hur svårt ett sökningsproblem är beror inte så mycket på hur dragen ser ut, utan i första hand på hur många "tillstånd" som finns, d.v.s. hur många olika spelpositioner som kan uppstå totalt. Om antalet tillstånd är mindre än vad man får plats med i minnet (i storleksordningen en miljon), går det alltid att lösa problemet effektivt med s.k. bredden-först-sökning (BFS). Denna sökning bygger på två principer, dels att man aldrig går till samma tillstånd flera gånger (man sparar var man har varit), och dels att man besöker tillstånden i "avståndsordning", d.v.s. först besöker man alla tillstånd som kan nås med ett drag från startpositionen, därefter alla med två drag o.s.v. Därmed är man garanterad att hitta den kortaste vägen till slutpositionen, och tidsåtgången är jämförbar med antalet tillstånd. Antalet tillstånd i detta problem är N*2^(N-1), d.v.s. maximalt 448, vilket gör sökningen väldigt effektiv. Det knepiga med att använda BFS i detta fall är att man måste kunna översätta varje position till ett heltal för att kunna spara om man har varit där innan. Detta kan göras genom att skapa ett binärt tal med brickornas färger (0 för svart, 1 för vit) samt baka in information om var den tomma platsen finns.

Lösningsförslag (BFS)

Vill man undvika krångel med numrering av tillstånden, kan man tillgripa den andra generella sökningsmetoden, djupet-först-sökning (DFS), ofta kallad backtracking. Från en viss ställning gör en rekursiv funktion alla tänkbara drag, och för varje drag anropar den sig själv med den nya ställningen. Resultatet blir att man utforskar alla fortsättningar på ett visst förstadrag innan man utför nästa förstadrag, man söker alltså på djupet istället för på bredden. Då är man naturligtvis inte längre garanterad att hitta den kortaste dragserien till slutpositionen först, utan man måste söka igenom alla olika alternativ och hela tiden hålla reda på det bästa resultatet. Däremot bör man naturligtvis aldrig fortsätta framåt i en dragserie som redan har fler drag än det bästa resultatet hittills. Därför är det viktigt att ha en övre gräns på antalet drag, eftersom man annars kan börja gå runt i loopar och aldrig komma fram till slutpositionen. Om man inte vet någon övre gräns kan man alltid, som i lösningsexemplet nedan, chansa på en övre gräns, köra DFS-lösningen och, om ingen lösning hittas, öka gränsen och köra igen.

Lösningsförslag (DFS)

Uppgift 6 - CD-brännaren

Till skillnad från föregående uppgift finns det  här ingen effektiv lösning (såvitt jag vet alltså, det är fritt fram för invändningar), utan här är det backtracking som gäller, alla fördelningar av katalogerna måste testas. Tanken med uppgiften är att man inte ska behöva uppfinna optimeringar med hänsyn till katalogernas storlekar eller kolla efter specialfall. Däremot måste man se upp så att man inte upprepade gånger testar fördelningar av katalogerna som egentligen är samma, då tar det svåraste fallet för lång tid. Mitt lösningsförslag bygger på att man fyller skiva efter skiva med kataloger. En rekursiv funktion testar att lägga in var och en av de kataloger som ännu inte har lagts på någon skiva, och för varje val anropar funktionen sig själv med en mindre katalog att bekymra sig över. Man håller naturligtvis reda på den bästa lösningen som man hittills hittat, så att man exemplevis aldrig börjar fylla den femte skivan om man redan har hittat en lösning med fem skivor. Två viktiga förbättringar av denna enkla lösning bör göras. För det första, när vi placerar den första katalogen på varje skiva är det onödigt att testa alla möjliga kataloger. Eftersom varje katalog ändå ska in på någon skiva kan vi utan problem bestämma oss för att ta den första ännu otagna katalog vi har. För det andra, inom en given skiva spelar katalogernas ordning ingen roll. Har vi testat att lägga in katalogerna A, C, E på en skiva är det helt överflödigt att kolla C, E, A, eftersom detta ger samma resultat. Alltså kan vi bestämma att när vi väl har lagt in en katalog på en skiva, så struntar vi i de kataloger som ligger före den (i indataordningen), även om det finns kataloger där som ännu inte är inlagda. Detta gäller naturligtvis endast så länge vi håller oss på samma skiva, när vi börjar på en ny skiva måste alla otagna kataloger komma ifråga igen. Läs gärna mer om liknande problem som har effektiva lösningar på träningssajten. (Dynamisk programmering -> Knapsackproblemet)

Lösningsförslag