I got this code challenge:
You are living in a neighborhood with a lot of potholes. Given a string
strconsisting 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 <= 1e5Example
Input
2 ?01??? PP12Output
4 0
I got this question one of my OT 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?
CodePudding user response：
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.
CodePudding user response：
The general technique that you should remember is:
The set of valid strings is a regular language
You can therefore make a DFA that accepts it.
For each position in the string, starting at the beginning, you can calculate how many ways there are to get into each state.
The answer is the sum of ways to get into accepting states at the end.
This technique works for a lot of "how many strings" problems.
In this case, the DFA is very simple, and needs only 4 states, which depend only on the character that got into the state. Lets call them
- S - the start of the string. No characters yet processed
- F - where a pothole is forced to appear because of a preceding 1 or 2
- N - where a pothole cannot appear
- P - following a pothole
The transitions are:
S: 0 -> N, 1 -> F, P -> P
F: P -> P
N: 0 -> N, 1 -> F
P: 1 -> N, 2 -> F, P -> P
Lets say that a tuple (s,f,n,p) gives how many ways you can get into each state at any position. At the start of the string, you must be in S, and you have (1,0,0,0)
To get the counts for the next position you have to process the next character. Starting with (s,f,n,p), each character produces the following counts:
0 -> (0, 0, s n, 0)
1 -> (0, s n, p, 0)
2 -> (0, p, 0, 0)
P -> (0, 0, 0, s f p)
? -> (0, s n, s n p, s f p) // sum of the above
All the states in the DFA are accepting, so after performing this transformation for each character, just add up the numbers in the tuple to get your answer.