Programming Praxis

Look And Say

March 15, 2011 9:00 AM

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.

Posted by programmingpraxis

Categories: Exercises

Tags:

« Older Newer »

22 Responses to “Look And Say”

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”]

By Martin Oldfield on March 15, 2011 at 9:34 AM
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)
```
By Remco Niemeijer on March 15, 2011 at 10:15 AM
[…] today’s Programming Praxis exercise, our task is to generate the Look and Say sequence (1, 11, 21, 1211, […]

By Programming Praxis – Look And Say « Bonsai Code on March 15, 2011 at 10:15 AM

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

By Dave Webb on March 15, 2011 at 12:09 PM

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)

By Graham on March 15, 2011 at 12:21 PM

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

By Graham on March 15, 2011 at 12:22 PM
Clojure solution:

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

By Leonel on March 15, 2011 at 3:01 PM

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)

By Jussi Piitulainen on March 15, 2011 at 3:12 PM

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()

By Mike on March 15, 2011 at 8:50 PM

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

By Rainer on March 16, 2011 at 8:45 AM

[…] autre petit exercice de Programming Praxis, programmer la suite Look and Say. Ce n’est pas très difficile : import Data.List import […]

By La suite Look and Say on March 16, 2011 at 9:23 AM

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]

By Benoît Huron on March 16, 2011 at 9:34 AM

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 _)

By Aaron on March 16, 2011 at 2:49 PM
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

By Vitaliy Isikov on March 17, 2011 at 8:29 PM

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

By Toby on March 19, 2011 at 1:18 AM

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]

By Jean-Pascal Billaud on March 19, 2011 at 5:44 PM

(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)

By yaq on March 20, 2011 at 10:57 AM

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"

By Khanh Nguyen on March 21, 2011 at 12:32 AM

Here is a solution in Factor:

http://re-factor.blogspot.com/2011/03/look-and-say.html

By John on March 23, 2011 at 5:55 PM
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 ;

By John on March 24, 2011 at 5:00 PM
is anybody have solution in c plz upload here

By rohit on March 30, 2011 at 5:26 AM
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.

By Toby on March 30, 2011 at 6:15 PM

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.

Programming Praxis

Look And Say

Share this:

Related

22 Responses to “Look And Say”

Leave a Reply