Skip to content

Instantly share code, notes, and snippets.

@amandoabreu
Last active October 18, 2018 06:39
Show Gist options
  • Save amandoabreu/0242bb23c8f2c1852d8c7657d8396c5a to your computer and use it in GitHub Desktop.
Save amandoabreu/0242bb23c8f2c1852d8c7657d8396c5a to your computer and use it in GitHub Desktop.
Finding cycles by iterating a list at different speeds until the same value is reached
const EMPTY = null;
const isEmpty = (node) => node === EMPTY;
const pair = (first, rest = EMPTY) => ({first, rest});
const list = (...elements) => {
const [first, ...rest] = elements;
return elements.length === 0
? EMPTY
: pair(first, list(...rest))
}
const forceAppend = (list1, list2) => {
if(isEmpty(list1)) {
return 'FAIL!'
}
if(isEmpty(list1.rest)) {
list1.rest = list2;
}
else {
forceAppend(list1.rest, list2);
}
}
const tortoiseAndHare = (aPair) => {
let tortoisePair = aPair,
harePair = aPair.rest;
while(true){
if(isEmpty(tortoisePair) ||
isEmpty(harePair)) {
return false;
}
if(tortoisePair.first === harePair.first){
return true;
}
harePair = harePair.rest;
if(isEmpty(harePair)) {
return false;
}
if(tortoisePair.first === harePair.first){
return true;
}
tortoisePair = tortoisePair.rest;
harePair = harePair.rest;
}
};
const aList = list(1,2,3,4,5);
console.log(aList);
console.log(tortoiseAndHare(aList));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment