17
\$\begingroup\$

You should all be familiar with the Conway sequence (a.k.a. 'look-and-say'-sequence) by now:

     1
    11
    21
  1211
111221
312211
etc

You can also start by any arbitrary number as starting point. Let f(s) be the next element of the sequence. Now for every given swe can find f(s). The reverse is not as trivial: it is not for every y possible to find the predecessor s such that f(s) = y. E.g. for y = 1 we cannot find a predecessor. But if y has an even length you can divide it into pairs of digits which describe each one part of a predecessor:

513211 divides in 51,32,11
so: 51 comes from 11111 
    32 comes from 222
    11 comes from 1
put together: 111112221

So this way there we can define an unique predecessor for every y of even length.

Note: The 'predecessor' s defined this way does generally NOT satisfy f(s) = y.

Goal

Write a function / program snippet that accepts a string of digits as input that

  • calculates the next element of the Conway sequence if the length of the input string is odd
  • calculates the predecessor of the input string as defined above if the input string length is even.

Shortest code in bytes wins.

Recent Questions based on the look-and-say sequences:

\$\endgroup\$
5
  • 1
    \$\begingroup\$ I'm confused. Can you explain how 513111 divides into 51, 32 and 11? \$\endgroup\$
    – r3mainer
    Nov 27, 2014 at 22:44
  • 1
    \$\begingroup\$ I feel like this is a combined duplicate of some look and say sequence challenge and a run-length decoding challenge (I'm sure we had those). \$\endgroup\$ Nov 27, 2014 at 22:57
  • 3
    \$\begingroup\$ What would the predecessor of 11111111111111 be? According to your spec, it would be 1111111. You should modify your specification to define a reasonable answer for this. \$\endgroup\$ Nov 27, 2014 at 23:44
  • 1
    \$\begingroup\$ @TheBestOne 11111111111111 simply has no predecessor. It's an illegal input. \$\endgroup\$
    – Kijewski
    Nov 28, 2014 at 0:37
  • 2
    \$\begingroup\$ @TheBestOne Yes this is correct, I defined an arbitrary rule for the predecessor that does not always match a 'real' predecessor. \$\endgroup\$
    – flawr
    Nov 28, 2014 at 9:19

16 Answers 16

5
\$\begingroup\$

Ruby, 125 120 119 101 bytes

f=->n{c=n.chars;(n.size%2>0?c.chunk{|x|x}.map{|a,b|[b.size,a]}:c.each_slice(2).map{|a,b|b*a.hex})*''}

String input taken through function f:

f['111221']    # => "1211"
f['513211']    # => "111112221"
f['111112221'] # => "513211"

Expanded with notes:

# define lambda that takes one arg
f = -> (n) {
  # store digits in c
  c = n.chars

  # n is of odd length
  if n.size % 2 > 0
    # group identical numbers
    c.chunk{ |x| x }.map do |a, b|
      # array of [digit count, digit value]
      [b.size, a]
    end
  else
    # slice array into groups of two elements
    c.each_slice(2).map do |a, b|
      # repeat the second digit in a pair
      # the first digit-times.
      b * a.hex
    end
  end * '' # join array
}
\$\endgroup\$
4
\$\begingroup\$

Prolog - 170 bytes

[]/[].
T/R:-0*_*T*R.
C*X*[X|T]*R:-(C+1)*X*T*R.
C*X*T*Y:-10*C+X+Y+R,T/R.
N+R+A:-N=:=0,A=R;D is N mod 10,N//10+R+[D|A].
F-C-R:-C/N,(N=F,R=C;F-N-R).
[1]-[1,1]. S-T:-S-[1]-T.

This snipped defines the function (-)/2. You can invoke it like

?- [1,1,1,3,2,1,3,2,1,1]-T.
T = [1, 3, 1, 1, 2, 2, 2, 1] .

?- [1]-T.
T = [1, 1] .

There seems to be only one lengths in this sequence with an odd parity: the initial [1].

wr_len :- wr_len(1, [1]).
wr_len(N, Cur) :-
    length(Cur, Len),
    TrailingZeroes is lsb(Len),
    (TrailingZeroes > 0 -> Par = 'even'; Par = 'odd'),
    writef('%t\t%t\t%t\t%t\n', [N, Len, Par, TrailingZeroes]),
    get_next(Cur, Next),
    succ(N, O),
    !, wr_len(O, Next).
% index, length, parity of length, num of trailing 0 in bin presentation of length
?- wr_len.
1       1       odd     0
2       2       even    1
3       2       even    1
4       4       even    2
5       6       even    1
6       6       even    1
7       8       even    3
8       10      even    1
9       14      even    1
10      20      even    2
11      26      even    1
12      34      even    1
13      46      even    1
14      62      even    1
15      78      even    1
16      102     even    1
17      134     even    1
18      176     even    4
19      226     even    1
20      302     even    1
21      408     even    3
22      528     even    4
23      678     even    1
24      904     even    3
25      1182    even    1
26      1540    even    2
27      2012    even    2
28      2606    even    1
29      3410    even    1
30      4462    even    1
31      5808    even    4
32      7586    even    1
33      9898    even    1
34      12884   even    2
35      16774   even    1
36      21890   even    1
37      28528   even    4
38      37158   even    1
39      48410   even    1
40      63138   even    1
41      82350   even    1
42      107312  even    4
43      139984  even    4
44      182376  even    3
45      237746  even    1
46      310036  even    2
47      403966  even    1
48      526646  even    1
49      686646  even    1
50      894810  even    1
51      1166642 even    1
52      1520986 even    1
53      1982710 even    1
54      2584304 even    4
55      3369156 even    2
56      4391702 even    1
57      5724486 even    1
58      7462860 even    2
59      9727930 even    1
ERROR: Out of global stack
% I added a few "strategic" cuts (`!`) to get so far.

Readable:

get_next([], []).
get_next(Current, Next) :-
    get_next_sub(0, _, Current, Next).

get_next_sub(Length, Digit, [Digit|Tail], Result) :-
    get_next_sub(Length+1, Digit, Tail, Result).
get_next_sub(Length, Digit, Further, Result) :-
    number_to_list(10*Length+Digit, Result, ResultTail),
    get_next(Further, ResultTail).

number_to_list(Number, Result, Accumulator) :-
    0 is Number -> Result = Accumulator;
    Digit is Number mod 10,
    number_to_list(Number // 10, Result, [Digit|Accumulator]).

get_previous(Stop, Current, Result) :-
    get_next(Current, Next),
    (   Next = Stop
    ->  Result = Current
    ;   get_previous(Stop, Next, Result)
    ).

get_prev_or_next(Input, Result) :-
    length(Input, Length),
    (   1 is Length mod 2
    ->  get_next(Input, Result)
    ;   get_previous(Input, [1], Result)
    ).
\$\endgroup\$
3
\$\begingroup\$

CJam, 46 45 44 43 42 bytes

l_,2%{0\{@)@@_2$=!{0\0}*;}*\)\}{2/{(~*}%}?

Test it here. It takes the number on STDIN and prints the result to STDOUT.

\$\endgroup\$
2
  • \$\begingroup\$ si -> ~ = 45 \$\endgroup\$
    – Optimizer
    Nov 28, 2014 at 14:19
  • \$\begingroup\$ @Optimizer Thanks, I forget you can eval a character. \$\endgroup\$ Nov 28, 2014 at 14:21
3
\$\begingroup\$

Python: 139 chars

import re
f=lambda s:''.join(['len(b)'+a for a,b in re.findall(r'((\d)\2*)',s)] if len(s)%2 else map(lambda a,b:b*int(a),s[::2],s[1::2]))

single test case

print f('1111122221111222112')
>>> 514241322112
print f('514241322112')
>>> 1111122221111222112
\$\endgroup\$
2
  • \$\begingroup\$ You can remove the space from s)] if to s)]if. \$\endgroup\$
    – Bakuriu
    Nov 30, 2014 at 8:38
  • \$\begingroup\$ You can also remove the space in between 2 else \$\endgroup\$
    – Beta Decay
    Nov 30, 2014 at 10:20
