Getting wrong answer for simple algorithm with cycle detection

user_1929678 0
Viewed 131

I am solving this problem, a part of the problem that is giving me troubles is formulated as follows:

a. Start from index i=0;

b. Jump to index i=A[i];

c. If the current index i is outside the valid bound of [0..N-1], print “Out” and stop;

d. Else if the current index i is index N-1, print “Done” and stop;

e1. Otherwise, repeat step b;

e2. If doing this leads to an infinite loop, print “Cyclic” and stop;

(all output are without the quotes)

arr is an array of non-negative integers:

let index = 0;
const seen = new Set([0]);
while (true) {
  index = arr[index];
  if (index > arr.length - 1) {
    console.log("Out");
    break;
  }
  if (index === arr.length - 1) {
    console.log("Done");
    break;
  }
  if (seen.has(index)) {
    console.log("Cyclic");
    break;
  }
  seen.add(index);
}

I am getting WA (Wrong Answer) on some hidden test cases, but I can't for the life of me come up with a failing test case.

  • 1 2 3 4 5 0 -> Done
  • 1 2 3 4 6 0 -> Out
  • 1 0 0 -> Cyclic

Edit:

My C++ solution has exactly the same failed test cases, must really be something with my logic...

cycle-detection algorithm javascript
1 Answers

I believe the issue is that the coded algorithm is not adhering to the requirement. Specifically e1 indicates to repeat step b which fetches the next value, and **if doing this** leads to an infinite loop then print "Cycle". The problem is that the code is actually doing it, rather than checking first...

So, as the current code is written, a test case of...

12344

...will return "Done" rather than "Cyclic"...

EDIT In the parlance code, this is what I'm suggesting (untested)...

let index = 0;
const seen = new Set([0]);
while (true) {
  index = arr[index];
  if (index > arr.length - 1) {
    console.log("Out");
    break;
  }
  if (index === arr.length - 1) {
    console.log("Done");
    break;
  }
  if (seen.has(index) || seen.has(arr[index])) {
    console.log("Cyclic");
    break;
  }
  seen.add(index);
}

EDIT #2 Upon getting a chance to test my previously untested code just above, I discovered that it did not capture the nuance of my point. So, in an effort to further clarify, below is the Current and Proposed algorithms, with sample cases to show the similarities and the difference.

The last case, where the cyclic entry is the final entry, is where step e2 reports "Cyclic" before step c is able to report "Done"...

Comments in the proposed() function show the steps of the algorithm...

function current( arr ) {
  let index = 0;
  const seen = new Set([0]);
  while (true) {
    index = arr[index];
    if (index > arr.length - 1) {
      console.log("Out");
      break;
    }
    if (index === arr.length - 1) {
      console.log("Done");
      break;
    }
    if (seen.has(index)) {
      console.log("Cyclic");
      break;
    }
    seen.add(index);
  }
}

function proposed( arr ) {
  // a. Start from index i=0;
  let index = 0;

  // b. Jump to index i=A[i];
  const seen = new Set( [ index ] );
  index = arr[ index ];

  while( true ) {
    // c. If the current index i is outside the valid bound of [0..N-1], print “Out” and stop;
    if ( index > arr.length - 1 ) {
      console.log( "Out" );
      break;
    }
    
    // d. Else if the current index i is index N-1, print “Done” and stop;
    if ( index === arr.length - 1 ) {
      console.log( "Done" );
      break;
    }
    
    // e1. Otherwise, repeat step b;
    seen.add( index );
    index = arr[ index ];
    
    // e2. If doing this leads to an infinite loop, print “Cyclic” and stop;
    if ( seen.has( arr[index] ) ) {
      console.log("Cyclic");
      break;
    }
  }
}

arr = [1,0,2];
console.log( arr );
current( arr );
proposed( arr );

arr = [1,2,3,4,5];
console.log( arr );
current( arr );
proposed( arr );

arr = [1,2,3,6,5];
console.log( arr );
current( arr );
proposed( arr );

arr=[1,2,3,4,0];
console.log( arr );
current( arr );
proposed( arr );

user_76961620
Related