Last active
September 12, 2021 12:14
-
-
Save silicakes/d397290e3dd5a30aa15ba63d25a16d63 to your computer and use it in GitHub Desktop.
Dedupe consecutive sequences from an array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
This removes consecutive sequences from an array of characters. | |
See examples below + a working example @ https://jsfiddle.net/63v4pbq7/5/ | |
*/ | |
dedupeSequence = (seq) => { | |
let sequences = []; | |
// The longest sequence can be exacly half of the values | |
const maxLength = Math.floor(seq.length / 2); | |
const stringSequence = seq.join(""); | |
for (let i = 0; i < maxLength; i++) { | |
for (let j = i + 1; j < seq.length - i; j++) { | |
// A sequence is a consecutive pattern repeated after the first | |
const firstHalf = stringSequence.slice(i, j); | |
const secondHalf = stringSequence.slice(j, (j * 2) - i); | |
if (firstHalf === secondHalf) { | |
sequences.push(firstHalf); | |
//console.log("sequence found", firstHalf) | |
} | |
} | |
} | |
// We want to remove the longest sequence first, | |
// in order to avoid a small sequence to be removed from a big one | |
// i.e BE removed from BEBEBE | |
const sortedSequences = sequences.sort((a, b) => b.length - a.length); | |
if (sortedSequences.length) { | |
// With this solution, we need to rebuild the sequences - | |
//for each update of the original sequence. | |
const [longestSequence] = sortedSequences | |
return dedupeSequence(stringSequence.replace(longestSequence, "").split("")); | |
} else { | |
return seq; | |
} | |
} | |
// Examples: | |
const arr = ["A", "B", "E", "B", "E", "B", "E", "B", "E", "D", "E", "D", "E", "B", "E", "D"] | |
const arr2 = ["A", "B", "E", "B", "E", "B", "E", "B", "E", "D", "E", "D", "B", "E", "D"] | |
console.log(dedupeSequence(arr)) // ["A", "B", "E","D","E","B","E","D"] | |
console.log(dedupeSequence(arr2)) // ["A", "B", "E","D"] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment