[HW] Homework 8 obbligatorio - prima scadenza ore 23:59 del 26/12

Question

ATTENZIONE

• Ho aggiunto sulla VM un test che fallisce se è presente caching. Solo una manciata di programmi ne sono affetti.
• Le scadenze sono state allungate di 10 gg
• Lo zip è stato aggiornato con alcuni nuovi test (11/12/23 ore 17)
• Esempio di nuovo test ... con log delle regole applicate (dalla mia implementazione)

  • Esempio di esecuzione del test multichar

    if __name__ == '__main__':
        encrypted_text=  "aaabaaac"
        pharaohs_cypher= {"aa":"bc","bb":"c","cc":"d"}
        expected=        { "d" }
        res = pharaohs_revenge(encrypted_text, pharaohs_cypher)
        assert res == expected

• Può essere utile studiare gli alberi di gioco. 
• ATTENZIONE: NON INSERITE EMOJI NEL TESTO O NEL PROGRAMMA
• eventuali correzioni verranno inserite qui, tenete d'occhio questa pagina
• NOTA: il programma test_01.py DISATTIVA la funzione print ed aggiunge alcuni controlli. Per disattivarli e usare print assegnate la variabile DEBUG=True in test_01.py

Istruzioni

Per svolgere l'homework:

• Installate le librerie necessarie inclusa typeguard
• Scaricate il file HW8req.zip e scompattatelo in una directory. Il compito consiste nel:
  • descrivere in un file di testo algorithm.txt l'algoritmo che avete realizzato (o state realizzando, senza inserire info personali, dev'essere anonimo)
  • Lo zip contiene:
    • il file program01.ita.py, il programma da realizzare, in cui trovate all'inizio la descrizione del problema da risolvere, se necessario definendo funzioni ausiliarie,
    • altre librerie e file necessari ad eseguire i test sulla vostra macchina
• Posizionatevi nella directory creata unzippando l'archivio ed:
  • rinominate il file program01.ita.py col nome program01.py
  • analizzate il problema spezzandolo in funzioni piccole e descrivetelo nel file algorithm.txt (createlo con un editor di testo come Notepad++ o Spyder se non c'è)
  • implementatelo editando il file program01.py  
• Posizionatevi nella directory creata unzippando l'archivio ed editate i due file algoritmo.txt (descrizione dell'algoritmo) e program01.py (implementazione del programma)
• ATTENZIONE: il programma NON DEVE eseguire nessun input() o print(), infatti riceve tutte le informazioni di cui ha bisogno tramite i parametri della funzione che dovete completare e torna il risultato con return.
• ATTENZIONE: SONO VIETATE le variabili globali.
• ATTENZIONE: SONO VIETATE tutte le altre librerie a parte quelle già importate nel testo.
• ATTENZIONE: i vostri programmi NON DEVONO sfruttare eventuali periodicità o caratteristiche strutturali degli input, ma devono essere applicabili a qualsiasi input valido.
• ATTENZIONE: NON LASCIATE ISTRUZIONI DI TEST NEL PROGRAMMA, A MENO CHE NON SIANO DOPO UNA RIGA
  • if __name__ == '__main__':
    • vostre istruzioni di test che in questo modo non vengono eseguite durante l'import del file che viene fatto dai test
• Per eseguire i test
  • aprite una finestra "Anaconda Prompt" e posizionatevi nella directory ottenuta scompattando lo zip
  • eseguite il comando
    • pytest test_01.py -v -rA
  • oppure (test con una stampa dei tempi impiegati per eseguire ciascun test)
    • pytest test_01.py -v -rA --durations 0
  • oppure (test con stampa dei tempi spesi dal programma nelle 20 funzioni complessivamente più lente)
    • pytest test_01.py -v -rA --profile
  • Per far fermare i test al primo errore aggiungete l'opzione -x
  • Per chi usa Spyder:
    • è possibile eseguire i test direttamente da dentro Spyder installando il plugin spyder-unittest (ma senza timeout o parametri aggiuntivi)
    • è possibile ottenere i tempi spesi in ciascuna funzione direttamente da dentro Spyder installando il plugin spyder-profiler

NOTA: per aprire i file di testo in formato utf8 NON usate Notepad che non riconosce gli accapi Unix ('\n') ma usate Spyder o Notepad++

Scadenze

• Prima scadenza per TUTTI: ore 23:59 del 26/12/23 (consegnate entrambi i file algoritmo.txt e program01.py)
• Il giorno seguente vi verranno assegnati 3 algoritmi anonimi da valutare entro le 23:59 del 28/12/23
• Una volta ricevuti i suggerimenti dai compagni, dopo averli valutati tutti, potrete riconsegnare un programma migliore entro le 23:59 del 30/12/23

Dovrete consegnare entrambi i file:

• program01.py
• algorithm.txt (file di testo utf8, usate Spyder o Notepad++)

La pagina di consegna è https://q2a.di.uniroma1.it/homeworks/delivery?homework=8

Potete consegnare più volte, vale l'ultima, dopo l'ultima scadenza tutti i codici sorgenti diverranno visibili a tutti.

Answer 1

Buongiorno, ho notato che manca il controllo sullle globali... è voluto e si possono usare?

Comments

Nel messaggio sopra è comunque scritto che sono vietate.

---

Esatto, come le scorse volte in cui c'era però anche il test... Quindi mi è sorto il dubbio lol

---

Vietato fare caching.

In realtà le globali si possono usare ma non per fare caching.

Ho un nuovo modo di verificare il caching e lo applicheró a hw4 hw6 e hw8 a natale