3
\$\begingroup\$

Haskell, 134 128 115

n=length
l x=x#mod(n x)2
(a:b:c)#0=replicate(read[a])b++c#0
(a:b)#1=(\(c,d)->show(1+n c)++a:d#1)$span(==a)b
_#_=[]

If it needs to be from stdin/stdout, add main=interact l for 150 144 131 total chars. The function is called l.

*Main> putStr . unlines $ map (\x->x++":\t"++l x) ([replicate n '1'|n<-[5..10]]++map show [0,6..30]++map show [n*n+n|n<-[2..10]])
11111:  51
111111: 111
1111111:    71
11111111:   1111
111111111:  91
1111111111: 11111
0:  10
6:  16
12: 2
18: 8
24: 44
30: 000
6:  16
12: 2
20: 00
30: 000
42: 2222
56: 66666
72: 2222222
90: 000000000
110:    2110
\$\endgroup\$
2
  • \$\begingroup\$ Could you please provide usage example? While I got l "11" to work, I get an exception with l "111" or l "1111111111111" \$\endgroup\$
    – Paul Guyot
    Nov 28, 2014 at 14:35
  • \$\begingroup\$ @PaulGuyot, Seems like fixing that cut a few chars off my score. Thanks :-) \$\endgroup\$
    – Zaq
    Nov 28, 2014 at 16:00
