Il treno circolare

[Gianfranco]

Ti trovi in ​​un treno composto da un numero imprecisato di vagoni collegati fra loro in modo da formare un cerchio (o una linea chiusa). È l'uroboro dei trasporti. Non pensare troppo ai suoi usi pratici. (Nota: l'uroboro è il serpente che si mangia la coda).
Dal vagone in cui ti trovi puoi raggiungere a piedi ciascuno dei due vagoni a cui è collegato e poiché il treno è un cerchio, se cammini abbastanza, prima o poi tornerai al punto di partenza.
Ogni vagone ha una lampadina che puoi accendere e spegnere. Ogni lampadina nel treno è inizialmente accesa o spenta a caso.

Qual è il metodo più efficiente per capire quanti vagoni ci sono nel treno?
Anche se non è il più efficiente, va bene lo stesso.

Sappi che:
a) non è permesso contrassegnare un vagone lasciando indizi o segnaposti;
b) la luce di ogni vagone è visibile solo dall'interno di quel vagone;
c) le porte si chiudono automaticamente dietro di te;
d) ci sono solo due azioni che puoi compiere: camminare da un vagone all'altro e accendere o spegnere le lampadine.

From Ben Tupper, ‘round and ‘round the railroad:
You find yourself in a train made up of some unknown number of connected train cars that join to form a circle. It’s the ouroboros of transportation. Don’t think too hard about its practical uses.
From the car you’re in, you can walk to a car on either side — and because the train is a circle, if you walk far enough eventually you’ll wind up back where you started. Each car has a single light that you can turn on and off. Each light in the train is initially set on or off at random.
What is the most efficient method for figuring out how many cars are in the train?
(Assume that you can’t mark or otherwise deface a train car, and that each car’s light is only visible from within that car. The doors automatically close behind you, too. There are only two actions you can take: turning on or off a light and walking between cars.)

Tratto da The riddler: https://fivethirtyeight.com/features/ho ... lar-train/

[Bruno]

D'emblée... potendo fare più di un giro, comincio a collezionare, passando da un vagone all'altro, una sequenza di lampadine accese (+) e spente (-) così:
+ -- +++ ---- +++++ ------ +++++++ -------- +++++++++ ---------- etc. fino a quando la ripercorro.
Vedo a quanti + o - consecutivi sono arrivato e faccio un paio di conti.

[Quelo]

Io farei così:
accendo la lampadina del vagone in cui mi trovo
parto in una direzione, ogni volta che incontro una lampadina accesa, la spengo e torno indietro al punto di partenza
quando trovo spenta la lampadina del vagone 0, significa che ho completato il giro

+++ aggiornamento +++

