4 ms·
My TXR Lisp session from the last 5 minutes: This is the TXR Lisp interactive listener of TXR 221. Quit with :quit or Ctrl-D on empty line. Ctrl-X ? for ch
by kazinator 7y ago
My TXR Lisp session from the last 5 minutes:
This is the TXR Lisp interactive listener of TXR 221.
Quit with :quit or Ctrl-D on empty line. Ctrl-X ? for cheatsheet.
1> (defun subseqs (seq)
(if (plusp (len seq))
(cons seq (append (subseqs [seq 0..-1]) (subseqs [seq 1..:])))))
subseqs
2> (subseqs "abc")
("abc" "ab" "a" "b" "bc" "b" "c")
3> (defun longest-subseq (. seqs)
(let ((subseq-sets (mapcar [chain subseqs hash-list] seqs)))
subseq-sets))
longest-subseq
4> (longest-subseq "abc" "cde")
(#H(() ("a" "a") ("c" "c") ("bc" "bc") ("ab" "ab") ("b" "b") ("abc" "abc"))
#H(() ("cd" "cd") ("d" "d") ("cde" "cde") ("c" "c") ("e" "e") ("de" "de")))
5> (defun longest-subseq (. seqs)
(let* ((subseq-sets (mapcar [chain subseqs hash-list] seqs))
(isec [reduce-left hash-isec subseq-sets]))
(car (find-max isec : [chain car len]))))
longest-subseq
6> (longest-subseq "ABABC" "BABCA" "ABCBA")
"ABC"
7>
Basically, convert the lists of subsequences into hashes (thus sets). Then just reduce-left over hash-isec to find the intersection of these hashes. Then find-max to get the maximum element. The third argument of find-max is the key function through which elements are projected to get the comparison key. Under find-max, hash elements are considered to be conses. We want the maximum length so we chain together car and len.
The : symbol in a function argument list means "use whatever is the default value for this optional argument"; in this case, it tells find-max to use the default comparison function.
(P.S. What we should be doing here is finding the maximum length among the input strings, and then generating substrings of only up to that length.)