2
\$\begingroup\$

Got this problem from Codewars.

There is a secret string which is unknown to you. Given a collection of random triplets from the string, recover the original string.

A triplet here is defined as a sequence of three letters such that each letter occurs somewhere before the next in the given string. "whi" is a triplet for the string "whatisup".

As a simplification, you may assume that no letter occurs more than once in the secret string.

You can assume nothing about the triplets given to you other than that they are valid triplets and that they contain sufficient information to deduce the original string. In particular, this means that the secret string will never contain letters that do not occur in one of the triplets given to you.

For example, given triplets [['t','u','p'], ['w','h','i'], ['t','s','u'], ['a','t','s'], ['h','a','p'], ['t','i','s'], ['w','h','s']], the code should return the string whatisup. All the context that I had to solve the problem came from the description. This is a programming challenge, not meant to solve a real life problem. My code passed the tests. There where no random tests though. My main interest is about performance.

function recoverSecret(triplets) {
    const after = {};

    const precedence = (a, b) => after[a].has(b)
        || [...after[a]].some(c => precedence(c, b) == -1) ? -1 : 1;

    for (let triplet of triplets) {
        after[triplet[0]] = new Set([...(after[triplet[0]] || []), ...triplet.slice(1)]);
        after[triplet[1]] = new Set([...(after[triplet[1]] || []), triplet[2]]);
        after[triplet[2]] = new Set([...(after[triplet[2]] || [])]);
    }

    return Object.keys(after).sort(precedence).join``;
}

Tried destructuring triplet into [a, b, c] to make it more readable, but got execution timeout. Codewars platform has a max time limit of 12000ms. Wanted to do this:

for (let [a, b, c] of triplets) {
    after[a] = new Set([...(after[a] || []), b, c]);
    after[b] = new Set([...(after[b] || []), c]);
    after[c] = new Set([...(after[c] || [])]);
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

I have mainly two things I'd like to look at:

I'm not a big of fan of the constant deconstructing and recreating of Sets in the loop, especially since this most likely has negative impact on the performance. Unfortunately because there is not direct way to add multiple values to a Set there is no functional "one line" solution. My function to do this would look like this:

const addToAfter = (key, values) => {
    const set = after[key] || (after[key] = new Set());
    values.forEach(a => set.add(a));
};

which changes the loop to

for (let triplet of triplets) {
    addToAfter(triplet[0], triplet.slice(1));
    addToAfter(triplet[1], [triplet[2]]);
    addToAfter(triplet[2], []);
}

This leads to my second point: the obvious code repetition. I don't think there is a reason not to use another loop here, which also has the "advantage", that you don't need to limit yourself to "triplets", but support arrays of any length:

for (let triplet of triplets) {
    for (let i = 0, len = triplet.length; i < len; i++) {
        addToAfter(triplet[i], triplet.slice(i + 1));  
    }
}

If performance is important, I'd even consider getting rid of the .slice call and replace it with a loop, that adds the characters directly to the Set.

In general: I'm avoiding the "modern" functional way, because it (at least in this case) leads to slightly cryptic syntax (and thus unread code) and a lot of (slow) memory reallocation and data copying.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.