a-conversion-2

Again a simple task from Oz! He has given you two strings STR1 and STR2. Each character of both strings is from the set {A, B, C, D, E, F, G, H, I, J}. You can perform 3 types of conversions on string STR1 :
Replace a character(except 'J') by next character from the set.
   i.e "ABE" to "ACE" 
Replace a character(except 'A') by previous  character from the
   set. i.e "ABE" to "ABD" 
Swap any two    characters. i.e "ABE" to "EBA"

Now you have to convert STR1 into STR2 using minimum number of conversions. Output the minimum number of conversions required.

Input:
First line of the input contains a single integer T  denoting the number of test cases.
Each test case consist of two lines. First line contains STR1 and second line contains STR2.

Output:
For each test case, output minimum number of conversions required.

Constraints:
1 ≤ T ≤ 10
1 ≤ |STR1| ≤ 8
|STR1| = |STR2|

SAMPLE INPUT
1
BC
DA

SAMPLE OUTPUT
3

Explanation

Following are 3 conversion steps :
- first swap 'B' and 'C' so STR1 becomes "CB"
- Replace 'C' by next character 'D' so STR1 becomes "DB"
- Replace 'B' by previous character 'A' so STR1 becomes "DA"
we can not convert STR1 into STR2 in fewer than 3 steps.

Source: hackerearth | Difficulty: EASY
Tags: Graph traversal

Complete search


Solutions:
import sys

def minoper(str1, str2):
	l = len(str1)
	# print str1, str2
	if l == 1:
		return abs(ord(str1[0]) - ord(str2[0]))
	minnum = sys.maxsize
	minnum = min(minnum, minoper(str1[1:], str2[1:]) + abs(ord(str1[0]) - ord(str2[0])))
	# print minnum
	for i in range(1, l):
		str11 = list(str1)
		str22 = list(str2)
		str22[0], str22[i] = str22[i], str22[0]
		minnum = min(minnum, 1 + minoper(str11[1:], str22[1:]) + abs(ord(str11[0]) - ord(str22[0])))
	return minnum
	
for i in range(int(input())):
	s = input()
	str1 = [c for c in s]
	s = input()
	str2 = [c for c in s]
	print(minoper(str1, str2))


import sys

def minoper(str1, str2):
	l = len(str1)
	# print str1, str2
	if l == 1:
		return abs(ord(str1[0]) - ord(str2[0]))
	minnum = sys.maxsize
	minnum = min(minnum, minoper(str1[1:], str2[1:]) + abs(ord(str1[0]) - ord(str2[0])))
	# print minnum
	for i in range(1, l):
		str11 = list(str1)
		str22 = list(str2)
		str22[0], str22[i] = str22[i], str22[0]
		minnum = min(minnum, 1 + minoper(str11[1:], str22[1:]) + abs(ord(str11[0]) - ord(str22[0])))
	return minnum
	
for i in range(int(input())):
	s = input()
	str1 = [c for c in s]
	s = input()
	str2 = [c for c in s]
	print(minoper(str1, str2))


T = int(input())

while T > 0:
	str1 = input().replace("\n","")
	str2 = input().replace("\n","")

	Q = []
	Q.append([str1,0])
	Cnt = 9999999999
	Min = 9999999999
	while len(Q) != 0:
		str1 = Q[0][0]
		Temp = Q[0][1]

		for i in range(len(str1)): Temp += abs(ord(str1[i]) - ord(str2[i]))
		Cnt = min(Min, Temp)
		for i in range(len(str1)):
			for j in range(i+1,len(str1)):
				New_Str = str1[:i] + str1[j:j+1] + str1[i+1:j] + str1[i:i+1] + str1[j+1:]
				Temp = Q[0][1] + 1
				for k in range(len(New_Str)): Temp += abs(ord(New_Str[k]) - ord(str2[k]))
				if Temp <= Cnt:
					Min = min(Min, Temp)
					Q.append([New_Str, Q[0][1] + 1])
		Cnt = min(Min, Cnt)
		del Q[0]
	print(Cnt)
	T -= 1


T = int(input())