3
\$\begingroup\$

Perl - 98 bytes

The size of all these control statements bugs me, but I'm pretty happy with how the regexes worked out.

($_)=@ARGV;if(length()%2){$\=$&,s/^$&+//,print length$&while/^./}else{print$2x$1while s/^(.)(.)//}

Uncompressed:

($_)=@ARGV;
if(length()%2)
{
$\=$&, #Assigning the character to $\ causes it to be appended to the print (thanks, tips thread!)
s/^$&+//, #Extract the string of characters
print length$& #Print its length
while/^./ #Get next character into $&
}else{
print$2x$1
while s/^(.)(.)//
}
\$\endgroup\$
2
\$\begingroup\$

Erlang, 205

f(L)->g(L,L,[]).
g([A,B|T],L,C)->g(T,L,lists:duplicate(A-$0,B)++C);g([],_,R)->R;g(_,L,_)->i(L,[]).
h([A|T],A,N,B)->h(T,A,N+1,B);h(L,B,N,C)->i(L,integer_to_list(N)++[B|C]).
i([H|T],A)->h(T,H,1,A);i(_,R)->R.

Main function is f, taking the input as an Erlang string and returning the output as a string as well.

f("11"). % returns "1"
f("111"). % returns "31"
f("1111111111111"). % returns "131"

The function can be made 15 bytes shorter (190) by dropping the more than 9 identical characters case requirement. f calls g which computes the predecessor recursively, and if the number of characters is odd (found at when computation ends), it calls function i which, paired with h, computes the next element.

\$\endgroup\$
2
\$\begingroup\$

Haskell, 105

import Data.List
l=length
c r|odd$l r=group r>>=(l>>=(.take 1).shows)|x:y:z<-r=[y|_<-['1'..x]]++c z|0<1=r

I think it's nice it turned out not using any helper functions :-).

\$\endgroup\$
3
  • \$\begingroup\$ |x:y:z<-r - I totally did not know you could do that. That's so cool! \$\endgroup\$
    – Flonk
    Nov 28, 2014 at 17:35
  • \$\begingroup\$ @Flonk Its called "pattern guards". It used to be an extension and in one of the versions of Haskell it was added :-) \$\endgroup\$ Nov 28, 2014 at 17:40
  • \$\begingroup\$ This makes a lot of things so much easier. You learn something new every day! :) \$\endgroup\$
    – Flonk
    Nov 28, 2014 at 17:48
2
\$\begingroup\$

APL (45)

∊{2|⍴⍵:(⊃,⍨⍕∘⍴)¨⍵⊂⍨1,2≠/⍵⋄/⍨∘⍎/¨⌽¨⍵⊂⍨1 0⍴⍨⍴⍵}

Yes, that's a valid function definition, even with the on the outside.

      ∊{2|⍴⍵:(⊃,⍨⍕∘⍴)¨⍵⊂⍨1,2≠/⍵⋄/⍨∘⍎/¨⌽¨⍵⊂⍨1 0⍴⍨⍴⍵}'513211'
