# HG changeset patch # User Steve Losh # Date 1549688837 18000 # Node ID 9b2cfb112dd6150ac10ce455bf1dc2d39be9a4a8 # Parent 2bb2d67ebe221388b36be71919e0930a968d104c LEXV, PROB, PPER diff -r 2bb2d67ebe22 -r 9b2cfb112dd6 src/problems/lexv.lisp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/problems/lexv.lisp Sat Feb 09 00:07:17 2019 -0500 @@ -0,0 +1,69 @@ +(in-package :rosalind) + +(defparameter *input-lexv* + "D N A +3") + +(defparameter *output-lexv* + "D +DD +DDD +DDN +DDA +DN +DND +DNN +DNA +DA +DAD +DAN +DAA +N +ND +NDD +NDN +NDA +NN +NND +NNN +NNA +NA +NAD +NAN +NAA +A +AD +ADD +ADN +ADA +AN +AND +ANN +ANA +AA +AAD +AAN +AAA +") + + +(define-problem lexv (data stream) + *input-lexv* + *output-lexv* + (let* ((alphabet (remove #\space (read-line data))) + (n (read data)) + (string (make-string n))) + (with-output-to-string (s) + (recursively ((n n) + (i 0)) + (unless (zerop i) + ;; The empty string *is* first, lexicographically, but I don't think + ;; they accept it in the answer for some reason. + (write-string string s :end i) + (terpri s)) + (unless (zerop n) + (map nil (lambda (ch) + (setf (aref string i) ch) + (recur (1- n) (1+ i))) + alphabet)))))) + diff -r 2bb2d67ebe22 -r 9b2cfb112dd6 src/problems/lia.lisp --- a/src/problems/lia.lisp Mon Dec 24 15:39:03 2018 -0500 +++ b/src/problems/lia.lisp Sat Feb 09 00:07:17 2019 -0500 @@ -14,61 +14,6 @@ ;; Because A's and B's are independent, this means there's a 1/2 * 1/2 = 1/4 ;; chance of any given child being Aa Bb. -(defmacro do-sum ((var from to) &body body) - "Sum `body` with `var` iterating over `[from, to]`. - - It's just Σ: - - to - === - \ - > body - / - === - n = from - - " - (once-only (to) - (with-gensyms (result) - `(do ((,var ,from (1+ ,var)) - (,result 0)) - ((> ,var ,to) ,result) - (incf ,result (progn ,@body)))))) - -(defmacro do-product ((var from to) &body body) - "Multiply `body` with `var` iterating over `[from, to]`. - - It's just Π: - - to - ===== - | | - | | body - | | - n = from - - " - (once-only (to) - (with-gensyms (result) - `(do ((,var ,from (1+ ,var)) - (,result 1)) - ((> ,var ,to) ,result) - (setf ,result (* ,result (progn ,@body))))))) - - -(defmacro Σ (bindings &body body) ;; lol - `(do-sum ,bindings ,@body)) - -(defmacro Π (bindings &body body) ;; lol - `(do-product ,bindings ,@body)) - - -(defun binomial-coefficient (n k) - "Return `n` choose `k`." - ;; https://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula - (Π (i 1 k) - (/ (- (1+ n) i) i))) - (defun bernoulli-exactly (successes trials success-probability) "Return the probability of exactly `successes` in `trials` Bernoulli trials. diff -r 2bb2d67ebe22 -r 9b2cfb112dd6 src/problems/pper.lisp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/problems/pper.lisp Sat Feb 09 00:07:17 2019 -0500 @@ -0,0 +1,31 @@ +(in-package :rosalind) + +(defparameter *input-pper* + "21 7") + +(defparameter *output-pper* + "51200") + + +(define-problem pper (data stream) + *input-pper* + *output-pper* + (let ((total (read data)) + (size (read data))) + ;; The number of combinations of k out of n elements is: + ;; + ;; (n choose k) = n! / k!(n-k)! + ;; + ;; To get the number of permutations, we multiply by the number of different + ;; ways to order the k elements and it ends up simplifying nicely: + ;; + ;; k!(n choose k) = k!n! / k!(n-k)! + ;; = n! / (n-k)! + ;; = (n)(n-1)(n-2)…(n-(k-1)) + ;; + (flet ((count-permutations (size total) + (iterate (for i :downfrom total) + (repeat size) + (multiplying i)))) + (mod (count-permutations size total) + 1000000)))) diff -r 2bb2d67ebe22 -r 9b2cfb112dd6 src/problems/prob.lisp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/problems/prob.lisp Sat Feb 09 00:07:17 2019 -0500 @@ -0,0 +1,30 @@ +(in-package :rosalind) + +(defparameter *input-prob* + "ACGATACAA +0.129 0.287 0.423 0.476 0.641 0.742 0.783") + +(defparameter *output-prob* + "-5.737 -5.217 -5.263 -5.360 -5.958 -6.628 -7.009") + + +(define-problem prob (data stream) + *input-prob* + *output-prob* + (let ((dna (read-line data)) + (gc-contents (read-all-from-string (read-line data)))) + (labels + ((gcp (base) + "Return whether `base` is G or C." + (or (char= #\G base) + (char= #\C base))) + (base-probability (gc-content base) + "Return the probability of `base` in DNA with the given `gc-content`." + (if (gcp base) + (/ gc-content 2) + (/ (- 1 gc-content) 2))) + (prob (gc-content) + (iterate + (for base :in-string dna) + (summing (log (base-probability gc-content base) 10))))) + (format nil "~{~,3F~^ ~}" (mapcar #'prob gc-contents))))) diff -r 2bb2d67ebe22 -r 9b2cfb112dd6 src/utils.lisp --- a/src/utils.lisp Mon Dec 24 15:39:03 2018 -0500 +++ b/src/utils.lisp Sat Feb 09 00:07:17 2019 -0500 @@ -95,6 +95,63 @@ result)) +;;;; Math --------------------------------------------------------------------- +(defmacro do-sum ((var from to) &body body) + "Sum `body` with `var` iterating over `[from, to]`. + + It's just Σ: + + to + === + \ + > body + / + === + n = from + + " + (once-only (to) + (with-gensyms (result) + `(do ((,var ,from (1+ ,var)) + (,result 0)) + ((> ,var ,to) ,result) + (incf ,result (progn ,@body)))))) + +(defmacro do-product ((var from to) &body body) + "Multiply `body` with `var` iterating over `[from, to]`. + + It's just Π: + + to + ===== + | | + | | body + | | + n = from + + " + (once-only (to) + (with-gensyms (result) + `(do ((,var ,from (1+ ,var)) + (,result 1)) + ((> ,var ,to) ,result) + (setf ,result (* ,result (progn ,@body))))))) + + +(defmacro Σ (bindings &body body) ;; lol + `(do-sum ,bindings ,@body)) + +(defmacro Π (bindings &body body) ;; lol + `(do-product ,bindings ,@body)) + + +(defun binomial-coefficient (n k) + "Return `n` choose `k`." + ;; https://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula + (Π (i 1 k) + (/ (- (1+ n) i) i))) + + ;;;; Iterate ------------------------------------------------------------------ (defmacro-driver (FOR var SEED seed THEN then) "Bind `var` to `seed` initially, then to `then` on every iteration. @@ -265,7 +322,7 @@ ;;;; Uniprot ------------------------------------------------------------------ -(defvar *uniprot-cache* (make-hash-table :test #'equal)) +(defparameter *uniprot-cache* (make-hash-table :test #'equal)) (defmacro get-cached (key cache expr) (once-only (key cache)