while T > 0:
	str1 = input().replace("\n","")
	str2 = input().replace("\n","")

	Q = []
	Q.append([str1,0])
	Cnt = 9999999999
	Min = 9999999999
	while len(Q) != 0:
		str1 = Q[0][0]
		Temp = Q[0][1]

		for i in range(len(str1)): Temp += abs(ord(str1[i]) - ord(str2[i]))
		Cnt = min(Min, Temp)
		for i in range(len(str1)):
			for j in range(i+1,len(str1)):
				New_Str = str1[:i] + str1[j:j+1] + str1[i+1:j] + str1[i:i+1] + str1[j+1:]
				Temp = Q[0][1] + 1
				for k in range(len(New_Str)): Temp += abs(ord(New_Str[k]) - ord(str2[k]))
				if Temp <= Cnt:
					Min = min(Min, Temp)
					Q.append([New_Str, Q[0][1] + 1])
		Cnt = min(Min, Cnt)
		del Q[0]
	print(Cnt)
	T -= 1


# import sys

def minoper(str1, str2):
	l = len(str1)
	# print str1, str2
	if l == 1:
		return abs(ord(str1[0]) - ord(str2[0]))
	minnum = 9999999999
	minnum = min(minnum, minoper(str1[1:], str2[1:]) + abs(ord(str1[0]) - ord(str2[0])))
	# print minnum
	for i in range(1, l):
		str11 = list(str1)
		str22 = list(str2)
		str22[0], str22[i] = str22[i], str22[0]
		minnum = min(minnum, 1 + minoper(str11[1:], str22[1:]) + abs(ord(str11[0]) - ord(str22[0])))
	return minnum
	
for i in range(int(input())):
	s = input()
	str1 = [c for c in s]
	s = input()
	str2 = [c for c in s]
	print(minoper(str1, str2))


def solution(s1, s2, i):
	if i == len(s2):
		return 0
	mop = abs(s2[i] - s1[i]) + solution(s1, s2, i + 1)
	for x in range(i + 1, len(s1)):
		s1[i], s1[x] = s1[x], s1[i]
		mop = min(mop, 1 + abs(s2[i] - s1[i]) + solution(s1, s2, i + 1))
		s1[i], s1[x] = s1[x], s1[i]
	return mop
	

def main():
	for _ in range(int(input())):
		s1, s2 = list(map(ord, input())), list(map(ord, input()))
		print(solution(s1, s2, 0))

main()		



ans = 0
def fun(s1,s2,idx,c):
	global ans
	if idx==len(s1):
	    if ans>c:
	        ans=c
            return
	if s1[idx]>s2[idx]:
            val=c+ord(s1[idx])
            val-=ord(s2[idx])
            fun(s1,s2,idx+1,val)
	if s2[idx]==s1[idx]:
            fun(s1,s2,idx+1,c)
            return
        if s2[idx]>s1[idx]:
            val=c+ord(s2[idx])
            val-=ord(s1[idx])
            fun(s1,s2,idx+1,val)
        for i in range(idx+1, len(s1)):
            if s1[idx]!=s1[i]:
                s1 = list(s1)
                s1[idx],s1[i] = s1[i],s1[idx]
                s1 = ''.join(s1)
	
                d=abs(ord(s1[idx])-ord(s2[idx]))
                val=c+1
                val+=d
                fun(s1,s2,idx+1,val)
	
                s1 = list(s1)
                s1[idx],s1[i] = s1[i],s1[idx]
                s1 = ''.join(s1)
t = int(input())
for j in range(t):
    ans=99999999
    s1 = str(input())
    s2 = str(input())
    try:
    	fun(s1,s2,0,0)
    except Exception as e:
    	print(e)
    print(ans)


ans = 0
def fun(s1,s2,idx,c):
	global ans
	if idx==len(s1):
	    if ans>c:
	        ans=c
            return
	if s1[idx]>s2[idx]:
            val=c+ord(s1[idx])
            val-=ord(s2[idx])
            fun(s1,s2,idx+1,val)
	if s2[idx]==s1[idx]:
            fun(s1,s2,idx+1,c)
            return
        if s2[idx]>s1[idx]:
            val=c+ord(s2[idx])
            val-=ord(s1[idx])
            fun(s1,s2,idx+1,val)
        for i in range(idx+1, len(s1)):
            if s1[idx]!=s1[i]:
                s1 = list(s1)
                s1[idx],s1[i] = s1[i],s1[idx]
                s1 = ''.join(s1)
	
                d=abs(ord(s1[idx])-ord(s2[idx]))
                val=c+1
                val+=d
                fun(s1,s2,idx+1,val)
	
                s1 = list(s1)
                s1[idx],s1[i] = s1[i],s1[idx]
                s1 = ''.join(s1)
t = int(input())
for j in range(t):
    ans=99999999
    s1 = str(input())
    s2 = str(input())
    try:
    	fun(s1,s2,0,0)
    except Exception as e:
    	print(e)
    print(ans)