Problem:


ふしぎな虫

会津生物学研究所のA博士は、とある南の島でふしぎな虫を発見しました。形は芋虫のように細長いのですが、ひとつの体節が玉のような形をしているので、糸でつないだビーズ玉のように見えます。ふしぎなのは体の色に様々なバリエーションがあることと、なかには時間がたつにつれて体の色が変っていく虫がいることでした。どの虫の体節の色も赤か緑か青のどれかに限られるようですが、1 秒ごとに体節の色が変わっていき、最後にはすべての体節が同じ色になって落ち着く場合もあれば、いつまで待ってもずっと色が変わりつづける場合もあるようでした。

調べていくうちに、ふだんはすべての体節が同じ色をしているのですが、何かに驚いたりして興奮した後は体節の色が勝手に変わってしまうことがわかりました。一度体節の色が変わってしまうと、ふたたびすべての体節が同じ色になるまではずっと色が変わり続けることがわかりました。

 A博士はこの虫を何匹も捕まえて興奮させてみては、色が変わる様子を興味深く観察していましたが、やがて色が変化している最中の色の変わり方には次のような規則性があることに気がつきました。

色が変わるのは、隣り合っている色違いの 2つの体節のペア 1組だけが変わり、他の体節の色は変わらない。ただし、そのようなペアが複数あるときに、どのペアの色が変わるかはあらかじめ予測できない。

そのようなペアは、2つの体節の色のどちらでもない色に同時に変わる(たとえば、緑と赤の体節が隣り合っているときは、それらが同時に青に変わる)。

 虫の色の変化を、2秒後まですべて書いたものが上の図です。図の上段のような色をした虫がいるとします。このとき、隣り合った色違いの体節のペアは 3組あるので、1秒後には中段に並べて描いた 3通りの色のどれかに変わります。1秒後に中段左側の 2つのように変わったときには、2秒後にすべての体節が緑色になることができます(図の下段の左側から 2番目)。 それに対して、1秒後に中段の1番右のように変わったときには、2秒後にすべての体節が同じ色に変わることはありません。

 博士は、目の前にいる虫の体節がすべて同じ色になる可能性があるのか、あるとしたらそうなるのは最短で何秒後なのかを予測することにしました。

目の前にいる虫の体節の色の並びを入力とし、その虫の体節がすべて同じ色になるのに要する最短の時間を秒単位で出力するプログラムを作成してください。ただし、同じ色になる可能性がないときは「NA(半角英大文字)」と出力してください。また、虫の体節の色の並びは2  以上 10 以下のr(赤)、g(緑)、b(青)からなる文字列で表されます。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されま
す。各データセットとして、 虫の体節の情報を表す１つの文字列が１行に与えられます。

データセットの数は 100 を超えません。

Output

データセット毎に、すべての体節の色が同じになるまでに要する最小時間 (秒単位の整数) または NA を１行に出力します。

Sample Input

rbgrg
rbbgbbr
bgr
bgrbrgbr
bggrgbgrr
gbrggrbggr
rrrrr
bgbr
0

Output for the Sample Input

5
7
1
6
NA
8
0
4



Sample input:
rbgrg
rbbgbbr
bgr
bgrbrgbr
bggrgbgrr
gbrggrbggr
rrrrr
bgbr
0


Sample output:
5
7
1
6
NA
8
0
4

Submission status: Wrong Answer

Solution code:
rgb = set(["r","g","b"])
while 1:
	worm = raw_input()
	if worm == "0": break
	n = len(worm)
	L = 1
	cnt = flag = 0
	queset = set([worm])
	while 1:
		que = list(queset)
		queset = set()
		for r in range(L):
			Worm = que.pop(0)
			if len(set(Worm)) == 1:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					worm = Worm[:]
					nextclr = list(rgb-set(worm[i:i+2]))[0]
					worm = worm[:i] + 2*nextclr + worm[i+2:]
					queset.add(worm)
		L = len(queset)
		if flag: break
		cnt += 1
		if cnt > 10: break
	print cnt if flag else "NA"

Submission status: Wrong Answer

