12
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
11
  • 3
    \$\begingroup\$ "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. \$\endgroup\$
    – Fabinout
    Commented Jan 3, 2014 at 16:16
  • 7
    \$\begingroup\$ 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". \$\endgroup\$
    – Vereos
    Commented Jan 3, 2014 at 16:18
  • 5
    \$\begingroup\$ If regexes are "not even useful", why do you ban them? \$\endgroup\$
    – J B
    Commented Jan 3, 2014 at 17:01
  • 1
    \$\begingroup\$ Regex restriction removed. \$\endgroup\$
    – Vereos
    Commented Jan 3, 2014 at 18:59
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – apsillers
    Commented Jan 4, 2014 at 14:47

12 Answers 12

Reset to default
7
\$\begingroup\$

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)*[12]?$/
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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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)

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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[1]+(a<13?'':a[1]):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[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)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Perl - 50 (+2) bytes

$a-=print while"$_"ne(s/(.)(.)/$2x$1/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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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;}?>

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

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)

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ CodeGolf is not about finding the most complicated solution, but rather the most simple. \$\endgroup\$
    – primo
    Commented Jan 17, 2014 at 11:51
  • \$\begingroup\$ You don't really need to do str_split since you can access individual characters in a string just like an array in PHP. \$\endgroup\$
    – Gareth
    Commented Feb 11, 2014 at 12:26
  • \$\begingroup\$ Yeah, after some time I thought that myself, but I was too lazy to edit it. But now I changed it. \$\endgroup\$
    – Leo Pflug
    Commented Feb 11, 2014 at 12:45
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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}
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.