# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1551472298 18000
# Node ID f94bcb40467614422884e1d59d167f24153182ec
# Parent  64aa58880d55892b85facf4ea8aedb0f080c3f70
LONG

diff -r 64aa58880d55 -r f94bcb404676 rosalind.asd
--- a/rosalind.asd	Sat Feb 23 12:42:13 2019 -0500
+++ b/rosalind.asd	Fri Mar 01 15:31:38 2019 -0500
@@ -24,6 +24,7 @@
                :1am
                :alexandria
                :cl-digraph
+               :cl-digraph.dot
                :cl-ppcre
                :drakma
                :iterate
diff -r 64aa58880d55 -r f94bcb404676 src/problems/long.lisp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/long.lisp	Fri Mar 01 15:31:38 2019 -0500
@@ -0,0 +1,39 @@
+(in-package :rosalind)
+
+(defparameter *input-long*
+  ">Rosalind_56
+ATTAGACCTG
+>Rosalind_57
+CCTGCCGGAA
+>Rosalind_58
+AGACCTGCCG
+>Rosalind_59
+GCCGGAATAC")
+
+(defparameter *output-long*
+  "ATTAGACCTGCCGGAATAC")
+
+
+(defun overlap (left right)
+  "Return the number of overlapping characters in `left` and `right`."
+  (iterate
+    (for size :from (min (length left) (length right)) :downto 0)
+    (for i = (- (length left) size))
+    (finding size :such-that (string= left right :start1 i :end2 size))))
+
+(defun join-overlapping (left right)
+  "Join `left` and `right` together, overlapping as much as possible."
+  (concatenate 'string left (subseq right (overlap left right))))
+
+
+(define-problem long (data stream)
+    *input-long*
+    *output-long*
+  (let* ((dna (mapcar #'cdr (read-fasta-into-alist data)))
+         (graph (digraph:make-digraph :initial-vertices dna :test #'equal)))
+    (dolist (left dna)
+      (dolist (right dna)
+        (when (and (not (equal left right))
+                   (> (overlap left right) (floor (length left) 2)))
+          (digraph:insert-edge graph right left)))) ; reversed edges for toposort
+    (reduce #'join-overlapping (digraph:topological-sort graph))))
diff -r 64aa58880d55 -r f94bcb404676 src/utils.lisp
--- a/src/utils.lisp	Sat Feb 23 12:42:13 2019 -0500
+++ b/src/utils.lisp	Fri Mar 01 15:31:38 2019 -0500
@@ -298,7 +298,7 @@
   `vars` must be a list of two symbols that will be bound to the label and data,
   respectively, on each iteration.
 
-  `stream` can be either a string or a character input stream.
+  `source` can be either a string or a character input stream.
 
   `generate` is supported.