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
}

C++: // 2011/02/23 Tazoe

#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;

struct change{
	string dat;
	int tim;
};

int main()
{
	while(true){
		struct change wor;
		cin >> wor.dat;
		if(wor.dat=="0")
			break;
		wor.tim = 0;

		queue<struct change> que;
		que.push(wor);

		map<string, bool> mem;

		int cost;
		while(true){
			if(que.empty()){
				cost = -1;
				break;
			}

			wor = que.front();
			que.pop();
//			cout << wor.dat << ' ' << wor.tim << endl;

			if(mem[wor.dat])
				continue;
			mem[wor.dat] = true;

			bool flg = true;
			for(int i=1; i<wor.dat.size(); i++)
				if(wor.dat[i]!=wor.dat[0]){
					flg = false;
					break;
				}
			if(flg){
				cost = wor.tim;
				break;
			}

			struct change tmp;
			for(int i=0; i<wor.dat.size()-1; i++)
				if(wor.dat[i]==wor.dat[i+1])
					continue;
				else if(wor.dat[i]!='r'&&wor.dat[i+1]!='r'){
					tmp.dat = wor.dat;
					tmp.dat[i] = tmp.dat[i+1] = 'r';
					tmp.tim = wor.tim+1;
					que.push(tmp);
				}
				else if(wor.dat[i]!='g'&&wor.dat[i+1]!='g'){
					tmp.dat = wor.dat;
					tmp.dat[i] = tmp.dat[i+1] = 'g';
					tmp.tim = wor.tim+1;
					que.push(tmp);
				}
				else if(wor.dat[i]!='b'&&wor.dat[i+1]!='b'){
					tmp.dat = wor.dat;
					tmp.dat[i] = tmp.dat[i+1] = 'b';
					tmp.tim = wor.tim+1;
					que.push(tmp);
				}
		}

		if(cost==-1)
			cout << "NA" << endl;
		else
			cout << cost << endl;
	}

	return 0;
}

C++: #include<iostream>
#include<deque>
#include<cmath>
using namespace std;

int s_i(string str){
  int ans = 0;
  int tmp = 1;
  for(int i=0;i<str.size();i++){
    if(str[i] == 'g')ans += tmp;
    else if(str[i] == 'b')ans += 2 * tmp;
    tmp *= 3;
  }
  return ans;
}
int main(){
  string worm,tmp;
  deque<string> open,open2;
  char first;
  int ans,max;
  bool flag;
  bool check[100000];

  while(1){
    cin >> worm;
    if(worm == "0")break;

    max = 1;
    for(int i=0;i<worm.size();i++)max *= 3;
    for(int i=0;i<max;i++)check[i] = false;

    open.clear();
    open2.clear();

    open.push_back(worm);
    check[s_i(worm)] = true;
    ans = 0;

    while(1){
      while(open.size()){
	worm = open[0];
	open.pop_front();
	
	flag = true;
	first = worm[0];
	for(int i=1;i<worm.size();i++){
	  if(worm[i]!=first){
	    flag = false;
	    break;
	  }
	}
	if(flag)break;
	
	for(int i=0;i<worm.size()-1;i++){
	  if(worm[i]!=worm[i+1]){
	    tmp = worm;
	    if(worm[i]!= 'r' && worm[i+1] != 'r')tmp[i] = tmp[i+1] = 'r';
	    else if(worm[i]!= 'g' && worm[i+1] != 'g')tmp[i] = tmp[i+1] = 'g';
	    else if(worm[i]!= 'b' && worm[i+1] != 'b')tmp[i] = tmp[i+1] = 'b';
	    if(!check[s_i(tmp)]){
	      check[s_i(tmp)] = true;
	      open2.push_back(tmp);
	    }
	  }
	}
      }
      if(flag)break;
      if(!open2.size())break;
      open = open2;
      open2.clear();
      ans++;
    }
    if(flag)cout << ans << endl;
    else cout << "NA" << endl;
  }
}

C++: #include <iostream>
#include <queue>
#include <cctype>
#include <stdio.h>
#include <map>
using namespace std;

void bfs(string worm);
char jump(char c1, char c2);
int main(int argc, char const* argv[])
{
    string worm;
    while ( cin >> worm ) {
        if( worm == "0" ) { break; }
        else
        {
            bfs(worm);
        }
    }
    return 0;
}


void bfs(string worm){
    //puts("enter bfs");
    queue<string> q;
    string str;
    map<string, int> dis;
    q.push(worm); 
    dis[worm] = 0;

    while ( q.size() != 0 ) 
    {
        //puts("enter while");
        //一つ取り出す
        str = q.front(); q.pop();

        //終了判定
        bool is_same = true;
        for( int i=0; i<str.length()-1; i++)
        {
            //cout << 
            if( str[i] != str[i+1]) { is_same = false; continue; }
        }
        if ( is_same == true ) 
        {
            cout << dis[str] << endl;
            return;
        }
        //cout<<"worm:" << worm<< endl;
        //cout<<"str:" << str << endl;
        //cout<<"time:" << time << endl;

        //色が違ったらpush
        for(int i=0; i<str.size()-1; i++){
            //隣が色違い
            //puts("enter while");
            if( str[i] != str[i+1])
            {
                string next_str = str;
                next_str[i] = next_str[i+1] = jump(str[i], str[i+1]);
                //まだ通ってない
                if ( dis.find(next_str) == dis.end() )
                {
                    q.push(next_str);
                    dis[next_str] = dis[str] + 1;
                }
                else { continue; }
            }
        }
    }
    cout << "NA" << endl;
}

char jump(char c1, char c2){
    if(c1 != 'r' && c2 != 'r')
    {
        return 'r';
    }
    else if(c1 != 'g' && c2 != 'g')
    {
        return 'g';
    }
    else if(c1 != 'b' && c2 != 'b')
    {
        return 'b';
    }
}