Solution code:
rgb = set(["r","g","b"])
while 1:
	worm = raw_input()
	if worm == "0": break
	n = len(worm)
	L = 1
	cnt = flag = 0
	queset = set([worm])
	while 1:
		que = list(queset)
		queset = set()
		for r in range(L):
			Worm = que.pop(0)
			if len(set(Worm)) == 1:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					worm = Worm[:]
					nextclr = list(rgb-set(worm[i:i+2]))[0]
					worm = worm[:i] + 2*nextclr + worm[i+2:]
					queset.add(worm)
		L = len(queset)
		if flag: break
		cnt += 1
		if cnt > 11: break
	print cnt if flag else "NA"

Submission status: Wrong Answer

Solution code:
rgb = set(["r","g","b"])
while 1:
	worm = raw_input()
	if worm == "0": break
	n = len(worm)
	L = 1
	cnt = flag = 0
	queset = set([worm])
	ref = set()
	while 1:
		que = list(queset)
		queset = set()
		for Worm in que:
			if len(set(Worm)) == 1:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					nextclr = list(rgb-set(Worm[i:i+2]))[0]
					worm = Worm[:i] + 2*nextclr + Worm[i+2:]
					queset.add(worm)
		queset = queset - ref
		ref = ref|queset
		L = len(queset)
		if flag: break
		cnt += 1
		if cnt > 13: break
	print cnt if flag else "NA"

Submission status: Accepted

Solution code:
import Queue
que = Queue.PriorityQueue()
dic = {
        ord('r')+ord('g'): 'b',
        ord('g')+ord('b'): 'r',
        ord('b')+ord('r'): 'g',
        }
while True:
    s = raw_input()
    if s=='0':
        break
    while not que.empty():
        que.get()
    cost = {}
    cost[s] = 0
    que.put((0, s))
    ans = -1
    while not que.empty():
        nn, ss = que.get()
        if all(e == ss[0] for e in ss):
            ans = nn
            break
        if cost[ss] < nn:
            continue
        for i in xrange(len(ss)-1):
            c0, c1 = ss[i], ss[i+1]
            if c0 != c1:
                code = dic[ord(c0)+ord(c1)]
                sa = ss[:i] + code*2 + ss[i+2:]
                if sa not in cost or nn+1 < cost[sa]:
                    cost[sa] = nn+1
                    que.put((nn+1, sa))
    print "NA" if ans<0 else ans

Submission status: Accepted

Solution code:
import Queue
dic = {
        'rg':'b', 'gr':'b',
        'gb':'r', 'bg':'r',
        'br':'g', 'rb':'g',
        }
while True:
    s = raw_input()
    if s=='0':
        break
    que = Queue.PriorityQueue()
    l = len(s)
    cost = {}
    cost[s] = 0
    que.put((0, s))
    ans = -1
    while not que.empty():
        nn, ss = que.get()
        if all(e == ss[0] for e in ss):
            ans = nn
            break
        if cost[ss] < nn:
            continue
        for i in xrange(l-1):
            cc = ss[i:i+2]
            if cc[0]!=cc[1]:
                code = dic[cc]
                sa = ss[:i] + code*2 + ss[i+2:]
                if sa not in cost or nn+1 < cost[sa]:
                    cost[sa] = nn+1
                    que.put((nn+1, sa))
    print "NA" if ans<0 else ans

Submission status: Accepted

Solution code:
import Queue
dic = {
        'rg':'bb', 'gr':'bb',
        'gb':'rr', 'bg':'rr',
        'br':'gg', 'rb':'gg',
        }
while True:
    s = raw_input()
    if s=='0':
        break
    que = Queue.PriorityQueue()
    l = len(s)
    cost = {s: 0}
    que.put((0, s))
    aa = ['r'*l, 'g'*l, 'b'*l]
    ans = -1
    while not que.empty():
        nn, ss = que.get()
        if ss in aa:
            ans = nn
            break
        if cost[ss] < nn:
            continue
        for i in xrange(l-1):
            cc = ss[i:i+2]
            if cc[0]!=cc[1]:
                sa = ss[:i] + dic[cc] + ss[i+2:]
                if sa not in cost or nn+1 < cost[sa]:
                    cost[sa] = nn+1
                    que.put((nn+1, sa))
    print "NA" if ans<0 else ans

Submission status: Accepted

Solution code:
import Queue

