From 885a74b40ba686cf2beedb9c9072ce7158cc7972 Mon Sep 17 00:00:00 2001 From: Mohammad S Anwar Date: Sun, 30 Aug 2020 17:27:51 +0100 Subject: - Moved Lisp solutions to the correct folder. --- challenge-075/jeongoon/commmon-lisp/ch-1.lsp | 65 --------------- challenge-075/jeongoon/commmon-lisp/ch-2.lsp | 116 --------------------------- challenge-075/jeongoon/common-lisp/ch-1.lsp | 65 +++++++++++++++ challenge-075/jeongoon/common-lisp/ch-2.lsp | 116 +++++++++++++++++++++++++++ 4 files changed, 181 insertions(+), 181 deletions(-) delete mode 100644 challenge-075/jeongoon/commmon-lisp/ch-1.lsp delete mode 100644 challenge-075/jeongoon/commmon-lisp/ch-2.lsp create mode 100644 challenge-075/jeongoon/common-lisp/ch-1.lsp create mode 100644 challenge-075/jeongoon/common-lisp/ch-2.lsp diff --git a/challenge-075/jeongoon/commmon-lisp/ch-1.lsp b/challenge-075/jeongoon/commmon-lisp/ch-1.lsp deleted file mode 100644 index 075e153215..0000000000 --- a/challenge-075/jeongoon/commmon-lisp/ch-1.lsp +++ /dev/null @@ -1,65 +0,0 @@ -;; tested with: -;; sbcl --script ch-1.lsp 6 1 2 4 # first one: sum; rest: coins -;; ( sollution ... ) -(defun combi-coin-sum (coin-sum coin-list) - (if (null coin-list) nil - ;; else - (let* - ((sorted-coin-list (sort coin-list #'<)) - (first-coin (car sorted-coin-list)) - (max-noc (floor coin-sum first-coin)) - (other-coins (cdr sorted-coin-list)) - (all-combi)) - (loop for noc from max-noc downto 0 - do - (let* ((small-change (- coin-sum (* first-coin noc)))) - (if (= small-change 0) - (let ((all-first-coins - (make-list noc :initial-element first-coin))) - (if (null all-combi) (setq all-combi (list all-first-coins)) - (nconc all-combi (list all-first-coins)))) - ;; else - (let ((sub-combis (combi-coin-sum small-change other-coins))) - (if (null sub-combis) nil - ;; else - (let ((head-combi - (make-list noc :initial-element first-coin))) - (map 'list - #'(lambda (a-sub-combi) - (let ((new-combi - (append head-combi a-sub-combi))) - (if (null all-combi) - (setq all-combi (list new-combi)) - (nconc all-combi (list new-combi))))) - sub-combis))))))) ;; if sub-combis is nil, - (remove-if #'null all-combi)))) ;; map will return nil - -;; ( testing ... ) -(defun get-command-line () - (or - #+CLISP *args* - #+SBCL *posix-argv* - #+LISPWORKS system:*line-arguments-list* - #+CMU extensions:*command-line-words* - nil)) - -(defparameter *cmdline* (get-command-line)) - -(defun print-usage () - (format t "Usage: sbcl --script ch-1.lsp " - (first *cmdline*))) - -(when (< (length *cmdline*) 3) (print-usage) (quit)) - -(defparameter *coin-sum* (parse-integer (second *cmdline*))) -(defparameter *coin-lst* (map 'list #'parse-integer (cddr *cmdline*))) -(format t "Input:~%@C = ( ~{~d~^, ~} )~%" *coin-lst*) -(format t "$S = ~d~%" *coin-sum*) - -(let ((total-combi (combi-coin-sum *coin-sum* *coin-lst*))) - (format t "Output: ~d~%~%" (length total-combi)) - (format t "possible ways are:~%") - (map nil - #'(lambda (combi) - (progn - (format t "( ~{~d~^, ~} )~%" combi))) total-combi)) diff --git a/challenge-075/jeongoon/commmon-lisp/ch-2.lsp b/challenge-075/jeongoon/commmon-lisp/ch-2.lsp deleted file mode 100644 index bd4626846c..0000000000 --- a/challenge-075/jeongoon/commmon-lisp/ch-2.lsp +++ /dev/null @@ -1,116 +0,0 @@ -;; ( solution ... ) -;; which depends on combinations function -(defun get-largest-rect-area (histogram-data) - (let* - ((histogram-size (length histogram-data)) - (all-possible-area - (append - histogram-data ;; by size of width 1 - (map 'list - #'(lambda (pos) - (let* ((x1 (apply #'min pos)) ;; ensure x1 < x2 - (x2 (apply #'max pos)) - (common-height - (apply #'min (subseq histogram-data x1 (1+ x2))))) - (* common-height (1+ (- x2 x1))))) - (combinations-index 2 histogram-size))))) - (apply #'max all-possible-area))) - -;; ( bonus ... ) -(defun print-histogram (histogram-data) - (let* ((histogram-size (length histogram-data)) - (max-height (apply #'max histogram-data)) - (word-width (1+ (length (format nil "~d" max-height)))) - (fmt-string (format nil "~~~d@a" word-width))) - - (loop for y from max-height downto 1 collect - (let* ((line (format nil fmt-string y)) ;; first column: y scale - ) - ;; whitespace or sharpmark - (map nil - #'(lambda (x-data) - (let* ((current-word - (format nil fmt-string - (if (< x-data y) "" "#")))) - (setq line(concatenate 'string line current-word)))) - histogram-data) - (format t "~a~%" line) - line)) - (format t "~a~%" (make-string (* word-width (1+ histogram-size)) - :initial-element #\_)) - (format t fmt-string "") - (map nil - #'(lambda (x-data) (format t fmt-string x-data)) histogram-data) - (format t "~%"))) - -;; ( dependecies ... ) -(defun make-range (minv maxv &optional (step 1)) ;; from #072 - (when (<= minv maxv) - (cons minv (make-range (+ minv step) maxv step)))) - -(defun make-vector-range (min max &optional (step 1)) - (let* ((range (make-range min max step)) - (size (length range))) - (make-array (list size) :initial-contents range))) - -(defun combinations-index (n m) ;; translated from ch-2.pl - ;; a non-recursive method for making combinations - (when (>= m n) - (let* ((initial-room-size (- m n)) - (room (make-array (list n) :initial-element initial-room-size)) - (pos (make-array (list n) - :initial-contents (make-vector-range 0 (1- n)))) - (next-cursor (1- n)) - (combi (list (coerce pos 'list)))) ;; coerce makes a copy of array - (loop named moving-element do - (if (> (aref room next-cursor) 0) - ;; still current element move to right - (let ((ref-room (aref room next-cursor)) - (ref-pos (aref pos next-cursor))) - (setf (aref room next-cursor) (1- ref-room)) - (setf (aref pos next-cursor) (1+ ref-pos)) - (nconc combi (list (coerce pos 'list)))) - ;; else - ;; no more room left on the right for current element - ;; have to move cursor to point next avaiable one. - (let* - ((cursor-moved - (loop named moving-cursor for i from next-cursor above 0 - do - (when (> (aref room (1- i)) 0) - (setq next-cursor (1- i)) - (return-from moving-cursor t))))) - (if cursor-moved - (let ((room-size (1- (aref room next-cursor))) - (base-pos (aref pos next-cursor))) - (loop for i from next-cursor below n - for p from 1 do - (progn - (setf (aref room i) room-size) - (setf (aref pos i) (+ base-pos p)))) - (nconc combi (list (coerce pos 'list))) - (setq next-cursor (1- n))) - ;; else : "no more movement" means we found all combinations - (return-from moving-element combi)))))))) - -;; ( testing ... ) -(defun get-command-line () - (or - #+CLISP *args* - #+SBCL *posix-argv* - #+LISPWORKS system:*line-arguments-list* - #+CMU extensions:*command-line-words* - nil)) - -(defparameter *cmdline* (get-command-line)) - -(defun print-usage () - (format t "Usage: sbcl --script ch-2.lsp ..." - (first *cmdline*))) - -(when (< (length *cmdline*) 2) (print-usage) (quit)) - -(defparameter *histogram-data* (map 'list #'parse-integer (cdr *cmdline*))) -(format t "Input: @A = ~A~%" *histogram-data*) -(format t "Ouput: ~d~%" (get-largest-rect-area *histogram-data*)) -(print-histogram *histogram-data*) diff --git a/challenge-075/jeongoon/common-lisp/ch-1.lsp b/challenge-075/jeongoon/common-lisp/ch-1.lsp new file mode 100644 index 0000000000..075e153215 --- /dev/null +++ b/challenge-075/jeongoon/common-lisp/ch-1.lsp @@ -0,0 +1,65 @@ +;; tested with: +;; sbcl --script ch-1.lsp 6 1 2 4 # first one: sum; rest: coins +;; ( sollution ... ) +(defun combi-coin-sum (coin-sum coin-list) + (if (null coin-list) nil + ;; else + (let* + ((sorted-coin-list (sort coin-list #'<)) + (first-coin (car sorted-coin-list)) + (max-noc (floor coin-sum first-coin)) + (other-coins (cdr sorted-coin-list)) + (all-combi)) + (loop for noc from max-noc downto 0 + do + (let* ((small-change (- coin-sum (* first-coin noc)))) + (if (= small-change 0) + (let ((all-first-coins + (make-list noc :initial-element first-coin))) + (if (null all-combi) (setq all-combi (list all-first-coins)) + (nconc all-combi (list all-first-coins)))) + ;; else + (let ((sub-combis (combi-coin-sum small-change other-coins))) + (if (null sub-combis) nil + ;; else + (let ((head-combi + (make-list noc :initial-element first-coin))) + (map 'list + #'(lambda (a-sub-combi) + (let ((new-combi + (append head-combi a-sub-combi))) + (if (null all-combi) + (setq all-combi (list new-combi)) + (nconc all-combi (list new-combi))))) + sub-combis))))))) ;; if sub-combis is nil, + (remove-if #'null all-combi)))) ;; map will return nil + +;; ( testing ... ) +(defun get-command-line () + (or + #+CLISP *args* + #+SBCL *posix-argv* + #+LISPWORKS system:*line-arguments-list* + #+CMU extensions:*command-line-words* + nil)) + +(defparameter *cmdline* (get-command-line)) + +(defun print-usage () + (format t "Usage: sbcl --script ch-1.lsp " + (first *cmdline*))) + +(when (< (length *cmdline*) 3) (print-usage) (quit)) + +(defparameter *coin-sum* (parse-integer (second *cmdline*))) +(defparameter *coin-lst* (map 'list #'parse-integer (cddr *cmdline*))) +(format t "Input:~%@C = ( ~{~d~^, ~} )~%" *coin-lst*) +(format t "$S = ~d~%" *coin-sum*) + +(let ((total-combi (combi-coin-sum *coin-sum* *coin-lst*))) + (format t "Output: ~d~%~%" (length total-combi)) + (format t "possible ways are:~%") + (map nil + #'(lambda (combi) + (progn + (format t "( ~{~d~^, ~} )~%" combi))) total-combi)) diff --git a/challenge-075/jeongoon/common-lisp/ch-2.lsp b/challenge-075/jeongoon/common-lisp/ch-2.lsp new file mode 100644 index 0000000000..bd4626846c --- /dev/null +++ b/challenge-075/jeongoon/common-lisp/ch-2.lsp @@ -0,0 +1,116 @@ +;; ( solution ... ) +;; which depends on combinations function +(defun get-largest-rect-area (histogram-data) + (let* + ((histogram-size (length histogram-data)) + (all-possible-area + (append + histogram-data ;; by size of width 1 + (map 'list + #'(lambda (pos) + (let* ((x1 (apply #'min pos)) ;; ensure x1 < x2 + (x2 (apply #'max pos)) + (common-height + (apply #'min (subseq histogram-data x1 (1+ x2))))) + (* common-height (1+ (- x2 x1))))) + (combinations-index 2 histogram-size))))) + (apply #'max all-possible-area))) + +;; ( bonus ... ) +(defun print-histogram (histogram-data) + (let* ((histogram-size (length histogram-data)) + (max-height (apply #'max histogram-data)) + (word-width (1+ (length (format nil "~d" max-height)))) + (fmt-string (format nil "~~~d@a" word-width))) + + (loop for y from max-height downto 1 collect + (let* ((line (format nil fmt-string y)) ;; first column: y scale + ) + ;; whitespace or sharpmark + (map nil + #'(lambda (x-data) + (let* ((current-word + (format nil fmt-string + (if (< x-data y) "" "#")))) + (setq line(concatenate 'string line current-word)))) + histogram-data) + (format t "~a~%" line) + line)) + (format t "~a~%" (make-string (* word-width (1+ histogram-size)) + :initial-element #\_)) + (format t fmt-string "") + (map nil + #'(lambda (x-data) (format t fmt-string x-data)) histogram-data) + (format t "~%"))) + +;; ( dependecies ... ) +(defun make-range (minv maxv &optional (step 1)) ;; from #072 + (when (<= minv maxv) + (cons minv (make-range (+ minv step) maxv step)))) + +(defun make-vector-range (min max &optional (step 1)) + (let* ((range (make-range min max step)) + (size (length range))) + (make-array (list size) :initial-contents range))) + +(defun combinations-index (n m) ;; translated from ch-2.pl + ;; a non-recursive method for making combinations + (when (>= m n) + (let* ((initial-room-size (- m n)) + (room (make-array (list n) :initial-element initial-room-size)) + (pos (make-array (list n) + :initial-contents (make-vector-range 0 (1- n)))) + (next-cursor (1- n)) + (combi (list (coerce pos 'list)))) ;; coerce makes a copy of array + (loop named moving-element do + (if (> (aref room next-cursor) 0) + ;; still current element move to right + (let ((ref-room (aref room next-cursor)) + (ref-pos (aref pos next-cursor))) + (setf (aref room next-cursor) (1- ref-room)) + (setf (aref pos next-cursor) (1+ ref-pos)) + (nconc combi (list (coerce pos 'list)))) + ;; else + ;; no more room left on the right for current element + ;; have to move cursor to point next avaiable one. + (let* + ((cursor-moved + (loop named moving-cursor for i from next-cursor above 0 + do + (when (> (aref room (1- i)) 0) + (setq next-cursor (1- i)) + (return-from moving-cursor t))))) + (if cursor-moved + (let ((room-size (1- (aref room next-cursor))) + (base-pos (aref pos next-cursor))) + (loop for i from next-cursor below n + for p from 1 do + (progn + (setf (aref room i) room-size) + (setf (aref pos i) (+ base-pos p)))) + (nconc combi (list (coerce pos 'list))) + (setq next-cursor (1- n))) + ;; else : "no more movement" means we found all combinations + (return-from moving-element combi)))))))) + +;; ( testing ... ) +(defun get-command-line () + (or + #+CLISP *args* + #+SBCL *posix-argv* + #+LISPWORKS system:*line-arguments-list* + #+CMU extensions:*command-line-words* + nil)) + +(defparameter *cmdline* (get-command-line)) + +(defun print-usage () + (format t "Usage: sbcl --script ch-2.lsp ..." + (first *cmdline*))) + +(when (< (length *cmdline*) 2) (print-usage) (quit)) + +(defparameter *histogram-data* (map 'list #'parse-integer (cdr *cmdline*))) +(format t "Input: @A = ~A~%" *histogram-data*) +(format t "Ouput: ~d~%" (get-largest-rect-area *histogram-data*)) +(print-histogram *histogram-data*) -- cgit