Last Updated: 22 Oct, 2021
Dominoes Game
Moderate
Asked in company
You are playing a dominoes game with your friends in which you have ‘N’ dominoes placed vertically upright. At the start of the game, you simultaneously pushed some of the dominoes either to the left or to the right. After each second, each domino falling to the right pushes the adjacent domino on the right. Similarly, the dominoes falling to the left pushes the adjacent domino on the left. When a vertical domino has dominoes falling to it from both sides, it stays as it is due to the balance of the forces. You are given a string ‘S’ of length ‘N’, representing the states of the dominoes where ‘L’ represents a domino falling in the left direction, ‘R’ represents domino falling right direction, and ‘.’ represents domino has not been pushed initially. Print the final state of the dominoes.
Note:
A falling domino exerts no additional force to a falling domino or an already fallen domino.
For example:
Let ‘S' be: “R.L”
The second domino is pushed from both directions, therefore remains still.
So the final state becomes “R.L”.
Input Format :
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains a string ‘S’, representing the initial state of the dominoes.
Output Format :
For each test case, print a single string representing the final state of the dominoes.
Print output of each test case in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= |S| <= 10^6
S only contains {‘L’, ‘R’, ‘.’}
Time Limit: 1 sec
Approaches
For each group of non-falling dominoes, we will have two falling dominoes at the end of each group. There are four cases we need to consider:
- If we have a group “A...B”, and A == B, we should write “AAAAA”. For example: “R...R” will become “RRRRR”.
- If we have a group “L...R”, we don’t need to do anything as they are falling in opposite directions and no one exerts a force on non-falling dominoes.
- If we have a group “R...L”, we need to find the number of non-falling dominoes (‘.’) in the group. If we have an even number of ‘.’ non-falling dominoes will be divided equally. For an odd count, we need to check our distance from non-falling dominoes from the falling dominoes.
Here is the algorithm :
- Create two arrays (say, ‘IDX’ and ‘VAL’) to store the index and position of falling dominoes and initialize the first and last index as -1 and ‘N’ for array ‘IDX’ and ‘L’ and ‘R’ for array ‘VAL’ respectively.
- Create a variable (say, ‘LENGTH’) to find the number of falling dominoes.
- Run a loop from 0 to ‘N’ (say, iterator ‘i’) and store the index and position of the falling dominoes.
- Run a loop from 0 to ‘LENGTH’ - 1 (say, iterator ‘i’).
- Create two variables (say, ‘INDEX’ and ‘nextINDEX’) to store the current indexes.
- Create two variables (say, ‘X’ and ‘Y’) to store the current values.
- Check if ‘X’ is equal to ‘Y’.
- Update all the values of ‘S’ in range ‘INDEX’ to ‘nextINDEX’ to ‘X’.
- Else, check if ‘X’ is greater than ‘Y’.
- Run a loop from ‘INDEX’ + 1 to ‘nextINDEX’ (say, iterator ‘k’)
- Check if ‘k’ - ‘INDEX’ is equal to ‘nextINDEX’ - ‘k’, update all the values of ‘S’ in range ‘INDEX’ to ‘nextINDEX’ to ‘.’.
- Else, check if ‘k’ - ‘INDEX’ is smaller than ‘nextINDEX’ - ‘k’ and update all the ‘S’ values in range ‘INDEX’ to ‘nextINDEX’ to ‘R’.
- Else, update all the values of ‘S’ in range ‘INDEX’ to ‘nextINDEX’ to ‘L’.
- Run a loop from ‘INDEX’ + 1 to ‘nextINDEX’ (say, iterator ‘k’)
- Finally, return ‘S’.
The basic idea is to find the net force on each domino. Using net force, we find how close a domino is to a leftward ‘R’ and a rightward ‘L’, the closer we are, the stronger the force. We start from left to right, our force decreases by 1, and resets to ‘N’ if we meet an ‘R’ direction. Similarly, we move from right to left, we can find closeness to ‘L’.
Here is the algorithm :
- Create an array (say, ‘FORCE’) of ‘N’ size to store each domino’s forces.
- Create a variable (say, ‘TEMP’) to calculate the force at each domino and initialize it with 0.
- Run a loop from 0 to ‘N’ (say, iterator ‘i’) to find the forces.
- Check if ‘S[i]’ is equal to ‘R’, update ‘TEMP’ with ‘N’.
- Else, check if ‘S[i]’ is equal to ‘L’, update ‘TEMP’ with ‘0’.
- Else, update ‘TEMP’ with a maximum of ‘TEMP’ - 1 and 0.
- Update ‘FORCE[i]’ with the sum of ‘FORCE[i]’ and ‘TEMP’.
- Run a loop from ‘N’ - 1 to 0 (say, iterator ‘i’) to find the forces in the opposite direction.
- Check if ‘S[i]’ is equal to ‘L’, update ‘TEMP’ with ‘N’.
- Else, check if ‘S[i]’ is equal to ‘R’, update ‘TEMP’ with ‘0’.
- Else, update ‘TEMP’ with a maximum of ‘TEMP’ - 1 and 0.
- Update ‘FORCE[i]’ with the difference of ‘FORCE[i]’ and ‘TEMP’.
- Run a loop from 0 to ‘N’ (say, iterator ‘i’) update the values.
- Check if ‘FORCE[i]’ is greater than 0, update ‘S[i]’ with ‘R’.
- Else, check if ‘FORCE[i]’ is smaller than 0, update ‘S[i]’ with ‘L’.
- Else, update ‘S[i]’ with ‘.’.
- Update ‘FORCE[i]’ with the difference of ‘FORCE[i]’ and ‘TEMP’.
- Finally, return ‘S’.
Similar problems