def solve(worm):
    dic = {
        "br" : "g",
        "bg" : "r",
        "gr" : "b"
    }
    Q = Queue.Queue()
    Q.put(worm)
    dist = {}
    dist[worm] = 0
    ans = -1
    while not Q.empty():
        cur = Q.get()
        if len(set(cur)) == 1:
            ans = dist[cur]
            break
        for i in range(len(cur)-1):
            if cur[i] != cur[i+1]:
                nxt = list(cur)
                color = dic["".join(sorted(nxt[i:i+2]))]
                nxt[i] = color
                nxt[i+1] = color
                nxt = "".join(nxt)
                if not nxt in dist:
                    dist[nxt] = dist[cur] + 1
                    Q.put(nxt)
    if ans == -1:
        print "NA"
    else:
        print ans

def main():
    while True:
        s = raw_input()
        if s == "0":
            break
        solve(s)
main()

Submission status: Accepted

Solution code:
from collections import deque
used = [0]*(3**10)


while True:
	s = raw_input()
	if s=="0":
		break
	n=len(s)
	t=0
	for i in range(len(s)):
		t*=3
		if s[i]=="r":
			t+=0
		if s[i]=="g":
			t+=1
		if s[i]=="b":
			t+=2
	f=0
	for i in range(3**n):
		used[i]=0
	tq=[t]
	q=deque(tq)
	used[t]=1
	ans=-1
	cnt=0
	while len(q)>0:
		qs=len(q)
		for o in range(qs):
			top=q.popleft()
			v=[0]
			v.pop()
			for i in range(n):
				v.append(top%3)
				top/=3
			ok=1
			a=v[0]
			for i in range(n):
				if v[i]!=a:
					ok=0
			if ok==1:
				f=1
				ans=cnt
				break
			for i in range(n-1):
				if v[i]!=v[i+1]:
					t1=v[i]
					t2=v[i+1]
					v[i]=3-t1-t2
					v[i+1]=3-t1-t2
					tmp=0
					for j in range(n):
						tmp*=3
						tmp+=v[j]
					if used[tmp]==0:
						q.append(tmp)
						used[tmp]=1
					v[i]=t1
					v[i+1]=t2
		if f==1:
			break
		else:
			cnt+=1
	if ans==-1:
		print "NA"
	else:
		print ans

Submission status: Accepted

Solution code:
q = []
lst = {}

def checker(letter, st):
  for i in xrange(len(st)):
    if letter != st[i]:
      return False
  return True

while True:
  q = []
  lst = {}
  st = raw_input()
  deep = 0
  if st == "0":
    break
  while True:
    # checked
    if st in lst:
      if len(q) == 0:
        print "NA"
        break
      st = q[0][0]
      deep = q[0][1]
      q = q[1:]
      continue
    # add checked list
    lst[st] = deep
    # check completed
    if checker(st[0], st):
      print deep
      break
    # que next pattern
    for i in xrange(len(st)-1):
      if st[i] == st[i+1]:
        continue
      if (st[i] == 'r' and st[i+1] == 'g') or (st[i] == 'g' and st[i+1] == 'r'):
        q.append([st[:i] + "bb" + st[i+2:], deep+1])
      elif (st[i] == 'r' and st[i+1] == 'b') or (st[i] == 'b' and st[i+1] == 'r'):
        q.append([st[:i] + "gg" + st[i+2:], deep+1])
      elif (st[i] == 'b' and st[i+1] == 'g') or (st[i] == 'g' and st[i+1] == 'b'):
        q.append([st[:i] + "rr" + st[i+2:], deep+1])
    # print NA if has no pattern in queue
    if len(q) == 0:
      print "NA"
      break
    # get next pattern from queue
    st = q[0][0]
    deep = q[0][1]
    q = q[1:]

Submission status: Accepted

Solution code:
from collections import deque

def isOneColor(w):
    sw = sorted(w)
    if sw[0] == sw[-1]:
        return True
    else:
        return False

def nextColor(c1, c2):
    cs = ['r', 'g', 'b']
    cs.remove(c1)
    cs.remove(c2)
    return cs[0]

def bfs(iw):
    q = deque()
    s = set()

    s.add(str(iw))
    q.append([iw, 0])
    while q:
        w, t = q.popleft()
        if isOneColor(w):
            return t
        else:
            for i in range(len(w)-1):
                if w[i] != w[i+1]:
                    nw = w.copy()
                    nc = nextColor(nw[i], nw[i+1])
                    nw[i], nw[i+1] = nc, nc
                    if str(nw) not in s:
                        s.add(str(nw))
                        q.append([nw, t+1])

    return -1