111112221
      ∊{2|⍴⍵:(⊃,⍨⍕∘⍴)¨⍵⊂⍨1,2≠/⍵⋄/⍨∘⍎/¨⌽¨⍵⊂⍨1 0⍴⍨⍴⍵}'111112221'
513211
      f←∊{2|⍴⍵:(⊃,⍨⍕∘⍴)¨⍵⊂⍨1,2≠/⍵⋄/⍨∘⍎/¨⌽¨⍵⊂⍨1 0⍴⍨⍴⍵}
      f ¨ '513211' '111112221'
┌─────────┬──────┐
│111112221│513211│
└─────────┴──────┘
\$\endgroup\$
2
\$\begingroup\$

Java 7, Score = 252 235 bytes

Yep, it's java again; the worst golfing language in the world. This approach uses strings. Arbitrarily large integers are supported in java but would take much more room to code in.

Call with f(intputString). Returns the corresponding string.

Golfed:

String f(String a){char[]b=a.toCharArray();a="";int i=0,j=0,d=0,e=b.length;if(e%2==0)for(;i<e;i+=2)for(j=0;j<b[i]-48;j++)a+=b[i+1];else{for(;i<e;i++)d=d==0?(j=b[i]-48)*0+1:b[i]-48!=j?(a+=d+""+j).length()*--i*0:d+1;a+=d;a+=j;}return a;}

Golfed Expanded with structure code:

public class LookAndSayExpandedGolfed{

    public static void main(String[] args){
        System.out.println(new LookAndSayExpandedGolfed().f(args[0]));
    }

    String f(String a){
        char[]b=a.toCharArray();
        a="";
        int i=0,j=0,d=0,e=b.length;
        if(e%2==0)
            for(;i<e;i+=2)
                for(j=0;j<b[i]-48;j++)
                    a+=b[i+1];
        else{
            for(;i<e;i++)
                d=d==0?(j=b[i]-48)*0+1:b[i]-48!=j?(a+=d+""+j).length()*--i*0:d+1;
            a+=d;
            a+=j;
        }
        return a;
    }

}

Partially Golfed:

public class LookAndSayPartiallyGolfed{

    public static void main(String[] args){
        System.out.println(new LookAndSayPartiallyGolfed().f(args[0]));
    }

    String f(String a){
        char[] number = a.toCharArray();
        String answer = "";
        int i, j, longestStreakLength = 0;
        if (number.length % 2 == 0){
            for (i = 0; i < number.length; i += 2)
                for (j = 0; j < number[i] - 48; j++)
                    answer += number[i+1];
        } else{
            j = 0;
            for (i = 0; i < number.length; i++)
                longestStreakLength = longestStreakLength == 0 ? (j = number[i] - 48) * 0 + 1 : number[i] - 48 != j ? (answer += longestStreakLength + "" + j).length()*--i*0 : longestStreakLength + 1;
            answer += longestStreakLength;
            answer += j;
        }
        return answer;
    }

}

Completely expanded:

public class LookAndSay{

    public static void main(String[] args){
        System.out.println(new LookAndSay().function(args[0]));
    }

    String function(String a){
        char[] number = a.toCharArray();
        if (number.length % 2 == 0){
            String answer = "";
            for (int i = 0; i < number.length; i += 2){
                for (int j = 0; j < number[i] - '0'; j++){
                    answer += number[i+1];
                }
            }
            return answer;
        }
        String answer = "";
        int longestStreakLength = 0;
        int longestStreakNum = 0;
        for (int i = 0; i < number.length; i++){
            if (longestStreakLength == 0){
                longestStreakNum = number[i] - '0';
                longestStreakLength = 1;
                continue;
            }
            if (number[i] - '0' != longestStreakNum){
                answer += longestStreakLength;
                answer += longestStreakNum;
                longestStreakLength = 0;
                i--;
            } else {
                longestStreakLength++;
            }
        }
        answer += longestStreakLength;
        answer += longestStreakNum;
        return answer;
    }

}

To run, first compile the second entry with: javac LookAndSayExpandedGolfed.java

Then run with: java LookAndSayExpandedGolfed

Edit: Fixed error.

