This is a homework problem where I am using nim to identify the longest common
subsequence. I have the correct output, but I don't know how to grab the output
from a recursive algorithm.
Example:
AACCTTGG
ACACTGTGA
Run
Code to run example:
import os, strutils, sequtils
# down = 1
# right = 2
# diag = 3
proc pp[T](matrix: seq[seq[T]]): char =
for line in matrix:
echo line
proc output_lcs(backtrack: seq[seq[int]], v: string, i: int, j: int):
string =
if i == 0 or j == 0:
return
if backtrack[i][j] == 1:
discard output_lcs(backtrack, v, i-1, j)
elif backtrack[i][j] == 2:
discard output_lcs(backtrack, v, i, j-1)
else:
discard output_lcs(backtrack, v, i-1, j-1)
echo v[i-1]
proc lcs_backtrack(v: string, w: string): string =
let vlen: int = v.len
let wlen: int = w.len
let sfill = repeat(repeat(0, wlen + 1), vlen + 1)
let btfill = repeat(repeat(0, wlen + 1), vlen + 1)
var s: seq[seq[int]]
var backtrack: seq[seq[int]]
result = ""
s.add(sfill)
backtrack.add(btfill)
echo "starting matrices: "
echo pp(s)
echo pp(backtrack)
for i in 1..vlen:
for j in 1..wlen:
if v[i-1] != w[j-1]:
s[i][j] = max(@[s[i-1][j], s[i][j-1]])
else:
s[i][j] = max(@[s[i-1][j], s[i][j-1], s[i-1][j-1] + 1])
if s[i][j] == s[i-1][j]:
backtrack[i][j] = 1
elif s[i][j] == s[i][j-1]:
backtrack[i][j] = 2
elif s[i][j] == s[i-1][j-1] + 1 and v[i-1] == w[j-1]:
backtrack[i][j] = 3
echo "s after pop: "
echo pp(s)
echo "backtrack after pop: "
echo pp(backtrack)
echo output_lcs(backtrack, v, vlen, wlen)
proc main() =
let f = open(paramStr(1))
defer: f.close()
let
v = f.readLine()
w = f.readLine()
echo lcs_backtrack(v, w)
main()
Run
I'm a bad coder so please ignore that. My main problem is with my recursive
function:
proc output_lcs(backtrack: seq[seq[int]], v: string, i: int, j: int):
string =
if i == 0 or j == 0:
return
if backtrack[i][j] == 1:
discard output_lcs(backtrack, v, i-1, j)
elif backtrack[i][j] == 2:
discard output_lcs(backtrack, v, i, j-1)
else:
discard output_lcs(backtrack, v, i-1, j-1)
echo v[i-1]
Run
The output looks like:
A
A
C
T
T
G
Run
which is the correct answer "AACTTG". But i'm not sure how to grab that output
from echo (return doesn't work since it simply returns the the first return
statement after i and j are both equal to 0.
Hopefully this made a bit of sense. Thanks!