if __name__ == '__main__':
    while True:
        w = list(input())
        if w == ['0']:
            break

        t = bfs(w)
        if t == -1:
            print('NA')
        else:
            print(t)

Submission status: Accepted

Solution code:
from collections import deque
def change(x,y):
    if [x,y] == ["r","g"] or [y,x] == ["r","g"]:
        return "b"
    elif [x,y] == ["g","b"] or [y,x] == ["g","b"]:
        return "r"
    elif [x,y] == ["r","b"] or [y,x] == ["r","b"]:
        return "g"



rgb = ['r','g','b']
while True:
    time = 0
    W_dic = {}
    W_que = deque([])
    worm = tuple(str(input()))
    if worm == ('0',):
        break
    else:
        W_que.append([time,worm])
        W_dic[worm] = time
    while True:
        now_list = W_que.popleft()
        now_time = now_list[0]
        now_worm = now_list[1]
        if now_worm.count('r') == len(now_worm) or now_worm.count('g') == len(now_worm) or now_worm.count('b') == len(now_worm):
            print(now_time)
            break
        a_0 = now_worm[0]
        for i in range(1,len(now_worm)):
            a_1 = now_worm[i]
            rgb_c = rgb
            worm_c = list(now_worm)
            if a_0 != a_1:
                coll = change(a_0,a_1)
                worm_c[i - 1] = coll
                worm_c[i] = coll
                if not tuple(worm_c) in W_dic:
                    W_dic[tuple(worm_c)] = now_time + 1
                    W_que.append([now_time + 1,worm_c])
            a_0 = a_1
        
        if len(W_que) == 0:
            print("NA")
            break

Submission status: Accepted

Solution code:
from copy import deepcopy
from collections import deque


class Bug:
    __convert = {"r": 1, "g": 2, "b": 3}
    __weight = [1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000]

    def __init__(self, state, time):
        self.state = list(state)
        self.time = time

    def color_change(self):
        box = []

        for item1, item2, index in zip(self.state[:-1], self.state[1:], range(len(self.state))):
            if item1 != item2:

                if item1 == "r" and item2 == "g" or item1 == "g" and item2 == "r":
                    color = "b"
                elif item1 == "r" and item2 == "b" or item1 == "b" and item2 == "r":
                    color = "g"
                else:
                    color = "r"

                copy_state = deepcopy(self.state)

                copy_state[index] = color
                copy_state[index + 1] = color

                box.append(copy_state)

        return box

    def is_same_color(self):
        first = self.state[0]
        return all([item == first for item in self.state])

    def __hash__(self):
        tmp = [self.__convert[item] * w for item, w in zip(self.state, self.__weight)]
        return sum(tmp)

    def __eq__(self, other):
        return all([item1 == item2 for item1, item2 in zip(self.state, other.state)])


while True:

    input_data = input()

    if input_data[0] == "0":
        break

    state_queue = deque()
    pattern = set()

    first = Bug(input_data, 0)

    if first.is_same_color():
        answer = 0
    else:
        answer = "NA"
        state_queue.appendleft(first)
        pattern.add(first)

    while len(state_queue) != 0:

        original = state_queue.pop()
        boxes = original.color_change()

        for state in boxes:

            item = Bug(state, original.time + 1)

            if item.is_same_color():
                answer = item.time

                state_queue.clear()
                break
            else:
                if item not in pattern:
                    pattern.add(item)
                    state_queue.appendleft(item)

    print(answer)

Submission status: Accepted

Solution code:
from collections import deque

def only_color(s):
  temp = s[0]
  for i in range(1, len(s)):
    c = s[i]
    if temp != c:
      return False
    temp = c

  return True

def new_color(s, i):
  color = [c for c in ("r", "g", "b") if c not in (s[i], s[i + 1])][0]
  return s[:i] + color * 2 + s[i + 2:]

def solve(s):
  if only_color(s):
    print(0)
    return
  length = len(s)
  dic = {}
  que = deque()
  que.append((s, 0))

  while que:
    colors, score = que.popleft()
    score += 1
    temp = colors[0]
    for i in range(1, length):
      ci = colors[i]
      if ci != temp:
        new = new_color(colors, i - 1)
        if only_color(new):
          print(score)
          return
        if new not in dic:
          dic[new] = score
          que.append((new, score))
      temp = ci
  else:
    print("NA")

