Exercises from Programming praxis

;; tribonacci sequence
;; Copyright (C) 2012  cage

;; This program is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.

;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.

;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <http://www.gnu.org/licenses/>.



(defmacro matrix-elt (mat row col)
  `(nth ,col (nth ,row ,mat)))

(defun column@ (mat at)
  (mapcar #'(lambda (r) (nth at r)) mat))

(defun m-mult (a b)
  (let ((res (loop for i from 0 below (length a) collect
                  (make-list (length (first b))))))
    (loop for i from 0 below (length a) do
         (loop for j from 0 below (length (first b)) do
              (setf (matrix-elt res i j)
                    (reduce #'+ (mapcar #'* (nth i a) (column@ b j)) :initial-value 0))))
    res))


(defun m-pow (a exp &optional (base (copy-tree a)))
  (if (> exp 2)
      (m-pow (m-mult a base) (1- exp) base)
      (m-mult a base)))

(defun nth-fibonacci (n)
  (if (= n 0)
      0
      (matrix-elt (m-pow '((1 1) (1 0)) (- n 1)) 1 0)))


(defun nth-tribonacci (n)
  (cond
    ((= n 0)
     0)
    ((= n 1)
     1)
    (t
     (matrix-elt (m-pow '((1 1 0) (1 0 1) (1 0 0)) (1- n)) 0 2))))


(defun tribonacci-real (n &optional (res (list 1 0 0)))
  (if (= 0 n)
      (reverse res)
      (tribonacci-real (- n 1) (push (+ (first res) (second res) (third res)) res))))

(defun tribonacci (n)
  (cond
    ((= n 0)
     nil)
    ((= n 1)
     (list 0))
    ((= n 2)
     (list 0 1))
    ((= n 3)
     (list 0 0 1))
    (t
     (tribonacci-real (- n 3)))))

(defun tribonacci-ratio (n)
  (float (/ (nth-tribonacci n) (nth-tribonacci (1- n)))))

;; skew binary number random access list
;; Copyright (C) 2012  cage

;; This program is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.

;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.

;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <http://www.gnu.org/licenses/>.

(defclass btree ()
  ((value
    :initarg :value
    :accessor value)
   (left
    :initarg :left
    :initform nil
    :accessor left)
   (right
    :initarg :right
    :initform nil
    :accessor right)))

(defmethod print-object ((object btree) stream)
  (with-slots (value left right) object
    (format stream " <value ~a left ~a right ~a> " value left right)))

(defgeneric leaf-p (object))
(defgeneric lookup-tree (object w pos))
(defgeneric update-tree (object w pos value))

(defmethod leaf-p ((object btree))
  (and (null (left object))
       (null (right object))))


(defmethod lookup-tree ((object btree) (w integer) (pos integer))
  (cond
    ((= pos 0)
     (value object))
    (t
     (if (< pos (/ w 2))
         (lookup-tree (left object) (truncate (/ w 2)) (- pos 1))
         (lookup-tree (right object) (truncate (/ w 2)) (- pos 1 (truncate (/ w 2))))))))

(defmethod update-tree ((object btree) (w integer) (pos integer) value)
  (cond
    ((= pos 0)
     (make-instance 'btree :value value :left (left object) :right (right object)))
    (t
     (if (< pos (/ w 2))
         (make-instance 'btree :value (value object)
                        :left  (update-tree (left object) (truncate (/ w 2)) (- pos 1) value)
                        :right (right object))

         (make-instance 'btree :value (value object)
                        :left  (left object)
                        :right (update-tree (right object) (truncate (/ w 2)) (- pos 1 (truncate (/ w 2))) value))))))


(defun scons (val slist)
  (cond
    ((null slist)
     (list (list 1 (make-instance 'btree :value val))))
    ((= (length slist) 1)
     (cons (list 1 (make-instance 'btree :value val)) slist))
    ((= (first (first slist)) (first (second slist)))
     (let ((w1 (first (first slist)))
           (w2 (first (second slist)))
           (tree-left (second (first slist)))
           (tree-right (second (second slist))))
       (cons (list (+ w1 w2 1)
                   (make-instance 'btree :value val :left tree-left :right tree-right))
             (subseq slist 2))))
    (t
     (cons (list 1 (make-instance 'btree :value val)) slist))))


(defun shead (slist)
  (if (null slist)
      nil
      (value (second (first slist)))))

(defmacro with-weight-and-node ((w node slist) &body body)
  `(let ((,node (second (first ,slist)))
         (,w (first (first ,slist))))
     ,@body))

(defun stail (slist)
  (with-weight-and-node (w node slist)
    (if (leaf-p node)
        (rest slist)
        (cons (list (truncate (/ w 2)) (left node))
              (cons (list (truncate (/ w 2)) (right node))
                    (rest slist))))))


