Old Typewriter dubbio

[v.bizzarri]

1. Ho un dubbio sull’interpretazione di una parte del testo che riporto sotto:

Furthermore, these errors may happen multiple times for the same string, and even multiple times for
the same characters: for instance, a doubly stuck key would change “aaa” into “a” and a doubly wild key
would do the opposite change.

La parte in grassetto si intrerpreta:

1. concludendo che la digitazione di una “a” può generare una sequenza di 3 o più “a”
2. che la digitazione di “aaa” può portare ad una sequenza di fino a 6 “a”.
3. altro ancora.

E’ “IMPOSSIBLE” solo il secondo caso di esempio?

[filippos]

@v.bizzarri

1. concludendo che la digitazione di una “a” può generare una sequenza di 3 o più “a”
2. che la digitazione di “aaa” può portare ad una sequenza di fino a 6 “a”.
3. altro ancora.

La digitazione di k caratteri ‘a’ può portare ad una sequenza di [1, N] ‘a’, in quanto potremmo avere un qualsiasi numero di duplicazioni e un qualsiasi numero di “stuck keys”

@v.bizzarri

E’ “IMPOSSIBLE” solo il secondo caso di esempio?

No, esistono molteplici casi che possono essere impossibili, ad esempio:

abc
abc
xxx

Non ho verificato che siano presenti come input tra i testcase del problema, ma nulla vieta la loro presenza

[v.bizzarri]

@filippos

Non ho verificato che siano presenti come input tra i testcase del problema, ma nulla vieta la loro presenza

Su questo punto mi spiego meglio:
Ho fatto più sottoposizioni che si limitavano a mandare in stampa “IMPOSSIBLE” e solo il secondo test-case risulta corretto:
O di impossibile c’è solo quello oppure che altro??

@filippos

La digitazione di k caratteri ‘a’ può portare ad una sequenza di [1,N] ‘a’ , in quanto potremmo avere un qualsiasi numero di duplicazioni e un qualsiasi numero di “stuck keys”

Quindi vero anche per K=1!
In ogni caso c’è qualcosa che mi sfugge ho provato due versioni:

1. una prende per buono quello che mi confermi tu (mio punto 1)
2. l’altra prende per buono il mio punto 2

Entrambe azzeccano solo i casi di esempio e sbagliano tutti gli altri.

In sostanza ricodifico le tre stringhe nel modo (carattere, numero di ripetizioni)
esempio: “aaabbccccd” diventa:
(‘a’,3),(‘b’,2),(‘c’,4),(‘d’,1)
controllo se tutte e 3 le stringhe hanno lo stesso numero di elementi (se no è impossibile)
controllo che i caratteri siano gli stessi e nella stessa sequenza. (se no è impossibile)
superati questi controlli per me il problema ammette soluzione e la vado a cercare:
(‘a’,3),(‘b’,2),(‘c’,4),(‘d’,1)
(‘a’,4),(‘d,’,4),(‘c’,4),(‘d’,2)
(‘a’,1),(‘b’,3),(‘c’,4),(‘d’,1)
queste 3 stringhe non superano i test ed non ammettono soluzione
(‘a’,3),(‘b’,2),(‘c’,4),(‘d’,1)
(‘a’,4),(‘b’,4),(‘c’,4),(‘d’,2)
(‘a’,1),(‘b’,3),(‘c’,4),(‘d’,1)
queste 3 stringhe superano i test ed ammettono soluzione
(‘a’,3),(‘b’,3),(‘c’,4),(‘d’,1)-> “aaabbbccccd”
per ogni carattere calcolo la lunghezza media delle ripetizioni (eventualmente +1) e quello sarà il numero di
ripetizioni di quel carattere nella stringa risultato.

[lucach]

@v.bizzarri

La parte in grassetto si intrerpreta:

La parte in grassetto è in un periodo introdotto da “for instance” e vuole essere solo l’esemplificazione di un possibile comportamento della macchina da scrivere.

Le regole sono:

• “Stuck key”
• “Wild key”
• qualsiasi loro combinazione.

@v.bizzarri

E’ “IMPOSSIBLE” solo il secondo caso di esempio?

Il fatto che i testcase siano deboli non dimostra (in ogni caso) il fatto che l’unico caso impossibile sia quello mostrato.

[v.bizzarri]

@lucach

Il fatto che i testcase siano deboli non dimostra (in ogni caso) il fatto che l’unico caso impossibile sia quello mostrato.

Certo però il fatto che:

@v.bizzarri

Ho fatto più sottoposizioni che si limitavano a mandare in stampa “IMPOSSIBLE” e solo il secondo test-case risulta corretto:

dovrebbe servire a dimostrare che nei test case proposti ci sia solo quello.

[lucach]

@v.bizzarri

dovrebbe servire a dimostrare che nei test case proposti ci sia solo quello.

Sicuramente (infatti la mia era un’affermazione! ).

Questo varrà finché non decidiamo di riscrivere il generatore .
Scherzi a parte, questa è una (ulteriore) riprova del fatto che superare tutti i casi di prova non significa avere la garanzia della correttezza assoluta della soluzione rispetto a un dato problema. Più in generale, il problema di testare un software è ancora largamente irrisolto.

[v.bizzarri]

Trovato il mio errore e problema risolto.
Grazie comunque per i chiarimenti.

[filippos]

@lucach

Scherzi a parte, questa è una (ulteriore) riprova del fatto che superare tutti i casi di prova non significa avere la garanzia della correttezza assoluta della soluzione rispetto a un dato problema.

Ma come, io sapevo che se faceva 100 era dimostrato

[lucach]

@filippos

Ma come, io sapevo che se faceva 100 era dimostrato

Evidentemente in Russia dimostrate cose sconosciute nel resto del mondo

Più seriamente: è davvero bello vedere che pian piano questa piattaforma sta entrando a far parte anche della didattica nelle scuole superiori. Tuttavia resta importante sensibilizzare i ragazzi sul fatto che superare una batteria di test, per quanto estesa possa essere, non dà garanzie sulla correttezza generale.

[filippos]

@lucach

Più seriamente: è davvero bello vedere che pian piano questa piattaforma sta entrando a far parte anche della didattica nelle scuole superiori. Tuttavia resta importante sensibilizzare i ragazzi sul fatto che superare una batteria di test, per quanto estesa possa essere, non dà garanzie sulla correttezza generale.

Hai perfettamente ragione, volevo solo fare il simpatico e citare questa frase sentita più e più volte nell’ambito delle olimpiadi

[v.bizzarri]

@lucach

Scherzi a parte, questa è una (ulteriore) riprova del fatto che superare tutti i casi di prova non significa avere la garanzia della correttezza assoluta della soluzione rispetto a un dato problema. Più in generale, il problema di testare un software è ancora largamente irrisolto.

A questo riguardo la mia soluzione attuale di “Art Gallery Selection”, che supera tutti i test case e che quindi fa 100/100, con l’input sotto riportato dice “YES”

4
1 4
9 4
8 5
8 7

(almeno fino alla sottoposizione n.366950)
Vedrò di correggerla