Così facendo, nel caso migliore, cioè quello in cui tutte le lampadine sono inizialmente spente, si fanno $2n$ passaggi di vagone
Mentre nel caso peggiore (tutte le lampadine accese all'inizio) se ne fanno $n^2+n$

Si può ottimizzare il processo radoppiando le lampadine, cioè lasciando accesa sia quella del vagone 0 che quella del vagone 1 e poi tornando indietro quando si trovano 2 lampadine accese di seguito.
Se non ho sbagliato i conti:

Caso migliore $2(n+1)$ passaggi
Caso peggiore con vagoni pari $\displaystyle \frac{n^2+4n-2}{2}$ passaggi
Caso peggiore con vagoni dispari $\displaystyle \frac{n^2+2n-3}{2}$ passaggi

[Gianfranco]

D'emblée... potendo fare più di un giro, comincio a collezionare, passando da un vagone all'altro, una sequenza di lampadine accese (+) e spente (-) così:
+ -- +++ ---- +++++ ------ +++++++ -------- +++++++++ ---------- etc. fino a quando la ripercorro.
Vedo a quanti + o - consecutivi sono arrivato e faccio un paio di conti.

Se ho capito la tua proposta...
Potresti incontrare proprio quella sequenza che hai costruito SENZA aver fatto un giro. Il giro potrebbe essere molto più lungo ma a un certo punto, per caso, potrebbe esserci proprio quella sequenza la quale potrebbe anche ripetersi migliaia di volte...

[Gianfranco]

Io farei così:
accendo la lampadina del vagone in cui mi trovo
parto in una direzione, ogni volta che incontro una lampadina accesa, la spengo e torno indietro al punto di partenza
quando trovo spenta la lampadina del vagone 0, significa che ho completato il giro

Bella soluzione, grazie Quelo!
Sono arrivato alla stessa soluzione, ma dopo un giorno di tentativi sbagliati e una notte di meditazione nel sonno.

Sulla tua ottimizzazione, devo ancora studiarla un po'.
Però mi è venuto in mente che, aumentando il numero di lampadine lasciate accese potrebbe entrare in gioco la probabilità.
Infatti, se inizialmente le lampadine sono accese o spente con probabilità 50% - 50% allora la probabilità che ce ne siano n di seguito accese diminuisce all'aumentare di n. Di conseguenza, la probabilità di aver completato il giro aumenta.

---
P.S. Con questa tecnica, alla fine tutte le lampadine sono spente.
C'è anche l'altra soluzione simile in cui alla fine le lampadine sono tutte accese.
La prima tecnica è certamente più ecologica ma un treno tutto buio fa paura!

[Bruno]

Se ho capito la tua proposta...
Potresti incontrare proprio quella sequenza che hai costruito SENZA aver fatto un giro. Il giro potrebbe essere molto più lungo ma a un certo punto, per caso, potrebbe esserci proprio quella sequenza la quale potrebbe anche ripetersi migliaia di volte...

L'ho buttata lì, Gianfranco, su due piedi, pensando di tornarci su e poi non l'ho fatto.
Comunque mi sono lasciato influenzare dalla seguente tua frase e non ho ovviamente presupposto che il treno fosse superlunghissimo

Ogni lampadina nel treno è inizialmente accesa o spenta a caso.

Be', fai finta che non abbia scritto niente.

[Gianfranco]

L'ho buttata lì, Gianfranco, su due piedi, pensando di tornarci su e poi non l'ho fatto.
...
Be', fai finta che non abbia scritto niente.

Bruno, anche a me come credo a quasi tutti, le prime strategie che sono venute in mente non focalizzavano bene sul fatto che il numero di vagoni del treno era variabile da 2 a qualunque numero, senza limiti. Ragionare su queste strategie un po' incerte è un'esperienza di apprendimento importantissima. E poi, possono sempre venir bene in altre situazioni.

Non è necessario che il treno abbia moltissimi vagoni: la strategia proposta da Quelo funziona da 2 vagoni in su.

[Bruno]

Vero, certo, ottimo.

[Alessandro B]

Propongo questa mia ottimizzazione della soluzione di Quelo:

Primo passo:
accendo la lampadina del vagone in cui mi trovo
parto in una direzione,
ogni volta che incontro una lampadina spenta, la accendo
ogni volta che incontro una lampadina accesa (dopo averne incontrate k spente):
- La spengo e spengo anche tutte le successive, fino ad arrivare alla lampadina in posizione “2k”
- Torno indietro, se incontro una lampadina spenta in posizione “x”, i vagoni saranno 2k-x
-
- Se arrivo al punto di partenza, senza incontrarne di accese, riparto in avanti
- Fino alla posizione 2k accendo tutte le lampadine che incontro
- Dalla posizione 2k+1 ripeto l’algoritmo:
(chiaramente la posizione della lampadina è sempre considerata a partire dal primo vagone)


Spero di essermi spiegato in modo sufficientemente chiaro

[Alessandro B]

Ho scritto un algoritmo in VBA per EXCEL che trova il numero di vagoni del treno
(per semplificare l'algoritmo ho utilizzato una semplificazione della soluzione da me proposta domenica scorsa)

Private Sub Treno_Click()
Dim lamp(1 To 1000) As Boolean

For riga = 2 To 1000
Cells(riga, 1) = ""
Cells(riga, 2) = ""
Next riga
riga = 2
trovato = False
lamp(1) = True 'Accendo la lampadina in posizione 1
posizione = 1
ipotesi = 1 'Ipotesi sul numero di vagoni
spente = 0 'Numero di lampadine spente
cammino = 0 'Numero di vagoni percorsi
Cells(riga, 1) = posizione
Cells(riga, 2) = cammino
Do
posizione = posizione + spente + 1
cammino = cammino + spente + 1
Do
luce = MsgBox("Luce del vagone " & posizione & " accesa?", vbYesNo, "Stato lampadina")
If luce = 6 Then MsgBox ("Spengo la lampadina")
spente = spente + 1 'Spengo la lampadina
lamp(posizione) = False
If luce = 7 Then posizione = posizione + 1: cammino = cammino + 1 'Se la lampadina era già spenta passo al vagone successivo
Loop Until luce = 6 'Procedo finche trovo una lampadina accesa
If posizione = 2 Then 'Caso in cui potrebbe esistere un solo vagone circolare
ipotesi = 1
riga = riga + 1
Cells(riga, 1) = posizione
Cells(riga, 2) = cammino
Else
ipotesi = posizione - 1 'Ipotesi sul numero di vagoni
Do
posizione = posizione + 1 'Passo al vagone successivo
luce = MsgBox("Luce del vagone " & posizione & " accesa?", vbYesNo, "Stato lampadina")
spente = spente + 1 'Spengo la lampadina
cammino = cammino + 1
lamp(posizione) = False
If luce = 6 Then
ipotesi = posizione - 1 'Se lampadina accesa formulo nuova potesi sul numero di vagoni
MsgBox ("Spengo la lampadina")
End If
Loop Until posizione = 2 * ipotesi 'Procedo fino a quando ipotizzo di aver finito il secondo giro del treno
riga = riga + 1
Cells(riga, 1) = posizione
Cells(riga, 2) = cammino
End If
cammino = cammino + posizione - 1
posizione = 1 'Torno alla posizione iniziale
riga = riga + 1
Cells(riga, 1) = posizione
Cells(riga, 2) = cammino
luce = MsgBox("Luce del vagone 1 accesa?", vbYesNo, "Stato lampadina") 'Verifico se lampadina ancora accesa
If luce = 7 Then trovato = True 'Se la lampadina è spenta, il numero di vagoni coincide con la ipotesi
Loop Until trovato 'Ripeto l'algoritmo fino a trovare la soluzione
luce = MsgBox("Il treno è composto da " & ipotesi & " vagoni", 0, "Numero vagoni")
End Sub

[Quelo]

Ciao Alessandro,
vediamo se ho capito bene il tuo metodo:
Parto in una direzione, accendo tutte le luci spente finché non ne trovo una accesa nel vagone k, quindi spengo tutti le luci fino a 2k.
Torno indietro e se nei primi k vagoni trovo una luce spenta, ho completato il giro.
Altrimenti torno nella posizione k'=2k, accendo tutte le luci spente finché non ne trovo una accesa in posizone k", quindi spengo tutte le luci fino a 2k" e torno indietro.

Ho fatto qualche simulazione e questo metodo è più rapido di quelli che avevo proposto io.
Il rapporto tra il numero medio di passaggi (da un vagone all'altro) per individuare la lunghezza del treno è quasi lineare e vale circa 5.
Se il treno ha 10 vagoni servono circa 43 passaggi, se ne ha 100 circa 490.

Per contro il mio metodo 1 segue, con buona approssimazione, questa proporzione $\displaystyle p=\frac{v^2+3v}{2}$
10 vagoni --> 65 passaggi, 100 vagoni --> 5150 passaggi

Mentre il metodo 2, con approssimazione meno buona: $\displaystyle p=\frac{v^2+9v+6}{12}$
10 vagoni --> 16 passaggi, 100 vagoni --> 909 passaggi

Il metodo 2 è buono per i treni corti mentre quello di Alessandro per i treni lunghi, ma quest'ultimo è preferibile perché quasi lineare

A questo punto mi è venuto in mente un metodo indipendente dalla configurazione iniziale delle luci:
Accendo i vagoni 1 e 2 e spengo 3 e 4, poi torno indietro
Mi fermo se trovo una luce spenta nella prima metà dei vagoni
In caso contrario accendo i vagoni 1,2,3,4 e spengo 5,6,7,8 e così via

In questo modo il numero di viaggi di andata e ritorno dipende solo dal numero dei vagoni e vale $\displaystyle m=\lfloor{\log_2{n}}\rfloor$
Il numero di passaggi si calcola come la somma di m viaggi a cui sottrarre il punto in cui si trova la prima luce spenta:
$\displaystyle p=2\left[\sum_{k=2}^{m+1}(2^k-1)\right]-(2^{m+1}-1)+n = 3\cdot2^m-2m+n-5$
10 vagoni --> 45 passaggi, 100 vagoni --> 465 passaggi

SE&O

Codice per la simulazione in Python

Codice: Seleziona tutto

from random import randint

tv = 100 # Numero massimo dei vagoni
tc = 10000 # Numero di cicli in test


m = 3

match m:
    case 1:
        for n in range(2,tv+1):
            q = 0
            for c in range(tc):
                p = 0 # numero di passaggi
                t = [randint(0,1) for _ in range(n)] # Treno con luci accese casuali
                v = 1 # Vagone corrente
                t[0] = 1 # Luce primo vagone accesa
                while t[0] == 1:
                    u = v % n # Il vagone dopo l'ultimo è il primo
                    if t[u] == 1:
                        t[u] = 0
                        p += v * 2
                    else:
                        v += 1
                q += p
            print(f'n={n}, p={round(q/tc,2)}')
    case 2:
        for n in range(2,tv+1):
            q = 0
            for c in range(tc):
                p = 0 # numero di passaggi
                t = [randint(0,1) for _ in range(n)] # Treno con luci accese casuali
                v = 1 # Vagone corrente
                t[0] = 1 # Luce primo vagone accesa
                t[1] = 1 # Luce secondo vagone accesa
                while t[0] == 1 and t[1]==1:
                    u = v % n # Il vagone dopo l'ultimo è il primo
                    w = (u+1) % n
                    if t[u] == 1 and t[w]==1:
                        t[u] = 0
                        t[w] = 0
                        p += v * 2
                    else:
                        v += 1
                q += p
            print(f'n={n}, p={round(q/tc,2)}')    
    case 3:
        for n in range(2,tv+1):
            q = 0
            for c in range(tc):
                p = 0 # numero di passaggi
                t = [randint(0,1) for _ in range(n)] # Treno con luci accese casuali
                v = 1 # Vagone corrente
                t[0] = 1 # Luce primo vagone accesa
                while True:
                    u = v % n # Il vagone dopo l'ultimo è il primo
                    if t[u] == 0:
                        t[u] = 1
                        v += 1
                    else:
                        for i in range(u,u+v):
                            j = i % n
                            t[j] = 0
                        k = sum(t[:v])
                        p += v * 4
                        if k < v:
                            break
                        else:
                            for i in range(u, u+v): t[i] = 1
                            v = v * 2
                q += p + k - n
            print(f'n={n}, p={round(q/tc,2)}')          

[Alessandro B]

Grazie Sergio per il tuo commento,
e per essere riuscito a testare con il tuo programma il mio algoritmo.

Nel mio programma in VBA che ho postato ieri, io ho testato invece una soluzione differente perché non sono riuscito a scrivere un programma corrispondente alla mia ottimizzazione della soluzione; per cui ho fatto in VBA alcune modifiche all'algoritmo di domenica scorsa (anche se il procedimento risulta molto simile ed il numero di passaggi di vagone rimane circa lo stesso).