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++: #include<vector>
#include<string>
#include<set>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
bool ck(string &s){
	rep(k,s.size()-1)if(s[k]!=s[k+1])return 0;
	return 1;
}
int main(){
	string s;
	while(cin>>s,s!="0"){
		int step=0; bool sc=ck(s);
		vector<string> frontier,next;
		frontier.push_back(s);
		set<string> visited; visited.insert(s);
		for(bool cg=1;cg&&!sc;step++){
			cg=0; next.clear();
			rep(i,frontier.size()){
				rep(j,frontier[i].size()-1){
					char c,cc=frontier[i][j],cn=frontier[i][j+1];
					if(cc==cn)continue;
					if(cc>cn)swap(cc,cn);
					if(cc=='b')c=cn=='g'?'r':'g';
					else c='b';
					
					string nx=frontier[i];
					nx[j]=nx[j+1]=c;
					if(visited.find(nx)==visited.end()){
						cg=1;
						sc=sc||ck(nx);
						next.push_back(nx),visited.insert(nx);
					}
				}
			}
			frontier=next;
		}
		if(sc)cout<<step<<endl;
		else cout<<"NA"<<endl;
	}
	return 0;
}

C++: #include <iostream>
#include <string>
#include <queue>
#include <map>

using namespace std;



int main()
{
    map<string, string> ct;
    ct["rr"] = "rr";
    ct["rb"] = "gg";
    ct["rg"] = "bb";

    ct["gr"] = "bb";
    ct["gg"] = "gg";
    ct["gb"] = "rr";

    ct["br"] = "gg";
    ct["bg"] = "rr";
    ct["bb"] = "bb";
    
    for(;;) {
        string in;
        cin >> in;

        if ( in == "0" )
            break;

        std::map<string, bool> correct;
        correct[string(in.size(), 'r')] = true;
        correct[string(in.size(), 'g')] = true;
        correct[string(in.size(), 'b')] = true;

        int result_times = 0;

        queue<pair<int, string> > q;
        q.push( make_pair( 0, in ) );

        map<string, bool> memo;
        bool goal = false;

        // loop
        while( !q.empty() ) {
            int const times = q.front().first;
            string const s = q.front().second;
            q.pop();

            //cout << gtimes << endl;
            if ( correct[s] ) {
                goal = true;
                result_times = times;
                break;
            } 

            for( size_t i=0; i<s.size()-1; ++i ){
                string const pa = s.substr( i, 2 );
                string const t = s.substr( 0, i ) + ct[pa] + s.substr( i + 2 );

                if ( t == s )
                    continue;
                if ( memo[t] )
                    continue;

                memo[t] = true;

                q.push( make_pair( times + 1, t ) );
            }
        }

        // put
        if ( goal ) {
            cout << result_times << endl;
        } else {
            cout << "NA" << endl;
        }
    }
}

C++: #include <iostream>
#include <string>
#include <queue>
#include <set>

using namespace std;

void solve()
{
	string str;
	while(cin >> str)
	{
		if(str == "0")
		{
			break;
		}
		queue<string> Que;
		Que.push(str);
		queue<string> NextQue;
		int depth = 0;
		set<string> Valiation;
		Valiation.insert(str);
		while(true)
		{
			if(depth >= 20)
			{
				cout << "NA" << endl;
				break;
			}
			while(!Que.empty())
			{
				string worm = Que.front();
				Que.pop();
				bool same_color_flag = true;
				for(int i = 1; i < worm.size(); ++i)
				{
					if(worm[i] != worm[0])
					{
						same_color_flag = false;
					}
				}
				if(same_color_flag)
				{
					cout << depth << endl;
					goto END;
				}
				char before_color = worm[0];
				for(int i = 1; i < worm.size(); ++i)
				{
					if(before_color != worm[i])
					{
						string next = worm;
						if(before_color == 'b')
						{
							if(worm[i] == 'g')
							{
								next[i - 1] = 'r';
								next[i] = 'r';
							}
							else if(worm[i] == 'r')
							{
								next[i - 1] = 'g';
								next[i] = 'g';
							}
						}
						else if(before_color == 'g')
						{
							if(worm[i] == 'b')
							{
								next[i - 1] = 'r';
								next[i] = 'r';
							}
							else if(worm[i] == 'r')
							{
								next[i - 1] = 'b';
								next[i] = 'b';
							}
						}
						else if(before_color == 'r')
						{
							if(worm[i] == 'g')
							{
								next[i - 1] = 'b';
								next[i] = 'b';
							}
							else if(worm[i] == 'b')
							{
								next[i - 1] = 'g';
								next[i] = 'g';
							}
						}
						if(Valiation.find(next) == Valiation.end())
						{
							NextQue.push(next);
							Valiation.insert(next);
						}
					}
					before_color = worm[i];
				}
			}
			while(!NextQue.empty())
			{
				Que.push(NextQue.front());
				NextQue.pop();
			}
			++depth;
		}
END:
		;
	}
}

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