TheSwamp
Code Red => AutoLISP (Vanilla / Visual) => Topic started by: gile on January 13, 2011, 04:37:02 PM
-
Hi,
A purpose for a little challenge around Pascal's triangle (http://en.wikipedia.org/wiki/Pascal%27s_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)
-
Excellent challenge! I love it :lol:
Quick & Dirty attempt at the first one:
(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:
(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:
(defun pascalnth ( n )
(if (< 0 n)
( (lambda ( x ) (mapcar '+ (cons 0 x) (append x '( 0 )))) (pascalnth (1- n)))
'( 1 )
)
)
Iterative:
(defun pascalnth_iter ( n / x )
(repeat (setq x '( 1 ) n n)
(setq x (mapcar '+ (cons 0 x) (append x '( 0 ))))
)
x
)
-
Well that was fun (Python 3.x):
def:
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:
for x in pascals_triangle(10):
print('{0:^39}'.format(x))
output:
[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]
:lol:
Thanks Gile!!!
-
Mine looks like Lee's, but not recursive.
(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)
)
-
Mild variant:
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. (http://www.theswamp.org/screens/mp/wave.gif)
-
Another [slow] one:
(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
)
-
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.
(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))
)
(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)
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
let pascalRow n =
let foo l = List.map2 (+) (0 :: l) (List.append l [0])
List.fold (fun l i -> foo l) [1] [1 .. n]
-
No need to use a sequence, I found a List.scan function:
let pascalTriangle n =
List.scan(fun l i -> List.map2 (+) (0 :: l) (List.append l [0])) [1] [1 .. n]
-
my version triangle:
(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:
(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! :-)
-
Awesome coding guys, thanks for sharing your expertise and approach to problem solving.
-
my new version triangle:
(defun f (n / f1)
(defun f1 (l) (append '(1) (mapcar '+ l (cdr l)) '(1)))
(if (>= n 0)
(cons '(1) (mapcar 'f1 (f (1- n))))
)
)
-
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 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
:lol:
-
I'm trying algorithm in other ways...
-
that's ugly code but still beautiful code
'ugly' algorithm, beautifully concise code to achieve the desired result :-)
-
note to self: probably shouldn't share "the voices"
doh, did it again
:-D
-
note to self: probably shouldn't share "the voices"
doh, did it again
:-D
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 ..
-
lol, figured out another by accident (was working on some thing else and went 'hey wait a second'):
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 (http://www.theswamp.org/screens/mp/dood.gif)
-
works too:
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
-
Another F#
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 :
let rec foo (l : int list) =
if l.Tail = [] then [1] else l.Head + l.Tail.Head :: foo l.Tail
-
my new version NTH:
(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.)
)
-
Fantastic Evgeniy!
A much better method to simplify the factorials than what I did here (http://www.theswamp.org/index.php?topic=36653.msg416594#msg416594). :-)
Here's how I understand your code:
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)!
-
cool thread is cool 8-)
-
Great!
I found (f 1. n 1.)
that the dot is very important,othewise it will take a mistake 'negative' results ,
just like (pascalrow 1000)
-
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
;|
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
;|
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
;|
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)
)
)
(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)
(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))
(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))
-
Excellent Gile !
how can change the following code into 'gc:unfold method ?
(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 :
(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 :
((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)...)
-
Sigh..... :-(
-
Sigh..... :-(
:?