Problem:


Problem B: Repeated Substitution with Sed

Do you know "sed," a tool provided with Unix? Its most popular use is to substitute every
occurrence of a string  contained in the input string (actually each input line) with another
string &beta;. More precisely, it proceeds as follows.

   
 Within the input string, every non-overlapping (but possibly adjacent) occurrences of &alpha; are
      marked. If there is more than one possibility for non-overlapping matching, the leftmost
      one is chosen.

   
 Each of the marked occurrences is substituted with &beta; to obtain the output string; other
      parts of the input string remain intact.

For example, when &alpha; is "aa" and &beta; is "bca", an input string "aaxaaa" will produce "bcaxbcaa",
but not "aaxbcaa" nor "bcaxabca". Further application of the same substitution to the string
"bcaxbcaa" will result in "bcaxbcbca", but this is another substitution, which is counted as the
second one.

In this problem, a set of substitution pairs (&alpha;i, &beta;i) (i = 1, 2, ... , n), an initial string &gamma;, and a
final string &delta; are given, and you must investigate how to produce &delta; from &gamma; with a minimum
number of substitutions. A single substitution (&alpha;i, &beta;i) here means simultaneously substituting
all the non-overlapping occurrences of &alpha;i, in the sense described above, with &beta;i.

You may use a specific substitution (&alpha;i, &beta;i ) multiple times, including zero times.

Input

The input consists of multiple datasets, each in the following format.

      n

      &alpha;1 &beta;1

      &alpha;2 &beta;2

      .

      .

      .

      &alpha;n &beta;n

      &gamma;

      &delta;

n is a positive integer indicating the number of pairs. &alpha;i and &beta;i are separated by a single space.
You may assume that 1 ≤ |&alpha;i| < |&beta;i| ≤ 10 for any i (|s| means the length of the string s),

&alpha;i &ne; &alpha;j for any i &ne; j, n ≤ 10 and 1 ≤ |&gamma;| < |&delta;| ≤ 10. All the strings consist solely of lowercase
letters. The end of the input is indicated by a line containing a single zero.

Output

For each dataset, output the minimum number of substitutions to obtain &delta; from &gamma;. If &delta; cannot
be produced from &gamma; with the given set of substitutions, output -1.

Sample Input

2
a bb
b aa
a
bbbbbbbb
1
a aa
a
aaaaa
3
ab aab
abc aadc
ad dee
abc
deeeeeeeec
10
a abc
b bai
c acf
d bed
e abh
f fag
g abe
h bag
i aaj
j bbb
a
abacfaabe
0

Output for the Sample Input

3
-1
7
4



Sample input:
2
a bb
b aa
a
bbbbbbbb
1
a aa
a
aaaaa
3
ab aab
abc aadc
ad dee
abc
deeeeeeeec
10
a abc
b bai
c acf
d bed
e abh
f fag
g abe
h bag
i aaj
j bbb
a
abacfaabe
0


Sample output:
3
-1
7
4

Submission status: Accepted

Solution code:
while 1:
    n = int(raw_input())
    if n == 0: break
    ab = [raw_input().split() for i in xrange(n)]
    s = raw_input()
    g = raw_input()
    memo = set([s])
    que = [[s,0]]
    while que:
        c,i = que.pop(0)
        if c == g:
            print i
            break
        for a,b in ab:
            cc = c.replace(a,b)
            if len(cc) > len(g) or cc in memo: continue
            memo.add(cc)
            que.append([cc,i+1])
    else:
        print -1

Submission status: Accepted

Solution code:
INF = 10**9
def dfs(s, d, P):
    if len(s) > len(d):
        return INF
    if s == d:
        return 0
    if s in memo:
        return memo[s]
    res = INF
    for a, b in P:
        r = s.replace(a, b)
        if r != s:
            res = min(res, dfs(r, d, P)+1)
    memo[s] = res
    return res

while 1:
    n = input()
    if n==0:
        break
    P = [raw_input().split() for i in xrange(n)]
    g = raw_input()
    d = raw_input()
    memo = {}
    res = dfs(g, d, P)
    print res if res < INF else -1

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque

while True:
    n = input()
    if n == 0:
        break
    dq = deque()

    lst = []
    for i in range(n):
        hoge = raw_input().split(" ")
        lst.append(hoge)
    gamma = raw_input()
    delta = raw_input()
    m = {}
    dq.append(gamma)
    num = 0
    while len(dq) > 0:
        sz = len(dq)
        for loop in range(sz):
            S = dq.popleft()
            if S in m:
                continue
            if len(S) > 10:
                continue
            m[S] = num
            for l in lst:
                SS = S.replace(l[0], l[1])
                dq.append(SS)
        num += 1
    
    if delta in m:
        print m[delta]
    else:
        print "-1"

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n = I()
        if n == 0:
            break
        a = [LS() for _ in range(n)]
        s = S()
        k = S()
        l = len(k)
        if s == k:
            rr.append(0)
            continue
        u = set([s])
        c = set([s])
        t = 0
        r = -1
        while c:
            t += 1
            ns = set()
            for cs in c:
                for d,e in a:
                    nt = cs.replace(d,e)
                    if len(nt) > l:
                        continue
                    ns.add(nt)
            if k in ns:
                r = t
                break
            c = ns - u
            u |= ns
        rr.append(r)

    return '\n'.join(map(str,rr))


print(main())

Submission status: Accepted

Solution code:
def substitute(text, a, b):
    pos = 0
    newText = text
    L1 = len(a)
    L2 = len(b)
    while True:
        idx = newText.find(a, pos)
        if idx < 0:
            return newText
        newText = newText[:idx] + b + newText[idx + L1:]
        pos = idx + L2
    return newText

