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.

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

13 Answers 13

-2
\$\begingroup\$

GTB, 25 24 26 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
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – FireFly Feb 11 '14 at 15:43
  • 3
    \$\begingroup\$ @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? \$\endgroup\$ – FireFly Feb 11 '14 at 16:19
  • 1
    \$\begingroup\$ @TimTech, there are people complaining about your answer: meta.codegolf.stackexchange.com/questions/988/… \$\endgroup\$ – Victor Stafusa Feb 13 '14 at 8:53
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ – Gareth Feb 13 '14 at 14:17
  • 8
    \$\begingroup\$ -1 for a wrong solution... \$\endgroup\$ – Doorknob Mar 15 '14 at 2:38
6
\$\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.

\$\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
\$\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
\$\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)

\$\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)
\$\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
\$\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)

\$\endgroup\$
  • 1
    \$\begingroup\$ CodeGolf is not about finding the most complicated solution, but rather the most simple. \$\endgroup\$ – primo Jan 17 '14 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 Feb 11 '14 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 Feb 11 '14 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
\$\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
\$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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