Datortentamen i TDP007 tisdag 27 mars 2015 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 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) I en databas över kurser vill man lagra information om vilket år och vilken läsperiod en kurs startar. Denna information lagras som en sträng med först årtalet, sedan ett kolon och sist läsperioden, dvs HT1, HT2, VT1 eller VT2, med antingen stora eller små bokstäver. Skriv ett reguljärt uttryck som matchar en kursstartsangivelse på detta format. (1p) b) I en av de senare uppgifterna i tentan ska man använda en generell problemlösare som finns i filen amb_test.rb. Vi gick igenom denna under en av föreläsningarna. Vad är poängen med att använda en sådan här typ av generell problemlösare, istället för att bara sätta upp ett antal for-loopar? (2p) c) På vilka grunder (utöver bara tycke och smak) kan man egentligen säga att ett programspråk är bättre än ett annat? Beskriv åtminstone två kriterier som man kan använda för att bedöma programspråk och relatera dem till något eller några språk som du känner till. (2p) Uppgift 2: Behandling av data i textfiler (5p) ---------------------------------------------- I textfilen tab40_1952.txt finns en tabell över folkmängdens utveckling i Sveriges tio största städer 1952. Förutom folkmängden vid årets början visar tabellen även antalet födda, döda, inflyttade och utflyttade. Din uppgift är att läsa in tabellen till lämplig datastruktur, göra vissa beräkningar och därefter skriva ut en tabell med ny information. I det här fallet vill vi först beräkna förändringen i folkmängden för varje stad (alltså summan av alla födda, döda, inflyttade och utflyttade). Vi vill också beräkna hur stor procentuell skillnad det blev under året, och listan över städer ska skrivas ut sorterad efter den procentuella skillnaden. Så här ska det se ut: >> find_growth("tab40_1952.txt") Linköping 1406 2.47% Västerås 1423 2.26% Uppsala 1055 1.61% Stockholm 10314 1.36% Göteborg 4735 1.31% Örebro 796 1.16% Malmö 2117 1.07% Borås 581 0.98% Norrköping 316 0.36% Hälsingborg 10 0.01% Förutom stadens namn visas alltså nettoförändringen samt den procentuella förändringen av folkmängden. Formatterad utskrift enligt ovanstående exempel ingår i uppgiften. (Även om Linköping bara var den tionde största staden i Sverige 1952 så hade vi alltså störst ökning i folkmängden.) Uppgift 3: XML (6p) ------------------- I filen playlist.xml finns en spellista med ett antal ganska blandade låtar. Din uppgift är att skriva olika funktioner för att kunna läsa in och hantera informationen i filerna. 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. Varje deluppgift är värd 3 poäng. a) En av egenskaperna som varje låt har är en viktning (i attributet weight i taggen settings). Viktningen kan vara någonstans 0-9 och anger hur bra man tycker att låten är, vilket i förlängningen påverkar hur ofta låten spelas. Högre värde innebär att låten spelas oftare. Vi vill ha en funktion random_song som väljer ut en slumpmässig låt ur listan. Slumpvärdet ska beräknas genom att först summera alla vikter, därefter välja ett slumptal i detta intervall och till sist hitta rätt låt baserat på detta. Statistiskt sett ska alltså låtar med högre viktning spelas oftare. När man använder funktionen ska det t.ex. se ut så här: >> p = read_playlist("playlist.xml") => ... >> 10.times { random_song(p) } Nobody Knows I'm Elvis (The Playtones) Hög på månen (Ebba Forsberg) Shake It Off (Taylor Swift) Prokofiev's Piano Concerto No. 2 (London Philharmonic Orchestra) Nobody Knows I'm Elvis (The Playtones) Prokofiev's Piano Concerto No. 2 (London Philharmonic Orchestra) Nobody Knows I'm Elvis (The Playtones) The Lion's Roar (First Aid Kit) Diggin' my potatoes no. 2 (Memphis Slim) Jolly Bob från Aberdeen (Eric Källquist) b) Varje låt kan ha en eller flera taggar (som finns i taggen tags). Vi vill ha en funktion find_tag som listar alla låtar som har en viss märkning. När man använder funktionen ska det t.ex. se ut så här: >> p = read_playlist("playlist.xml") => ... >> find_tag(p, 'Svenska') The Lion's Roar (First Aid Kit) Jag måste glömma Carina (Larz Kristerz) Jag skulle ge vad som helst (Lasse Stefanz) Han hade seglat för om masten (Harry Brandelius) Ta mig till havet (Peter Lundblad) Jolly Bob från Aberdeen (Eric Källquist) Hög på månen (Ebba Forsberg) >> find_tag(p, 'Klassiskt') Prokofiev's Piano Concerto No. 2 (London Philharmonic Orchestra) Così Fan Tutte (Mozart) (Teodir Currentzis, Musicaeterna) 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) ------------------------------------------------- Lisa ska bygga en uteplats i sin trädgård. Den ska vara i form av en rätvinklig triangel. På de tre sidorna ska hon sätta kantstenar, och för att slippa dela på dessa vill hon gärna att sidorna ska vara så långa att stenarna går jämnt upp. Här kommer den (kanske) välkända Pythagoras sats in i bilden. Den säger att om man har en rätvinklig triangel med de två korta sidorna av längden a och b, så är förhållandet till längden på den långa "sneda" sidan c så här: a^2+b^2=c^2. Den mest kända Pythagorastriangeln är den som har följande sidor: 4 |\ stenar | \ 5 stenar |__\ 3 stenar En sådan tjusig uteplats skulle Lisa kunna bygga med totalt 12 kantstenar. Hon är nu intresserad av att hitta alla möjliga sådana trianglar för att kunna välja vilken som är bäst till hennes uteplats. Eftersom trädgården inte är hur stor som helst så får en sida vara högst 20 kantstenar lång. Din uppgift är att lösa Lisas problem med hjälp av problemlösaren i filen amb_test.rb. (Rent matematisk ska du alltså hitta alla heltalslösningar till a^2+b^2=c^2 sådana att a,b,c<=20. Lisa vill inte ha med "speglade" lösningar två gånger, dvs om vi har med triangeln med sidorna 3, 4 och 5 behöver vi inte ha med triangeln med sidorna 4, 3 och 5.) Uppgift 6: Parsning (6p) ------------------------ I filen spreadsheet.rb finns ett par klasser som utgör grunden för ett mycket enkelt kalkylprogram. Klassen Worksheet representerar ett kvadratiskt arbetsblad. Skapar man ett nytt sådant med t.ex. Worksheet.new(4) så får man ett arbetsblad med cellen "A1" i övre vänstra hörnet och "D4" i nedre högra hörnet. Man kan hämta ut och placera in innehåll i cellerna genom att ange sådana cellreferenser, antingen som strängar eller som symboler. Se exempel i metoden test_ws, som returnerar ett sådant arbetsblad. Pröva att skriva ut det genom att anropa metoden pr. Klassen Formula används för att lagra formler i arbetsbladen. Varje sådan formelcell innehåller dels själva formeln, dels vilket värde formeln har beräknats till. Just nu saknas dock en metod att beräkna formlerna. Din uppgift är att, med utgångspunkt i rdparse.rb, konstruera en parser som kan analysera och beräkna värdet av kalkylbladsformler. Vi tänker oss att formlerna kan se ut enligt följande specifikation: FORMULA ::= '=' EXPRESSION EXPRESSION ::= REFERENCE | NUMBER | COMPOUND_EXPRESSION | '(' EXPRESSION ')' COMPOUND_EXPRESSION ::= EXPRESSION '+' EXPRESSION | EXPRESSION '-' EXPRESSION | EXPRESSION '*' EXPRESSION | EXPRESSION '/' EXPRESSION | FUNCTION_NAME '(' AREA ')' FUNCTION_NAME ::= 'Summa' | 'Medel' AREA ::= REFERENCE ':' REFERENCE REFERENCE ::= LETTER NUMBER Definiera klassen FormulaParser på ett sådant sätt att du kan byta ut vilken rad som är bortkommenterad i metoden update och göra så att formlerna beräknas korrekt.