Datortentamen i TDP007 torsdag 12 juni 2014 kl 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. 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 acroread. 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) Förklara kort hur du kan styra åtkomsten till metoderna i en klass. (1p) b) I en text som innehåller recept vill vi hitta alla förekomster av mängdangivelser, t.ex. "2 msk", "0,5 tsk", "2 l". Skriv ett reguljärt uttryck som matchar sådana mängder, d.v.s. ett tal följt av en enhet. (2p) c) 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. (2p) Uppgift 2: Behandling av data i textfiler (5p) ---------------------------------------------- Textfilen sysselsatta.txt innehåller två tabeller med uppgifter om hur många tusen personer som jobbade med olika typer av yrken under fyra år: 1997, 1999, 2001 och 2003. Den första tabellen är antal män och den andra är antal kvinnor. Vi är intresserade av att få reda på hur jämställda dessa yrken är. Därför ska du skriva en funktion som kan läsa in tabellerna och skriva ut samma yrkeskategorier, men med kvoten mellan män och kvinnor istället för det absoluta antalet. Funktionen ska funka så här: >> read_tables("sysselsatta.txt") 213 dataspecialister 3.40 2.65 3.04 2.87 214 civilingenjörer, arkitekter m.fl. 4.50 3.60 4.45 3.86 2221 läkare 1.45 1.70 1.30 1.46 ... Så långt det är möjligt ska lösningen utformas generellt, dvs den ska kunna gå att återanvända även för andra tabeller som är strukturerade på ungefär samma sätt. Färre hårdkodade konstanter ger mer poäng. Filen innehåller svenska tecken. Om det skulle uppstå problem med att hantera dessa är det helt okej att ändra dem till något annat. Uppgift 3: XML (6p) ------------------- Lille Timmy är tolv år och går i Big Rock Elementary School som ligger någonstans i Texas. Varje dag äter Timmy lunch i skolans cafeteria, där det finns 3-5 olika hälsosamma rätter att välja mellan. Timmy tycker att det är svårt att välja, så därför vill hans mamma Christy gärna hjälpa honom. Christy jobbar för ett multinationellt programvaruföretag och tänker att det bästa sättet att hjälpa sin son är att skriva ett program som väljer åt honom. Tyvärr har hon händerna fulla av företagets nästa stora och viktiga release, så hon vill istället att du ska skriva programmet. Just nu är hon väldigt mycket inne på Ruby, och behändigt nog publicerar skolan lunchmenyn i XML-format. I filen menu.xml återfinns lunchmenyn för några dagar i oktober. Varje dag finns det 3-5 rätter att välja mellan, och förutom namnet på rätten finns även kaloriinnehållet angivet. Christy vill nu att du ska skriva två alternativa program för att hitta på vad lille Timmy ska välja. a) (4p) Skriv en funktion choose1 som givet en XML-fil som är strukturerad på samma sätt som menu.xml skriver ut en lista med förslag på vad man borde äta varje dag. Funktionen choose1 ska ha strategin att hela tiden ta nästa nummer på listan. Man börjar med val 1 första dagen, går vidare till val 2 nästa dag, osv. Kommer man till ett nummer som inte finns på den aktuella dagen så börjar man om från början på 1. Utskriften från funktionen ska se ut så här: >> choose1("menu.xml") Monday 1. Soft Pretzels and Cheese Tuesday 2. Cheeseburger on a Bun Wednesday 3. Chicken Caesar Salad Thursday 4. Corn Dog on a Stick Friday 1. Stuffed Crust Pizza Monday 2. Cheeseburger on a Bun ... b) (2p) Skriv en funktion choose2 med samma förutsättningar som ovan, men med strategin att alltid välja den rätt som har högst kaloriangivelse. Utskriften från denna funktion ska även inkludera kalorivärdet och se ut så här: >> choose2("menu.xml") Monday 2. Chicken Patty on a Bun (550) Tuesday 1. Little Caesar's Pizza (540) Wednesday 4. BBQ Pork on a Bun (535) Thursday 2. Lasagna with Garlic Toast (505) ... 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) ------------------------------------------------- Den här uppgiften ska vi så småningom lösa genom att bygga ett constraint- nätverk, men först en introduktion till problemet. Två bilar A och B startar samtidigt i två olika städer som vi också kan kalla A och B. De kör mot varandra på samma väg och kommer, om inget oförutsett inträffar, att mötas någonstans på ungefär halva vägen. För enkelhets skull antar vi att bilarna kör med konstant hastighet hela tiden, den ena något fortare än den andra. Huvudfrågan är var någonstans på vägen de kommer att mötas. Förhållandet mellan sträcka, hastighet och tid kan uttryckas med formeln s = h*t. För att hålla reda på de två bilarna lägger vi till A och B efter, och får alltså två formler: sA = hA*tA och sB = hB*tB. Bilarna kommer mötas samtidigt, dvs när tA = tB, och vi kan då slå ihop formlerna till en enda: sA/hA = sB/hB Vi vet också att summan av sA och sB måste vara hela vägens sträcka, som vi kan kalla s. Vi skulle alltså kunna skriva: sA/hA = (s-sA)/hB Detta kan vi i olika steg omvandla så här: sA*hB/hA = s-sA sA*(1+hB/hA) = s Din uppgift är att bygga upp ett constraint-nätverk som motsvarar ovanstående formel, med utgångspunkt i koden i constraint_networks.rb. Uppgift 6: Parsning (6p) ------------------------ Schack är ett klassiskt brädspel som spelas av två spelare på ett bräde med 8x8 rutor. Varje spelare har från början 16 pjäser till sitt förfogande: en kung, en dam, två löpare, två springare, två torn och åtta bönder. Den ena spelaren har ljusa pjäser och kallas vit, den andra har mörka pjäser och kallas svart. Vit spelare börjar alltid, och därefter fortgår spelet med vartannat drag tills någondera parten kan ta den andres kung. Schackspelare har utvecklat flera olika sätt att redovisa vilka drag som har gjorts under en match. Ett sådant sätt är s.k. algebraisk notation i vilket inledningen av en match kan skrivas så här: 1. e4 c5 2. Nf3 d6 3. Bb5+ Bd7 4. Bxd7+ Qxd7 5. c4 Nc6 6. Nc3 Nf6 Varje omgång består av ett drag från vit spelare och ett drag från svart spelare (under förutsättning att inte svart redan förlorat). Dessa omgångar är numrerade ovan. Varje drag talar om vilken pjäs som flyttas, samt till vilken ruta. Formatet för varje drag ser ut så här: - Pjäsen anges med en stor bokstav (K=kung, Q=dam, R=torn, B=löpare, N=springare). Om ingen pjäs anges innebär det att det är en bonde som flyttats. - Rutorna anges med två koordinater: en bokstav a-h samt en siffra 1-8. - Om en pjäs tar en annan pjäs skjuter man in ett x innan målrutan. - Om ett drag innebär att motspelarens kung är hotad ("schack") lägger man till ett + efter målrutan. Det finns många fler specialregler, och flera varianter på den algebraiska notationen, men för den här tentan nöjer vi oss med ovanstående. Du ska inte behöva känna till mer om schack än detta för att kunna lösa uppgifterna. Utgå från den parser som finns i rdparse.rb och skriv en parser som kan läsa in och tolka filer som innehåller beskrivningar av schackspel i algebraisk notation. Målet är att parsern ska ge som utdata någon form av datastruktur som innehåller alla gjorda drag i spelet på ett lämpligt format. Du får själv avgöra hur detta interna format ska se ut (t.ex. speciella klasser, arrayer eller Struct). Exempelsträngen ovan är lämplig testdata. Du behöver inte verifiera att dragen överensstämmer med reglerna, eller ta hänsyn till hur partierna slutar. Din enda uppgift är att skriva en parser som kan behandla dylika textsträngar och producera någon form av vettiga datastrukturer.