I wanted to know weather we can calculate the move order such that if the order of the element is played out sequentially we get the current position on board.

example:

we know the coordinates of the coins from this picture, :

• row 1 col 3 = yellow
• row 1 col 4 = red
• row 1 col 5 = yellow
• row 2 col 3 = red
• row 2 col 5 = red
• row 3 col 5 = yellow

in this scenario, the move order (columns) played was : 4, 3, 3, 5, 5, 5 (red and yellow alternates, the numbers represent which columns the coin was dropped, i.e., the first coin(red) was dropped on the 4th row, second coin(yellow) was dropped on 3rd row, third coin(red) was dropped again on 3rd row... )

I wanted to know weather we can reconstruct the move order from the position matrix (the move order need not be the exact order played, but if we were to simulate, the resulting position matrix should be the same)

I tried separating the red moves and yellow moves and created the list of position for both sets starting from the bottom layer

 # (y,x cordinates ) based on image

 red  = [ (1,4), (2,3), (2,5) ] 
 yellow = [ (1,3), (1,5), (3,5) ] 

# resulting sequences

red = [4,3,5]
yellow = [3,5,5]

interlaced = [4,3,3,5,5,5]

#sequence : 433555 - wrong, doesn't generate the same position

and I tried interlacing the column value from these list, but it doesn't seem to work as it messes up the 2nd red as it assumes a yellow has already been placed there instead of the 3rd column that was played first.

is there any way to generate a sequence of alternating moves as I mentioned above, if simulated, get the same matrix of game position?

CodePudding user response：

You could:

• Loop over the moves:
  • note that a "move" is a column to drop the next token
  • tracking the number of tokens already dropped per column
  • tracking whose move it is, alternating red or yellow
  • check if the position to drop the token corresponds to one of the positions of the current player

Like this:

MAX_COLUMNS = 10

def are_valid_moves(red: Tuple[int, int], yellow: Tuple[int, int], moves: List[int]) -> bool:
    """
    :param red: 1-based (y, x) positions of red
    :param yellow: 1-based (y, x) positions  of yellow
    :param moves: columns of the moves
    :return: will the sequence of moves produce the red and yellow positions
    """
    red_set = set(red)
    yellow_set = set(yellow)
    tokens_per_column = [0] * MAX_COLUMNS

    current_is_red = True
    for column in moves:
        row = tokens_per_column[column]   1
        tokens_per_column[column] = row
        if current_is_red:
            if (row, column) not in red_set:
                return False
        else:
            if (row, column) not in yellow_set:
                return False

        current_is_red = not current_is_red

    return True


red = [(1, 4), (2, 3), (2, 5)]
yellow = [(1, 3), (1, 5), (3, 5)]

assert are_valid_moves(red, yellow, [4, 3, 3, 5, 5, 5]) is True
assert are_valid_moves(red, yellow, [4, 3, 5, 3, 5, 5]) is False

CodePudding user response：

I would suggest turning the data structure into stacks -- one stack per column. These stacks contain values 0 or 1, where 0 is a disc of the first player (red in your case), and 1 is a disc of the second player. So for your example board, those stacks could look like this:

[
    [],        # first column is empty
    [],        # second column is empty
    [1, 0],    # yellow, red
    [0],       # red
    [1, 0, 1], # yellow, red, yellow
    [],
    [],
]

Once you have that, you could use a recursive backtracking algorithm that tries to find a path of "take-back" moves, popping discs from the above-mentioned stacks with alternating colors, until all stacks are empty. Once that state is found the series of moves is known and can be returned.

Here is an implementation of both the conversion to stacks and of the backtracking algorithm:

def getstacks(player1, player2):
    if not (0 <= len(player1) - len(player2) <= 1):
        raise ValueError("Number of discs per player is inconsistent")
    # Convert data structure to stacks -- one stack per column
    stacks = [[] for _ in range(7)]
    for player, coordinates in enumerate([player1, player2]):
        for row, col in coordinates:
            if not (1 <= col <= 7) or not (1 <= row <= 6):
                raise ValueError(f"Cel {row},{col} is out of range")
            stack = stacks[col - 1]
            while len(stack) < row:
                stack.append(None)
            if stack[row - 1] is not None:
                raise ValueError(f"Cell {row},{col} is occupied twice")
            stack[row - 1] = player
    # Verify there are no holes
    for col, stack in enumerate(stacks):
        if None in stack:
            raise ValueError(f"Cell {stack.index(None) 1},{col 1} should be occupied")
    return stacks


def searchmoves(stacks, player):
    # Perform a depth first search with backtracking
    for col, stack in enumerate(stacks):
        if stack and stack[-1] == player:
            stack.pop()
            moves = searchmoves(stacks, 1 - player)
            stack.append(player)  # Restore
            if moves is not None:  # Success
                moves.append(col   1)
                return moves
    if any(stacks):
        return None  # Stuck: backtrack.
    return []  # Success: all discs were removed


def solve(player1, player2):
    return searchmoves(getstacks(player1, player2), len(player1) == len(player2))

You can run it as follows:

red  = [ (1,4), (2,3), (2,5) ]
yellow = [ (1,3), (1,5), (3,5) ]
print(solve(red, yellow))  # [4, 5, 5, 3, 3, 5]

CodePudding user response：

(y,x cordinates ) based on image

red = [ (1,4), (2,3), (2,5) ] yellow = [ (1,3), (1,5), (3,5) ]

resulting sequences

red = [4,3,5] yellow = [3,5,5]

interlaced = [4,3,3,5,5,5]

#sequence : 433555 - wrong, doesn't generate the same position