def main():
  while True:
    s = input()
    if s == "0":
      break
    solve(s)

main()

Submission status: Accepted

Solution code:
from collections import deque

def only_color(s, monos):
  if s in monos:
    return True
  else:
    return False

def new_color(s, i, rgb):
  for color in rgb:
    if color != s[i] and color != s[i + 1]:
      break
  return s[:i] + color * 2 + s[i + 2:]

def solve(s):
  length = len(s)
  monos = ["r" * length, "g" * length, "b" * length]
  if s in monos:
    print(0)
    return
  dic = {s:0}
  rgb = "rgb"
  que = deque()
  que.append((s, 0))

  while que:
    colors, score = que.popleft()
    score += 1
    temp = colors[0]
    for i in range(1, length):
      ci = colors[i]
      if ci != temp:
        new = new_color(colors, i - 1, rgb)

        if new in monos:
          print(score)
          return

        if new not in dic:
          dic[new] = score
          que.append((new, score))

      temp = ci

  print("NA")

def main():
  while True:
    s = input()
    if s == "0":
      break
    solve(s)

main()

Submission status: Accepted

Solution code:
from collections import deque

def new_color(s, i, rgb):
  for color in rgb:
    if color != s[i] and color != s[i + 1]:
      break
  return s[:i] + color * 2 + s[i + 2:]

def solve(s):
  length = len(s)
  monos = ["r" * length, "g" * length, "b" * length]
  if s in monos:
    print(0)
    return
  dic = {s:0}
  rgb = "rgb"
  que = deque()
  app = que.append
  pop = que.popleft
  que.append((s, 0))

  while que:
    colors, score = pop()
    score += 1
    temp = colors[0]

    for i in range(1, length):
      ci = colors[i]
      if ci != temp:
        new = new_color(colors, i - 1, rgb)

        if new in monos:
          print(score)
          return

        if new not in dic:
          dic[new] = score
          app((new, score))

      temp = ci

  print("NA")

def main():
  while True:
    s = input()
    if s == "0":
      break
    solve(s)

main()

Submission status: Accepted

Solution code:
from collections import deque

def new_color(s, i, color):
  return s[:i] + color * 2 + s[i + 2:]

def solve(s):
  length = len(s)
  monos = ["r" * length, "g" * length, "b" * length]
  if s in monos:
    print(0)
    return
  rgb = "rgb"
  another = {("r", "g"):"b", ("g", "r"):"b", 
             ("r", "b"):"g", ("b", "r"):"g",
             ("g", "b"):"r", ("b", "g"):"r"}
  dic = {s:0}
  que = deque()
  app = que.append
  pop = que.popleft
  que.append((s, 0))

  while que:
    colors, score = pop()
    score += 1
    temp = colors[0]

    for i in range(1, length):
      ci = colors[i]
      if ci != temp:
        new = new_color(colors, i - 1, another[(ci, temp)])

        if new in monos:
          print(score)
          return

        if new not in dic:
          dic[new] = score
          app((new, score))

      temp = ci

  print("NA")

def main():
  while True:
    s = input()
    if s == "0":
      break
    solve(s)

main()

Submission status: Accepted

Solution code:
from collections import deque

def new_color(s, i, color):
  return s[:i - 1] + color * 2 + s[i + 1:]

def solve(s):
  length = len(s)
  monos = ["r" * length, "g" * length, "b" * length]
  if s in monos:
    print(0)
    return

  another = {("r", "g"):"b", ("g", "r"):"b", 
             ("r", "b"):"g", ("b", "r"):"g",
             ("g", "b"):"r", ("b", "g"):"r"}
  visited = {s:True}
  que = deque()
  app = que.append
  pop = que.popleft
  que.append((s, 0))

  while que:
    colors, score = pop()
    score += 1
    temp = colors[0]

    for i in range(1, length):
      ci = colors[i]
      if ci != temp:
        new = new_color(colors, i, another[(ci, temp)])
        if new in monos:
          print(score)
          return

        if new not in visited:
          visited[new] = True
          app((new, score))

      temp = ci

  print("NA")

def main():
  while True:
    s = input()
    if s == "0":
      break
    solve(s)

