Indovinello algoritmico.

[Bruno]

In una libreria mi è capitato fra le mani un testo molto gradevole, si tratta di "Breve e universale storia degli algoritmi" di Luigi Laura, docente di Machine Learning e Analisi dei Big Data alla Luiss e responsabile tecnico e scientifico delle Olimpiadi Italiane di Informatica.

Si tratta di un volume pubblicato lo scorso anno, scritto con particolare chiarezza e uno stile coinvolgente, anche per chi ha esigue esperienze nel campo degli algoritmi e dell'informatica in genere (come me).

Si scoprono cose curiose. Come quando, a causa dell'interazione di due algoritmi, un libro venduto su Amazon a un prezzo iniziale di appena cento dollari, a un certo punto è venuto a costare ventiquattro milioni di dollari

Alla fine di ogni capitolo viene proposto un indovinello algoritmico, appunto, e di seguito ne trascrivo uno.

Guardiamo lo schema:

Laura_IndAlg.jpg (4.36 KiB) Visto 20831 volte

Domanda 1.
Considerate i numeri da 1 a 6. Riuscite a disporli nelle precedenti celle rispettando i versi?

Domanda 2.
Riuscite a inventare un algoritmo che, data una qualsiasi lista di numeri (tutti distinti tra di loro) e una serie di celle da riempire, riesca a mettere i numeri nelle celle rispettando i versi?

Limitiamoci a carta e penna

[franco]

Mi sembra che la domanda 1 abbia svariate soluzioni valide:
1<5>3<4<6>2
2<4>1<5<6>3
3<6>2<4<5>1
4<5>1<2<6>3
....
Il numero uno deve essere in prima, terza o sesta posizione.
Il numero sei in seconda o quinta.
Per il resto ci sono tante possibilità.

Per la domanda 2 devo pensare a un approccio ...

[gnugnu]

Come dice Franco vi sono molte disposizioni accettabili. Sarebbe interessante trovare un algoritmo per contare quante siano in generale.
Uno per disporre correttamente i numeri, a mano e senza pretesa di ottimizzare la rapidità di esecuzione, potrebbe essere l'adattamento di quello usato per bilanciare le parentesi in un'espressione:
Si inizia da uno degli estremi etichettando la prima casella di quel lato con un numero arbitrario , si prosegue passando alla casella contigua associando a questa il numero della casella precedente aumentato/diminuito di $ 1 $ in modo da rispettare la relazione fra le due e si itera fino all'etichettatura dell'ultima casella.
A questo punto basta individuare le(la) caselle con l'etichetta più grande, farcirle (a caso se sono più di una) con i ripieni più consistenti e ripetere il procedimento diminuendo di uno il valore dell'etichetta, iterando fino alla fine del compito.
Ciao

[Bruno]

Gnugnu, per rendere il tuo ragionamento più chiaro (soprattutto a me) puoi applicarlo intanto (passo passo, se ti è possibile) al caso proposto con la prima domanda?

Grazie

[Gianfranco]

Ecco una proposta, da dimostrare e implementare.
Algoritmo:
1) Scrivo nell'ordine i numeri 1, 2, 3, ... nelle caselle seguite dal segno "<"
2) Scrivo nell'ordine i numeri n, n-1, n-2,... nelle restanti caselle.

Se i numeri dati non sono 1, 2, 3, ..., n, dapprima li metto in ordine crescente, poi li indicizzo, poi scrivo i vari n(i) nelle caselle i-esime.

Aggiornamento.
Ecco l'implementazione in BASIC.

Codice: Seleziona tutto

!'Numero dei dati (indici)
DATA 10
!'Sequenza di relazioni
DATA "<",">",">",">",">","<",">",">","<"
!'Inizializzazione variabili
RESTORE
READ n
DIM a(n)
DIM r$(n-1)
LET magg=0
LET mino=0
!'Algoritmo
FOR i=1 TO n-1
   READ a$
   LET r$(i)=a$
   IF a$="<" THEN
      LET mino=mino+1
      LET a(i)=mino
   END IF
   IF a$=">" THEN
      LET magg=magg+1
      LET a(i)=n-magg+1
   END IF
