POSSIBILE ERRORE TEST RANDOM_180_ITA HW4[req]

G
Giordano_Dionisi (3100 points)
12 38 58
asked Nov 6, 2020 in HW4 obbligatorio by Giordano_Dionisi (3,100 points)
edited Nov 6, 2020 by Giordano_Dionisi

Salve a tutti ragazzuoli,

Sarò breve e coinciso:

Il test Random-180-ita ha la prosodia seguente:

 [0, 1, 2, 3, 2, 4, 5, 6, 5, 7, 8, 1, 9, 10, 11, 12, 13, 14, 15, 14, 16, 17, 18, 17, 19, 20, 13, 21, 22, 23, 24, 25, 26, 27, 26, 28, 29, 30, 29, 31, 32, 25, 33, 34, 35, 36, 37, 38, 39, 38, 40, 41, 42, 41, 43, 44, 37, 45, 46, 47, 48, 49, 50, 51, 50, 52, 53, 54, 53, 55, 56, 49, 57, 58, 59, 60, 61, 62, 63, 62, 64, 65, 66, 65, 67, 68, 61, 69, 70, 71, 72, 73, 74, 75, 74, 76, 77, 78, 77, 79, 80, 73, 81, 82, 83, 84, 85, 86, 87, 86, 88, 89, 90, 89, 91, 92, 85, 93, 94, 95, 96, 97, 98, 99, 98, 100, 101, 102, 101, 103, 104, 97, 105, 106, 107, 108, 109, 110, 111, 110, 112, 113, 114, 113, 115, 116, 109, 117, 118, 119, 120, 121, 122, 123, 122, 124, 125, 126, 125, 127, 128, 121, 9, 129, 130, 131, 132, 133, 134, 133, 135, 136, 137, 136, 138, 139, 132, 140, 141, 142],

Il periodo dovrebbe essere di 15, ma se andiamo a verificare si hanno le due sequenze:

[0, 1, 2, 3, 2, 4, 5, 6, 5, 7, 8, 1, 9, 10, 11]
[120, 121, 122, 123, 122, 124, 125, 126, 125, 127, 128, 121, 9, 129, 130]

Dove risulta ovvio che c'è una corrispondenza biunivoca con tutti, ma poi tra i due terzultimi elementi non c'è alcuna corrispondenza, cioè il primo decrescente di un valore pari ad 8, il secondo decresce di un valore pari a 120, quindi non mi sembra che ci sia una correlazione

La domanda è: Basta che ci sia una correlazione biunivoca tra i due, ovvero che 9 nel primo periodo è correlato solo con quel 9 e stiamo apposto, oppure è necessario anche che si rispetti una certa regolarità ?
P.S.: Mi spiego: se ci dovesse essere solo una semplice correlazione biunivoca allora se avessimo le due sequenze:

s1 = [0, 1]

s2 = [3, 5]

Allora le considereremo apposto, ma in realtà è palese che non sono apposto, proprio perchè la differenza tra s2[0] ed s1[0] è diversa rispetto alla differenza tra s2[1] ed s1[1]... Per me il periodo lo si ha quando le due sequenze hanno proprio la stessa differenza dal primo all'ultimo elemento o no ??