main()

Submission status: Accepted

Solution code:
from collections import deque

def new_color(s, i, color):
  return s[:i] + color * 2 + s[i + 2:]

def solve(s):
  length = len(s)
  monos = ["r" * length, "g" * length, "b" * length]
  if s in monos:
    print(0)
    return

  another = {("r", "g"):"b", ("g", "r"):"b", 
             ("r", "b"):"g", ("b", "r"):"g",
             ("g", "b"):"r", ("b", "g"):"r"}
  visited = {s:0}
  que = deque()
  app = que.append
  pop = que.popleft
  que.append((s, 0))

  while que:
    colors, score = pop()
    score += 1
    temp = colors[0]

    for i in range(1, length):
      ci = colors[i]
      if ci != temp:
        new = new_color(colors, i - 1, another[(ci, temp)])
        if new in monos:
          print(score)
          return

        if new not in visited:
          visited[new] = score
          app((new, score))

      temp = ci

  print("NA")

def main():
  while True:
    s = input()
    if s == "0":
      break
    solve(s)

main()

Submission status: Accepted

Solution code:
from Queue import Queue
while True:
    s=raw_input()
    if s=="0":break
    s=s.replace("r","0")
    s=s.replace("b","1")
    s=s.replace("g","2")
    Q=Queue()
    visited=set()
    visited.add(s)
    Q.put((s,0))
    while not Q.empty():
        ptn,tim=Q.get()
        if len(set(ptn))==1:
            print tim
            break
        for i in range(len(ptn)-1):
            if ptn[i]==ptn[i+1]:
                continue
            col1,col2=int(ptn[i]),int(ptn[i+1])
            s=list(ptn)
            if col1+col2==1:
                s[i]=s[i+1]="2"
            elif col1+col2==2:
                s[i]=s[i+1]="1"
            elif col1+col2==3:
                s[i]=s[i+1]="0"
            s="".join(s)
            if s not in visited:
                Q.put((s,tim+1))
                visited.add(s)
    else:
        print "NA"

Submission status: Accepted

Solution code:
from collections import deque,defaultdict
T = {"rg":"bb","gr":"bb",
     "rb":"gg","br":"gg",
     "gb":"rr","bg":"rr"}
def change(s):
    for i in xrange(len(s)-1):
        if s[i:i+2] in T:
            yield "".join((s[:i],T[s[i:i+2]],s[i+2:]))

def BFS(s):
    d = deque()
    d.append((s,0))
    visited = defaultdict(bool)
    A = map(lambda c:len(s)*c, ("r","g","b"))
    while len(d) > 0:
        s,n = d.popleft()
        if s in A:
            return n
        for ns in change(s):
            if not visited[ns]:
                d.append((ns,n+1))
                visited[ns] = True
    return "NA"

while True:
    s = raw_input()
    if s == "0":
        break
    print BFS(s)

Submission status: Accepted

Solution code:
rgb = set(["r","g","b"])
while 1:
	worm = raw_input()
	if worm == "0": break
	n = len(worm)
	que = [worm]
	ref = set(worm)
	L = 1
	cnt = flag = 0
	while 1:
		for r in range(L):
			Worm = que.pop(0)
			if Worm in ref: continue
			else: ref.add(Worm)
			if len(set(Worm)) == 1:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					worm = Worm[:]
					nextclr = list(rgb-set(worm[i:i+2]))[0]
					worm = worm[:i] + 2*nextclr + worm[i+2:]
					if worm not in que: que.append(worm)
		L = len(que)
		if flag or L == 0: break
		cnt += 1
	print cnt if flag else "NA"

Submission status: Accepted

Solution code:
rgb = set(["r","g","b"])
while 1:
	worm = raw_input()
	if worm == "0": break
	n = len(worm)
	que = [worm]
	ref = set(worm)
	L = 1
	cnt = flag = 0
	while 1:
		for r in range(L):
			Worm = que.pop(0)
			if Worm in ref: continue
			else: ref.add(Worm)
			if len(set(Worm)) == 1:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					worm = Worm[:]
					nextclr = list(rgb-set(worm[i:i+2]))[0]
					worm = worm[:i] + 2*nextclr + worm[i+2:]
					if worm not in que: que.append(worm)
		L = len(que)
		if flag or L == 0: break
		cnt += 1
		if cnt > 15: break
	print cnt if flag else "NA"

