Go: package main

import (
    "bufio"
    "os"
    "fmt"
)

var sc = bufio.NewScanner(os.Stdin)

/**************  Cell  *****************/
type Cell struct {
    item interface{}
    next *Cell
    prev *Cell
}

func NewCell(x interface{}, ne *Cell, pr *Cell) *Cell {
    newCp := new(Cell)
    newCp.item = x
    newCp.next = ne
    newCp.prev = pr
    return newCp
}
/************  End Cell  ***************/

/**************  Queue  ****************/
type Queue struct {
    size int
    front *Cell
    rear *Cell
}

func NewQueue() *Queue {
    return new(Queue)
}

func (q *Queue) Push(x interface{}) {
    newNode := NewCell(x, nil, nil)
    if q.size == 0 {
        q.front = newNode
        q.rear = newNode
    } else {
        newNode.prev = q.rear
        q.rear.next = newNode
        q.rear = newNode
    }
    q.size++
}

func (q *Queue) PopLeft() interface{} {
    if q.size == 0 {
        return nil
    } else {
        x := q.front.item
        if q.size == 1 {
            q.front = nil
            q.rear = nil
        } else {
            q.front = q.front.next
            q.front.prev = nil
        }
        q.size--
        return x
    }
}

func (q *Queue) IsEmpty() bool {
    return q.size == 0
}

func (q *Queue) Length() int {
    return q.size
}

type State struct {
    color string
    cnt int
}

func main() {
    for {
        sc.Scan()
        init := sc.Text()
        if init == "0" {
            break
        }
        bfs(init)
    }
}

func bfs(init string) {
    dic := make(map[string]int)
    que := NewQueue()
    que.Push(State{init, 0})
    length := len(init)
    isSolved := false
    for !que.IsEmpty() {
        state := que.PopLeft().(State)
        _, ok := dic[state.color]
        if ok {
            continue
        } else {
            dic[state.color] = state.cnt
        }

        if isSingleColor(state.color) {
            fmt.Println(state.cnt)
            isSolved = true
            break
        }

        for i := 0;i < length - 1; i++ {
            color1, color2 := string(state.color[i]), string(state.color[i + 1])
            if color1 != color2 {
                color3 := other(color1, color2)
                if i <= length - 2 {
                    que.Push(State{state.color[:i] + color3 + state.color[i + 2:], state.cnt + 1})
                } else {
                    que.Push(State{state.color[:i] + color3, state.cnt + 1})
                }
            }
        }
    }
    if !isSolved {
        fmt.Println("NA")
    }
}

func other(color1, color2 string) string {
    if color1 == "r" {
        if color2 == "g" {
            return "bb"
        } else if color2 == "b" {
            return "gg"
        }
    } else if color1 == "g" {
        if color2 == "r" {
            return "bb"
        } else if color2 == "b" {
            return "rr"
        }
    } else if color1 == "b" {
        if color2 == "r" {
            return "gg"
        } else if color2 == "g" {
            return "rr"
        }
    }
    return ""
}

func isSingleColor(color string) bool {
    for _, c := range color {
        if string(c) != string(color[0]) {
            return false
        }
    }
    return true
}

Python: 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()

Python: 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

Python: 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)