Old Typewriter dubbio


#1
  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?


#2

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”

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 :slight_smile:


#3

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??

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.


#4

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.

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


#5

Certo però il fatto che:

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


#6

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

Questo varrà finché non decidiamo di riscrivere il generatore :smiling_imp:.
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.


#7

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


#8

Ma come, io sapevo che se faceva 100 era dimostrato :open_mouth:


#9

Evidentemente in Russia dimostrate cose sconosciute nel resto del mondo :joy:

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.


#10

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