Discussion on: Advent of code Day 2 Part 2 Complexity

[Tiago Romero Garcia]

I have been also wrapping my head around that.

I tried tinkering around with Robin-Karp algorithm but because we have to take the order into consideration, we would have to build a clever hash function that also takes the order into consideration. So we could maybe get it down to O(N).

I didn't try too hard but it also crossed my mind the same think that @aspittel said, the size input is small and hence it won't really matter to the point of getting it resolved and proceed on AoC.

But just for curiosity sake I was planning to get back at that sometime later.

I have a JS implementation of this Robin-Karp algorithm as one of the exercises from "Cracking the Code Interview, 6th Ed", here you go:

// Robin-karp substring search with rolling hash function
function substringSearch(string, substring) {
    const stringLength = string.length;
    const substringLength = substring.length;

    // Generating hashes
    const hashes = [calculateHash(string, substringLength)];
    for (let i = 1; i < stringLength - substringLength; i++) {
        hashes[i] = updateHash(string, substringLength, hashes[i-1], i-1);
    }
    const substringHash = calculateHash(substring, substringLength);

    // Comparing hashes
    for (let i = 0; i < stringLength - substringLength; i++) {
        const index = i + substringLength;
        if (hashes[i] === substringHash && compare(string, i, substring)) {
            return i;
        }
    }

    return -1;
}

function calculateHash(string, length, startIndex = 0) {
    let hash = 0;
    for (let i = startIndex, power = length-1; i < length; i++, power--) {
        hash += string.charCodeAt(i) * Math.pow(128, power);
    }
    return hash;
}

function updateHash(string, length, hash, outcomingIndex) {
    return (hash - string.charCodeAt(outcomingIndex) * Math.pow(128, length-1)) * 128 + string.charCodeAt(outcomingIndex + length);
}

function compare(string, index, substring) {
    const stringLength = string.length;
    const substringLength = substring.length;

    if (index + substringLength > stringLength) {    
        return false;
    }

    for (let i = index, j = 0; i < stringLength && j < substringLength; i++, j++) {
        if (string.charAt(i) !== substring.charAt(j)) {
            return false;
        }
    }

    return true;
}

console.log(substringSearch('doe are hearing me', 'ear'));

[Conectado]

Awesome! I will study this possibility later! I didn't know this algorithm and get back here tell how did I fare. The reason I am trying to make this < O(N²⁾ is just because it seemed interesting not for some specific requisite of the problem, I imagined that the input wasn't big enough to justify all this effort.

[Tiago Romero Garcia]

Gotcha! It’s great to challenge ourselves to see if we can go one step beyond. Please let me know if you can find out something!

One limitation that I just thought with this algorithm is that it had been originally used to search subsequent characters inside a bigger string. But in our case, any char can be different, so we might need to look at the whole substring (which happens to have the same size as every other string) and hence maybe we won’t be able to get down to O(N).

But maybe there’s a way to create a very clever hash function that would work regardless of this limitation so we don’t need to manually compare each char. But I might be overlooking this.

Thanks!