18 gennaio 2017
Linguaggi e Traduttori
Prof. Marco Gavanelli
18 gennaio 2017
Esercizio 1 (punti 15)
Nel gioco della tombola, vengono estratti a caso dei numeri uno alla volta.
Ciascun giocatore ha una cartella, su cui sono riportati dei numeri. Quando viene annunciato un numero, ogni giocatore controlla se la sua cartella lo contiene: se il numero annunciato è presente nella sua cartella, il giocatore lo cancella.
Vince il giocatore che cancella per primo tutti i numeri dalla sua cartella (si dice che ha fatto "tombola").
Nella versione della tombola infinita, le cartelle possono contenere qualunque numero naturale e i numeri che vengono estratti potrebbero essere infiniti.
Sono dati
- un file cartelle.txt che contiene i dati delle cartelle, uno per ogni riga. Per ogni cartella, si hanno
- il nome del giocatore (stringa)
- una sequenza di numeri interi, tutti diversi
- un file estratti.txt che contiene la sequenza dei numeri estratti
Si desidera scrivere un programma Haskell che calcola qual è il giocatore che fa tombola per primo, cioè quello che usa la più piccola porzione del file estratti.txt.
È indispensabile fare uso di funzioni di ordine superiore.
Per ottenere tutti i punti, non si deve leggere ed utilizzare l'intero file estratti.txt, ma considerare che potrebbe essere infinito, usando la valutazione lazy di Haskell per elaborare il file estratti.txt.
Esercizio 2 (Punti 3)
Si scriva un programma Lex che, dato un file html, elimina tutti i tag. Un tag html è costituito come segue:
- comincia con il carattere <
- contiene una sequenza di caratteri che non contiene il simbolo >
- è terminato dal simbolo >
Ad esempio il testo:
<html><body>Scrivere a <a href="mailto:luigi.rossi@esempio.com">Luigi Rossi</a></body></html>
viene sostituito con
Scrivere a Luigi Rossi
Soluzione 1
data Cartella = Cartella { nome :: String, numeri :: [Int]} deriving Show
main = do
cartString <- readFile "cartelle.txt"
estrString <- readFile "estratti.txt"
let estratti = (map read (words estrString)) :: [Int]
cartelle = map (conv.words) (lines cartString)
winner = vince (elimina estratti cartelle)
print winner
conv (x:xs) = Cartella x (map read xs)
vince (x:xs) =
let indiceVuota = cartellaVuota x 1
in if (indiceVuota > 0)
then nome (x !! (indiceVuota-1))
else vince xs
cartellaVuota [] _ = 0
cartellaVuota (x:xs) n =
if (numeri x) == []
then n
else cartellaVuota xs (n+1)
elimina estratti cartelle =
itera eliminazione estratti cartelle
eliminazione e cartelle =
(map (\c -> Cartella (nome c) (filter (/= e) (numeri c))) cartelle )
itera f [] _ = []
itera f (x:xs) y = y:(itera f xs (f x y))
Soluzione 2
TAG \<[^\>]*\>
%%
{TAG} ;
%%
