1<<-DOC
  2You are given a single linked list, and you are asked to determine if there is a circle inside it
  3A circle means, a -> b -> c -> b, then it is a circle
  4
  5Part 2.
  6Could you get the length of the circle for the input single linked list if there is one, 
  7or output 0 if there is no circle? (O(1) space and O(n) time complexity)
  8
  9A -> B -> C -> D -> E -> F -> D
 10|T|H|
 11|A|B|
 12|B|D|
 13|C|F|
 14|D|E|
 15|E|D|
 16
 17Part 3.
 18could you find the entry point of the circle?
 19which means the point A for (a->b->c->a)
 20DOC
 21
 22describe "cycle" do
 23  def circle?(head)
 24    return false if head.nil?
 25
 26    tortoise, hare = head, head.next_item
 27
 28    until hare.nil?
 29      return true if tortoise == hare
 30      tortoise, hare = tortoise.next_item, hare.next_item&.next_item
 31    end
 32
 33    false
 34  end
 35
 36  def cycle_length(head)
 37    return 0 if head.nil?
 38
 39    tortoise, hare = head, head.next_item
 40
 41    detected = false
 42    count = 0
 43
 44    until hare.nil?
 45      if tortoise == hare
 46        return count if detected
 47        detected = true
 48      end
 49      count += 1 if detected
 50      tortoise, hare = tortoise.next_item, hare.next_item&.next_item
 51    end
 52    0
 53  end
 54
 55  def cycle_length(head)
 56    return 0 if head.nil?
 57
 58    tortoise, hare = head, head
 59    d1, d2 = 0, 0
 60
 61    while hare && tortoise
 62      break if tortoise == hare && hare != head
 63
 64      tortoise, hare = tortoise.next_item, hare.next_item&.next_item
 65      d1 += 1
 66      d2 += 2
 67    end
 68    return 0 if hare.nil?
 69
 70    d2 - d1
 71  end
 72
 73  def entry_point(head)
 74    return nil if head.nil?
 75
 76    tortoise, hare = head, head.next_item
 77
 78    until hare.nil?
 79      break if tortoise == hare
 80      tortoise, hare = tortoise.next_item, hare.next_item&.next_item
 81    end
 82
 83    tortoise = head
 84    until hare == tortoise
 85      tortoise = tortoise.next_item
 86      hare = hare.next_item
 87    end
 88    return tortoise
 89  end
 90
 91  def entry_point(head)
 92    return nil if head.nil?
 93
 94    tortoise, hare = head, head.next_item
 95
 96    until hare.nil?
 97      break if tortoise == hare
 98      tortoise, hare = tortoise.next_item, hare.next_item&.next_item
 99    end
100
101    return nil if tortoise.nil? || hare.nil?
102
103    visited = {}
104    tortoise = head
105    until hare == tortoise
106      tortoise = tortoise.next_item
107      hare = hare.next_item
108      return hare if visited[hare]
109
110      visited[hare] = true
111    end
112    return tortoise
113  end
114
115  class Node
116    attr_reader :next_item, :value
117
118    def initialize(value)
119      @value = value
120    end
121
122    def add(value)
123      @next_item = value.is_a?(Node) ? value : Node.new(value)
124    end
125
126    def inspect
127      "#{object_id} #{value}"
128    end
129  end
130
131  it do
132    a = Node.new("A")
133    b = Node.new("B")
134    c = Node.new("C")
135
136    a.add(b)
137    b.add(c)
138    c.add(b)
139    expect(circle?(a)).to be_truthy
140    expect(cycle_length(a)).to eql(2)
141  end
142
143
144  <<-DOC
145A -> B -> C -> D -> E -> F -> D
146
147|T|H|
148|A|B|
149|B|D|
150|C|F|
151|D|E|
152|E|D|
153  DOC
154
155  it do
156    a = Node.new("A")
157    b = Node.new("B")
158    c = Node.new("C")
159    d = Node.new("D")
160    e = Node.new("E")
161    f = Node.new("F")
162
163    a.add(b)
164    b.add(c)
165    c.add(d)
166    d.add(e)
167    e.add(f)
168    f.add(d)
169
170    expect(circle?(a)).to be_truthy
171    expect(cycle_length(a)).to eql(3)
172  end
173
174  it do
175    a = Node.new("A")
176    b = Node.new("B")
177
178    a.add(b)
179
180    expect(circle?(a)).to be_falsey
181    expect(cycle_length(a)).to eql(0)
182  end
183
184  it 'detects the entry point' do
185    # (a->b->c->a)
186    # a|b
187    # b|a
188    # c|c
189    a = Node.new("A")
190    b = Node.new("B")
191    c = Node.new("C")
192    a.add(b)
193    b.add(c)
194    c.add(a)
195
196    expect(entry_point(a)).to eql(a)
197  end
198
199
200  it 'detects entry point' do
201    # A -> B -> C -> D -> C is C the entry point
202    a = Node.new("A")
203    b = Node.new("B")
204    c = Node.new("C")
205    d = Node.new("D")
206    a.add(b)
207    b.add(c)
208    c.add(d)
209    d.add(c)
210
211    expect(entry_point(a)).to eql(c)
212  end
213
214  it 'finds no entry point' do
215    #(a->b->c)
216    a = Node.new("A")
217    b = Node.new("B")
218    c = Node.new("C")
219    a.add(b)
220    b.add(c)
221
222    expect(entry_point(a)).to be_nil
223  end
224end