Perchè a me non sembrano periodiche le due sequenze e praticamente io non mi sono limitato a cercare la sequenza tra la prima sequenza e la seconda sequenza lunghe un certo modulo (nell'esempio è 15), ma ho cercato di vedere se tale periodicità la si ha su tutte le altre sequenze ogni modulo passi (quindi avanzo di volta in volta lo step iniziale)

P.2.: Vorrei farvi capire ancora meglio il problema, per evitare disguidi nei commenti:
Avendo quella sequenza che ho postato all'inizio, allora ho che il risultato del test mi dice che il modulo è 15, ma se divido la sequenza nei vari periodi ottengo che:

 [0, 1, 2, 3, 2, 4, 5, 6, 5, 7, 8, 1, 9, 10, 11,
 12, 13, 14, 15, 14, 16, 17, 18, 17, 19, 20, 13, 21, 22, 23,
 24, 25, 26, 27, 26, 28, 29, 30, 29, 31, 32, 25, 33, 34, 35,
 36, 37, 38, 39, 38, 40, 41, 42, 41, 43, 44, 37, 45, 46, 47,
 48, 49, 50, 51, 50, 52, 53, 54, 53, 55, 56, 49, 57, 58, 59,
 60, 61, 62, 63, 62, 64, 65, 66, 65, 67, 68, 61, 69, 70, 71,
 72, 73, 74, 75, 74, 76, 77, 78, 77, 79, 80, 73, 81, 82, 83,
 84, 85, 86, 87, 86, 88, 89, 90, 89, 91, 92, 85, 93, 94, 95,
 96, 97, 98, 99, 98, 100, 101, 102, 101, 103, 104, 97, 105, 106, 107,
 108, 109, 110, 111, 110, 112, 113, 114, 113, 115, 116, 109, 117, 118, 119,
 120, 121, 122, 123, 122, 124, 125, 126, 125, 127, 128, 121, 9, 129, 130,
 131, 132, 133, 134, 133, 135, 136, 137, 136, 138, 139, 132, 140, 141, 142],

Ora tutte queste sequenze dovrebbero essere periodiche tra loro, io confronto sempre la prima sequenza, il primo periodo, con le restanti, dato che se è periodica la prima con la seconda e la prima con la terza, allora per transitività è anche periodica la seconda con la terza... Ora spero di essermi spiegato ancora meglio, più che altro per capire come calcolare il periodo, almeno ho finito l'homework crying


Visto che ho trovato questa stranezza, aspetta un vostro conforto

Grazie per l'attenzione

1,815 views

4 Answers

Best answer
andrea.sterbini (172680 points)
511 927 1776
answered Nov 6, 2020 by andrea.sterbini (172,680 points)
selected Nov 7, 2020 by Giordano_Dionisi

Perchè devono avere tutte le stesse differenze?
Basta che esista una corrispondenza biunivoca.
Nell'esempio quello che conta sono la differenza e l'uguaglianza tra valori nel segmento di 15 che si ripete.
Prendo proprio il caso che non torna ed evidenzio i gruppi di versi uguali:

0 1 2 3 2 4 5 6 5 7 8 1 9 10 11
120 121 122 123 122 124 125 126 125 127 128 121 9 129 130

Come vedete la struttura è la stessa, i versi uguali si corrispondono, tutti gli altri sono tutti diversi tra loro e da quelli uguali. 

G
Giordano_Dionisi (3100 points)
12 38 58
commented Nov 6, 2020 by Giordano_Dionisi (3,100 points)
Okay prof però allora a me sorge questo dubbio seguente, cioè se ho la solita sequenza:

 [0, 1, 2, 3, 2, 4, 5, 6, 5, 7, 8, 1, 9, 10, 11,
 12, 13, 14, 15, 14, 16, 17, 18, 17, 19, 20, 13, 21, 22, 23,
 24, 25, 26, 27, 26, 28, 29, 30, 29, 31, 32, 25, 33, 34, 35,
 36, 37, 38, 39, 38, 40, 41, 42, 41, 43, 44, 37, 45, 46, 47,
 48, 49, 50, 51, 50, 52, 53, 54, 53, 55, 56, 49, 57, 58, 59,
 60, 61, 62, 63, 62, 64, 65, 66, 65, 67, 68, 61, 69, 70, 71,
 72, 73, 74, 75, 74, 76, 77, 78, 77, 79, 80, 73, 81, 82, 83,
 84, 85, 86, 87, 86, 88, 89, 90, 89, 91, 92, 85, 93, 94, 95,
 96, 97, 98, 99, 98, 100, 101, 102, 101, 103, 104, 97, 105, 106, 107,
 108, 109, 110, 111, 110, 112, 113, 114, 113, 115, 116, 109, 117, 118, 119,
 120, 121, 122, 123, 122, 124, 125, 126, 125, 127, 128, 121, 9, 129, 130,
 131, 132, 133, 134, 133, 135, 136, 137, 136, 138, 139, 132, 140, 141, 142],

Allora può vedere che tale sequenza ha anche periodo 2, infatti basta considerare un pò di periodi per auto-convincersi:

 0, 1,
 2, 3,
 2, 4,
 5, 6,
 5, 7,
 8, 1,
 9, 10
e via dicendo...

Come vede posso creare una relazione biunivoca, prima tra lo zero ed il due e l'uno con il tre, poi con lo zero ed il due e l'uno con il quattro e via discorrendo... Quindi in questo modo a me escono fuori periodi assai piccoli, perchè tutto ha una correlazione biunivoca, almeno in questo esempio, per questo non capisco come interpretarla... Poi se io so che il modulo è 15, allora riesco a verificare benissimo che si ha una relazione biunivoca, ma se io ciò non lo so allora trovo sempre periodi molto piccoli come risultato (passo tipo 7-8 test con questa implementazione, uno che non passo e proprio questo qui, perchè mi torna periodo = 2)
twgever (15190 points)
7 27 105
commented Nov 6, 2020 by twgever (15,190 points)
quoto, ho avuto lo stesso problema con 2-3 test
G
Giordano_Dionisi (3100 points)
12 38 58
commented Nov 7, 2020 by Giordano_Dionisi (3,100 points)
Io calcola facevo una cosa fighissima e velocissima, ovvero partivo dal periodo più piccolo (per uno verificavo in modo esaustivo ed quindi partivo con due) ed arrivavo fino al massimo periodo possibile (ovvero la lunghezza della parosodia) e collezionavo gli elementi del primo periodo in una struttura dati molto veloce (penso che non posso dirla ma è palese) e quella era per sempre, poi collezionavo gli elementi di tutte le altre strutture che venivano, quindi se il periodo era 2 io prendevo prima gli elementi [2:4] , [4:6] , [6:8] e via dicendo e li confrontavo con il primo periodo ([0:2]) e così basta che esisteva una correlazione tra 0 - 2 e 1 - 3 e tra 0 - 4 ed 1 - 5 e via dicendo (così come l'ha descritta proprio precisamente il prof) ed allora ero contento perchè quello era il periodo più piccolo... Però mi escono sempre periodi troppo piccoli facendo questa correlazione precisa, in particolare su determinati test
andrea.sterbini (172680 points)
511 927 1776
commented Nov 7, 2020 by andrea.sterbini (172,680 points)
edited Nov 7, 2020 by andrea.sterbini

ATTENZIONE: il minimo periodo deve essere maggiore di 2.
 

1
1937764 (3520 points)
6 14 42
commented Nov 7, 2020 by 1937764 (3,520 points)
edited Nov 7, 2020 by 1937764

Seguo la discussione che avevo capito come @Giordano_Dionisi anche io.

EDIT: ho riletto tante volte la risposta del professore e credo averla intesa. L'ho spiegata con altre parole nell'altro commento mio

s
stefanocali (1230 points)
1 2 9
commented Nov 7, 2020 by stefanocali (1,230 points)
Anche io ho lo stesso problema, trovo periodi piu' piccoli di quelli riportati nel test.ad esempio per il testo random_1024_rnd trovo 20 come periodo piu piccolo, invece dovrebbe essere 512
G
Giordano_Dionisi (3100 points)
12 38 58
commented Nov 7, 2020 by Giordano_Dionisi (3,100 points)
Prof confermo che l'unica condizione è che il periodo sia maggiore strettamente di due per funzionare, per il resto è una semplice correlazione biunivoca proprio!!!

Grazie mille ancora e buon weekend
twgever (15190 points)
7 27 105
commented Nov 7, 2020 by twgever (15,190 points)
grazie per la conferma prof, buona giornata.
Valerio_01 (600 points)
2 6 10
answered Nov 6, 2020 by Valerio_01 (600 points)
sono arrivato anche io a questo punto e infatti il mio codice non rileva nessuna corrispondenza tra le cifre della prosodia e restituisce 1 dato che è appunto il valore minimo, qualcuno sa come risolvere in qualche modo?
G
Giordano_Dionisi (3100 points)
12 38 58
commented Nov 6, 2020 by Giordano_Dionisi (3,100 points)
Io sto aspettando la sola risposta del prof... Ovviamente per 1 io l'ho risolto in modo esaustivo (cioè devi verificare che se ci sono tutti zeri allora va bene il periodo 1, altrimenti no) e sono partito da 2... Ma è chiaro che come te ho il problema sul periodo 2 se considero una semplice corrispondenza biunivoca... Mentre se considero la differenza, insomma il metodo che ho espresso nel post, allora supero tipo 7 test (tipo la sufficienza), però non mi tornano i valori degli esempi, cioè a me non sembra che le sequenze siano periodiche, a meno che devo proprio riconsiderare la definizione di periodicità, ma mi sembra abbastanza palese, ecco quanto
Valerio_01 (600 points)
2 6 10
commented Nov 6, 2020 by Valerio_01 (600 points)
guarda mi trovo esattamente nella tua stessa situazione, a questo punto non ci resta che aspettare il prof che magari definendo per il meglio la periodicità che si cerca nel programma riuscirà a sciogliere qualche dubbio
e
e.pauroso (420 points)
0 0 4
answered Nov 6, 2020 by e.pauroso (420 points)

In questo esempio il modulo = 5, infatti la prosodia è formata da due sequenze uguali di 5 elementi che seguono lo schema [0, 1, 1, 2, 0], infatti [0, 1, 1, 2, 0] è equivalente a [3, 4, 4, 5, 3]

io ho risolto capendo in cosa sono uguali le due sequenze 

G
Giordano_Dionisi (3100 points)
12 38 58
commented Nov 6, 2020 by Giordano_Dionisi (3,100 points)
E queste due sequenze in cosa sarebbero uguali:

[0, 1, 2, 3, 2, 4, 5, 6, 5, 7, 8, 1, 9, 10, 11]
[120, 121, 122, 123, 122, 124, 125, 126, 125, 127, 128, 121, 9, 129, 130]

Cioè il 9 sarebbe uguale al 9 per quale principio realisticamente ?
e
e.pauroso (420 points)
0 0 4
commented Nov 6, 2020 by e.pauroso (420 points)
sono equivalenti, ma non uguali.

quindi non sono uguali nel valore di prosodia  puro ma potrebbero esserlo in qualcos'altro.
G
Giordano_Dionisi (3100 points)
12 38 58
commented Nov 6, 2020 by Giordano_Dionisi (3,100 points)
Okay ma in cos'altro possono essere uguali, cioè è quello che non comprendo calcola
e
e.pauroso (420 points)
0 0 4
commented Nov 6, 2020 by e.pauroso (420 points)
quella è una sequenza di interi che crei tu.

quindi è una derivata, forse la visualizzazione del suo integrale ti chiarirebbe subito in cosa sono uguali, prova a ripartire dal come crei quella sequenza
1
1937764 (3520 points)
6 14 42
answered Nov 7, 2020 by 1937764 (3,520 points)
edited Nov 7, 2020 by 1937764

Credo di aver capito come viene inteso il periodo, dato che sono riuscito a passare tutti i test.

Faccio l'esempio con Random-180-ita

Le sequenze:

[  0,   1,   2,   3,   2,   4,   5,   6,   5,   7,   8,   1,   9,  10,  11]

[120, 121, 122, 123, 122, 124, 125, 126, 125, 127, 128, 121,   9, 129, 130]

Sembrano diverse ma devi considerare la corrispondenza solo sui valori uguali.

Quindi devi considerarle come: (gli underscore sono i valori che nella porzione di lista sono unici, quindi li andiamo a ignorare completamente.

[ _, A, B, _, B, _, C, _, C, _, _, A, _, _, _]     (A = 1,   B = 2,   C = 5)
[ _, A, B, _, B, _, C, _, C, _, _, A, _, _, _]     (A = 121, B = 122, C = 125)

E viste così sono identiche, perchè i valori identici stanno nelle stesse posizioni. Ancora, i valori non ripetuti sono stati ignorati.

In caso questo che ho detto sia errato, vi prego di dirmelo. Io l'ho implementato così e passo tutti i test.

G
Giordano_Dionisi (3100 points)
12 38 58
commented Nov 7, 2020 by Giordano_Dionisi (3,100 points)
Approvo in pieno, ho appena reimplementato l'idea con il fatto che il periodo deve essere maggiore di due e passo tutti i 13 test... L'idea che hai espresso è corretta, l'importante è che riesci a trovare una qualsivoglia correlazione biunivoca nella sequenza proprio, come ha detto il prof nell'esempio a colori della risposta superiore... L'unico problema era questo vincolo di periodo maggiore strettamente di due
G
Giuseppe01 (1500 points)
0 0 10
commented Nov 7, 2020 by Giuseppe01 (1,500 points)
Io sto ancora ragionando sul concetto di periodo minimo in generale. Ho capito che vogliamo trovare una corrispondenza biunivoca ma non mi è chiaro come vengono definiti gli insiemi da confrontare.

Le mie doti poetiche sono molto scarse ma spontaneamente mi viene da pensare che la prosodia debba sempre essere suddivisa in porzioni uguali per poter fare questo confronto, altrimenti su una lista di ad esempio 8 elementi si potrebbe trovare un periodo valido tra i primi due gruppi formati da tre valori e rimanere con un gruppo di due elementi "orfano".

Quindi in base al numero di elementi della lista andremo a suddividere in parti uguali per poter controllare la biunivocità su tutti gli insiemi generati (qui però si pone il problema dei numeri primi in teoria).

É corretto il ragionamento oppure sto interpretando male il problema? Come dicevo non mi riferisco ai test in particolare ma a ciò che si intende per periodo minimo data una lista di prosodia
G
Giuseppe01 (1500 points)
0 0 10
commented Nov 7, 2020 by Giuseppe01 (1,500 points)
Pare che sia corretto (stando al risultato dei test). Mi sono risposto da solo. :)
T
Tommaso (1480 points)
0 8 22
commented Nov 14, 2020 by Tommaso (1,480 points)
Sinceramente ho proprio questo dubbio, come dobbiamo dividere gli intervalli per considerare gli insiemi? Nel tuo caso se abbiamo 8 elementi... partiamo con il periodo minimo possibile (ovvero 3):

Parto ad esempio con i primi 3 elementi (elem 1, elem 2, elem3) che dovrei confrontare con i seguenti gruppi: (elem 4, elem 5, elem6),  (elem 5, elem 6, elem7) e  (elem 6, elem 7, elem8).

Poi prendo (elem 2, elem 3, elem 4) che dovrei confrontare con i gruppi: (elem 5, elem 6, elem7) e  (elem 6, elem 7, elem8)

Poi prendo (elem 3, elem 4, elem 5) che dovrei confrontare col solo gruppo:  (elem 6, elem 7, elem8).

Se trovo coincidenza in uno solo di questi confronti allora il periodo minimo è 3... altrimenti passo ad analizzare i gruppi di periodo 4, però adottando sempre lo stesso ragionamento. giusto?

grazie!