Dugga 2 i TDP007 onsdag 8 mars 2017 kl 08.30-10.30 -------------------------------------------------- Duggan startar kl. 08.30 och pågår till 10.30. Ni kommer att få köra på i vår begränsade datortentamiljö, som ni säkert redan känner till. Instruktioner för att logga in lämnas i salen. Alla filer som ni behöver för att lösa uppgifterna finns i hemkatalogen, under given_files, 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 t ex kommandot xpdf. Under tentan kommer ni också att kunna komma åt ruby-doc.org och rubular.com för att kunna kolla upp och testa saker. Svar på frågor skrivs i vanliga textfiler och programkod skrivs i rb-filer. En fil per huvuduppgift ska produceras, totalt alltså fyra filer. Ingen särskild inlämning behöver göras. När man är färdig loggar man ut och lämnar salen. Duggan består av fyra uppgifter (några indelade i deluppgifter) som totalt kan ge 25 poäng. Dessa poäng summeras ihop med poängen från den första duggan. Uppgift 1: Teorifrågor (7p) --------------------------- a) På vilka sätt skiljer sig ett domänspecifikt språk (DSL) från ett "vanligt" programmeringsspråk (eng. general purpose language, GPL). (2p) b) Vad händer i lexer- respektive parserdelen av t.ex. en kompilator? Använd gärna rdparse.rb för att exemplifiera. (2p) c) I uppgift 2 längre ner i duggan ska man hitta alla möjliga kombinationer med hjälp av problemlösaren i filen amb_test.rb. Vad är poängen med att använda den istället för att bara sätta upp en massa for-loopar eller liknande? (2p) d) Beskriv kortfattat en faktor som kan bidra till att ett datorspråk blir populärt och motivera varför. (1p) Uppgift 2: Icke-deterministisk programmering (6p) ------------------------------------------------- Rutger Jönåker jobbar som musikläggare på en radiokanal. Det är inte särskilt roligt, eftersom kanalen har ganska hårda bestämmelser för vilken musik som får spelas. Den här veckan får han bara använda topplistelåtar som finns i listan i filen music.rb. Rutger gillar egentligen inga av låtarna på topplistan, men han har ändå delat in dem i tre olika kategorier (blå, grön, röd) som han tycker lite olika illa om. Kategoriseringen syns i listan. Rutger vill välja ut fyra olika låtar från listan, som ska spelas efter varandra. För att få en lämplig blandning vill han att varje låt ska ha en annan kategori (blå, grön, röd) än den som spelades omedelbart innan. På hur många sätt kan han välja ut fyra låtar från topplistan? Lös problemet genom att använda problemlösaren i filen amb_test.rb för att hitta alla möjliga kombinationer. Uppgift 3: DSL (6p) ------------------- Okej, det är mycket text i den här uppgiften, men den är egentligen inte så svår, när man väl har läst hela texten, och man behöver inte skriva särskilt mycket kod. Så här är det... Företaget DarkMap har utvecklat en utrustning som kan hjälpa till med att kartlägga gamla avloppssystem åt kommuner. En del av lösningen består av en handdator som personalen kan ha med sig ner i kloaksystemen för att mata in information om hur kopplingar ser ut mellan olika rör. Den här handdatorn dumpar sedan ur sig den inlästa informationen i form av ett mycket enkelt litet domänspecifikt språk. I filerna map1.rb och map2.rb ser du två sådana exempel. Kartorna som byggs upp med hjälp av DarkMaps lösning består av två saker: kopplingspunkter (kallade 'junctions') och avloppsrör (kallade 'pipes'). Det lilla språket som utdatan från handdatorerna kommer på har egentligen bara två konstruktioner. Den nyare versionen av programvaran matar ur sig t.ex. connect 'b', 10, 11 Det betyder att kopplingspunkten 'b' är kopplad till rören 10 och 11. Den äldre versionen av programvaran, som vi också måste kunna hantera, matar ur sig t.ex. connect_junction 'b', 10 connect_junction 'b', 11 Det är alltså samma information, men i den här gamla versionen av programvaran kan man bara koppla en kopplingspunkt med ett rör och måste alltså använda flera rader. Båda dessa konstruktioner kan komma om vartannat, som i den andra exempelkartan. Kopplingarna är alltid strängar och rören är alltid tal. DarkMap vill nu ha en ny del av programvaran som kan läsa in det här lilla språket som ett internt DSL i Ruby. Du ska alltså använda dig av tekniker för DSL som vi har tittat på i kursen för att läsa in denna typ av filer. DarkMap vill också ha en funktion för att kunna söka i rörsystemet. Om man anger numret på en viss rördel så ska man få en lista på alla ändpunkter, alltså kopplingspunkter som bara har en rördel kopplade till sig och som på något sätt sitter ihop med det angivna röret. Man vill att det ska funka så här: >> m1 = DarkMap.new('map1.rb') => # >> m1.follow_pipe(11) => ["a", "e", "d"] En konsult har redan börjat på lösningen och har än så länge hunnit implementera metoden follow_pipe. Den söker igenom en karta och talar om vilka ändpunkter det finns. Hennes lösning finns i filen darkmap.rb. Din uppgift är att utöka klassen DarkMap så att den kan läsa in kartfilerna (alltså utdatan från handdatorerna) med hjälp av DSL-tekniker till någon lämplig datastruktur. För att follow_pipe ska funka måste du också implementera metoderna pipes_connected_to_junction och junctions_connected_to_pipe som båda returernar listor av rörnummer respektive beteckningar för kopplingspunkter. Ett tips: Om du är nyfiken på hur follow_pipe funkar kan du anropa den med t.ex. follow_pipe(11, true). Det valfria true-värdet slår på spårutskrifter så att du kan se vad som händer (under förutsättning att dina implementationer funkar som de ska). Observera att lösningen måste söka sig genom kartan. Det går inte bara att hitta alla kopplingspunkter som bara har ett rör kopplat till sig, för kartan kan innehålla flera olika avloppsnät. Det lite mer komplicerade exemplet från map2.rb ska funka så här: >> m2 = DarkMap.new('map2.rb') => # >> m2.follow_pipe(101) => ["MR", "GA", "MA", "MQ", "AB", "AE"] >> m2.follow_pipe(201) => ["TA", "TH", "TE"] Så, vad ska du göra? a) Utöka klassen DarkMap med en initialize som tar ett filnamn, tolkar innehåller i filen som programkod och bygger upp en datastruktur som innehåller information om kopplingar och rör. (4p) b) Utöka klassen DarkMap med metoderna pipes_connected_to_junction och junctions_connected_to_pipe så att den redan existerande metoden follow_pipe funkar som i körexemplen. (2p) Uppgift 4: Parsning (6p) ------------------------ 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 på de kemiska ämnena ska inte hanteras av parsern. De är bara med för att det är kul.