Uppgifter för dugga 2 i TDP007 2010-03-05 ----------------------------------------- Observera att det inte är säkert att uppgifterna kommer i svårighetsordning. Kolla därför snabbt igenom alla uppgifter och se efter vilka du tror att du har störst chans att klara av. Om du vill lösa alla uppgifter bör du lägga i snitt 20 min per uppgift för att bli klar i tid. Uppgift 1 --------- a) Beskriv en fördel som man kan hoppas uppnå genom att skapa ett domänspecifikt språk! (1p) b) Vad är en lexer och vad är en parser, och hur samarbetar de? (1p) c) Förklara kortfattat hur de olika komponenterna i ett constraint- nätverk kommunicerar med varandra! (1p) d) Antag att vi har definierat följande metod: def add(arr,elem) callcc do |c| arr << elem return c end arr.delete(elem) end Förklara någorlunda detaljerat vad det är som händer när vi kör följande exempel: >> storage=[1,2,3,4,5] => [1, 2, 3, 4, 5] >> undo=add(storage,42) => # >> storage => [1, 2, 3, 4, 5, 42] >> undo.call => 42 >> storage => [1, 2, 3, 4, 5] Vad gör funktionen? Vad returneras? Vad händer med arrayen? (2p) Uppgift 2: Domänspecifika språk ------------------------------- I filen my_world.rb finns en karta över en spelvärld uttryckt i ett enkelt domänspecifikt språk. Kartan beskrivs genom att man går runt i världen och observerar olika objekt. Med hjälp av kommandon som motsvarar de fyra väderstrecken flyttas man runt. Om kommandot får en tal som parameter förflyttas man det antal steg som anges, annars endast ett steg. Alla övriga kommandon är namn på saker som finns på den aktuella positionen. Dessa namn kan vara vilket ord som helst. Filen börjar så här: north east house Det innebär alltså att i en punkt nordost om startpunkten finns ett hus. Din uppgift är att skriva ett program som kan läsa in en karta som är beskriven på det här sättet. Kartan ska läsas in till ett format så att den kan skrivas ut med hjälp av funktionen i filen print_map.rb. Tanken är att det ska se ut så här, om allt fungerar: >> print_map(MapReader.load("my_world.rb")) -------- -------- -------- house -------- sword -------- -------- -------- -------- -------- dragon -------- -------- treasure => nil I uppgiften ingår alltså att först förstå hur funktionen print_map fungerar. Jämför det som står i filen med utskriften ovan. Därefter ska du skapa klassen MapReader som kan läsa in en karta i det givna formatet. Du ska använda dig av någon av de tekniker för domänspecifika språk i Ruby som vi har gått igenom i kursen. Uppgift 3: Icke-deterministisk programmering -------------------------------------------- Om man ska resa med flyg får man tyvärr inte ta med sig hur mycket bagage som helst. Kalle ska flyga hem från USA och har 24 kg ledigt i bagaget när han har packat allt annat. Detta utrymme vill han fylla ut med presenter, men han vet inte riktigt vilka han borde köpa. Kalle vill naturligtvis utnyttja vikten till max. Presenterna han funderar på väger 1, 3, 5, 7, 11, 13 samt 19 kg. Vilka ska han välja? Lös problemet med hjälp av problemlösaren som finns i filen amb_test.rb. Skriv en funktion find_combination som tar en array av presentvikter samt den önskade totalvikten och som med hjälp av Amb-klassen hittar den bästa kombinationen. Om det finns flera möjliga kombinationer ska den första hittade returneras. Funktionen ska funka ungefär så här: >> find_combination([1,3,5,7,11,13,19], 24) [1, 3, 7, 13] Detta är en variant på det välkända kappsäcksproblemet (eng. knapsack problem). Uppgift 4: Constraint-nätverk ----------------------------- De constraint-nätverk som vi har arbetat med har endast innehållit logiska värden och tal. Du ska nu få konstruera constraints som även kan innehålla tecken. Uppgiften består av två delar som kan ge poäng oberoende av varandra. a) Konstruera en ny constraint Converter som i ena änden tar in ett heltal i intervallet 1-26 och i andra änden skickar ut ett tecken (eller snarare en sträng med ett tecken) i intervallet "A" till "Z". Givetvis ska informationsflödet kunna gå åt båda hållen. Så här skulle det kunna funka: >> key_char=Connector.new("key char") => # >> key_int=Connector.new("key int") => # >> Converter.new(key_int, key_char) => #, @char_connector=#> >> key_char.user_assign "C" D, [2010-02-23T15:34:06.744356 #28241] DEBUG -- : key char ignored request D, [2010-02-23T15:34:06.744702 #28241] DEBUG -- : key char got new value: C D, [2010-02-23T15:34:06.744799 #28241] DEBUG -- : key int got new value: 3 => "ok" Om någonting hamnar utanför intervallet är det odefinierat vad som händer, dvs ni behöver inte hantera fel eller något sådant. b) Konstruera en ny constraint Transposer som har tre in-/utgångar. Denna constraint har till uppgift att genomföra en mycket enkel kryptering som består i att man förskjuter en bokstav ett visst antal steg i alfabetet. Om man ska förskjuta tre steg betyder det alltså att t.ex. A blir D. En Transposer ska ha tre in-/utgångar som har följande uppgifter: - en krypteringsnyckel i form av ett tal i intervallet 1-26 som talar om hur stor förskjutningen ska vara - en klartext i form av ett tecken (sträng av längden 1) i intervallet "A" till "Z" - en krypterad text, också i form av ett tecken i samma intervall som ovan Om man förskjuter så många steg att man passerar "Z" ska man givetvis börja om från "A" igen. De två deluppgifterna ger 2,5 poäng vardera. Uppgift 5: Parsning ------------------- Med utgångpunkt från parsern som finns i filen rdparse.rb ska du bygga en parser som kan tolka textsträngar som innehåller kemiska formler. Parsern ska bygga upp någon form av datastruktur som motsvarar den molekyl som formeln betecknar. Denna datastruktur ska innehålla uppgifter om hur många av respektive atomslag som ingår i molekylen. Här är ett exempel på hur det ska funka: >> cp=ChemicalParser.new => # >> cp.parse("C2H5OH") => [#, #, #] Formeln C2H5OH betecknar etanol, dvs vanlig sprit. Den innehåller två st kolatomer (C), fem st väteatomer (H) och därefter en syreatom (O) och ytterligare en väteatom (H). Parsern har räknat ihop alla dessa och svarar med en array som innehåler tre structar, och där ser vi att alla väteatomerna har räknats ihop till 6 st. Den datastruktur som din lösning skapar behöver inte se ut exakt så här, så länge samma information finns med och den summerar ihop alla atomer av varje slag. En kemisk formel består av ett eller flera atomslag. Om det inte står något tal direkt efter symbolen betyder det att det endast är en atom, annars är det så många som talet anger. Samma atomslag kan förekomma flera gånger i formeln, men får bara förekomma en gång i den resulterande datastrukturen. Din parser ska åtminstone klara av följande grundämnen: Symbol Engelskt namn Svenskt namn ------------------------------------- H Hydrogen Väte B Boron Bor C Carbon Kol N Nitrogen Kväve O Oxygen Syre Cl Chlorine Klor Ba Barium Barium Här är exempel på några formler som din parser ska klara av: Formel Namn -------------------------------- C2H5OH Etanol (vanlig sprit) BaC2O4 Bariumoxalat CHCl3 Kloroform CH2O Formaldehyd BN Bornitrid Namnen ska inte hanteras av parsern. De är bara med för att det är kul.