Dada uma sequência de 1e 2de qualquer comprimento, escreva algum código (não precisa mais ser uma função , tudo ficará bem) que calcula quantas etapas é necessário para encolher a sequência para uma forma final, seguindo este critério:

Se a seqüência é 112112, isso significa que você tem que imprimir a 1, dois 1s e a 2, como este: 1112. Quando você realizar a operação novamente, precisará imprimir 1 e 2. Você recebe 12. Então você imprime um 2, obtendo 2. Esta é uma forma final, pois essa sequência não será mais alterada. Seu código será exibido 3, pois você precisou de três etapas para chegar ao formulário final.

Outras regras

• Se a sequência tiver um comprimento irregular, o último número permanecerá intocado.

• Toda string que não pode mais mudar (como 222222) é considerada uma forma final.

• Você não pode usar nenhuma fonte externa.

• Seu código deve funcionar com todas as cadeias de caracteres 1e 2.

• O código mais curto vence, pois é um código de golfe.

• Seu código deve imprimir todas as etapas.

• Todo método de entrada ficará bem.

Exemplos

Input >> 122122122121212212

Your code has to print:
211222111111222
11222111222
122111222
2111222
111222
1222
222
Steps:7 (you can omit the "Steps")
---- ---- ---- ----
Input >> 22222221

Your code has to print:
22222211
2222221
2
---- ---- ---- ----
Input >> 2222

Your code has to print:
0

Edição: Pesadamente editado. Sinto muito por isso.

Ruby 1.9+, 73 caracteres

Eu vejo a regra no-regex como boba e arbitrária, então aqui está uma solução baseada em regex rancorosa :

gets
($.+=1;puts$_.gsub!(/(.)(.)/){$2*$1.to_i})until~/^(22)*[12]?$/
p~-$.

Execução de teste:

$ ruby 21.rb <<< 122122122121212212
211222111111222
11222111222
122111222
2111222
111222
1222
222
7

A última linha é o número de etapas.

Editar: a restrição Regex foi removida pela Vereos.

C - 156 154

Meu primeiro código de golfe aqui!

f(char*s,c){puts(s);char*a=s,*b=s,m=50,x,y;while(*a){
x=*a++;y=*a++;if(y)m&=x&y;*b++=y?:x;x-49?*b++=y:(*b=0);}
*b=*a;return m/50?printf("%i",c),c:f(s,c+1);}

Teste:

char c[] = "12211122211222221";
f(c,0);

Resultado:

12211122211222221
21112211222221
111221222211
121122221
21222211
1122221
122221
22211
22111
2211
221
10

GolfScript: 69 caracteres