Submission status: Accepted

Solution code:
rgb = set(["r","g","b"])
while 1:
	worm = raw_input()
	if worm == "0": break
	n = len(worm)
	L = 1
	cnt = flag = 0
	queset = set([worm])
	while 1:
		que = list(queset)
		queset = set()
		for r in range(L):
			Worm = que.pop(0)
			if len(set(Worm)) == 1:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					nextclr = list(rgb-set(Worm[i:i+2]))[0]
					worm = Worm[:i] + 2*nextclr + Worm[i+2:]
					queset.add(worm)
		L = len(queset)
		if flag: break
		cnt += 1
		if cnt > 15: break
	print cnt if flag else "NA"

Submission status: Accepted

Solution code:
rgb = set(["r","g","b"])
while 1:
	worm = raw_input()
	if worm == "0": break
	n = len(worm)
	L = 1
	cnt = flag = 0
	queset = set([worm])
	ref = set()
	while 1:
		que = list(queset)
		queset = set()
		for Worm in que:
			if len(set(Worm)) == 1:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					nextclr = list(rgb-set(Worm[i:i+2]))[0]
					worm = Worm[:i] + 2*nextclr + Worm[i+2:]
					queset.add(worm)
		queset = queset - ref
		ref = ref|queset
		L = len(queset)
		if flag: break
		cnt += 1
		if cnt > 15: break
	print cnt if flag else "NA"

Submission status: Accepted

Solution code:
dic = {"r":1,"g":2,"b":3}
rgb = ["r","g","b"]
while 1:
	worm = raw_input()
	if worm == "0": break
	n = len(worm)
	ref = ["r"*n,"g"*n,"b"*n]
	cnt = flag = 0
	queset = set([worm])
	done = set()
	while 1:
		que = list(queset)
		queset = set()
		for Worm in que:
			if Worm in ref:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					nextclr = rgb[5-dic[Worm[i]]-dic[Worm[i+1]]]
					queset.add(Worm[:i] + 2*nextclr + Worm[i+2:])
		if flag or cnt > 14: break
		cnt += 1
		queset -= done
		done |= queset
	print cnt if flag else "NA"

Submission status: Accepted

Solution code:
dic = {"r":1,"g":2,"b":3}
while 1:
	worm = raw_input()
	if worm == "0": break
	n = len(worm)
	ref = ["r"*n,"g"*n,"b"*n]
	cnt = flag = 0
	queset = set([worm])
	done = set()
	while 1:
		que = list(queset)
		queset = set()
		for Worm in que:
			if Worm in ref:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					nextclr = "rgb"[5-dic[Worm[i]]-dic[Worm[i+1]]]
					queset.add(Worm[:i] + 2*nextclr + Worm[i+2:])
		if flag or cnt > 14: break
		cnt += 1
		queset -= done
		done |= queset
	print cnt if flag else "NA"

Submission status: Accepted

Solution code:
dic = {"0":0,"1":1,"2":2}
while 1:
	worm = raw_input()
	if worm == "0": break
	worm = worm.replace("r","0").replace("g","1").replace("b","2")
	n = len(worm)
	ref = ["0"*n,"1"*n,"2"*n]
	done = [1]*(3**n)
	done[int(worm,3)] = 0
	cnt = flag = 0
	nxtque = [worm]
	while 1:
		que = nxtque
		nxtque = []
		for Worm in que:
			if Worm in ref:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					nextclr = "012"[3-dic[Worm[i]]-dic[Worm[i+1]]]
					worm = Worm[:i] + 2*nextclr + Worm[i+2:]
					num = int(worm,3)
					if done[num]:
						done[num] = 0
						nxtque.append(worm)
		if flag or len(nxtque) == 0: break
		cnt += 1
	print cnt if flag else "NA"

Submission status: Accepted

Solution code:
def change(s, n):
  c = ['r', 'g', 'b']
  a, b = s[n], s[n + 1]
  if a == b:
    return s
  s = list(s)
  c.remove(a)
  c.remove(b)
  s[n], s[n + 1] = c[0], c[0]
  return ''.join(s)

