# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1660001178 14400
# Node ID 97dda08645b3fb098228345e889e788a7e56d12e
# Parent  7fcd748a4f00830bb3655d2a5c4ad5869b7e5435
SCSP

diff -r 7fcd748a4f00 -r 97dda08645b3 src/problems/scsp.lisp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/scsp.lisp	Mon Aug 08 19:26:18 2022 -0400
@@ -0,0 +1,30 @@
+(defpackage :rosalind/scsp (:use :cl :rosalind :losh :iterate))
+(in-package :rosalind/scsp)
+
+(defparameter *input* "ATCTGAT
+TGCATA")
+
+(defparameter *output* "ATCTGCATA")
+
+
+(defun shortest-common-supersequence (a b)
+  ;; Since we did LCS with a dynamic programming table, let's use memoization
+  ;; for this one.
+  (let ((seen (make-hash-table :test #'equal)))
+    (_ (recursively ((a (reverse (coerce a 'list)))
+                     (b (reverse (coerce b 'list))))
+         (alexandria:ensure-gethash (list a b) seen
+           (cond ((null a) b)
+                 ((null b) a)
+                 (t (let ((ca (first a))
+                          (cb (first b)))
+                      (if (char= ca cb)
+                        (cons ca (recur (rest a) (rest b)))
+                        (alexandria:extremum (list (cons ca (recur (rest a) b)) ; lol
+                                                   (cons cb (recur a (rest b))))
+                                             #'< :key #'length)))))))
+      nreverse
+      (coerce _ 'string))))
+
+(define-problem scsp (data stream) *input* *output*
+  (shortest-common-supersequence (read-line data) (read-line data)))