Gammalt Ommästarprov i Funktionell Programmering 2022

Mästarprovet ska lösas individuellt och redovisas både skriftligt och muntligt. Inget samarbete är tillåtet, se vidare hederskodexen. Du ska alltså inte diskutera lösningar med någon annan fram till dess att alla muntliga redovisningar är avklarade. Inlämningarna plagiatgranskas.

Skriftliga lösningar ska lämnas in i Canvas (som PDF; om du skriver med LaTeX, använd pdflatex för att göra om det till en pdf; Om du skriver i Word, välj spara som och välj filformatet pdf; inskannade handskrivna lösningar går också bra men LaTeX är bäst; det går också bra att skicka in kod i separata .hs-filer) senast Deadline. Det är viktigt att du lämnar in i tid! Om du inte ser någon inlämningsknapp på denna sida så ska du kontrollera att du är inloggad i Canvas. Klicka i så fall på inloggningsikonen i den gråa vänstermenyn.

Skriv ditt namn och KTH-adress överst på framsidan av lösningarna. Läs på dina lösningar inför den individuella muntliga redovisningen som kommer att ske kort efter deadline i Zoom för någon i lärarlaget. Tidsbokningen kommer att komma upp nära uppgiftens deadline och det kommer att anslås på Canvas när de har kommit upp. Den muntliga redovisningen tar 10 minuter för dig, men de som bedömer dig har 5 minuters paus innan varje redovisning.

Uppdatering: Eftersom det här är ett gammalt prov så ges ingen redovisning längre.

Det är viktigt att du förbereder dig inför den muntliga redovisningen. För att en uppgift ska godkännas ska du kunna förklara och motivera din implementation och de delar av Haskell och paradigmet funktionell programmering som du har använt. Alla programmeringsuppgifter ska lösas i Haskell. Det är alltid tillåtet att använda hjälpfunktioner. Det är alltid tillåtet att använda nästlade typer.

Läs uppgifterna mycket noga så att du inte råkar basera dina lösningar på en missuppfattning. Fråga en lärare på kursen om något är oklart.

Generella regler för mästarprov såsom vad som krävs för godkänt finns på mästarprovssidan i Canvas.

Som exempel på hur kod-delen av en inlämningsuppgift kan se ut, se facit och rättningsmallar från Tentaarkivet i DD1361, till exempel 2017-09-18 som gicks igenom på föreläsningen. Som exempel på hur en teorifråga kan besvaras, se facit och rättningsmallar från tentaarkivet i DD1362 till exempel juni 2021.

Lycka till!
/Marcus

Card Royale

Card Royale är ett kortspel som går till på detta sätt:
A. Det finns en vanlig kortlek Links to an external site. utan jokrar, dvs den innehåller 52 spelkort.
B. Varje spelkort har en valör mellan 2-14 och en färg som är hjärter, spader, ruter eller klöver.
C. Det finns N spelare i spelet. N kommer att variera under spelets gång.
D. Alla spelare har ett antal kort på handen, från början 5.
E. Det är en av spelarnas tur (turn).
F. Det finns en kasthög som innehåller de spelkort som har kastats.
G. Det finns en chanshög som innehåller de spelkort som varken har delats ut eller kastats.

Vem som börjar avgörs genom lottning. Varje spelomgång går till som följer:
1. Spelaren vid turen väljer ett kort från handen och lägger det på bordet med baksidan upp utan att visa någon annan. Det är också tillåtet att ta det översta kortet i chanshögen, men då måste det kortet spelas. Det får inte bytas ut mot ett på handen.
2. Spelaren vid turen väljer en annan spelare att utmana som då behöver välja ett av sina kort från handen, alternativt det översta kortet i chanshögen och lägger ut på bordet.
3. Korten avslöjas. Den som har den högsta valören vinner. Om det är samma valör så vinner hjärter över alla andra färger, ruter vinner över allt som inte är hjärter, klöver vinner över spader och spader förlorar alltid. Båda korten kastas i kasthögen och vinnaren får förlorarens eventuella kort på handen tillagda till sin egen hand. Förloraren är ute ur spelet.
4. Om det bara finns en spelare kvar så har den spelaren vunnit och spelet är slut.
5. Om det finns flera spelare kvar går turen över till vinnaren från den senaste duellen och spelet fortsätter från punkt 1.

Uppgift 1:
Använd Haskells record syntax Links to an external site. för att bygga upp tillståndet (state) för spelet. Gör records för spelkort, spelare och spelet som helhet. Se till att alla alfabetiska punkter finns med.
Uppgift 2:
Skapa en funktion isHealthy som tar in ett state för spelet och verifierar att:
i: Alla spelkort i spelet är giltiga (alla valörer är mellan 2-14 och färgen är en av de fyra giltiga).
ii: Alla spelkort i spelet är unika.
iii: Alla spelare utan kort är eliminerade.

Kom ihåg typsignaturerna.
Punkt i och ii behöver vara implementerade med hjälp av högre ordningens funktioner, dvs ni behöver åtminstone använda högre ordningens funktioner i lösningen.
Punkt iii behöver vara implementerad med rekursion. Det går lika bra med svansrekursion som icke-svansrekursion men du behöver förklara vilket som din lösning använder.

Uppgift 3:

Förklara i detalj hur en implementation av spelets tillstånd med immutability (oföränderlighet) skulle skilja sig från en implementation med mutability (föränderlighet). Förklara i detalj vad som händer när en spelare blir eliminerad i en strid om vi (1) använder immutability och (2) inte använder immutability.

Överkurs:
Implementera hela spelet så att det går att spela. Observera att det är överkurs och inte betygsatt på något sätt så att inte göra det alls, göra en textimplementation eller en grafisk implementation går precis lika bra.

Uppgift 4 (som är orelaterad till kortspelet):
En funktion heter allCloseTriplets. Den tar in en lista med koordinater i 3D med x, y och z samt ett avstånd delta längdenheter och ger ifrån sig en lista med tripplar av koordinater. Din uppgift är att skriva denna funktion så att den ger ifrån sig alla tripplar som uppfyller att:
1. Alla tre punkterna är olika.
2. Avståndet mellan alla par av dessa 3 punkter är mindre än delta längdenheter. Om punkterna heter A, B och C så ska alltså A och B, B och C samt A och C vara högst delta längdenheter från varandra. Det är som vanligt tillåtet med hjälpfunktioner. Kom som vanligt ihåg typsignaturen. Det är tillåtet att använda funktioner i Haskells standardbibliotek och/eller att läsa på om Euklidiskt avstånd på Wikipedia Links to an external site..

En lösning som är O(n³) är tillräckligt effektiv för det här provet.

Facit och rättningsanvisningar.