#!/usr/bin/env newlisp

;O(N)
(define (Puissance1 P N)
  (cond
    ((= N 0) 1)
    ((= N 1) P)
    ((< N 0) (div 1 (Puissance1 P (- N))))
    ((* P (Puissance1 P (- N 1))))))
(println "Puissance1")
(println (Puissance1 5 5))
(println (Puissance1 2 12))

;(trace true)

;O(log N)
(define (Puissance2 P N)
  (cond
    ((= N 1) P)
    ((= N 2) (* P P))
    ((> N 2)
     (cond
       ((= (mod N 2) 0) (Puissance2 (Puissance2 P 2) (/ N 2)))
       ((* P (Puissance2 (Puissance2 P 2) (/ (- N 1) 2))))))))
(println "Puissance2")
(println (Puissance2 5 5))
(println (Puissance2 2 12))

;(trace nil)

; https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide
(define (pgcd N P) 
  (cond
    ((< N P) (pgcd P N))
    ((= N P) N)
    ((= P 0) N)
    ((pgcd (- N P) P))))
(println "PGCD")
(println (pgcd 12 4))
(println (pgcd 25 5))
(println (pgcd 21 7))

;(trace true)

; https://fr.wikipedia.org/wiki/Coefficient_binomial
; relation de pascal commenté
(define (comb N P) 
  (cond
    ((= P 0) 1)
    ((= N P) 1)
    ;((+ (comb (- N 1) P) (comb (- N 1) (- P 1))))))
    ((/ (* N (comb (- N 1) (- P 1))) P))))
(println "comb")
(println (comb 5 4))
(println (comb 60 4))
(println "(comb 12 8) = "(comb 12 8))

;(trace nil)
;(trace true)

(setq L '(3 7 + 4 2 + *))
(setq M '(4 3 7 + * 2 -))
(setq N '(10 10 5 / +))
(define (calculExp P L)
  (cond
    ((null? L) (first P))
    ; all these conditions could probably be simplified
    ((= (first L) '+) (calculExp (cons (+ (P 1) (first P)) (rest (rest P))) (rest L)))
    ((= (first L) '-) (calculExp (cons (- (P 1) (first P)) (rest (rest P))) (rest L)))
    ((= (first L) '*) (calculExp (cons (* (P 1) (first P)) (rest (rest P))) (rest L)))
    ;FIXME: test for divide by zero
    ((= (first L) '/) (calculExp (cons (/ (P 1) (first P)) (rest (rest P))) (rest L)))
    ((number? (first L)) (calculExp (cons (first L) P) (rest L)))))
(println "calculExp")
(println (calculExp '() L))
;(trace true)
(println (calculExp '() M))
(println (calculExp '() N))

;(trace nil)

(setq Q '(+ (* x 0) (* 10 (+ y 0))))
(define (algsimplificator L)
  (cond
    ((null? L) '())
    ; I'm having hard time to find a way of escaping the '(' and ')' characters 
    ((= (first L) ) (rest L))
    ;here is the idea: detect the lower well formed expression: begin with (op and finish with ) where op = + - * / and have only two parameters that are atoms.
    ;then if it match a known pattern, simplify it by following the matching rule.
    ;do it again on the upper layer recursively until we only have (op A B) that just match no known simplication rules.

    ))
(println "algsimplificator")
;(println algsimplificator(Q))

(define (fibonacci N)
  (cond
    ((= N 0) 0)
    ((= N 1) 1)
    ((> N 1) (+ (fibonacci (- N 1)) (fibonacci (- N 2))))))
(println "fibonacci")
;(println (fibonacci 21))
;(println (fibonacci 14))
(println (fibonacci 20))
(println (time (fibonacci 20)))

;(trace true)

(define (fibo:fibo n)
  (if (not fibo:mem) (set 'fibo:mem '(0 1)))
  (dotimes (i (- n 1))
    ;this create a LIFO (or stack) of all previous fibonnaci serie result values
    (push (+ (fibo:mem -1) (fibo:mem -2)) fibo:mem -1))
  (last fibo:mem))
(println "fibo")
(println (fibo 20))
(println (time (fibo 20)))

;(trace nil)
;(trace true)

(setq S '())
(define (Somme3ou5 N)
    (dolist (i (sequence 0 N))
      (cond
        ((= (mod i 3) 0) (setq S (cons i S)))
        ((= (mod i 5) 0) (setq S (cons i S)))))
    (apply + S))
(println "Somme3ou5")
(println (Somme3ou5 100))

;(trace nil)

(exit)