Datortentamen i TDP007 torsdag 17 mars 2016 08:00-12:00 ------------------------------------------------------- Tentan startar kl. 08:00 och pågår till 12:00. Ni kommer att få köra på begränsade datortentakonton, precis som under duggan. Instruktioner för att logga in på dessa lämnas i salen. Alla filer som ni behöver för att lösa uppgifterna finns i hemkatalogen när ni har loggat in. Där finns också en PDF-version av en tidig utgåva av kursboken som ni gärna får använda er av. Öppna den med kommandot okular eller xpdf. Svar på frågor skrivs i vanliga textfiler och programkod skrivs i rb-filer. En fil per huvuduppgift ska produceras, totalt alltså sex filer. Ingen särskild inlämning behöver göras. När man är färdig loggar man ut och lämnar salen. Tentan består av sex uppgifter, några indelade i deluppgifter, som totalt kan ge 32 poäng. För godkänt krävs 50%, dvs minst 16 poäng. För betyg 4 krävs minst 21 poäng och för 5 minst 26 poäng. Inga poäng från duggor kan räknas tillgodo, utan tentan bedöms helt på egen hand. Om man redan har fått ett betyg genom duggan eller tidigare tentor kan det aldrig sänkas, bara höjas. Uppgift 1: Teorifrågor (5p) --------------------------- a) (2p) Den här uppgiften innehåller mycket text, men ska förhoppningsvis inte vara allt för svår. Den testar att du förstår ett antal grundläggande begrepp inom objektorientering i allmänhet och Ruby i synnerhet. Skriv fullständig och körbar kod enligt följande långrandiga specifikation. - Skapa en klass Publication som har tre instansvariabler: title, author och year. Instansvariablerna ska vara läsbara, men inte skrivbara. Ge klassen en initieringsfunktion som tar tre parametrar motsvarande dessa instansvariabler och som sparar värdena i instansvariablerna. De två första variablerna är tänkta att innehålla strängar, den sista ett heltal. - Skapa en klass Book som utökar klassen Publication. Den ska ha ytterligare en instansvariabel publisher som är läsbar men inte skrivbar. Initieringsfunktionen ska ha totalt fyra parametrar som precis som för Book ska innehålla värden till instansvariablerna. De tre som är gemensamma för Book ska initieras med superklassens initieringsfunktion. Klassen Book ska dessutom ha en överlagrad jämförelseoperator som endast jämför titel och författare, inte de övriga två instansvariablerna. b) (2p) Om man läser in ett XML-dokument med hjälp av strömparsning (SAX), vad gör då lyssnarklassen? Beskriv kortfattat vad lyssnarklassen gör och vilken roll dess standardmetoder har. c) (1p) Vad är ett domänspecifikt språk? Vad kan man hoppas uppnå genom att skapa ett sådant? Uppgift 2: Behandling av data i textfiler (5p) ---------------------------------------------- Foobar Inc. har en webbserver som är mycket viktig för företaget. På webbservern finns en loggfil som lagrar information om alla förfrågningar som har kommit in, alltså varje gång någon hämtar en fil. Raderna i loggfilen ser ut så här 67.33.163.249 - - [16/Feb/2012:15:39:39 +0100] "GET /hdr/department/document.shtml HTTP/1.0" 200 11683 "-" "Mozilla/5.0 (compatible; Yahoo! Slurp; http://help.yahoo.com/help/us/ysearch/slurp)" Först kommer IP-adressen för den som skickade förfrågan. Därefter kommer två fält som inte används och som markeras med streck. Sedan visas tid och datum inom hakparenteser. Därefter kommer den egentliga förfrågan. Om det är en normal begäran om att bara ladda ner en fil börjar strängen med GET, följt av katalog och filnamn och sist versionen på protokollet som användes (vilket oftast är HTTP/1.0). Efter denna sträng följer två tal. Det första är statuskoden, som är 200 om allt var okej. Det andra är storleken på filen. Sist på raden är två strängar som anger varifrån användaren kom samt vilken webbläsare som används. I filen access_log finns ett utsnitt av loggfilen. Din uppgift är att skriva ett program som läser in, analyserar loggfilen och presenterar vissa slutsatser. Foobar Inc. är just nu intresserade av att veta hur mycket av vissa typer av filer som användarna laddar ner. De funderar på att lägga dessa filer på en särskild server, om det visar sig att det blir mycket trafik. Just idag är de intresserade av PDF-filer och JPG-filer. Hur många sådana laddades ner under de fem minuter som loggfilen speglar och vad var den totala storleken? Exempel på hur det kan se ut: >> read_log("access_log") 57 PDF-files (12985775 bytes) 88 JPG-files (4327304 bytes) => nil Uppgift 3: XML (6p) ------------------- I filen exam.xml finns ett utdrag ur LiU:s tentaanmälningssystem. Det är i praktiken en lista över alla tentatillfällen på IDA under 2015 i XML-format. Varje tentatillfälle har ett unikt id och innehåller dessutom följande information: - vilken kurs det gäller - när tentan genomförs - hur många som är anmälda - på vilken ort tentan går - om det är en omtenta (markeras med X) - om det är en datortenta (markeras med X) Din uppgift är att skriva olika funktioner för att kunna läsa in och hantera informationen i filen. Om du vill göra en strömparser-lösning hittar du ett exempel att utgå från i filen sax_example.rb och om du vill göra en trädparser-lösning hittar du lite information om metoderna i klassen REXML::Element samt några exempel på XPath-uttryck i filen rexml.txt. a) (3p) Skriv en funktion stat_faculty som räknar hur många tentatillfällen för vanliga tentor (alltså inte datortentor) som finns inom filosofisk respektive teknisk fakultet. Man kan kolla fakultetstillhörighet genom att titta på kurskoden. Om den börjar med 7 är det filfak, om den börjar med T eller N är det tekfak. Funktionen ska funka så här: >> stat_faculty("exam.xml") Teknisk fakultet: 200 Filosofisk fakultet: 83 b) (3p) Skriv en funktion stat_count som räknar ut vilka tentapass som det är flest anmälda till. Det finns två möjliga pass, fm och em, även om start- och sluttiderna kan variera något. Funktionen ska även ta ett heltal N och skriva ut de N mest populära tentapassen sorterade. Det innebär att den ska funka så här: >> stat_count("exam.xml",4) 2015-03-18 em: 210 2015-05-30 em: 248 2015-10-27 em: 280 2015-10-30 em: 360 Uppgift 4: DSL (5p) ------------------- Vi vill ha ett mycket litet domänspecifikt språk, inbyggt i Ruby, för att kunna hantera längdenheter. I slutändan vill vi i Ruby-interpretatorn kunna skriva så här: >> 5.cm+14.cm => 19.cm >> 2.cm+3.dm-7.cm => 2.5.dm För att lösa detta behöver vi inte nödvändigtvis tillämpa de tekniker för DSL som vi har tittat på i kursen (som oftast utgår från en textfil med rader på ett påhittat minispråk). Det räcker att använda lite olika objektorienterade egenskaper hos Ruby. För att hjälpa till lite på traven finns några olika frågeställningar som du måste lösa: - Vad ska returneras om man skriver bara 2.cm vid prompten? - Vilket objekts metod + respektive - är det som anropas i exemplen ovan? - Hur får man Ruby att ge returvärdet 19.cm i första exemplet ovan? a) (3p) Skriv programkod som gör att man kan skriva precis som i exemplet ovan. Du har goda chanser att få delpoäng även om du inte löser hela uppgiften. b) (2p) Varför är detta ett domänspecifikt språk? Definiera vad ett DSL är och argumentera för eller emot att detta skulle vara ett DSL. Uppgift 5: Icke-deterministisk programmering (5p) ------------------------------------------------- Ett klassiskt schackproblem är hur man placerar ut åtta damer på ett schackbräde så att ingen av dem kan ta någon annan. En dam (eller drottning) kan som bekant gå hur många steg som helst rakt eller diagonalt på brädet, så det gäller att placera ut dem strategiskt. Man kan generalisera problemet till ett bräde av storlek N. Nedanstående skiss visar ett mindre bräde där N=4, samt en möjlig lösning för att placera ut fyra damer. 0 1 2 3 +-------+ 3| X |3 2| X|2 1|X |1 0| X |0 +-------+ 0 1 2 3 Man inser snart att det bara kan finnas en enda dam per rad, men också bara en per kolumn. Dessutom ska de inte kunna komma åt varandra diagonalt. Vi ska försöka lösa det här problemet med en av våra problemlösare som vi tittade på under den näst sista föreläsningen. För att inte trötta ut problemlösaren med allt för många alternativ ska vi välja damernas placering systematiskt. Ett sätt att lösa problemet är att använda sig av följande algoritm: För varje kolumn i, välj en lämplig rad j för damen Vår dam står nu på position p=(i,j) på brädet Från position p, gå åt vänster och kolla att det inte finns några andra damer i samma rad Från position p, gå snett uppåt vänster och kolla att det inte finns några andra damer i den diagonalen Från position p, gå snett nedåt vänster och kolla att det inte finns några andra damer i den diagonalen Om vi inte hittat några damer som krockar verkar position p vara okej Din uppgift är att, med utgångspunkt i problemlösaren som finns i filen amb_test.rb, implementera ovanstående algoritm. Skriv en funktion n_queens som paketerar ihop problemlösningen och som returnerar den först hittade lösning som en array. Exempel: >> n_queens(4) => [1, 3, 0, 2] >> n_queens(7) => [0, 2, 4, 6, 1, 3, 5] Den första körningen ger oss samma resultat som i exemplet ovan, d.v.s. damernas rader i kolumnerna från vänster till höger. Uppgift 6: Parsning (6p) ------------------------ I många gamla dialekter av programspråket BASIC finns enkla kommandon för att producera ljud. Ett vanligt sådant kommando är SOUND som funkar så här: SOUND 440, 20 Första argumentet är tonens frekvens och andra argumentet är tonens längd i antal klocktick. Det går (i den här uppgiften) 18.2 klocktick på en sekund, så det här kommandot låter tonen A (440 Hz) ljuda i lite mer än en sekund. Om man ska spela melodier blir det lite klurigare, för då måste man utföra en lång rad SOUND-kommandon efter varandra och hela tiden hålla reda på lämpliga frekvenser och klockticks. För att göra det lite enklare finns ett PLAY-kommando. Det funkar så här: PLAY "O2L4CEL2DL4CEL2DL4CEDFEDL2C" Ovanstående exempel spelar den kända melodin "Till Paris...". Kommandot PLAY tar en sträng som innehåller ett litet specialspråk med vars hjälp man kan konstruera enkla melodier. Den här uppgiften går ut på att med utgångspunkt i parsern som finns i filen rdparse.rb skriva en parser som kan tolka PLAY-språket och översätta det till lämpliga SOUND- kommandon. I den bifogade filen play.rb finns dels en kommentar som visar en BNF-grammatik för det PLAY-språk som vi ska behandla, dels en hash- tabell med frekvenser för olika toner som används. PLAY-språket funkar så här: C, D, E, F, G, Spelar motsvarande ton i aktuell oktav A eller B i aktuell längd. Man kan också lägga till +, #, eller - efter tonen för att höja eller sänka ett halvt steg. On Sätter aktuell oktav där n=0, 1, 2 eller 3 Ln Sätter aktuell längd där n=1, 2, 4, 8, 16, 32 eller 64. Längden anges i delar av en helnot, så högre tal innebär kortare ton. Pn Gör en paus under längden n, där n är samma som för kommandot L ovan. Detta innebär att man gör ett SOUND-kommando med 0 som frekvens. Längden på en not ska anges i antal klocktick. Det går 18.2 klocktick på en sekund, vilket innebär att ett tick är 1/18.2 = 0.0549 sekunder. Vi kör alltid i samma tempo T=120, vilket innebär att det går 120 fjärdedelar på en minut. Det i sin tur innebär, om man räknar lite på det, att en helnot alltid är 36.4 klocktick lång. Från detta kan man sedan räkna ut hur långa de kortare noterna ska vara genom att dela med L=2, 4, 8, o.s.v. Frekvenserna för grundtonerna finns i en tabell i filen play.rb, men för att höja eller sänka en halvton ska man multiplicera eller dividera med tolfte roten ur 2 som är 1.05946. Tonen A i oktav 2 har frekvensen 440 Hz och den höjda tonen A# har alltså frekvensen 440*1.05946 = 466.16 Hz. Att parsa en sträng enligt det lilla PLAY-språket ska resultera i en sekvens av SOUND-kommandon. Det finns (tack och lov) inget sätt att testa detta praktiskt under tentan, utan man får kolla noga på utdata från parsern. Ungefär så här vill vi att det ska funka: >> pp = PlayParser.new => # >> pp.play "O2L4CEL2DP2" => ["SOUND 523.25, 9.1", "SOUND 659.26, 9.1", "SOUND 587.33, 18.2", "SOUND 0, 18.2"]