while True:
  s = raw_input()
  if s == '0':
    break
  
  q = [(s, 0)]
  mem = []
  while len(q) > 0:
    v, n = q.pop(0)
    if v in mem:
      continue
    if v.count(v[0]) == len(v):
      print(n)
      break
    mem.append(v)
    for i in range(len(v) - 1):
      vv = change(v, i)
      if vv != v:
        q.append((vv, n + 1))
  else:
    print('NA')

Submission status: Accepted

Solution code:
def solve():
    while True:
        worm = input()
        if worm == '0':
            break
        
        q = [worm]
        m = {('r', 'g'): 'bb', ('g', 'r'): 'bb', ('r', 'b'): 'gg',
             ('b', 'r'): 'gg', ('g', 'b'): 'rr', ('b', 'g'): 'rr'}
        d = {worm: True}
        ans = 0
        
        while q:
            nq = []
            for w in q:
                flag = True
                for i, t in enumerate(zip(w, w[1:])):
                    s1, s2 = t
                    if s1 != s2:
                        flag = False
                        nw = w[:i] + m[t] + w[i+2:]
                        if nw not in d:
                            d[nw] = True
                            nq.append(nw)
                if flag:
                    print(ans)
                    break
            else:
                q = nq[:]
                ans += 1
                continue
            break
        else:
            print('NA')

solve()

Submission status: Runtime Error

Solution code:
from collections import deque
import copy

def another_color(a, b):
    if a == 'r' and b == 'g' or a == 'g' and b == 'r':
        return 'b'
    if a == 'r' and b == 'b' or a == 'b' and b == 'r':
        return 'g'
    if a == 'g' and b == 'b' or a == 'b' and b == 'g':
        return 'r'
    return None


def is_all_same_elements(es):
    return all([e == es[0] for e in es[1:]]) if es else False

class State:
    def __init__(self, sequence):
        self.colors = list(sequence)
        self.label = sequence
        self.depth = 0

    def nextStates(self):
        nextStates = []
        for i in range(1, len(self.colors)):
            if self.colors[i] != self.colors[i - 1]:
                c = another_color(self.colors[i], self.colors[i - 1])
                if c is None:
                    continue
                newColors = copy.copy(self.colors)
                newColors[i] = c
                newColors[i - 1] = c
                nextStates.append(State(''.join(newColors)))
        return nextStates

    def print(self):
        print(self.depth)
        # for debug
#         print("{} {}".format(self.label, self.depth))


sequence = input()
while sequence != '0':
    root = State(sequence)
    printed = False
    visited = [root.label]
    queue = deque([])
    queue.append(root)
    # BFS
    while queue:
        state = queue.popleft()
        if is_all_same_elements(state.colors):
            state.print()
            printed = True
            break
        for nextState in state.nextStates():
            if not nextState.label in visited:
                visited.append(nextState.label)
                nextState.depth = state.depth + 1
                queue.append(nextState)

    if not printed:
        print("NA")
    # 次の行へ
    sequence = input()

Submission status: Runtime Error

Solution code:
from collections import deque
import copy

def another_color(a, b):
    if not a == 'r' and not b == 'r':
        return 'r'
    if not a == 'g' and not b == 'g':
        return 'g'
    return 'b'


def is_all_same_elements(es):
    return all([e == es[0] for e in es[1:]]) if es else False

class State:
    def __init__(self, sequence):
        self.colors = list(sequence)
        self.label = sequence
        self.depth = 0

    def nextStates(self):
        nextStates = []
        for i in range(1, len(self.colors)):
            if self.colors[i] != self.colors[i - 1]:
                c = another_color(self.colors[i], self.colors[i - 1])
                newColors = copy.copy(self.colors)
                newColors[i] = c
                newColors[i - 1] = c
                nextStates.append(State(''.join(newColors)))
        return nextStates

    def print(self):
        print(self.depth)
        # for debug
#         print("{} {}".format(self.label, self.depth))


sequence = input()
while sequence != '0':
    root = State(sequence)
    printed = False
    visited = [root.label]
    queue = deque([])
    queue.append(root)
    # BFS
    while queue:
        state = queue.popleft()
        if is_all_same_elements(state.colors):
            state.print()
            printed = True
            break
        for nextState in state.nextStates():
            if not nextState.label in visited:
                visited.append(nextState.label)
                nextState.depth = state.depth + 1
                queue.append(nextState)

    if not printed:
        print("NA")
    # 次の行へ
    sequence = input()