def transform(orig, goal, count):
    global subs
    global minCount

    if len(orig) > len(goal):
        return

    if orig == goal:
        minCount = min(minCount, count)
        return
    
    for key in subs:
        newStr = substitute(orig, key, subs[key])
        if newStr != orig:
            transform(newStr, goal, count + 1)

if __name__ == '__main__':
    while True:
        N = int(input())
        if N == 0:
            break

        subs = {}
        for _ in range(N):
            a, b = input().strip().split()
            subs[a] = b
        
        orig = input().strip()
        goal = input().strip()

        minCount = 999999999
        transform(orig, goal, 0)

        if minCount == 999999999:
            print(-1)
        else:
            print(minCount)

Submission status: Accepted

Solution code:
from collections import deque

def testcase_ends():
    n = int(input())
    if n == 0:
        return 1

    sub = [input().split() for i in range(n)]
    gamma = input()
    delta = input()

    q = deque()
    q.append((gamma, 0))
    res = 10000
    while q:
        s, i = q.popleft()
        for alpha, beta in sub:
            if alpha not in s: continue

            t = s.replace(alpha, beta)
            if t == delta:
                res = min(res, i+1)
                continue
            elif len(t) >= len(delta):
                continue

            q.append((t, i+1))

    if res == 10000: res = -1
    print(res)
    return 0

def main():
    while not testcase_ends():
        pass

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import queue
while 1:
    n=int(input())
    if n==0:
        break
    dic={}
    for i in range(n):
        k,s=input().split()
        dic[k]=s
    s=input()
    ans=input()
    q=queue.Queue()
    q.put((s,0))
    find=False
    while not q.empty():
        s=q.get()
        if s[0]==ans:
            print(s[1])
            q=queue.Queue()
            find=True
        if not find:
            for k in dic.keys():
                t=s[0].replace(k,dic[k])
                if len(t)<=len(ans) and s[0]!=t:
                    q.put((t,s[1]+1))
    if not find:
        print(-1)

Submission status: Runtime Error

Solution code:
while 1:
    n = int(raw_input())
    if n == 0: break
    ab = [raw_input().split() for i in xrange(n)]
    s = raw_input()
    g = raw_input()
    que = [[s,0]]
    while que:
        c,i = que.pop(0)
        if c == g:
            print i
            break
        for a,b in ab:
            cc = c.replace(a,b)
            if len(cc) > len(g): continue
            que.append([cc,i+1])
    else:
        print -1

Submission status: Runtime Error

Solution code:
// C++11
#include "bits/stdc++.h"
#include <sys/time.h>
#include <emmintrin.h>
#include <string>
#include <sstream>
#include <fstream>
#include <random>
#include <bitset>

using namespace std;

inline long long GetTSC() {
  long long lo, hi;
  asm volatile ("rdtsc": "=a"(lo), "=d"(hi));
  return lo + (hi << 32);
}
inline double GetSeconds() {
  return GetTSC() / 2.8e9;
}

const long inf = pow(10,15);
int di[] = {-1,0,1,0};
int dj[] = {0,1,0,-1};
tuple<int, int>q[50*50*50*50];

void solve(){
  double starttime = GetSeconds();
  while(1){
    int w,h;
    cin >> w >> h;
    // cerr << w << ", " << h << endl;
    if(w==0 && h==0) break;
    int lp,ls,rp,rs;
    bool lb[2500] = {};
    bool rb[2500] = {};
    bool f[2500][2500] = {};
    for(int i=0; i<h; i++){
      string s;
      cin >> s;
      for(int j=0; j<w; j++){
        if(s[j]=='#') lb[i*w+j] = 1;
        if(s[j]=='%') lp = i*w+j;
        if(s[j]=='L') ls = i*w+j;
      }
      cin >> s;
      for(int j=0; j<w; j++){
        if(s[j]=='#') rb[i*w+j] = 1;
        if(s[j]=='%') rp = i*w+j;
        if(s[j]=='R') rs = i*w+j;
      }
    }
    f[ls][rs] = 1;
    int qi = 0;
    int qe = 1;
    q[0] = make_tuple(ls,rs);
    bool ff = 0;
    while(qi<qe){
      int lt = get<0>(q[qi]);
      int rt = get<1>(q[qi]);
      int li = lt / w;
      int lj = lt % w;
      int ri = rt / w;
      int rj = rt % w;
      qi++;
      // cerr << "qie: " << qi << ", " << qe << ", lij: " << li << ", " << lj << ", rij: " << ri << ", " << rj << endl;
      for(int i=0; i<4; i++){
        int nli = li + di[i];
        int nlj = lj + dj[i];
        int nri = ri + di[i];
        int nrj = rj - dj[i];
        if(nli < 0 || nli >= h || nlj < 0 || nlj >= w || lb[nli*w+nlj]){
          nli = li;
          nlj = lj;
        }
        if(nri < 0 || nri >= h || nrj < 0 || nrj >= w || rb[nri*w+nrj]){
          nri = ri;
          nrj = rj;
        }
        int nlt = nli*w+nlj;
        int nrt = nri*w+nrj;
        if(nlt == lp && nrt == rp){
          ff = 1;
          break;
        }
        if(nlt == lp || nrt == rp) continue;
        if(f[nlt][nrt]) continue;
        f[nlt][nrt] = 1;
        q[qe++] = make_tuple(nlt,nrt);
      }
      if(ff) break;
    }
    if(ff){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  }
  // cerr << "time: " << GetSeconds() - starttime << endl;

  return;
}

int main() {
  solve();
  return 0;
}