# Shrink a number string

Given a string of 1 and 2 of any length, write some code (doesn't have to be a function anymore, everything will be just fine) that calculates how many steps does it need to shrink the string to a final form, following this criterion:

If your string is 112112, this means that you have to print a 1, two 1s and a 2, like this: 1112. When you'll perform the operation again you'll have to print a 1 and a 2. You get 12. Then you print one 2, obtaining 2. This is a final form, since this string is not going to change anymore. Your code will output 3, since you needed 3 steps to get to the final form.

Other Rules

• If the string has uneven length, the last number remains untouched.

• Every string that cannot change anymore (like 222222) is considered a final form.

• You cannot use any external source.

• Your code must work with every string of 1 and 2.

• Shortest code wins, as it is code-golf.

• Your code should print every step.

• Every input method will be fine.

Examples

Input >> 122122122121212212

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

22222211
2222221
2
---- ---- ---- ----
Input >> 2222

0


EDIT: Heavily edited. So sorry about that.

• "If your string is 112112, this means that you have to print a 1, two 1s and a 2, like this: 1112. " I don't get it. Jan 3, 2014 at 16:16
• Try to read it loudly. It's "one one", "two ones" and "one two". I mean, "1 time 1", "2 times 1" and "1 time 2". Jan 3, 2014 at 16:18
• If regexes are "not even useful", why do you ban them?
– J B
Jan 3, 2014 at 17:01
• Regex restriction removed. Jan 3, 2014 at 18:59
• @ProgramFOX "one 1, two 1s, and a 2": 1 11 2. Every two numbers is a pair: the first number of the pair says how many times to render the second number in the pair. Any final odd digit without a pair partner is rendered as-is. Jan 4, 2014 at 14:47

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

$ruby 21.rb <<< 122122122121212212 211222111111222 11222111222 122111222 2111222 111222 1222 222 7  The last line is the number of steps. Edit: Regex restriction has been removed by Vereos. ## C - 156 154 My first code golf here! 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);}  Test: char c[] = "12211122211222221"; f(c,0);  Output: 12211122211222221 21112211222221 111221222211 121122221 21222211 1122221 122221 22211 22111 2211 221 10  ## GolfScript: 69 characters 0\{\)\.p.[]\{~10base{.,1>{($$@\{''+*}++~@\+\.}{~+0.}if}do;}~.@=!}do;(  Every iteration of the inner loop finds the first 2 numbers in the string, and use them to form a block of the form {num1 num2 '' + *}. When this block is evaluated, we get the desired reading of those numbers. Repeat this until there are no more characters. Then, repeat that loop while keeping track of the number of iterations and printing. Sample: 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  This doesn't print the input value. If it needs to, then move print s; to right before n=""; Note: you said "function", so this is a function. Here is a version that is not a function (127 chars): 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  (If I can have the user paste the number in then 118 (paste data between quotes on first line)): 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  Sample run: 211222111111222 11222111222 122111222 2111222 111222 1222 222 7  As a bonus, each of these solutions work for strings containing larger numbers (up to 9), but some strings produce larger and larger outputs (for example, 99) # JavaScript, 107 (requires arrow function support, e.g. as in Firefox) for(p=prompt,s=p(),k=0;r=s.match(/.?.?/g).map(a=>a>2?a+(a<13?'':a):a).join(''),p(s),r!=s;s=r)k++;p(k)  • s is the input string • Each round, we use the regex .?.? to explode s into an array of two-character strings, then map those strings into their reduced forms and glue the array back together • r stores the result of the current round for comparison against the previous s • k is the round counter • We horribly abuse prompt (aliased to p) as both an input and output mechanism, since it can present a message to the user for(p=prompt,s=p(),k=0; r=s.match(/.?.?/g).map( a=> a>2? // if a is more than one char a+(a<13?'':a) // 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/(.)(.)/2x1/ge,_);_=-a  Requires -pl command line switches. Sample usage:  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++){echoh.'<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];}returns;}?>  211222111111222 11222111222 122111222 2111222 111222 1222 222 7  I'm kinda bad at codegolf ._. Maybe I shouldn't use only Java and PHP (and I should think more complicated) • CodeGolf is not about finding the most complicated solution, but rather the most simple. Jan 17, 2014 at 11:51 • You don't really need to do str_split since you can access individual characters in a string just like an array in PHP. Feb 11, 2014 at 12:26 • Yeah, after some time I thought that myself, but I was too lazy to edit it. But now I changed it. Feb 11, 2014 at 12:45 ## 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)  Example: 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 Based on Vereos's response " You can use whatever input method shortens your code" to my question in the comments of the OP, the following script achieves the result: a  Example run for "122122122121212212": # 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  Obviously this isn't a serious entry - it's purpose is to illustrate my point that allowing any input method can trivialize the actual code needed to yield the answer. Hence the input method needs to be more rigorously specified. ## J, 41 chars As a function (ew parens! not terribly happy about them): (,":@#)@}:@(([:;_2&(<@((".@[#])/)$$)^:a:)  Exploded view  _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)  Sample run  (,":@#)@}:@(([:;_2&(<@((".@[#])/)\))^:a:) '1121121' 1121121 11121 121 21 11 5 (,":@#)@}:@(([:;_2&(<@((".@[#])/)\))^:a:) '122122122121212212' 122122122121212212 211222111111222 11222111222 122111222 2111222 111222 1222 7  # Perl, 107 chars The other perl code clearly beats this, but for what it's worth, here it is. I used the -l switch at the cost of an extra character: $_=<>;while(1){$l=$_;$_=join"",map{($a,$b)=split//;$b?$b x$a:$a}grep/./,split/(..?)/;last if$l eq$_;print}  A more legible version of that: $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}