;; contract: (list x) * (list y) --> (list x) or (list y)
;; purpose: to determine which list has more elements.
;; example: (bigger_list '(1 2 3) '(1 2 3 4)) should return '(1 2 3)
;; definition:
(define (bigger_list list1 list2) (if (< (length list1) (length list2)) list2 list1))

;; contract: (list x) *(list y) --> (length (list x))
;; purpose: to determine and use the list with a bigger length
;; example: (bigger_length '( a b c) '(a b) --> 3
;; definition:
(define (bigger_length list1 list2)(if (> (length list1) (length list2)) (length list1) (length list2)))

;; contract: (list x) --> (list x)
;; purpose: to reverse a list
;; example: (reverse_list '(a b c)) --> (c b a)
;; definition:
(define (reverse_list list1)
  (if (null? list1)
      '()
      (append (reverse (cdr list1)) (list (car list1)))))

;; contract: (list x) * integer --> symbol
;; purpose: to create a list-ref function
;; example: (symbol_at_index '( a b c) 1 should return b
;; definition:
(define (symbol_at_index list index)
  (if (equal? list '())
      '()
      (if (= index 0)
          (car list)
          (symbol_at_index (cdr list) (- index 1)))))

;; contract: integer x --> '( () () () () ... *x ())
;; purpose: init the 2d array for dynamic programming, the len of the list determine the number of coloumns
;; example: (base_case 3) should return '( () () () )
;; definition:
(define (base_case len_list)
  (if (= len_list 0)
      '()
      (cons '() (base_case (- len_list 1)))))

;; contract: (integer x) (list y) (list z) ---> ( () () () () )
;; purpose: to compute column number x of the dynamic programming 2d list
;; example: (compute_column 2 '(a c b) '(a b c)) ---> ((c a) (a) (a) ())
;; definition:

(define (compute_column column_number list1 list2)
  ;if we are at the 0th column return empty lists (base case)
  (if (= column_number 0)
       ;return base case
      (base_case (+ (length list2) 1))
      ;else recursively call 1,2,3...(length list) to get columns 1 2 3... etc
      (get_current_column '(()) (compute_column (- column_number 1) list1 list2) column_number list1 list2)))

;;contract: '((x) ()) '(() () ()) (int x) '(x) '(x) --> '( () () () ())
;;purpose: using the previous column compute the current column
;;example: (get_current_column '(()) (compute_column 3 '(a b c d) '(c d a b)) 4 '(a b c d) '(c d a b))
;;         returns ((d c) (d c) (d c) (c) ())
;;definition:

(define (get_current_column current_column prev_column column_number list1 list2)
  ;If the column size is equal to the previous columns's size, were done
  (if (= (length current_column) (length prev_column))
      ;return the column
      current_column
      ;else recursively call compute_cell, which adds the next cell in the column.
      (get_current_column (compute_cell current_column prev_column column_number list1 list2) prev_column column_number list1 list2)))

;;contract: '( () ) '( () ) (int x) '(list) '(list) ---> '( () )
;;purpose: to compute the next cell for the current column based on the previous column
;;example: (compute_cell '((a) ()) '( () () () ) 1 '(a b c) '(a b d)) returns((a) (a) ())
;;definition
(define (compute_cell current_column prev_column column_number list1 list2)

  (let*
      (
       ;to determine which row we look at how many things we've appened to current_column
       (row_number (length current_column))
       ;to find symbol one we subtract one because our column/row numbers contain the base case of ()
       (symbol1 (symbol_at_index list1 (- column_number 1)))
       (symbol2 (symbol_at_index list2 (- row_number 1)))
       ;the cell below is the thing previously appened to current_column
       (cell_below (car current_column))
       ; the cell to the right in in the previous column and in order to index it we
       ; must calculate the index backwards. This is because append puts items of the list
       ; in the front. This also means each subtraction is actually + 1 not - 1.
       (cell_right (symbol_at_index prev_column (- (- (length prev_column) row_number) 1)))
       (diagonal_cell (symbol_at_index prev_column (- (length prev_column) row_number)))
               )
  (if (equal? symbol1 symbol2)
      ;if the symbols are equal append the symbol to the diagonal cell solution
      (append (list (cons symbol2 diagonal_cell)) current_column)
      ;else append the best solution from cell below and cell right
      (append (list (bigger_list cell_below cell_right)) current_column))))




;; contract: (list x) * (list y) --> (list z) where z is the largest common subset
;; purpose: to determine the largest common subset
;; example: '(a b c)
;; definition:
(define (lcs_slow list1 list2)
     ; If either list is an empty list, return an empty list
    (if (or (equal? list1 '()) (equal? list2 '()))

        '()
        ; else - if the head of both lists are equal
        (if (equal? (car list1) (car list2))
            ; #t then return the current element plus the recursively returned list ( until it returns an empty list )
            (cons (car list1) (lcs_slow (cdr list1) (cdr list2)))
            ; #f then return the best result from either list1 -1 or list2 -1
            (bigger_list (lcs_slow list1 (cdr list2)) (lcs_slow (cdr list1) list2))
        )
    )
)

;;contract (list x) (list y) --> (list z)
;;purpose: a dynamic programming solution to find the largest common subsequence
;;example '(a b c) '(a b d) --> (a b)
;;definition
(define (lcs_fast list1 list2)
  (reverse_list (car (compute_column (bigger_length list1 list2) list1 list2))))

;;Test Cases
;; (define list1 `(q q q a b d e))
;; (define list2 `(g g g g g a b c e))
;; (lcs_slow list1 list2)
;; (symbol_at_index '(a (a b) d c) 1 )
;; (compute_cell '((a) ()) '( () () () ) 1 '(a b c) '(a b d))
;; (get_current_column '(()) (compute_column 3 list1 list2) 4 list1 list2)
;; (lcs_fast list1 list2)
;; (reverse_list '(a b c))
;; (compute_column 2 '(a c b) '(a b c))
;; (get_current_column '(()) (compute_column 3 '(a b c d) '(c d a b)) 4 '(a b c d) '(c d a b))