# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1550881397 18000
# Node ID 7052ec0c6e1deb5c7ec5d309cf92e646d58b8ed9
# Parent  e0c558fa549bdc631e645b708b232facb4e9aa5e
PMCH

diff -r e0c558fa549b -r 7052ec0c6e1d src/problems/pmch.lisp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/pmch.lisp	Fri Feb 22 19:23:17 2019 -0500
@@ -0,0 +1,32 @@
+(in-package :rosalind)
+
+(defparameter *input-pmch* ">Rosalind_23
+AGCUAGUCAU")
+
+(defparameter *output-pmch* "12")
+
+;; We can make a few observations to make things easier (well, trivial).
+;;
+;; First: the adjacency edges are a red herring.  Ignore them.
+;;
+;; Next: because adenine only interacts with uracil and guanine only interacts
+;; with cytosine, we can split the problem apart into two separate graphs.  We
+;; can compute the number of perfect matchings of each graph separately and then
+;; multiply them together at the end to find the total.
+;;
+;; For each sub graph, every node has edges to all nodes of the complementary
+;; base.  The problem description also guarantees that the number of
+;; complementary bases are equal.
+;;
+;; Say we're looking at the A/U graph, and there are N adenine bases and
+;; N uracil bases.  For each adenine, we need to pick a uracil to match it with.
+;; For the first adenine we have N uracil's to choose from.  For the second
+;; adenine we have N-1 uracils.  And so on down to the final pair.  So the total
+;; number of choices we have for each graph is N(N-1)(N-2)…(1) = N!
+
+(define-problem pmch (data stream)
+    *input-pmch*
+    *output-pmch*
+  (let ((bases (nth-value 1 (read-fasta data))))
+    (* (factorial (count #\A bases))
+       (factorial (count #\G bases)))))