(defun lookup (pos slist)
  (if (null slist)
      nil
      (with-weight-and-node (w node slist)
        (if (< pos w)
            (lookup-tree node w pos)
            (lookup (- pos w) (rest slist))))))


(defun update (pos value slist)
  (if (null slist)
      nil
      (with-weight-and-node (w node slist)
        (if (< pos w)
            (cons (update-tree node w pos value) (rest slist))
            (cons (first slist)
                  (update (- pos w) value (rest slist)))))))

;; simple open addressing hashtable
;; Copyright (C) 2012  cage

;; This program is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.

;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.

;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <http://www.gnu.org/licenses/>.

(asdf:load-system :alexandria)

(alexandria:define-constant +hashtable-size+ 10 :test #'=)

(defun hash (string)
  (if (string/= string "")
      (let ((first-char (char-code (elt string 0))))
        (mod (+ first-char (hash (subseq string 1))) +hashtable-size+))
      0))


(defclass hashnode ()
  ((key
    :initform nil
    :accessor key
    :initarg :key
    :type 'string)
   (datum
    :initform nil
    :accessor datum
    :initarg :datum)
   (status
    :initform :empty
    :accessor status
    :initarg :status)))

(defmethod print-object ((object hashnode) stream)
  (with-slots (key datum status) object
    (print-unreadable-object (object stream :type nil :identity t)
      (format stream "key: ~s datum: ~a status: ~a" key datum status))))

(defparameter *hashtable* '())


(defun h-initialize ()
  (setf *hashtable*
        (loop for i from 0 below +hashtable-size+ collect
             (make-instance 'hashnode))))



(defun h-add-datum (key datum &optional (address (hash key)) (count 0))
  (if (< count +hashtable-size+)
      (if (or
           (eq (status (nth address *hashtable*)) :empty)
           (eq (status (nth address *hashtable*)) :deleted)
           (string= key (key (nth address *hashtable*))))
          (progn
            (format t "address ~a (key ~a) empty~%"
                    address key)
            (setf (datum (nth address *hashtable*)) datum)
            (setf (key (nth address *hashtable*)) key)
            (setf (status (nth address *hashtable*)) :occupied))
          (progn
            (format t "collision for address ~a (key ~a) collide with ~a~%"
                    address key (nth address *hashtable*))
            (h-add-datum key datum (mod (1+ address) +hashtable-size+) (1+ count))))
      (error "hashtable full for key ~s" key)))


(defun h-lookup (key &optional (address (hash key)) (count 0))
  (if (< count +hashtable-size+)
      (let ((node@address (nth address *hashtable*)))
        (if (not (eq (status node@address) :empty))
            (if (string= (key node@address) key)
                (values (datum node@address) address)
                (h-lookup key (mod (1+ address) +hashtable-size+) (1+ count)))
            nil))
      nil))


(defun h-delete (key)
  (multiple-value-bind (found address)
      (h-lookup key)
    (if found
        (let ((node@address (nth address *hashtable*)))
          (setf (datum node@address) nil)
          (setf (key node@address) nil)
          (setf (status node@address) :deleted))
        nil)))


(defun test-hashtable ()
  (h-initialize)
  (loop
     for i in '("a" "b" "c" "d" "d" "e" "f" "g" "h" "i" "m")
     and d = 0 then (1+ d) do
       (format t "add ~a -> ~a~%" i d)
       (h-add-datum i d)
       (format t "~a~%" *hashtable*))

  (format t "delete m key ~a ~%" (hash "m"))
  (h-delete "m")
  (format t "~a~%" *hashtable*)

  (format t "re add m key ~a ~%" (hash "m"))
  (h-add-datum "m" 11)
  (format t "~a~%" *hashtable*)

  (format t "delete c key ~a ~%" (hash "c"))
  (h-delete "c")
  (format t "~a~%" *hashtable*)

  (format t "delete m key ~a ~%" (hash "m"))
  (h-delete "m")
  (format t "~a~%" *hashtable*))

(defun n-tuple (input &optional (count (length input)))
  (let ((res '()))
    (labels ((actual-n-tuple (input &optional (count (length input)) (accum '()))
               (if (> count 0)
                   (mapcar #'(lambda (a)
                               (actual-n-tuple input (1- count) (append accum (list a))))
                           input)
                   (push accum res))))
      (actual-n-tuple input count)
      res)))



(defun 4sum (input)
  (if (or (every #'(lambda (a) (< a 0)) input)
          (every #'(lambda (a) (> a 0)) input))
      nil
      (remove-if #'(lambda (v) (not (= (reduce #'+ v) 0)))
                 (n-tuple input 4))))

(defun min-scalar (a b)
  (reduce #'+ (mapcar #'(lambda (v1 v2) (* v1 v2))
                      (sort a #'<)
                      (sort b #'>))))

;; simplicistic build system
;; Copyright (C) 2012  cage

;; This program is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.

;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.

;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <http://www.gnu.org/licenses/>.

(asdf:load-system :alexandria)
(asdf:load-system :osicat)
(asdf:load-system :cl-lex)
(asdf:load-system :yacc)
(asdf:load-system :trivial-shell)

(defparameter *debug* t)

(defmacro define-stat-time (slot-name)
  (alexandria:with-gensyms (stat)
    `(defun ,(alexandria:format-symbol t "~:@(get-stat-~a~)" slot-name) (file)
       (restart-case
           (let ((,stat (nix:stat file)))
             (if ,stat
                 (,(alexandria:format-symbol :nix "~:@(stat-~a~)" slot-name)
                   ,stat)))
         (use-value (value) value)))))


(define-stat-time mtime)
(define-stat-time ctime)
(define-stat-time atime)


(defun file-outdated-p (file &rest dependencies)
  (handler-bind ((nix:enoent #'(lambda (c)
                                 (declare (ignore c))
                                 (invoke-restart 'use-value nil))))
    (let ((atime (get-stat-atime file))
          (mtimes (remove-if #'null (mapcar #'get-stat-mtime dependencies))))
      (when *debug*
        (format t "file ~a ~a ~a ~a~%" file atime dependencies mtimes))
      (if atime
          (remove-if #'(lambda (mtime) (<= mtime atime)) mtimes)
          t))))



(defclass rule ()
  ((name
    :initform nil
    :accessor name
    :initarg :name)
   (dependencies
    :initform '()
    :accessor dependencies
    :initarg :dependencies)
   (commands
    :initform '()
    :accessor commands
    :initarg :commands)))


(defparameter *all-rules* '())

(defun find-dependency (rule-name &optional (all-rules *all-rules*))
  (find-if #'(lambda (dep) (string= (name dep) rule-name)) all-rules))

(defmethod print-object ((object rule) stream)
  (format stream "name ~a dep ~a cmds ~a"
          (name object) (dependencies object) (commands object)))

(defgeneric build (object))



(defmethod build ((object rule))
  (let ((commands-trigger (cond
                            ((not (osicat:file-exists-p (name object)))
                             t)
                            ((dependencies object)
                             nil)
                            (t
                             t))))
    (loop for i in (dependencies object) do
         (let ((dep (find-dependency i)))
           (if dep
               (let ((trigger (build dep)))
                 (when trigger
                   (setf commands-trigger trigger)))
               (when (file-outdated-p (name object) i)
                 (setf commands-trigger t)))))
    (when commands-trigger
      (if *debug*
          (format t "rule: ~a~%~{~a~%~}~%~%" (name object) (commands object))
          (mapc #'(lambda (cmd)
                    (format t "~a~%~{~a~}~%" cmd (subseq (multiple-value-list
                                                          (metashell:shell-command cmd))
                                                         0 2)))
                (commands object))))
    commands-trigger))


(defmethod build ((rule string))
  (build (find-dependency rule)))

(cl-lex:define-string-lexer lexer
  ("\\t(.*)" (return (values 'command $1)))
  ("([a-z,0-9,_,\\-,\\.]+):" (return (values 'name $1)))
  ("([a-z,0-9,_,\\-,\\.]+) " (return (values 'dependency $1)))
  ("([a-z,0-9,_,\\-,\\.]+)\\n" (return (values 'terminal-dependency $1))))



;; make := rule*
;; rule := name dependencies* terminal-dependency command*

(yacc:define-parser *make-parser*
  (:start-symbol make)
  (:terminals (name dependency terminal-dependency command))
  (make rules nil)

  (rules
   (rule rules)
   rule)
  (rule
   (name dep stopper commands
         #'(lambda (name dependency terminal-dependency command)
            (push (make-instance 'rule
                                 :name name
                                 :dependencies (alexandria:flatten
                                                (append dependency (list terminal-dependency)))
                                 :commands (alexandria:flatten command))
                  *all-rules*))))

  (dep
   (dependency dep)
   dependency
   nil)

  (stopper
   terminal-dependency
   nil)
  (commands
   (command commands)
   command)

  (dependency)
  (command)
  (name)
  (terminal-dependency))



(defun read-file (file)
  (with-open-file (stream file :direction :input)
    (do ((lines ""))
        (nil)
      (handler-case
          (setf lines (concatenate 'string lines (format nil "~%") (read-line stream)))
        (end-of-file (c)
          (declare (ignore c))
          (return lines))))))



(defun make (root-rule &optional (file "Makefile"))
  (yacc:parse-with-lexer (lexer (read-file file))
                         *make-parser*)
  (build root-rule))

;; cryptarithm solver with hill-climbing algorithm
;; Copyright (C) 2012  cage

;; This program is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.

;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.

;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <http://www.gnu.org/licenses/>.

(eval-when (:execute)
  (setf *random-state* (make-random-state t)))

(defparameter *all-letters-values* (make-hash-table :test 'equal))
(defparameter *all-letters* (coerce "abcdefghijklmnopqrstuvwuxyz" 'list))

(defparameter *use-jump* t)
(defparameter *jump-count* 100)

(defun dump-hashtable (table)
  (maphash (lambda (k v) (format t "~s -> ~s~%" k v))  table))


(defun reverse-hashtable (table)
  (let ((res (make-hash-table :test 'equal)))
    (maphash (lambda (k v)
               (setf (gethash v res) k))
             table)
    res))


(defun copy-hashtable (table)
  (let ((res (make-hash-table :test 'equal)))
    (maphash (lambda (k v)
               (setf (gethash k res) v))
             table)
    res))


(defun random-permutation (vals)
    (if vals
        (let ((random-pos (random (length vals))))
          (append (list (nth random-pos vals))
                  (random-permutation (append
                                       (subseq vals 0 random-pos)
                                       (if (< (1+ random-pos) (length vals))
                                           (subseq vals (1+ random-pos))
                                           nil)))))
        nil))

(defun initialize-hashtable (&optional (letters *all-letters*)
                             (hashtable *all-letters-values*)
                             (max-val 10))
  (loop for i from 0 below max-val do
       (if (nth i letters)
         (setf (gethash i hashtable) (format nil "~a" (nth i letters)))
         (setf (gethash i hashtable) nil)))
    hashtable)


(defun string->number (str &optional (hashtable *all-letters-values*))
  (let ((reverse-hashtable (reverse-hashtable hashtable)))
    (parse-integer
     (format nil "~{~a~}"
             (loop for i across str collect (gethash (string i) reverse-hashtable))))))


(defun fitness (first second res hashtable &optional (operator :+))
  (ecase operator
    (:+
     (abs (- (+ (string->number first hashtable)
                (string->number second  hashtable))
             (string->number res hashtable))))))


(defun swap (&optional
             (hashtable *all-letters-values*)
             (max-number 10))
  (let* ((first-random-number (random max-number))
         (second-random-number (random max-number))
         (first-random-val (gethash first-random-number hashtable))
         (second-random-val (gethash second-random-number hashtable)))
    (setf (gethash first-random-number hashtable) second-random-val
          (gethash second-random-number hashtable) first-random-val)
    hashtable))



(defun get-letter-set (the-set &rest str)
  (if str
      (apply #'get-letter-set (union the-set (remove-duplicates
                                              (coerce (first str) 'list)
                                              :test #'equal)
                                     :test #'equal)
             (rest str))
      the-set))


(defun first-letter-0-p (hash-table &rest words)
  (loop for i in words do
       (if (= (gethash (string (char i 0)) (reverse-hashtable hash-table)) 0)

           (return-from first-letter-0-p t)))
  nil)


(defun solve (first second res &optional (hashtable (initialize-hashtable
                                                     (get-letter-set nil first second res)
                                                     (make-hash-table :test 'equal)))
              (operator :+) (ct 0))
  (let ((current-fitness (fitness first second res hashtable operator)))
    (if (and (= current-fitness 0)
             (not (first-letter-0-p hashtable first second res)))
        (progn
          (format t "~a ~a ~a = ~a => ~a ~a ~a = ~a~%" first operator second res
                  (string->number first hashtable)
                  operator
                  (string->number second hashtable)
                  (string->number res hashtable))
          (dump-hashtable (reverse-hashtable hashtable)))
        (let* ((swapped-hashtable (swap (copy-hashtable hashtable)))
               (new-fitness (fitness first second res swapped-hashtable operator)))
          (if (or
               (and *use-jump*
                    (= (mod ct *jump-count*) 0))
               (< new-fitness current-fitness))
              (solve first second res swapped-hashtable operator (1+ ct))
              (solve first second res hashtable operator (1+ ct)))))))

(defparameter *stack* nil)
(defparameter *minimum* nil)

(defparameter *compare-fun* #'<=)

(defun push-min (val)
  (when (or (null *stack*)
            (funcall *compare-fun* val (first *minimum*)))
    (push val *minimum*))
  (push val *stack*))


(defun pop-min ()
  (let ((popped (pop *stack*)))
    (when (and popped
               (funcall *compare-fun* popped (first *minimum*)))
      (pop *minimum*))
    popped))

(defun minimum ()
 (first *minimum*))