[HOMEWORK] Homework 7 opzionale

andrea.sterbini (172680 points)
511 927 1776
asked Dec 3, 2021 in Avvisi by andrea.sterbini (172,680 points)

ATTENZIONE

  • eventuali correzioni verranno inserite qui
  • NOTA: per eseguire i test SENZA i controlli ed il timeout modificate test_01.py settando la variabile DEBUG=True

Istruzioni

Per svolgere l'homework:

  • Installate le librerie necessarie (compreso stopit)
  • Scaricate il file HW7opt.zip e scompattatelo in una directory
    • Lo zip contiene
      • l'esercizio da svolgere, descritto all'inizio del file program01.ita.py (in italiano) oppure program01.eng.py (in inglese)
        • l'esercizio consiste nel realizzare, se necessario definendo funzioni ausiliarie, la funzione descritta all'inizio del file, completandone il codice
        • 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/eng.py che preferite con il nome program01.py
    • Editate il file program01.py implementando le funzioni necessarie a risolvere l'esercizio.
    • 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
    • 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-line-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: questo homework non ha scadenza

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

    Potete consegnare più volte, vale l'ultima.

    1 Answer

    S
    S3b4stian82 (2250 points)
    3 6 27
    answered Dec 5, 2021 by S3b4stian82 (2,250 points)

    ATTENZIONE: i vostri programmi NON DEVONO sfruttare eventuali periodicità o caratteristiche strutturali degli input, ma devono essere applicabili a qualsiasi input valido.

    Le stringhe palindrome vengono risolte con tempi che crescono in maniera esponenziale in base alla lunghezza della stringa. I test responsabili, il 16 ed il 18 terminano in modo corretto ma solamente dopo 10 minuti circa (590s in locale)

    Apparte cercare di eliminare le parti palindrome (da sperientare e non so se funzionerà), altre soluzioni?

    d
    davidepnc1 (220 points)
    2 4 5
    commented Dec 5, 2021 by davidepnc1 (220 points)
    Posso consigliarti una cosa che ho provato, e ha funzionato. Prima di iniziare la ricorsione, togli tutti i numeri che appaiono un numero pari di volte nella sequenza, quei numeri sparirebbero comunque in ogni caso.
    S
    S3b4stian82 (2250 points)
    3 6 27
    commented Dec 5, 2021 by S3b4stian82 (2,250 points)
    Si era una delle cose che avevo intenzione di provare a fare.

    Grazie!
    S
    S3b4stian82 (2250 points)
    3 6 27
    commented Dec 5, 2021 by S3b4stian82 (2,250 points)
    Ok risolto affinando la parte di memoization per evitare le chiamate a funzione già effettuate. Ora funziona senza dover gestire input particolari.
    l
    luca.pierlorenzi (120 points)
    0 0 1
    commented Dec 5, 2021 by luca.pierlorenzi (120 points)
    Ho provato il tuo consiglio, ha migliorato molto le prestazioni.

    Grazie
    S
    S3b4stian82 (2250 points)
    3 6 27
    commented Dec 5, 2021 by S3b4stian82 (2,250 points)
    Ho aggiunto anche la pulizia della stringa dai numeri presenti in quantità pari. Migliorato tantissimo, Grazie!
    Exyss (21390 points)
    1 2 79
    commented Dec 6, 2021 by Exyss (21,390 points)
    edited Dec 6, 2021 by Exyss
    Qualcuno ha trovato altre soluzioni oltre a quella "matematica/logica" del pulire la sequenza dalle coppie pari o quella delle sequenze palindrome? Credo che solo con la memoization/caching non si possa fare molto per il test 16 e 18  oltre a qualche ottimizzazione
    S
    S3b4stian82 (2250 points)
    3 6 27
    commented Dec 6, 2021 by S3b4stian82 (2,250 points)
    Allo stato attuale non riesco nemmeno a uscire dallo schema mentale che ho usato per far ruotare le coppie di numeri uguali da eliminare...... comunque concordo per il discorso su memoization, da solo non basta