[Teoria] Tartaruga e lepre con crazy-list

[3m0o]

Homer Simpson non è esattamente conosciuto per essere l'Einstein di Springfield. Per nostra sfortuna Homer ha deciso di progettare una struttura dati con un linked-list, che chiameremo carzy-list. Una crazy-list è una single-linked list con la seguente importante differenza: l'ultimo puntatore punta ad un elemento precedente della lista invece di essere NIL.
Progetta e a analizza un algoritmo che prende come input una crazy-list (i.e. un puntatore L.head) e come output restituisce il numero \(n\) di elementi presenti nella lista.
Il tuo algoritmo non può modificare l'input, e deve avere un run time \( O(n) \) e una quantità costante di spazio extra nella memoria (senza contare la memoria per storare la lista).

Hint: usa la tecnica della tartaruga e della lepre per rilevare il ciclo ed inseguito calcola la lunghezza del ciclo dopodiché calcola la lunghezza della lista.


Primo: Cos'è la tecnica della tartaruga e della lepre?
Secondo: non ho idea di come trovare il ciclo.

[ghira]

https://en.m.wikipedia.org/wiki/Cycle_detection

[apatriarca]

La tecnica della tartaruga e della lepre consiste nell'iterare lungo la lista a due velocità. Il primo puntatore avanza di un solo elemento per volta, mentre il secondo ne salta uno (quindi avanza di due). Quando il primo puntatore avrà visitato \(N\) nodi, il secondo ne avrà visitati \(2\,N\).

Supponiamo che il ciclo inizi dopo \(K\) elementi. Quando la tartaruga sarà arrivata all'inizio del ciclo, la lepre sarà \(K \mod C\) elementi all'interno del ciclo di lunghezza \(C\). Dopo \(i\) iterazioni la tartaruga sarà nel nodo \(i \bmod C\) del ciclo e la lepre nel nodo \((K + 2\,i) \bmod C\). I due puntatori si incontreranno quindi quando la loro differenza è un multiplo di \(C\) per cui abbiamo \(K + 2\,i - i = K + i = s\,C\). I due puntatori si incontrano quindi a \(K\) nodi dall'inizio del ciclo.

L'idea è quindi la seguente:
1. Usare la tecnica sopra descritta fermandosi quando i due puntatori puntano allo stesso nodo.
2. Calcolare \(K\) iterando con un nuovo puntatore dell'inizio della lista e con l'altro a partire da dove i due puntatori si erano incontrati. Siccome entrambi i puntatori sono a \(K\) nodi dall'inizio del ciclo si incontreranno proprio in questo inizio.
3. A questo punto non rimane che calcolare \(C\) iterando sul ciclo fino a tornare al nodo iniziale (non mi sembra sia possibile calcolarlo direttamente da quello che abbiamo scritto perché conosciamo solo \(s\,C\) e quindi qualsiasi divisore del numero potrebbe andare bene.

[3m0o]

Allora scrivere questo, forse sbaglio il modo di scrivere

Faccio due puntatori, uno lo inizializzo \(p1\) alla testa della Lista (che è un puntatore che punta al primo elemento della lista se ho capito bene), l'altro \(p2\) al primo elemento della lista. Poi faccio andare \(p1\) un elemento alla volta e \(p2\) lo faccio andare due elementi alla volta. Ad una certa si incontrano (penso necessariamente all'interno del ciclo). Poi così ora faccio un contatore che parte da uno gli faccio fare un ulteriore salto (di uno e di due rispettivamente) poi faccio un nuovo loop while che gli fa fare dei salti e aumenta per ogni salto di \(p1\) il contatore di 1, quando si incontreranno di nuovo avrò la lunghezza del ciclo. Poi inizializzo \(p1\) alla testa e \(p2\) esattamente ad una distanza cycle (la lunghezza del ciclo) e gli faccio andare avanti di un salto alla volta (non più uno di uno e l'altro di due) e allo stesso tempo faccio faccio partire un contatore startcycle che conta quanti elementi ci sono prima che il ciclo incomincia. Quando si incontreranno avrò la lunghezza della parole prima che il ciclo inizi (credo) e quindi poi restituisco startcycle + cycle. La complessità è lineare perché sia i for che i while alla peggio percorrono un multiplo di \(n\) (la lunghezza della lista), e la memoria è costante perché inizializzo solamente due contatori e due puntatori

CrazyList(L.head)

Codice:

create two empty pointer p1 and p2
p1 <- L.head
p2 <- L.head.next
while p1 not p2
  p1 <- p1.next
  p2 <- (p2.next).next
end while
cycle = 1
p1 <- p1.next
p2 <- (p2.next).next
while p1 not p2
  p1 <- p1.next
  p2 <- (p2.next).next
 cycle = cycle + 1
end while
p1 <- L.head
p2 <- L.head
for i = 1 to cycle
  p2 <- p2.next
end for
startcycle = 0
while p1 not p2
  p1 <- p1.next
  p2 <- p2.next
  startcycle = startcycle +1
end while
return (startcycle + cycle)


[apatriarca]

Non hai seguito esattamente quello che ti abbiamo suggerito. Credo che l'idea sia ancora più o meno corretta, ma nel secondo ciclo non è necessario che entrambi i puntatori si muovano. In effetti conviene fermare la "lepre" e far fare alla tartaruga un intero giro fino a raggiungere nuovamente la lepre.