Search code examples
stringalgorithmlanguage-agnostic

find number of valid potholes string

I got this code challenge:

You are living in a neighborhood with a lot of potholes. Given a string str consisting of:

  • 'P' - denoting a pothole.
  • '0' - denoting there is no pothole here, and neither at (i-1)st and (i+1)st positions.
  • '1' - denoting there is no pothole here, and 1 pothole at either (i-1)st and (i+1)st position.
  • '2' - denoting there is no pothole here, and 2 potholes at both (i-1)st and (i+1)st position.
  • '?' - denoting that we don't know what is there. It could be '0', '1', '2' or 'P'.

Report the number of possible strings that can be made. In case the given input has conflicting information, report 0.

Use modulo for reporting the answer.

The input has the number of tests T on the first line. Each of the T next lines will have an input string.

Constraints

1 <= T <= 100
1 <= str <= 1e5

Example

Input

2
?01???
PP12

Output

4
0

I got this question in an online test and I feel I almost reached the solution, but I'm unable to implement it even after spending lot of time on it. What would be the algorithm for this?

Solution

  • This can be solved by sweeping through the characters from left to right and apply the effect of "0", "1" and "2" to question marks that follow them. At the same time detect inconsistencies (like "0" followed by "P", or "2" followed by "0", ...).

    The effect can be either that the question mark must resolve to a "P", or to the absence of a pothole. For encoding that "absence" we should use one of the characters "0", "1" or "2", and when the whole string is resolved, the one to use depends directly on the number of "P"-neighbors this position has. In the below algorithm I have opted to use a new character "_" for denoting "no pothole", knowing that in reality it would be either a "0", "1" or "2" (no free choice). But it doesn't matter as we are not asked to return the valid strings, only their count.

    Then the idea is to perform the same process in the opposite direction -- sweeping from right to left. In that second sweep keep a count of the number of unresolved question marks: these can apparently be both (a "P" or "_"). But special care is needed for chains of alternating "1" and "?". For instance, if the input is "?1?1?1?", we can make the first "?" a "P", but that will determine all the other "?" (they are no longer free). So this input has only 2 solutions, depending on how just one of the "?" is resolved to either "P" or "_". In short, the question marks followed by a "1" should not be counted as "free" choices.

    The remaining free choices each represent a binary choice, therefore the total number of possibilities is 2 raised to the power of the count of free "?".

    Here is an implementation of the above idea in plain JavaScript:

    function countSolutions(s) {
    // Helper function to resolve a "?" to either "P" or "_"
    function set(list, i, ch) {
        if (list[i] == "?") list[i] = ch; // Resolve "?"
        return (list[i] == "P") == (ch == "P"); // Is false when there is a contradiction
    }
    
    // Main algorithm for a single sweep from left to right
    function sweep(list) {
        let count = 0;
        for (let i = 2; i < list.length; i++) {
            switch (list[i-1]) {
            case "0":
                if (!set(list, i, "_")) return 0; // Contradiction
                break;
            case "2":
                if (!set(list, i, "P")) return 0; // Contradiction
                break;
            case "1":
                switch (list[i-2]) {
                case "?": 
                    count--; // Undo. Take into account the chain-effect
                    break;
                case "P":
                    if (!set(list, i, "_")) return 0; // Contradiction
                    break;
                default: // "0", "1", or "_"
                    if (!set(list, i, "P")) return 0; // Contradiction
                    break;
                }
                break;
            case "?":
                count++;
            }                
        }
        return 1 << count;
    }

    // Convert character string to array of characters (so it is mutable)
    //    To ease the process, add two extra characters (denoting no pitholes)
    let list = Array.from("_" + s + "_");
    // Perform two sweeps in opposite directions. If the first returns 0
    //    then don't bother with the second sweep as there is no solution.
    return sweep(list) && sweep(list.reverse());
}

// Execute the algorithm for the two test cases given in the question
const tests = [
    "?01???",
    "PP12"
]

for (const test of tests) {
    // Output both the test and the result for it
    console.log(test, countSolutions(test));
}

    Notes:

    • Your question mentioned "modulo", but didn't provide which modulo to use. I suppose you'll have no difficulty to apply that yourself.
    • The code challenge specifies an input/output format. Again, I suppose you'll not have any difficulty with first reading the tests into variables and then applying the algorithm on those, and produce the output.