# 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

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


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. – Fabinout Jan 3 '14 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". – Vereos Jan 3 '14 at 16:18
• If regexes are "not even useful", why do you ban them? – J B Jan 3 '14 at 17:01
• Regex restriction removed. – Vereos Jan 3 '14 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. – apsillers Jan 4 '14 at 14:47

## GTB, 25 2426 characters

0→X_[@_="1":X+1→X@_≠"]~X


Explanation

• 0→X Put 0 in X (remember GTB adds a colon at the front of every program)
• _ Input into string _
• [ Start loop
• @_="1" Test if case is finished, if so X+1→X
• @_≠" If not empty, keep looping
• ~X After finished, display X
• I wrote a simple GTB compiler. Your program seems to compile to 0→X:Input Str0:Lbl 0::If Str0="1":X+1→X:If Str0≠":Goto 0::Disp X, correct? This doesn't seem to solve the task at all. – FireFly Feb 11 '14 at 15:43
• @Timtech Hm, I tried it on my TI-84 and it complained about "invalid dim" for the empty string. Anyway, the problem specifies that one should apply a tranformation repeatedly while counting the number of steps needed to reach a fixpoint (a point where the tranformation doesn't change the string). Did you try the testcases in the problem description as input to your program? – FireFly Feb 11 '14 at 16:19
• @TimTech, there are people complaining about your answer: meta.codegolf.stackexchange.com/questions/988/… – Victor Stafusa Feb 13 '14 at 8:53
• @Victor Actually, I was wondering whether or not it a) works and b) meets the requirements as given in the question. As FireFly points out, the code created by following the translations on this page throws an error. I wanted to be sure before saying anything though and that raised the larger question of whether untestable languages should be valid (which is the actual question on meta you've linked to). My understanding of the program leads me to believe it will just output the number of steps and not each step - Your code should print every step. – Gareth Feb 13 '14 at 14:17
• -1 for a wrong solution... – Doorknob Mar 15 '14 at 2:38

# Ruby 1.9+, 73 characters

I see the no-regex rule as silly and arbitrary, so here's a spiteful regex based solution:

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


Test run:

$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. – primo Jan 17 '14 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. – Gareth Feb 11 '14 at 12:26 • Yeah, after some time I thought that myself, but I was too lazy to edit it. But now I changed it. – Leo Pflug Feb 11 '14 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}