Look And Say

March 15, 2011

The “Look and Say” sequence, Sloane number A005150, begins 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, …. Each term is constructed from its predecessor by stating the frequency and number of each group of like digits. For instance, the term after 1211 is “one 1, one 2, and two 1s”, or 111221. This sequence was studied by the British mathematician John Horton Conway, and has some fascinating properties; see MathWorld or follow the references at Sloane’s if you are interested.

Your task is to write a program to compute the look and say sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

22 Responses to “Look And Say”

  1. Martin Oldfield said

    Here’s a quick solution in ghci:

    Prelude> import Data.List
    Prelude Data.List> let n = concatMap (\x -> (show $ length x) ++ [head x]) . group
    Prelude Data.List> take 10 $ iterate n “1″
    ["1","11","21","1211","111221","312211","13112221","1113213211","31131211131221","13211311123113112211"]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2011/03/15/programming-praxis-look-and-say/ for a version with comments):

    import Data.List
    
    lookAndSay :: Integer -> [Integer]
    lookAndSay = iterate (read . f . group . show) where
        f = (>>= \x -> show (length x) ++ take 1 x)
    
  3. [...] today’s Programming Praxis exercise, our task is to generate the Look and Say sequence (1, 11, 21, 1211, [...]

  4. Dave Webb said

    A Python solution:

    import itertools
    
    def lookandsay(number):
        return "".join(str(sum(1 for x in g)) + k for k,g in itertools.groupby(number))
    
    seq = ['1']
    for _ in xrange(10):
        seq.append(lookandsay(seq[-1]))
    print seq
    
  5. Graham said

    Using the groupby() function from Python’s itertools module:

    from itertools import groupby
    
    def next_iter(s):
        return ''.join([str(len(list(g))) + k for k, g in groupby(s)])
    
    if __name__ == "__main__":
        s = '1'
        for _ in xrange(10):
            print s
            s = next_iter(s)
    
  6. Graham said

    Looks like Dave beat me to it :-) I should have refreshed the page before posting.

  7. Leonel said

    Clojure solution:

    (defn lookandsay [s]
    (mapcat (juxt count first)
    (partition-by identity s)))
    (take 10 (iterate lookandsay [1]))

  8. Jussi Piitulainen said

    A listless solution, integer to integer, in Scheme.

    (define (say-next n)
      (let loop ((m (quotient n 10))
                 (digit (remainder n 10))
                 (count 1)
                 (result 0)
                 (length 1))
        (if (= m digit 0)
            result
            (let ((m1 (quotient m 10))
                  (digit1 (remainder m 10)))
              (if (= digit1 digit)
                  (loop m1 digit (+ count 1) result length)
                  (loop m1 digit1 1
                        (+ (* count 10 length)
                           (* digit length)
                           result)
                        (* length 100)))))))
    

    Output using iterate from that Standard Prelude.

    guile> (iterate 10 say-next 1)
    (1 11 21 1211 111221 312211 13112221 1113213211
     31131211131221 13211311123113112211)
    
  9. Mike said

    Because Sloane’s is a catalogue of integer sequences, I wrote a generator that return successive integers of the sequence.

    My first version is basically the same as Webb’s and Graham’s above, so I also did a second version using the regular expression library.

    I was somewhat suprised that the second version appears to be slightly faster, based on using the timeit module.

    # version 1: Uses itertools.groupby().
    from itertools import groupby
    
    def look_and_say1(n):
        '''generate 'look and say' sequence.
    
        >>> list(islice(look_and_say1(13),5))
        [13, 1113, 3113, 132113, 1113122113]
        '''
    
        s = list(str(n))
        
        while True:
            yield int(''.join(s))
            s = [d for k,g in groupby(s) for d in (str(len(list(g))), k)]
    
    
    # version 2: Uses re.sub().
    import re
    
    def look_and_say2(n):
        '''generate 'look and say' sequence.
    
        >>> list(islice(look_and_say2(13),5))
        [13, 1113, 3113, 132113, 1113122113]
        '''
    
        def say(mo):
            g = mo.group()
            return '{}{}'.format(len(g),g[0])
        
        s = str(n)
        pat = re.compile(r'([1-9])\1*')
        
        while True:
            yield int(s)
            s = pat.sub(say ,s)
    
    #testing
    from itertools import islice, izip
    
    def test(limit=10):
        '''compares output of both generators.
    
        >>> test()
        Ok
        '''
        for n in range(1,9):
            for s,t in islice(izip(look_and_say1(n),look_and_say2(n)), limit):
                if s != t:
                    print s, '!=', t
                    return
        print 'Ok'
    
    if __name__ == "__main__":
        import doctest
        doctest.testmod()
    
  10. Rainer said

    My try in REXX

    txt = '1'                                                    
    MAXLEN = 20                                                  
                                                                 
    say lookandsay(txt)                                          
    exit                                                         
                                                                 
    lookandsay: procedure expose MAXLEN                          
        parse arg seq                                            
        outseq = seq                                             
        do while length(seq) < MAXLEN                            
            new = ''                                             
            prv = ''                                             
            cnt = 0                                              
            do x = 1 to length(seq)                              
                n = substr(seq, x, 1)                            
                if n \= prv then do                              
                    if cnt > 0 then new = new||cnt||prv          
                    prv = n                                      
                    cnt = 0                                      
                end                                      
                if length(new) > MAXLEN then leave       
                cnt = cnt + 1                            
            end                                          
            if cnt > 0 then new = new||cnt||prv          
            outseq = outseq new                          
            seq = new                                    
        end                                              
        return outseq                                    
    
  11. [...] autre petit exercice de Programming Praxis, programmer la suite Look and Say. Ce n’est pas très difficile : import Data.List import [...]

  12. Benoît Huron said

    My Haskell solution

    import Data.List
    import Data.Digits
    
    lookAndSay :: [Integer]
    lookAndSay = map (unDigits 10) $ iterate next [1]
        where next = concatMap count . group
              count lst@(x:xs) = [fromIntegral (length lst), x]
    
  13. Aaron said

    in scala:

    def lookAndSay(previous:List[Int]) : Stream[List[Int]] = {
    def next(num : List[Int]) : List[Int] = num match {
    case Nil => Nil
    case head :: Nil => 1 :: head :: Nil
    case head :: tail => {
    val size = (num takeWhile{_ == head}).size
    List(size, head) ::: next(num.drop(size))
    }
    }
    val x = next(previous)
    x #:: lookAndSay(x)
    }

    lookAndSay(1::Nil) take 10 foreach (println _)

  14. Vitaliy Isikov said

    Here’s a JS solution. I’ve only been programming for about a year, mostly JS and PHP. Going to attempt a PHP version next, then subsequently, ajax-ify it.

    Look and Say Sequence

    var start = false;
    var result;
    function lookSay(int, repeat) {
    for (t=1; t<=repeat; t++) {
    if (!start) {
    start = int;
    result = start+"”;
    }
    newNumber = “”;
    digit = start.charAt(0);
    count = 1;
    for (var i = 1; i < start.length; i++) {
    if (digit == start.charAt(i)) {
    count++;
    }
    else {
    newNumber = newNumber + count + digit;
    digit = start.charAt(i);
    count = 1;
    }
    }
    start = newNumber + count + digit;
    if (t == repeat) {
    result+=start;
    document.getElementById('result').innerHTML=result;
    start = false;
    result = '';
    }
    else {
    result +=start+"”;
    }
    }
    }

    function returnResult() {
    s = document.getElementById(‘start’).value;
    r = document.getElementById(‘repeat’).value;
    lookSay(s, r);
    }

    Start Integer:
    Repeat Amount:
    Submit

  15. Toby said

    A Scheme solution using lists is:

    ; Copyright (C) 2011 Toby Thain, toby@telegraphics.com.au
    
    (define (look-and-say terms)
      (define (next-value lst)
        (let count-digit ((this-digit (car lst))
                          (count 1)
                          (rest (cdr lst)))
          (cond
            ((null? rest)
              (list count this-digit))
            ((eq? this-digit (car rest))
              (count-digit this-digit (+ count 1) (cdr rest)))
            (else
              (append (list count this-digit)
                      (count-digit (car rest) 1 (cdr rest)))))))
      (let step ((value '(1))
                 (n terms))
        (if (zero? n)
            '()
            (cons value (step (next-value value) (- n 1))))))
    
  16. Jean-Pascal Billaud said

    A ruby version:

    sloane = [1]
    puts sloane.inspect

    8.times.each do |iteration|
    new_sloane = []
    rep_digit = 1

    last_sum = sloane.inject(0) do |sum, digit|
    next sum + 1 if digit == rep_digit

    new_sloane << rep_digit
    new_sloane << sum
    rep_digit = digit
    1
    end

    new_sloane << rep_digit
    new_sloane << last_sum

    puts sloane.replace(new_sloane).reverse.inspect
    end
    [/sourcecode]

  17. yaq said

    (define (build-next items)
      (define (build-next-iter items number freq next)
        (cond ((and (pair? items) (equal? (car items) number))
               (build-next-iter (cdr items) number (+ freq 1) next))
              ((and (pair? items) (not (equal? (car items) number)))
               (build-next-iter (cdr items) (car items) 1 (cons next (cons freq number))))
              (else 
               (cons next (cons freq number)))))
      (flatten (build-next-iter items (car items) 0 '())))
    
    (define (look-and-say-from s)
      (cons-stream s (look-and-say-from (build-next s))))
    
    (define look-and-say-stream (look-and-say-from (cons 1'())))
    
    (stream-head look-and-say-stream 8)
  18. Khanh Nguyen said

    Mine in F#

    let look_and_say (s:string) = 
        let next  = s.ToCharArray() 
                    |> List.ofArray
                    |> List.fold (fun acc x -> 
                                        match acc with
                                        | [] -> [(x, 1)]
                                        | (a,b)::t ->                     
                                            match compare x a with
                                            | 0 -> (a,b+1)::t
                                            | _ -> (x,1)::acc
                                  ) [] 
                    |> List.rev
                    |> List.map (fun (a,b) -> (string b) + (string a))
                    |> Seq.ofList 
                    |> String.concat ""
        Some(s, next)
    
    let Sloan = Seq.unfold look_and_say "1"
    
    
  19. John said

    For the curious, Factor looks like this:

    : look-and-say ( n — n’ )
    number>string [ = ] monotonic-split [
    [ length ] [ first ] bi "%d%c" sprintf
    ] map concat string>number ;

  20. rohit said

    is anybody have solution in c plz upload here

  21. Toby said

    Rohit, check my website link here for a version in C. Please note that it is NOT written for clarity. But it is in C, and it works. Increase the ‘M’ constant if you want more numbers in the series; for example, 1000000 gives you the first 49 terms.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: