src/problems/scsp.lisp @ 97dda08645b3 default tip

(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)))