Topic: [Challenge] Pascal's triangle

[gile]

Hi,

A purpose for a little challenge around Pascal's triangle.

Define a function which returns the a Pascal's triangle to its nth row:

(foo 4) => ((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1))

and/or a function which returns the nth row:

(foo 6) => (1 6 15 20 15 6 1)

[Lee Mac]

Excellent challenge! I love it 

Quick & Dirty attempt at the first one:

Code: [Select]

(defun pascalntable ( n )
  (if (< n 1)
   '(( 1 ))
    (
      (lambda ( x )
        (append x (list (mapcar '+ (cons 0 (last x)) (append (last x) '( 0 )))))
      )
      (pascalntable (1- n))
    )
  )
)
Iterative:

Code: [Select]

(defun pascalntable_iter ( n / x )
  (repeat (setq x '(( 1 )) n n)
    (setq x (append x (list (mapcar '+ (cons 0 (last x)) (append (last x) '( 0 ))))))
  )
  x
)
And tweaked for the second:

Code: [Select]

(defun pascalnth ( n )
  (if (< 0 n)
    ( (lambda ( x ) (mapcar '+ (cons 0 x) (append x '( 0 )))) (pascalnth (1- n)))
   '( 1 )
  )
)
Iterative:

Code: [Select]

(defun pascalnth_iter ( n / x )
  (repeat (setq x '( 1 ) n n)
    (setq x (mapcar '+ (cons 0 x) (append x '( 0 ))))
  )
  x
)


[MP]

Well that was fun (Python 3.x):

def:

Code: [Select]

def pascals_triangle(n):
    x=[[1]]
    for i in range(n-1):
        x.append([a+b for a,b in zip([0]+x[-1],x[-1]+[0])])
    return x
call:

Code: [Select]

for x in pascals_triangle(10):
    print('{0:^39}'.format(x))
output:

Code: [Select]

                  [1]                 
                [1, 1]                 
               [1, 2, 1]               
             [1, 3, 3, 1]             
            [1, 4, 6, 4, 1]           
         [1, 5, 10, 10, 5, 1]         
       [1, 6, 15, 20, 15, 6, 1]       
     [1, 7, 21, 35, 35, 21, 7, 1]     
   [1, 8, 28, 56, 70, 56, 28, 8, 1]   
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]


Thanks Gile!!!

[T.Willey]

Mine looks like Lee's, but not recursive.

Code: [Select]

(defun tmw_PascalTriangle ( num / lst)
   
    (repeat num
        (setq lst
            (cons
                (if lst
                    (mapcar (function +) (cons 0 (car lst)) (append (car lst) (list 0)))
                    (list 1)
                )
                lst
            )
        )
    )
    (reverse lst)
)


[MP]

Mild variant:

Code: [Select]

def pascals_triangle(n):
    x=[[1]]
    for i in range(n-1):
        x.append([sum(i) for i in zip([0]+x[-1],x[-1]+[0])])
    return x
Python rocks.

[Lee Mac]

Another [slow] one:

Code: [Select]

(defun pascalnth_fact ( n / _fact k n! l )

  (defun _fact ( i )
    (if (< i 2) 1 (* i (_fact (1- i))))
  )

  (setq k -1 n! (_fact n))
  (repeat (1+ n) (setq l (cons (/ n! (* (_fact (setq k (1+ k))) (_fact (- n k)))) l)))
  l
)

[gile]

Very nice guys !!!
While I was sleeping, you were not...

So, not so many place left for LISP solutions.
Here's one using another algorithm to avoid using append.

Code: [Select]

(defun pascalTriangle (n / f1 f2)
  (defun f1 (l n)
    (if (< 0 n)
      ((lambda (x)
(cons (cons 1 x) (f1 x (1- n)))
       )
(f2 (cons 1 l))
      )
    )
  )
  (defun f2 (l)
    (if (cdr l)
      (cons (+ (car l) (cadr l)) (f2 (cdr l)))
      '(1)
    )
  )
  (cons '(1) (f1 nil n))
)

Code: [Select]

(defun pascalRow (n / f1 f2)
  (defun f1 (l n)
    (if (< 0 n)
      (f1 (f2 (cons 1 l)) (1- n))
      (cons 1 l)
    )
  )
  (defun f2 (l)
    (if (cdr l)
      (cons (+ (car l) (cadr l)) (f2 (cdr l)))
      '(1)
    )
  )
  (f1 nil n)
)
And a F# one (the first one uses an infinite lazy sequence)

Code: [Select]

let pascalTriangle n =
    let foo l = List.map2 (+) (0 :: l) (List.append l [0])
    Seq.unfold (fun l -> Some(l, foo l)) [1] |> Seq.take (n + 1) |> Seq.toList

Code: [Select]

let pascalRow n =
    let foo l = List.map2 (+) (0 :: l) (List.append l [0])
    List.fold (fun l i -> foo l) [1] [1 .. n]

[gile]

No need to use a sequence, I found a List.scan function:

Code: [Select]

let pascalTriangle n =
    List.scan(fun l i -> List.map2 (+) (0 :: l) (List.append l [0])) [1] [1 .. n]

[ElpanovEvgeniy]

my version triangle:

Code: [Select]

(defun f (n / f1)
 (defun f1 (l) (append l (list (append '(1) (mapcar '+ (last l) (cdr (last l))) '(1)))))
 (cond ((< n 1) '((1)))
       ((f1 (f (1- n))))
 )
)
my version NTH:

Code: [Select]

(defun f (n / f1)
 (defun f1 (l) (append '(1) (mapcar '+ l (cdr l)) '(1)))
 (cond ((< n 1) '(1))
       ((f1 (f (1- n))))
 )
)

ps. This time, I could not write the shortest code...
You're the best!  

[MP]

Awesome coding guys, thanks for sharing your expertise and approach to problem solving.

[ElpanovEvgeniy]

my new version triangle:

Code: [Select]

(defun f (n / f1)
 (defun f1 (l) (append '(1) (mapcar '+ l (cdr l)) '(1)))
 (if (>= n 0)
  (cons '(1) (mapcar 'f1 (f (1- n))))
 )
)

[Lee Mac]

I should imagine that's quite inefficient as you are repeating the (f1) calculation for all items at every level of the recursion, but still beautiful code 

[MP]

what I read:

I should imagine that's quite inefficient as you are repeating the (f1) calculation for all items at every level of the recursion, but still beautiful code  

what I heard:

that's ugly code but still beautiful code

[ElpanovEvgeniy]

I'm trying algorithm in other ways...

[Lee Mac]

that's ugly code but still beautiful code

'ugly' algorithm, beautifully concise code to achieve the desired result