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 

[MP]

note to self: probably shouldn't share "the voices"

doh, did it again

[Kerry]

note to self: probably shouldn't share "the voices"

doh, did it again

I undestand about the 'voices' ....
I've started to discuss issues with one of the back verandah posts ... If it ignores me I don't post critiques ..

[MP]

lol, figured out another by accident (was working on some thing else and went 'hey wait a second'):

Code: [Select]

def pascals_triangle(n):
    # python 3.x
    x=[[1]]
    for i in range(n-1):
        x.append(list(map(sum,zip([0]+x[-1],x[-1]+[0]))))
    return x
python

[MP]

works too:

Code: [Select]

def pascals_triangle(n):
    x=[[1]] ; f = lambda *a: list(map(sum,zip(*a)))
    for i in range(n-1): x.append(f([0]+x[-1], x[-1]+[0]))
    return x

[gile]

Another F#

Code: [Select]

let rec foo l =
    match l with
    | []      -> []
    | h :: [] -> [1]
    | h :: t  -> h + t.Head :: foo t
   
let pascalTri n = List.scan(fun l i -> 1 :: foo l) [1] [1 .. n]

let pascalRow n = List.fold(fun l i -> 1 :: foo l) [1] [1 .. n]
Works too with :

Code: [Select]

let rec foo (l : int list) =
    if l.Tail = [] then [1] else l.Head + l.Tail.Head :: foo l.Tail

[ElpanovEvgeniy]

my new version NTH:

Code: [Select]

(defun f_nth (n / f)
 (defun f (a b c)
  (if (>= b 0)
   (cons a (f (* a (/ b c)) (1- b) (1+ c)))
  )
 )
 (f 1. n 1.)
)

[Lee Mac]

Fantastic Evgeniy!

A much better method to simplify the factorials than what I did here. 

Here's how I understand your code:

Code: [Select]

Binomial Coefficient is given by:

   n!
--------
k!(n-k)!

Your code operating on the (k-1)th iteration:

       n!              n-(k-1)         n!
----------------  x   ---------  =  --------
(k-1)!(n-(k-1))!          k         k!(n-k)!



[MP]

cool thread is cool

[chlh_jd]

Great!
I found (f 1. n 1.)
  that the dot is very important,othewise it will take a mistake 'negative' results ,
just like

Code: [Select]

(pascalrow 1000)

[gile]

Some new ways implementing fold, scan and unfold F# functions in LISP.

EDIT: new definitions so that the functions require a *quoted* function as argument (as others 'higher order' LISP functions as apply, mapcar, ...)

gc:fold

Code: [Select]

;|
gc:fold
Returns the final state of an accumulator which initial state is changed
by applying a function to the accumulator and each item of a list.

Arguments
fun: a function (lambda or defun) which takes a state and a list item as arguments
     and returns the modified state
acc : accumulator initial state
lst ; list
|;

(defun gc:fold (fun acc lst)
  (foreach n lst (setq acc ((eval fun) acc n)))
)
gc:scan

Code: [Select]

;|
gc:scan
Returns the list of all intermediates states mor final state of an accumulator
which initial state is changed by applying a function to the accumulator and
each item of a list.

Arguments
fun: a function (lambda or defun) which takes a state and a list item as arguments
     and returns the modified state
acc : accumulator initial state
lst ; list
|;

(defun gc:scan (fun acc lst)
  (cons acc (mapcar '(lambda (x) (setq acc ((eval fun) acc x))) lst))
)
gc:unfold

Code: [Select]

;|
gc:unfold
Generates a list from a calculation function which takes a state
and modify it to product the next item.

Arguments
fun: a function (lambda or defun) which takes a state as argument and
     returns a list of type: (result next_state) or nil (requiered stop condition).
state: the initial state
|;

(defun gc:unfold (fun state)
  ((lambda (r)
     (if r
       (cons (car r) (gc:unfold fun (cadr r)))
     )
   )
    ((eval fun) state)
  )
)

Code: [Select]

(gc:fold '(lambda (a l) (mapcar '+ (cons 0 a) (append a '(0)))) '(1) '(1 2 3 4 5))returns: (1 5 10 10 5 1)

Code: [Select]

(gc:scan '(lambda (a l) (mapcar '+ (cons 0 a) (append a '(0)))) '(1) '(1 2 3 4 5))returns: ((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1) (1 5 10 10 5 1))

Code: [Select]

(gc:unfold '(lambda (a)
      (if (<= (length a) 6)
(list a (mapcar '+ (cons 0 a) (append a '(0))))
      )
    )
   '(1)
)returns: ((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1) (1 5 10 10 5 1))

[chlh_jd]

Excellent Gile !
how can change the following code into 'gc:unfold method ?

Code: [Select]

(defun get-Ndim-IA-lst (l / a b c d e i)
  (if (< (length l) 2)
    l
    (progn
      (setq a nil
   i 1
      )
      (while (setq b (nth i l))
(if (null a)
 (setq a (car l))
)
(setq e nil)
(foreach c b
 (foreach d a
   (if (<= (if (listp c)
 (car c)
 c
)
(if (listp d)
 (car d)
 d
)
)
     (setq e
    (cons
      (if (and (null (listp c)) (listp d))
(cons c d)
(if (and (null (listp c)) (null (listp d)))
  (list c d)
  (append c d)
)
      )
      e
    )
     )
   )
 )
)
(setq a e)
(setq i (1+ i))
      )
      a
    )
  )
)
arg :

Code: [Select]

(setq l '((0.95 0.9 0.85 0.8 0.75 0.7 0.65 0.6 0.55 0.5) (0.95 0.9 0.85 0.8 0.75 0.7 0.65 0.6 0.55 0.5 0.45)
 (0.95 0.9 0.85 0.8 0.75 0.7 0.65 0.6 0.55 0.5 0.45 0.4) (0.95 0.9 0.85 0.8 0.75 0.7 0.65 0.6 0.55 0.5 0.45 0.4 0.35)
 (0.95 0.9 0.85 0.8 0.75 0.7 0.65 0.6 0.55 0.5 0.45 0.4 0.35 0.3)))

Returns :

Code: [Select]

((0.3 0.8 0.85 0.9 0.95) (0.3 0.75 0.8 0.9 0.95) (0.3 0.75 0.8 0.85 0.95) (0.3 0.75 0.8 0.85 0.9)
(0.3 0.75 0.85 0.9 0.95) (0.3 0.7 0.75 0.9 0.95) (0.3 0.7 0.75 0.85 0.95)...)

[krampaul82]

Sigh.....

[Lee Mac]

Sigh.....