Last active
October 23, 2020 12:23
-
-
Save sebinsua/3d71bd5afd41a6f09ce9046142d2bbff to your computer and use it in GitHub Desktop.
Check if triangle strings are valid (e.g. abb, abbccc, abbcccdddd, xyyzzz).
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
// Check if triangle strings are valid. | |
// | |
// e.g. | |
// | |
// Valid: abb, abbccc, abbcccdddd, xyyzzz | |
// Invalid: ab, abbbccc, abbcccddddd, abbccddd | |
function isTriangleString(str) { | |
// An empty string or a single character are valid. | |
if (str.length === 0 || str.length === 1) { | |
return true; | |
} | |
let acceptedChunkSize; | |
let currentChunkSize; | |
let previousChar; | |
for (let idx = 0; idx < str.length; idx++) { | |
const currentChar = str[idx]; | |
// For the first character we do nothing apart from | |
// setting up our expectations of the first chunk. | |
if (idx === 0) { | |
acceptedChunkSize = 1; | |
// And describing the current state. | |
previousChar = currentChar; | |
currentChunkSize = 1; | |
continue; | |
} | |
// When the current character is different from the previous | |
// character it implies that a chunk has been finished. | |
if (previousChar !== currentChar) { | |
// If the previous chunk was smaller than the accepted size it is invalid. | |
if (currentChunkSize < acceptedChunkSize) { | |
return false; | |
} | |
// Otherwise, the previous chunk was valid and so we silently | |
// move to setting up our expectations of the next chunk. | |
acceptedChunkSize++; | |
// And describing the current state. | |
previousChar = currentChar; | |
currentChunkSize = 1; | |
continue; | |
} | |
// When the current character is the same as the previous character | |
// we increment the current chunk size, and if it goes higher than | |
// the accepted chunk size bail as invalid. | |
currentChunkSize++; | |
if (currentChunkSize > acceptedChunkSize) { | |
return false; | |
} | |
} | |
// We must cover the case in which the string appears to be a | |
// triangle string so far but then completes early. | |
if (currentChunkSize < acceptedChunkSize) { | |
return false; | |
} | |
return true; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
It seems there are heuristics to check whether a string can even be a triangle string and that these would speed everything up (e.g. detect invalid lengths given the chunking increments, check first and last elements of each chunk which we should expect to be positioned in particular places, etc.)
Doing extra work in the situation in which the heuristic is not able to invalidate the string would worsen the performance, but I reckon in most situations it'd improve the performance when a string has an incorrectly sized/positioned chunk or a bad total length (which might be common).
To be more clear, there is a sequence here, and on closer inspection it seems to be a triangular number sequence. It should be possible to use the inverse of this to be more efficient at validation when there are likely to be lots of invalid strings.
CodeSandbox