game-of-bots

There are two kind of bots in the game BOT A and BOT B. Both are designed so as to move only in one direction in a 1-D array. Bot A can move towards left whereas bot B is constrained to move rightwards. Both are constrained to move only to the empty elements and one cannot jump over another bot. Now, a particular state of array can be represented with a string of A,B and # where A/B represents that BOT of kind A/B is sitting there and # represents an empty space.

For example: AA###B, 
represents an arena of length 5, where A sits at first two places, then three empty places and bot of kind B at last place.
Here, B can be atmost 3 positions leftwards and that too when both A do not move.

Input:

First line of input contains an integer which is the number of test cases, then, t lines follow where each line contains two strings initial and final. where both strings consists of A,B and # representing a particular state.
NOTE: initial and final string will be of same length

Output:

For each test case print "Yes" if it is possible to move from initial state to final state else "No". 

constraints:

1 ≤ t ≤ 1000    
1≤ \; length\; of\; string ≤ 10^6   
Total\; number\; of\; characters\; doesn't\; exceed\; 10^7

UPDATE 
The test cases for this problem have been updated and the solutions will be rejudged. You are recommended to re-submit your solutions.

SAMPLE INPUT
2
#A#B#B# A###B#B
#A#B# #B#A#

SAMPLE OUTPUT
Yes
No

Explanation

First case: A bot can move one unit leftwards and both bot B can move one unit right wards to get the desired state.
Second case: Since, no bots cannot jump over each other. final state is impossible to reach.

Source: hackerearth | Difficulty: EASY
Tags: Implementation

Mathematics

Ad-hoc


Solutions:
t_case=int(input())
while t_case!=0:
	s=input()
	s=s.split(" ",len(s))
	init = s[0]
	fina = s[1]
	fin_in = init.replace("#","")
	fin_fi = fina.replace("#","")
	stposa=[]
	stposb=[]
	fiposa=[]
	fiposb=[]
	#pdb.set_trace()
	if fin_in==fin_fi:
		for i in range(len(init)):
			if init[i]=='A':
				stposa.append(i)
			elif init[i]=='B':
				stposb.append(i)
		for i in range(len(fina)):
			if fina[i]=='A':
				fiposa.append(i)
			elif fina[i]=='B':
				fiposb.append(i)
		flag=True
		for i in range(len(stposa)):
			if stposa[i]<fiposa[i]:
				flag=False
				break
		for i in range(len(stposb)):
			if stposb[i]>fiposb[i]:
				flag=False
				break
		if flag==True:
			print("Yes")
		else:
			print("No")
	else:
		print("No")
	t_case=t_case-1    
				
		


import re

T = int(input())

for i in range(T):
	start,final = input().split()

	start_bindex = [m.start() for m in re.finditer('B', start)]
	final_bindex = [m.start() for m in re.finditer('B', final)]
	
	start_aindex = [m.start() for m in re.finditer('A', start)]
	final_aindex = [m.start() for m in re.finditer('A', final)]

	if len(start_aindex) != len(final_aindex):
		print('No')
		continue
	if len(start_bindex) != len(final_bindex):
		print('No')
		continue
	l = len(start_bindex)
	i =0
	go = False
	while( i < l ):
		if(start_bindex[i] > final_bindex[i] ):
			print('No')
			go = True
			break
		i+=1
		
	if go :
		continue
	l = len(start_aindex)
	i =0
	go = False
	while( i < l ):
		if(start_aindex[i] < final_aindex[i] ):
			print('No')
			go = True
			break
		i+=1

	if go :
		continue
	
	if start.find('BA') > 0 and final.find('BA') < 0:
		print('No')
	elif start.replace('#','') == final.replace('#','') :
		print('Yes')
	else:
		print('No')


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

T = int(input())