NEXT i
LET a(n)=n-magg
!'Stampa
FOR i=1 TO n-1
   PRINT a(i);r$(i);
NEXT i
PRINT a(n)
END

[franco]

Interpretando l'ipotesi di Gnugnu e applicandola al nostro caso A<B>C<D<E>F potrebbe essere così (passo passo):
- associo arbitrariamente il "valore di riferimento" VR=0 alla casella A
- B è maggiore quindi gli assegno un VR=1
- C con lo stesso criterio è nuovamente VR=0
- D assume VR=1, E -> VR=2 e F -> VR=1
- alla fine mi trovo così: 0<1>0<1<2>1

Sulla casella con il valore di riferimento più alto (VR=2) metto il numero 6, su quelle successive (VR=1) metto i numeri successivi, 5-4-3 (a caso, tanto va bene comunque) e infine metto sulle caselle con VR=0 gli ultimi due numeri 2-1
Quindi per finire 1/2<3/4/5>2/1<4/5/3<6>5/3/4

Ipotizzando un mix di caselle diverso:
A>B>C>D<E<F mi porta a 0>-1>-2>-3<-2<-1 e quindi 6>5/4>3/2>1<2/3<4/5

Evidentemente, questo sistema trova soluzioni valide ma ce ne possono essere anche di diverse; nel secondo esempio funziona anche 4>3>2>1<5<6

[gnugnu]

@Bruno
Decido di partire da sinistra con l'etichetta "5" (è del tutto indifferente, ma così evito i negativi), aumentando di uno quando transito per un "<" e diminuendo di uno nel caso opposto, ottengo, nell'ordine:
$ [5,6,5,6,7,6]$
queste etichette rispettano le relazioni d'ordine volute; alcune si ripetono, ma questo indica semplicemente che vi sono, sicuramente, più soluzioni.
Cerco il(i) massimo delle etichette: $ 7 $, in quella casella scrivo il maggiore dei numeri proposti $ 6 $.
Cerco le caselle marchiate con $ 6 $, son tre, in queste scrivo i tre maggiori numeri proposti restanti $ 3,4,5 $, non importa in quale ordine.
Cerco le caselle etichettate con $ 5 $, sono due, vi scrivo i numeri restanti. Ottenendo ad esempio:
$[1,3,2,4,6,5]$, ma anche $[2,5,1,3,6,4]$, oppure $[1,4,2,5,6,3]$..........

Se avessi iniziato da destra, poniamo con l'etichetta $ 2 $, avrei ottenuto:
$[1,2,1,2,3,2]$ che differiscono dalle etichette trovate prima per una costante ($4$) e questo si dimostra facilmnte.
NB Le $ 6 \cdot 2=12 $ permutazioni generate con questo algoritmo sono, generalmente, lungi dall'esaurire quelle possibili.
Ciao

[gnugnu]

@Franco
sottoscrivo (hai postato mentre scrivevo)
Ciao

[Bruno]

Capito

[gnugnu]

@Gianfranco
molto bello il tuo algoritmo; semplicissimo ed efficiente.
Ciao

[Gianfranco]

Domanda 2.
Riuscite a inventare un algoritmo che, data una qualsiasi lista di numeri (tutti distinti tra di loro) e una serie di celle da riempire, riesca a mettere i numeri nelle celle rispettando i versi?

Limitiamoci a carta e penna

Cari amici, limitandoci all'uso di carta e penna e al fatto che la domanda chiede solo una soluzione (non tutte), la cosa secondo me è molto più semplice di quanto appare a prima vista. O non ho capito qualcosa?
La mia proposta di algoritmo applicata a un esempio con 9 numeri.

algo1.png (1.9 KiB) Visto 20787 volte

---
1)Scrivo nell'ordine i numeri 1, 2, 3, ... nelle caselle seguite dal segno "<"
In questo modo ho scritto tutti i numeri che sono minori di altri numeri. Tutti i numeri che mi restano da scrivere sono sicuramente maggiori di quelli che ho scritto.
Poiché li ho scritti in ordine crescente, sono sicuro che non ci sono inversioni.

