Incroci su un cammino

[miuemia]

Ciao a tutti,
ho il seguente esercizio da proporvi.
Sia dato un array di lunghezza $n$ contenente interi positivi. Tali numeri positivi indicano i passi che si compiono nelle 4 direzioni:nord, est,sud,ovest (sempre in questo ordine).
Quindi ad esempio se l'array è $[3,12,4,6,10,4,5,8]$ vuol dire che si compiono 3 passi a nord,12 ad est,4 a sud, 6 ad ovest, 10 a nord, 4 a est, 5 a sud, 8 a ovest.

L'esercizio è scrivere un codice (qualsiasi linguaggio, c++, python,ecc.) che permetta di capire quando ci sono incroci nel cammino. Ad esempio se l'array è quello di prima vi sta un incrocio.

Suggerimenti, idee?

[Raptorista1]

"miuemia":Suggerimenti, idee?

Comincia tu!

[miuemia]

io avevo pensato a questo:

function path(A) {
for (i=3;i if (A[i-1] <= A[i-3] && (A >= A[i-2] || A[i-1] >= A[i-3]-(A[i-5] || 0) && A >= A[i-2]-A[i-4] && A[i-2] >= A[i-4]))
return i
}
return -1
}

dove $A$ è l'array.

[Raptorista1]

Magari messo nell'ambiente per il codice, magari commentato, magari spiegando anche quale sia l'idea dell'algoritmo...

[Super Squirrel]

... Ad esempio se l'array è quello di prima vi sta un incrocio.

Io ne conto 2

Una domanda, per incroci si intendono intersezioni tra tratti orizzontali e verticali? In caso di risposta negativa sorgono altri dubbi:
- come deve essere trattato il caso in cui una parte del cammino viene percorsa nuovamente?
- il passaggio per un vertice (punto in cui è avvenuto un cambio di direzione) o per l'origine vale come incrocio?

Anche io pensavo ad un metodo prettamente logico che tenga conto degli spostamenti orizzontali e verticali, ma mi sembra abbastanza complicato e dovrei perderci un po' di tempo.
In ogni caso così su due piedi l'unica cosa che mi viene in mente è quella di immaginare il punto di partenza come origine di un piano cartesiano e di memorizzare le coordinate dei punti corrispondenti ad ogni singolo passo. Quindi ogni volta che uno dei suddetti punti viene riattraversato si avrà un'incrocio.

[Cronovirus]

Ci sono una infinità di modi in cui puoi risolvere l'esercizio. La prima cosa che mi viene in mente è che, in assenza di particolari requisiti sulla complessità di tempo e spazio, puoi semplicemente simulare il cammino passo per passo su una matrice (da dimensionare, anche in maniera dinamica magari) composta da tutti zeri e tenendo traccia ogni volta della casella visitata (la imposti a uno). Chiaramente nel momento in cui arrivi in una casella in cui è già presente un uno allora passeresti due volte per la stessa casella.

[vict85]

Ma devi determinare quanti sono gli incroci o se ci sono incroci?

[Cronovirus]

Il mio algoritmo ti consente pure di contare quanti incroci ci sono se ci pensi un momento. Quando passi due volte per la stessa "casella" (o "punto", o chiamalo come vuoi) allora nella matrice ci sarà un 2. Se passi 3 volte ci sarà un 3 e così via (quindi utilizzando un contatore che viene incrementato ogni volta che passi per una casella). Una volta conclusa la simulazione sottrai un uno a tutti gli elementi non zero della matrice e fai la somma di tutti gli elementi della matrice e così avrai il numero di incroci.