---

Capisco, bel regalo per Natale ahahah

Comunque il caching è proibito in ogni sua forma, oppure l'importante è che non intacchi i test successivi? Se ad esempio avessi un dizionario globale e poi lo azzerassi con .clear all'inizio della funzione principale sarebbe un problema? Giusto per evitare di passarmelo in ogni funzione dove è necessario il suo utilizzo

---

Non deve cambiare tra prima e dopo il run di un test

Answer 2

Buongiorno a tutti,

dato l'esempio del professore se ho capito bene la stringa 'aa' diventa 'bc', la stringa 'bb' diventa 'c' e 'cc' diventa 'd'. Come è possibile che il risultato atteso sia solo la lettera 'd' ?

Il mio ragionamento è questo: AAABAAAC applico la 1°key -> BCABBCAC applico la 2° key -> BCACCAC e applico la 3° key -> BCADAC .

Ho letto il multichar.log e anche li non capisco la logica di trasformazione, ad esempio la prima riga:

'|aaa|baaac'         -> '|bc|baaac'                 aa -> bc

se nel primo blocco ci sono tre lettere 'a' perchè dopo trasformo solo le prime due e l'altra la cancello ?

Grazie in anticipo

Paolo Lofaro

Comments

Nel testo viene specificato che gli anagrammi hanno una lettera spuria, ovvero una lettera aggiuntiva. Nel caso che hai descritto la lettera aggiuntiva è una qualsiasi delle tre 'a'.

Answer 3

segnalo possibile VM bloccata

Answer 4

Buongiorno, il mio codice funziona sui due esempi dati dal professore ma poi sugli altri test mi da un timeOutError, se vado a fare debugging l'unica cosa che riesco a trovare è un unicode error dato dalle "\" negli input, è possibile che sia quello il problema? se si c'è modo di risolverlo? o di avere degli esempi senza "\" in modo di poter fare altri test?

Comments

se stai cercando di fare il print sui test con i geroglifici, prova così: 

print(stringa.encode('utf-16','surrogatepass').decode('utf-16')) 

---

okay grazie, provo

Answer 5

Buongiorno a tutti, ho provato ad eseguire i test nella zip nuova e fino all'1.3 va tutto bene, da quello successivo mi da un timeout error, qualche idea sul motivo?

Comments

Cerca di migliorare la comparazione, o migliorare la parte ricorsiva riducendo le chiamate:

È inutile ri-processare qualcosa che già hai/hai già processato

---

Controlla nel log Correttezza quale funzione o metodo che usi impiega troppo tempo e ti fa superare il limite di tempo. Potrebbe essere ad esempio un problema di troppa ricorsione oppure nel procedimento che usi per trovare i quasi-anagrammi.

---

dove si trova il log Correttezza?

---

vai su Corso, poi su Risultati

Answer 6

Buonasera a tutti,

Per quanto riguarda il file di testo in cui spieghiamo il codice, volevo sapere se la spiegazione può essere discorsiva, in pseudocodice o entrambe? inoltre vanno spiegate anche le eventuali funzioni di appoggio (ex come verifichiamo se una sotto stringa è un "quasi anagramma" o come scegliamo le decriptazioni più brevi) ?

grazie!!

Comments

Va bene la forma discorsiva, puoi anche usare lo pseudocodice ma non dettagliato a tal punto da poter essere tradotto direttamente in istruzioni python, meglio una descrizione delle idee dell'algoritmo e delle funzioni create.

---

ok perfetto, nel dubbio ieri ho pushato con entrambi ma lo pseudocodice credo sia troppo dettagliato. correggo e ripusho, tanto la vm non l'ha ancora corretto. grazie

---

Puoi modificarlo quante volte vuoi senza problemi, l'algoritmo .txt viene mostrato in chiaro agli altri studenti solo dopo il 26 dicembre.

Answer 7

Ciao a tutti,

vorrei chiedere cortesemente un aiuto per sapere se sto ragionando correttamente sul problema:

#per ogni stringa di encrypted_text lunga come la chiave+1

 #se togliendo un carattere a caso è uguale alla chiave

   #allora sostituisco encrypted_text[:len(chiave)+1] con il valore della chiave i-esima

e questo ciclo va fatto per ogni chiave presente, giusto ?

nel log di esempio ci sono moltissime permutazioni di encrypted_text, devono essere tante quanto le chiavi o tante quanto le porzioni di encrypted_text ?

Come si fa a stabilire quante volte va iterato il tutto?

Grazie

Paolo Lofaro

Comments

"uguale alla chiave" -> "anagramma della chiave" 

---

non devi sostituire encrypted_text[:len(chiave)+1] con il valore della chiave i-esima, perché se ad esempio hai una chiave di lunghezza 6, encrypted_text[:len(chiave)+1] indica sempre i primi 7 caratteri di encrypted_text, ma non è detto che la sottostringa quasi-anagramma sia all'inizio di encrypted_text, devi effettuare la sostituzione del quasi-anagramma nella sua posizione

---

nel log di esempio ci sono tutte le possibili sostituzioni che vengono effettuate dal programma, messe in ordine alfabetico e non in ordine di esecuzione (e senza ripetizioni, alcune sostituzioni si possono verificare infatti più volte), non c'è un modo per verificare quante volte va iterato il tutto, l'hw si basa sulla ricorsione, procedi a sostituire finché si può, la ricorsione si ferma quando raggiungi il caso-base, in questo caso una stringa che non ha all'interno quasi-anagrammi per alcuna coppia chiave-valore