algo2.png (4.21 KiB) Visto 20787 volte

---
2) Scrivo nell'ordine i numeri n, n-1, n-2,... nelle restanti caselle.
In questo modo ho scritto tutti i numeri che sono maggiori dei numeri già scritti. Poiché li ho scritti in ordine decrescente sono sicuro che non ci sono inversioni.

algo3.png (4.79 KiB) Visto 20787 volte

---
Se invece vogliamo trovatre tutte le soluzioni, allora il problema si complica (forse).

[Bruno]

Bravi!
Il metodo di Gianfranco potrebbe essere riformulato così:
1. ordino i numeri della lista data;
2. guardo il segno di disuguaglianza alla destra della prima cella:
$\;\;$ se è ">", prendo il massimo della lista e lo scrivo nella prima cella, eliminandolo dalla lista,
$\;\;$ se è "<", prendo il minimo della lista e lo scrivo nella prima cella, eliminandolo dalla lista;
3. ripeto l'operazione per ogni cella successiva, fino a collocare l'ultimo numero nella cella rimasta vuota.

Esempio:

[] > [] < [] < [] > [] > [] > [] < [] < []
{1,2,3,4,5,6,7,8,9}

[9] > [] < [] < [] > [] > [] > [] < [] < []
{1,2,3,4,5,6,7,8}

[9] > [1] < [] < [] > [] > [] > [] < [] < []
{2,3,4,5,6,7,8}

[9] > [1] < [2] < [] > [] > [] > [] < [] < []
{3,4,5,6,7,8}

[9] > [1] < [2] < [8] > [] > [] > [] < [] < []
{3,4,5,6,7}

[9] > [1] < [2] < [8] > [7] > [] > [] < [] < []
{3,4,5,6}

[9] > [1] < [2] < [8] > [7] > [6] > [] < [] < []
{3,4,5}

[9] > [1] < [2] < [8] > [7] > [6] > [3] < [] < []
{4,5}

[9] > [1] < [2] < [8] > [7] > [6] > [3] < [4] < []
{5}

[9] > [1] < [2] < [8] > [7] > [6] > [3] < [4] < [5]

[Gianfranco]

@Gianfranco
molto bello il tuo algoritmo; semplicissimo ed efficiente.

Grazie gnugnu. Questa mattina viaggiavo in treno, in uno scompartimento quasi vuoto, alle prese con questo problema: grafici che andavano su e giù ma senza scendere sotto zero, procedure di backtracking e così via. A un certo punto ho pensato che Bruno lo ha definito "indovinello" e dopo un po' mi è venuta in mente una soluzione semplicissima.

[Gianfranco]

Bravi!
Il metodo di Gianfranco potrebbe essere riformulato così:
1. ordino i numeri della lista data;
2. guardo il segno di disuguaglianza alla destra della prima cella:
$\;\;$ se è ">", prendo il massimo della lista e lo scrivo nella prima cella, eliminandolo dalla lista,
$\;\;$ se è "<", prendo il minimo della lista e lo scrivo nella prima cella, eliminandolo dalla lista;
3. ripeto l'operazione per ogni cella successiva, fino a collocare l'ultimo numero nella cella rimasta vuota.

In effetti, quando ho implementato l'algoritmo in BASIC ho fatto proprio così. In questo modo i numeri si collocano tutti in un unico passaggio.
Ho collocato solo gli indici (1, 2, 3, ...), perché se i numeri dati vengono dapprima ordinati in un vettore a(1), a(2), a(3), ... basta collocare il numero a(i) al posto dell'indice i.

Questo problema è bello perché si può proporre anche alle scuole medie come gioco matematico.
Ed è interessante perché è focalizzato più sull'algoritmo che sul "coding".
Da tempo nella scuola di base si dà troppo risalto al coding rispetto alla creazione di algoritmi, e questo è un errore (grave).
A questo proposito segnalo il bell'articolo:
Speak math, not code, basato su un intervento di Leslie Lamport alla Singapore Management University (SMU), 14 gennaio 2020.
(https://phys.org/news/2020-03-math-code.html)