0\{\)\.p.[]\{~10base{.,1>{(\(@\{''+*}++~@\+\.}{~+0.}if}do;}~.@=!}do;(

Toda iteração do loop interno localiza os 2 primeiros números da string e os utiliza para formar um bloco do formulário {num1 num2 '' + *}. Quando esse bloco é avaliado, obtemos a leitura desejada desses números. Repita isso até que não haja mais caracteres. Em seguida, repita esse loop, mantendo o controle do número de iterações e impressões.

Amostra:

echo '12211122211222221' | ruby golfscript.rb g.gs
"12211122211222221"
"21112211222221"
"111221222211"
"121122221"
"2122221"
"1122221"
"122221"
"22211"
"22111"
"2211"
"221"
10

Python - 126

def f(s):
 j=0
 while 1:
    n="";i=0
    for c in s:n+=c*i;i=[int(c),0][i>0]
    if i:n+=`i`
    if s==n:break
    s=n;print s;j+=1
 print j

Isso não imprime o valor de entrada. Se necessário, vá print s;para a direita antes den="";

Nota: você disse "função", então esta é uma função. Aqui está uma versão que não é uma função (127 caracteres):

s=raw_input();j=0
while 1:
    n="";i=0
    for c in s:n+=c*i;i=[int(c),0][i>0]
    if i:n+=`i`
    if s==n:break
    s=n;print s;j+=1
print j

(Se eu puder fazer com que o usuário cole o número em 118 (cole dados entre aspas na primeira linha)):

s="";j=0
while 1:
    n="";i=0
    for c in s:n+=c*i;i=[int(c),0][i>0]
    if i:n+=`i`
    if s==n:break
    s=n;print s;j+=1
print j

Exemplo de execução:

211222111111222
11222111222
122111222
2111222
111222
1222
222
7

Como bônus, cada uma dessas soluções funciona para cadeias que contêm números maiores (até 9), mas algumas cadeias produzem saídas cada vez maiores (por exemplo, 99)

JavaScript, 107

(requer suporte à função de seta, por exemplo, como no Firefox)

for(p=prompt,s=p(),k=0;r=s.match(/.?.?/g).map(a=>a>2?a[1]+(a<13?'':a[1]):a).join(''),p(s),r!=s;s=r)k++;p(k)

• s é a sequência de entrada

• A cada rodada, usamos o regex .?.?para explodir sem uma série de seqüências de caracteres de dois caracteres, depois mapas seqüências em suas formas reduzidas e colar a matriz novamente

• r armazena o resultado da rodada atual para comparação com o anterior s

• k é o contador redondo

• Nós abusamos horrivelmente prompt(com alias de p) como um mecanismo de entrada e saída, pois ele pode apresentar uma mensagem ao usuário

for(p=prompt,s=p(),k=0;
    r=s.match(/.?.?/g).map(
        a=>
            a>2?                     // if a is more than one char
                a[1]+(a<13?'':a[1])  // double the second char if the first char is 2
               :a                    // if not two chars, return a
    ).join(''),                      // glue new array together
     p(s),                           // print s
     r!=s;                           // test if string has changed
    s=r)
        k++;
p(k)

Perl - 50 (+2) bytes

$a-=print while"$_"ne(s/(.)(.)/$2x$1/ge,$_);$_=-$a

Requer -plopções de linha de comando.

Uso da amostra:

$ more in.dat
122122122121212212

$ perl -pl rev-count.pl < in.dat
211222111111222
11222111222
122111222
2111222
111222
1222
222
7

$ more in.dat
22222221

$ perl -pl rev-count.pl < in.dat
22222211
2222221
2

$ more in.dat
2222

$ perl -pl rev-count.pl < in.dat
0

PHP, 240

<?php
$s=$_GET['i'];$h=$s;for($t=1;$h!=r($h);$t++){echo$h.'<br>';$h=r($h);}echo r($s)==$s?0:$h.'<br>'.$t;function r($c){for($i=0;$i<strlen($c)-1;$i+=2){$s.=$c[$i]==1?$c[$i+1]:$c[$i+1].$c[$i+1];if($i+3==strlen($c))$s.=$c[$i+2];}return$s;}?>

Exemplo: http://skyleo.de/codegolf.php?i=211222111111222

211222111111222
11222111222
122111222
2111222
111222
1222
222
7

Eu sou meio ruim em codegolf ._. Talvez eu não deva usar apenas Java e PHP (e devo pensar mais complicado)

R, 158

s=utf8ToInt(scan(,""))-48;i=0;while(any(!!s-2)){t=(a<-sum(s|T))%%2;u=s[seq(a-t)];cat(s<-c(rep(u[c(F,T)],u[c(T,F)]),s[a*t]),"\n",sep="");i=i+1};cat("Steps:",i)

Exemplo:

122122122121212212

211222111111222
11222111222
122111222
2111222
111222
1222
222
Steps: 7

MATHEMATICA, 117

s="122122122121212212";
Grid@FixedPointList[(Partition[#,2,2,1,{}]/.{{1,1}->{1},{1,2}->{2},{2,1}->{1,1}}//Flatten)&,FromDigits/@Characters@s]

122122122121212212
211222111111222
11222111222
122111222
2111222
111222
1222
222
222

POWERSHELL, 2

Com base na resposta da Vereos "Você pode usar qualquer método de entrada que encurte seu código" à minha pergunta nos comentários do OP, o seguinte script alcança o resultado:

$a

Exemplo de execução para "12212212212121221212":

# Input method is to assign answer to $a:
$a = @"
211222111111222
11222111222
122111222
2111222
111222
1222
222
Steps: 7
"@

# Execute script
$a

# Answer follows:
211222111111222
11222111222
122111222
2111222
111222
1222
222

Obviamente, essa não é uma entrada séria - seu objetivo é ilustrar meu argumento de que permitir que qualquer método de entrada possa trivializar o código real necessário para fornecer a resposta. Portanto, o método de entrada precisa ser especificado com mais rigor.

J, 41 caracteres

Como uma função (ew parens! Não muito feliz com eles):

(,":@#)@}:@(([:;_2&(<@((".@[#])/)\))^:a:)

                _2&(            )\          NB. on non-overlapping 2-grams:
                       (      )/            NB.   insert between the two chars:
                        ".@[                NB.     read left operand ([) as a number
                            #]              NB.     and repeat right this many times,
                    <@(           )         NB.   then put it in a box
            ([:;                   )        NB. open and concatenate the boxes
           (                        ^:a:)   NB. repeat until fixpoint (keeping intermediates)
        }:@                                 NB. drop first element (the input)
(,":@#)@                                    NB. append length of array (# steps)

   (,":@#)@}:@(([:;_2&(<@((".@[#])/)\))^:a:) '1121121'
1121121
11121  
121    
21     
11     
5      
   (,":@#)@}:@(([:;_2&(<@((".@[#])/)\))^:a:) '122122122121212212'
122122122121212212
211222111111222   
11222111222       
122111222         
2111222           
111222            
1222              
7                 

Perl, 107 caracteres

O outro código perl claramente supera isso, mas pelo que vale a pena, aqui está. Eu usei a opção -l ao custo de um caractere extra:

$_=<>;while(1){$l=$_;$_=join"",map{($a,$b)=split//;$b?$b x$a:$a}grep/./,split/(..?)/;last if$l eq$_;print}

Uma versão mais legível disso:

$x = <>; while(1) { $l = $x; $x = join "", map{ ($a,$b) = split//, $_; $b ? $b x $a: $a } grep /./, split /(..?)/, $x; last if $l eq $x; print $x}