You are playing a Flip Game with your friend.
You are given a string currentState that contains only '+' and '-'. You and your friend take turns to flip two consecutive "++ " into "-- ". The game ends when a person can no longer make a move, and therefore the other person will be the winner.
Return all possible states of the string currentState after one valid move. You may return the answer in any order. If there is no valid move, return an empty list [].
Example 1:
Input: currentState = "++++ " Output: [ "--++ ", "+--+ ", "++-- "]
Example 2:
Input: currentState = "+ " Output: []
Constraints:
1 <= currentState.length <= 500currentState[i] is either '+' or '-'.program main
implicit none
character(len=500) :: currentState
character(len=500), allocatable :: possibleStates(:)
integer :: i, j, k
! Example 1
currentState = "++++ "
call solveFlipGame(currentState, possibleStates)
do i = 1, size(possibleStates)
write (*, '(A)') trim(possibleStates(i))
end do
! Example 2
currentState = "+ "
call solveFlipGame(currentState, possibleStates)
if (size(possibleStates) > 0) then
write (*, '(A)') trim(possibleStates(1))
else
write (*, '(A)') "[ ]"
end if
contains
subroutine solveFlipGame(currentState, possibleStates)
implicit none
character(len=*), intent(in) :: currentState
character(len=*), allocatable, intent(out) :: possibleStates(:)
integer :: i, j, k
allocate(possibleStates(0))
! Check if we can make a move
do i = 1, len_trim(currentState)-1
if (currentState(i:i+1) == "++ ") then
! We can make a move, add it to the list of possible states
allocate(possibleStates(size(possibleStates)+1))
possibleStates(size(possibleStates)) = currentState(1:i-1) // "--" // currentState(i+3:)
end if
end do
end subroutine solveFlipGame
end program maintemp.f95:38:39:
38 | allocate(possibleStates(size(possibleStates)+1))
| 1
Error: ‘possiblestates’ must not appear in the array specification at (1) in the same ALLOCATE statement where it is itself allocated
module flip_game
implicit none
contains
function flip_game_helper(current_state) result(possible_states)
character(len=*), intent(in) :: current_state
character(len=:), allocatable :: possible_states(:)
integer :: i, j
if (current_state(1:2) == "++") then
possible_states = ["-- "]
else if (current_state(1:2) == "+-") then
possible_states = ["-+ "]
else
possible_states = []
endif
do i = 2, len(current_state) - 1
if (current_state(i:i+1) == "++") then
possible_states = [possible_states, "-- "]
else if (current_state(i:i+1) == "+-") then
possible_states = [possible_states, "-+ "]
endif
enddo
end function flip_game_helper
end module flip_game
program main
use flip_game
implicit none
character(len=500) :: current_state
character(len=:), allocatable :: possible_states(:)
current_state = "++++ "
possible_states = flip_game_helper(current_state)
write (*,*) "Possible states:"
do i = 1, size(possible_states)
write (*,*) possible_states(i)
enddo
end program main
temp.f95:24:20:
24 | possible_states = []
| 1
Error: Empty array constructor at (1) is not allowed
temp.f95:48:5:
48 | use flip_game
| 1
Fatal Error: Cannot open module file ‘flip_game.mod’ for reading at (1): No such file or directory
compilation terminated.
def generate_possible_next_moves(current_state):
result = []
for i in range(1, len(current_state)):
if current_state[i] == '+' and current_state[i - 1] == '+':
result.append(current_state[:i - 1] + '--' + current_state[i + 1:])
return result
The algorithm iterates through the currentState string starting from the second character to check for two consecutive '+' characters. When it finds a pair, it flips them to '-' and adds the resulting string to the result list. After adding the result, it flips the characters back to '+' to continue searching for more pairs.
In Python and JavaScript, the string concatenation is done using slicing and concatenation, while in C++ and Java, the strings are first modified and then restored to their original state after adding the modified result. The final output is a list of all the possible next moves after one valid flip.
#include <vector>
#include <string>
std::vector<std::string> generatePossibleNextMoves(std::string currentState) {
std::vector<std::string> result;
for (int i = 1; i < currentState.size(); ++i) {
if (currentState[i] == '+' && currentState[i - 1] == '+') {
currentState[i] = currentState[i - 1] = '-';
result.push_back(currentState);
currentState[i] = currentState[i - 1] = '+';
}
}
return result;
}
The algorithm iterates through the currentState string starting from the second character to check for two consecutive '+' characters. When it finds a pair, it flips them to '-' and adds the resulting string to the result list. After adding the result, it flips the characters back to '+' to continue searching for more pairs.
In Python and JavaScript, the string concatenation is done using slicing and concatenation, while in C++ and Java, the strings are first modified and then restored to their original state after adding the modified result. The final output is a list of all the possible next moves after one valid flip.