for i in range(T):
	inp = input()
	[ini, final] = inp.split()
	if not len(ini)==len(final):
		print("No")
	else:
		j = 0
		k = 0
		flag2 = True
		for ch in ini:
			if ch=='A':
				flag = False
				while j<len(final):
					if final[j]=='A' and k>=j:
						flag = True
						j += 1
						break
					elif final[j]=="#":
						pass
					else:
						break
					j += 1
				if not flag:
					print("No")
					flag2 = False
					break
			if ch=='B':
				flag = False
				while j<len(final):
					if final[j]=='B' and k<=j:
						flag = True
						j += 1
						break
					elif final[j]=="#":
						pass
					else:
						break
					j += 1
				if not flag:
					print("No")
					flag2 = False
					break	
			k += 1
		if flag2:
			print("Yes")


t = int(input())
ans = []
for i in range(t):
	line = input().split(" ")
	if line[1].index("B") < line[0].index("B"):
		ans.append("No")
		continue
	if line[0].index("A") < line[1].index("A"):
		ans.append("No")
		continue
	first, second = ''.join(line[0].split("#")), ''.join(line[1].split("#"))
	if first == second:
		ans.append("Yes")
	else:
		ans.append("No")

for a in ans:
	print(a)


import sys
testCase = int(input())

def findOccurences(s, ch):
	return [i for i, letter in enumerate(s) if letter == ch]

while (testCase>0):
	try:
		line = input()
	except KeyboardInterrupt:
		break

	if not line:
		break
	else:
		temp = line.split(" ")
		orig1 = temp[0]
		orig2 = temp[1]
		temp[0]=temp[0].replace("#","")
		temp[1] = temp[1].replace("#","")
		if temp[0]==temp[1]:
			listA1 = findOccurences(orig1, "A")
			listA2 = findOccurences(orig2, "A")
			listB = findOccurences(orig1, "B")
			listB2 = findOccurences(orig2, "B")
			flag =1
			for index in range(len(listA1)):
				if listA1[index]<listA2[index]:
					flag=0
			for index in range(len(listB)):
				if listB2[index]<listB[index]:
					flag =0
			if flag ==0:
				print("No")
			else:
				print("Yes")
		else:
			print("No")
	testCase-=1



t=eval(input())
for j in range(t):
	a=0
	b=0
	s=input()
	l=s.split()
	s1=l[0]
	s2=l[1]
	for i in range(len(s1)):
		if s1[i]=='#' and s2[i]=='#':
			continue
		elif s1[i]=='A' and s2[i]=='A':
			if b!=0 :
				print("No")
				break
			else:
				continue
		elif s1[i]=='B' and s2[i]=='B':
			if a!=0 :
				print("No")
				break
			else:
				continue
		elif s1[i]=='#' and s2[i]=='A':
			if b!=0 :
				print("No")
				break
			else:
				a=a+1
				continue
		elif s1[i]=='B' and s2[i]=='#':
			if a!=0 :
				print("No")
				break
			else:
				b=b+1
				continue
		elif s1[i]=='A' and s2[i]=='#':
			if a!=0:
				a=a-1
				continue
			else:
				print("No")
				break
		elif s1[i]=='#' and s2[i]=='B':
			if b!=0:
				b=b-1
				continue
			else:
				print("No")
				break
		else:
			print("No")
			break
	else:
		print("Yes")





import re

T = int(input())

for i in range(T):
	start,final = input().split()

	start_bindex = [m.start() for m in re.finditer('B', start)]
	final_bindex = [m.start() for m in re.finditer('B', final)]
	
	start_aindex = [m.start() for m in re.finditer('A', start)]
	final_aindex = [m.start() for m in re.finditer('A', final)]

	if len(start_aindex) != len(final_aindex):
		print('No')
		continue
	if len(start_bindex) != len(final_bindex):
		print('No')
		continue
	l = len(start_bindex)
	i =0
	go = False
	while( i < l ):
		if(start_bindex[i] > final_bindex[i] ):
			print('No')
			go = True
			break
		i+=1
		
	if go :
		continue
	l = len(start_aindex)
	i =0
	go = False
	while( i < l ):
		if(start_aindex[i] < final_aindex[i] ):
			print('No')
			go = True
			break
		i+=1

	if go :
		continue
	
	if start.find('BA') > 0 and final.find('BA') < 0:
		print('No')
	elif start.replace('#','') == final.replace('#','') :
		print('Yes')
	else:
		print('No')