\$\endgroup\$
8
  • \$\begingroup\$ Doesn't work for me, Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 4 at java.lang.String.charAt(String.java:658) \$\endgroup\$ Nov 30, 2014 at 4:18
  • \$\begingroup\$ @KenzieTogami Fixed. \$\endgroup\$ Nov 30, 2014 at 23:51
  • \$\begingroup\$ I don't think so, is --1 supposed to be --i? \$\endgroup\$ Dec 1, 2014 at 0:03
  • \$\begingroup\$ @KenzieTogamie Yes, it is. It's fixed now. \$\endgroup\$ Dec 1, 2014 at 0:33
  • \$\begingroup\$ Cool, that works. The reverser fails, however. 513211 -> 11111. \$\endgroup\$ Dec 1, 2014 at 0:59
1
\$\begingroup\$

Javascript (in-browser, ES5, IE8+), 152

var s=prompt(),r='',n=r,c=r,i=0;do{c!=s[i]?(r+=n+c,n=1,c=s[i]):n++;i++}while(c)n='';i=0;while(s[i]){n+=Array(1*s[i]+1).join(c=s[i+1]);i+=2}alert(c?n:r)

Can be shortened by 4 chars if you skip var, or a few more chars with other intermediate unvarred globals too, but let's pretend we are not bad programmers for a minute.

Switching to ES6 short-syntax function with argument and return value instead of using prompt, alert for IO can save more.

JSFiddle here: http://jsfiddle.net/86L1w6Lk/

\$\endgroup\$
1
  • 5
    \$\begingroup\$ Don't worry about those vars... we're all "bad programmers" here. ;) \$\endgroup\$ Nov 28, 2014 at 12:30
1
\$\begingroup\$

Python 3 - 159 bytes

import re;l=input();x=len;print(''.join([str(x(i))+j for i,j in re.findall('((.)\2*)',l)]if x(l)%2 else[j*int(i)for i,j in[l[i:i+2]for i in range(0,x(l),2)]]))
\$\endgroup\$
1
\$\begingroup\$

Cobra - 217

(186 if I can assume a use statement for System.Text.RegularExpressions exists elsewhere)

do(s='')=if((l=s.length)%2,System.Text.RegularExpressions.Regex.replace(s,(for x in 10 get'[x]+|').join(''),do(m=Match())="['[m]'.length]"+'[m]'[:1]),(for x in 0:l:2get'[s[x+1]]'.repeat(int.parse('[s[x]]'))).join(''))
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6) 85

Using regular expression replace with function. Different regexp and different function depending on input length being even or odd.

F=s=>s.replace((i=s.length&1)?/(.)(\1*)/g:/../g,x=>i?x.length+x[0]:x[1].repeat(x[0]))
\$\endgroup\$
0
\$\begingroup\$

Ruby, 78 bytes

->s{s.size%2<1?s.gsub(/(.)(.)/){$2*$1.to_i}:s.gsub(/(.)\1*/){$&.size.to_s+$1}}

Attempt This Online!

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 18 (or 17?) bytes

S2ôø`s×IÅγs.ι‚JIgè

Try it online or verify some more test cases.

Since the challenge asks for a string input, which by default allows for a list of characters, it would be 1 byte less by removing the leading S:
Try it online or verify some more test cases.

Explanation:

S        # Convert the (implicit) input to a list of digits
 2ô      # Split it into parts of size 2
   ø     # Zip/transpose; swapping rows/columns
    `    # Pop and push both lists separately to the stack
     s   # Swap the two lists on the stack
         # (or swap it with the implicit input if the input was a single digit number)
      ×  # Repeat the digits the numbers amount of times (at the same positions of the
         # lists)
I        # Push the input again
 Åγ      # Run-length encode it, pushing the list of digits and list of lengths
         # separately to the stack
   s     # Swap those two lists on the stack
    .ι   # Interleave the two lists into one:
         #  [a,b,c,...] and [d,e,f,...] → [a,d,b,e,c,f,...]
‚        # Pair the two lists together
 J       # Join both inner lists to a number
  I      # Push the input yet again
   g     # Pop and push its length
    è    # Modular 0-based index it into the pair
         # (after which the result is output implicitly)
\$\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.