How to locate a specific difference between two strings in Python

user_19213267 0
Viewed 64

I have a list of strings:

['oXoXXoo', 'oXXoooo', 'oooXooo']

These are moves of a puzzle where one peg jumps over an adjacent peg. The first item in the list is the starting state and the final item is the solved board.

I am trying to display the moves needed to solve the board in the format:

[ (4, L), (1, R) ]

where peg at index [4] jumps left to get to the second board state and peg at index [1] jumps right to solve the puzzle. Basically I need to find specific differences between each list item and return a tuple list based on them. My current pseudocode idea is:

find where oXX became Xoo
    path.add((index of the o+2, L))
find where XXo became ooX
    path.add((index of the X+2, R))

I have also considered turning the strings into a list and doing something with .difference but im not sure where to go from there. Any suggests into how I can compare strings or lists in python welcome!

python
3 Answers

Something like this would probably work if I understood your problem correctly:

l = ['oXoXXoo', 'oXXoooo', 'oooXooo']
path = []
for i in range(len(l) - 1):
    before = l[i]
    after = l[i+1]
    string_length = len(before)
    for j in range(string_length):
        if before[j] != after[j] and before[j] == "o":
            # It means that the peg went LEFT! (it jumped from j+2 to j)
            path.append((j+2,"L"))
            break
        if before[j] != after[j] and before[j] == "X":
            # It means that the peg went RIGHT! (it jumped from j to j+2)
            path.append((j,"R"))
            break
        
for p in path:
    print(p)

Output:

(4,L)
(1,R)

It's sufficient to check the first elements that differ in two consecutive strings, then we can both infer if the peg went LEFT or RIGHT and the original peg position.

user_107683750

There is a considerably simpler implementation though it's based on the same observation as ИванКарамазов's answer below. Just to give some inspiration (and for my own pleasure of optimizing stuff):

states = ['oXoXXoo', 'oXXoooo', 'oooXooo']
moves = []
for i, state1 in enumerate(states[:-1]):
    state2 = states[i+1]
    pos, char = next((i,a) for i, (a,b) in enumerate(zip(state1, state2)) if a != b)
    moves.append((pos, 'R') if char == 'X' else (pos + 2, 'L'))

# result
[(4, 'L'), (1, 'R')]

Explanation

  • There are only two possible options – L or R
  • There is only one action allowed per move
  • There are only the symbols o and X

That means you only need to get

  1. the position of the first character char that's different between the two states and
  2. the value of char (o or X) in either of the states.

(i,a) for i, (a,b) in enumerate(zip(state, state2)) if a != b) is a generator that yields elements from the two states in sync plus the current index (enumerate) if the characters are different. By next we only iterate up to the first match, which makes it quite efficient.

If char is o, we know we are going from oXX to Xoo (= L), in which case we need to add 2 positions to the right to get the origin of X in the first state. If the char is X, the move was R and we just return the pos.

user_158730430

IIUC, you want a function that takes two strings, s1 and s2, and describes the move used to get from s1 to s2 - or in other words

describe_move('XXoXXoo', 'oXXXXoo') should return (0, 'R')

You could write such a function by checking for the position of ('o', 'X') and identifying the move as coming from 2 places off on either side -

def describe_move(s1, s2):
    move = list(zip(s1, s2))
    peg_final_index = move.index(('o', 'X'))
    peg_initial_index = (peg_final_index + 2) if move[peg_final_index + 2] == ('X', 'o') else (peg_final_index - 2)
    direction = 'L' if peg_initial_index > peg_final_index else 'R'
    return peg_initial_index, direction

s1 = 'oXoXXoo'
s2 = 'oXXoooo'

describe_move(s1, s2)
# (4, 'L')

describe_move(s2, 'oooXooo')
# (1, 'R')

describe_move('XXoXXoo', 'oXXXXoo')
# (0, 'R')
user_42488420
Related