Datortentamen i TDP007 tisdag 16 augusti 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) Vad är poängen med klassen Enumerable och vad används den till? Förklara med egna ord, alltså inte bara det som står i böcker eller dokumentation. (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. Du får själv göra lämpliga antaganden om vilka enheter som ska kunna hittas. (2p) c) När ska man använda strömparsning (SAX) och när ska man använda trädparsning (DOM)? Ge ett exempel på användningsområde och förklara kort varför den ena metoden skulle kunna vara bättre. (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 ... Om kvoten är större än 1.0 innebär det att fler män arbetar inom yrket. Om den är mindre än 1.0 är det fler kvinnor. 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. Uppgift 3: XML (6p) ------------------- I filen weather.xml finns väderobservationer från ett antal städer i Europa lagrade i XML. Uppgifterna kommer från OpenWeatherMap.org som tillhandahåller fria väderdata från ett stort antal stationer världen över. Formatet är ganska självförklarande. 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 SAX-lösning hittar du ett exempel att utgå från i filen sax_example.rb och om du vill göra en DOM-lösning hittar du lite information om metoderna i klassen REXML::Element samt några exempel på XPath-uttryck i filen rexml.txt. a) (4p) Skriv ett program som läser in väderobservationer från en fil som är strukturerad på samma sätt som weather.xml. Programmet ska skriva ut en lista över städernas namn, landsbeteckning samt aktuell temperatur i grader Celsius, angivet med en decimal. (Man får grader Celsius genom att ta grader Kelvin och lägga till 272.15.) Programmet ska fungera så här: >> report("weather.xml") London (GB): 5.2 C Paris (FR): 6.5 C Moscow (RU): -3.7 C Vienna (AT): 9.2 C Madrid (ES): 5.1 C Berlin (DE): 5.0 C Athens (GR): 12.2 C Nice (FR): 10.5 C Lisbon (Portugal): 9.3 C Ankara (TR): 7.5 C Stockholm (SE): 3.1 C Roma (IT): 15.0 C Milano (IT): 5.5 C Lyon (FR): 5.5 C b) (2p) Vi vill kunna rita ut väderobservationerna på en karta, men innan vi kan göra det vill vi veta hur stor kartan behöver vara. Därför behövs ett program som kan gå igenom alla observationerna och hitta största och minst latituden och longituden (finns i taggen coord). Programmet ska fungera så här: >> make_map("weather.xml") Longitude -9.15 - 37.62 Latitude 37.98 - 59.33 Uppgift 4: DSL (5p) ------------------- Bob Arlington, även känd som "Bob the Builder", äger en kedja av bygg- och järnaffärer runt om i USA. En gång per månad vill han ha en sammanställning av hur mycket som har sålts i alla affärer. Hans utvecklingsavdelning har lyckats skriva ett program som kan generera rapporter från de olika affärerna och ett exempel på en sådan månadsrapport finns i filen sales.rb. Det som behöver göras nu är att gå igenom rapporten och summera hur många som sålts av varje vara. Bob vill att du ska göra detta med hjälp av någon teknik för domänspecifika språk i Ruby. Du ska alltså betrakta den här textfilen som källkod och skriva ett litet program som kan köra filen och därmed få fram statistiken som Bob vill ha. Som du ser i filen finns det tre huvudtyper av artiklar som Bob säljer. Han vill veta vilken artikel i varje kategori som säljer bäst. I praktiken innebär det att han vill att det ska funka ungefär så här: >> s=SalesAccumulator.load("sales.rb") => # >> s.most_popular For tool the most popular item is pliers (61) For fixing the most popular item is shank_nail (97) For other the most popular item is ear_plugs (82) => nil Definiera klassen SalesAccumulator som kommer fungera som en enkel interpretator för det lilla domänspecifika språket. Klassen ska kunna läsa in och summera artiklar, samt tala om vilken som säljer bäst i varje kategori. Klassen ska utformas på ett sådant sätt att det inte blir några problem om Bob börjar sälja andra artiklar, dvs hårdkoda så lite som möjligt. Uppgift 5: Icke-deterministisk programmering (5p) ------------------------------------------------- Du ska arrangera en middag för åtta inbjudna personer: Kalle, Pelle, Nisse och Janne samt Anna, Disa, Lisa och Tina. Du vill placera dem i par (kille och tjej) på lämpligt sätt, men det finns några konstellationer att undvika. Pelle och Lisa är tillsammans, liksom Kalle och Anna. Därför vill du inte placera dem ihop. Pelle har dessutom varit ihop med Tina tidigare, och därför bör du inte placera dem ihop. I filen amb_test.rb hittar du ett problemlösarverktyg där man med hjälp av s.k. continuations kan specificera problem deklarativt. Använd denna teknik för att hitta ett bra sätt att bilda par inför middagen. Din lösning ska utgå från exemplet, men vara så generell att den lätt går att återanvända för en annan middag med godtyckligt antal deltagare (dock lika många av varje kön). Uppgift 6: Parsning (6p) ------------------------ Det rykande färska språket STRIMLA (String Manipluation Language) är ett enkelt interpreterat språk för att manipulera textsträngar på olika sätt. Ett uttryck i STRIMLA kan se ut på fem olika sätt, vilket illustreras med följande exempel: [Hejsan] En enkel sträng anges med hakparenteser och den kan innehålla i princip vad som helst, förutom hakparenteser. 3x[banan] Detta skapar en sträng som innehåller banan tre gånger, d.v.s. "bananbananbanan". 2#[abc] Flyttar respektive tecken två steg framåt, d.v.s. resultatet är "cde". (Lös detta på enklast möjliga valfria sätt. Det behöver inte nödvändigtvis wrappas på något snyggt sätt heller.) [foo]&[fie] Slår ihop två strängar, d.v.s. "foofie". (2x[oh])&[hai] Parenteser kan användas för att bestämma prioriteten. I det här fallet blir resultatet "ohohhai". Alternativt skulle man kunna uttrycka syntaxen med en BNF-regel så här: EXPRESSION ::= STRING | INTEGER 'x' EXPRESSION | INTEGER '#' EXPRESSION | EXPRESSION '&' EXPRESSION | '(' EXPRESSION ')' Alla strängar måste omges med hakparenteser. Talet som står framför 'x' måste vara positivt, medan talet som står framför '#' även kan vara negativt. Din uppgift är att, med utgångspunkt från parsern i rdparse.rb, konstruera en parser för STRIMLA som kan hantera det språk som beskrivs ovan. Språket får inte utökas på något sätt som gör parsern enklare. Följande exempel visar hur det kan se ut: >> StrimlaParser.new.repl [STRIMLA] 4x[boom] => boomboomboomboom [STRIMLA] [I haz a ]&[pony!] => I haz a pony! [STRIMLA] (2x[HEJ ])&[MON]&-1#[JDB] => HEJ HEJ MONICA