How can I check two "pointers" meet each other when going through a list?

Question

For example, I have a list [1; 2; 1; 3; 2; 4; 1; 5; 6; 8;...]. The list has duplicate elements.

Then we go through the list by two virtual pointers.

One pointer a goes from the beginning and has speed of 2.

The other pointer b goes from somewhere in the middle of list and has speed of 1.

So how can I check whether a meeting with b?

For example:

a starts from [1; 2; 1; 3; 2; 4; 1; 5; 6; 8;...]

b starts from index 1, which is [2; 1; 3; 2; 4; 1; 5; 6; 8;...]

So after one time move, both a and b will arrive at index 2 and they meet.

How can I check whether meet or not by the element only, without info of index?

We can just compare the value of the two elements, as there might be duplicates inside.

In term of code:

let l = [1; 2; 1; 3; 2; 4; 1; 5; 6; 8;...]

let find_middle_start l n = 
  let rec aux i = function
    | [] -> []
    | _::tl when i >= n -> tl
    | _::tl -> aux (i+1) tl
  in
  aux 0 l

let parallel_travel l =
  Random.self_init();
  let b_start = find_middle_start l (Random.int (List.length l)) in
  let rec go = function
    | [], _::_ | _::_, [] | _::[], _::_ -> print_endline "Never meet"
    | x::x1::xs, y::ys ->
      if check_meet x y then print_endline "Meet"
      else go xs ys
  in
  go l b_start

How can I implement check_meet? i can't just do x == y right?

score 3 · Accepted Answer · answered Mar 18 '15 at 12:23

3

Bind the lists, and compare them by identity (with ==).

| ((_::_::xs) as a)), ((_::ys) as b) ->
  if a == b then ...
  else ...

Note that if you are trying to determine whether a list shares a tail with another list, this method is not sufficient (the slow pointer can reach the end before the fast pointer catches up with it).

answered Mar 18 '15 at 12:23

gsg

9,167
1
21
23

But can `==` be trusted? Does it just compare the pysical address? or all values inside? – Jackson Tale Mar 18 '15 at 14:35
For immutable types its meaning is implementation dependent. So it's not strictly usable here in my opinion. – Jeffrey Scofield Mar 18 '15 at 15:02
I admit this is a bit lax, but there is no real alternative (other than the somewhat unsatisfying position of "you should not do that"). – gsg Mar 18 '15 at 15:39
@JeffreyScofield could you please explain a bit more? – Jackson Tale Mar 18 '15 at 21:59
You can read my take on physical equality here: http://stackoverflow.com/questions/13590307/whats-the-difference-between-equal-and-identical-in-ocaml/13590433?s=14%7C0.2034#13590433 – Jeffrey Scofield Mar 18 '15 at 22:08
@JeffreyScofield from your answer in that post, it seems you were saying that even if I know the two lists are the same thing, `==` may give wrong answer as OCaml might move or split around? I got a bit confused. In my question here and this answer, `a` and `b` are def from the same list, and you say `a==b` may not be trusted? – Jackson Tale Mar 24 '15 at 20:55
Strictly speaking (according to the definitions in `Pervasives`) you can't depend on pure OCaml values having an identity at all. So you can't depend on `==` giving any particular answer. All you know is that if `a == b` then `a = b`. (Thus it would be perfectly correct to return false always for pure values.) In practice, currently you can use `==` to test identity. It seems wrong to depend on it, at least to me. – Jeffrey Scofield Mar 24 '15 at 22:49

How can I check two "pointers" meet each other when going through a list?

1 Answers1

Linked