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
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()
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]
The output looks like:
A
A
C
T
T
G
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!
You should be able to pass an additional variable of type 'var string' around your recursive functions, and simply use add() to add characters as you go - strings in Nim are modifiable and adding to them is cheap.
When you've fully bubbled back up the call stack the result is there for you in your string.
Grabbing the result from stdout(echo) is a bit of a detour. You usually want to seperate the calculation of something from the I/O. So for example if you later want to use that function in a GUI application you wouldn't need any modifications to the function itself, you would fetch the inputs from the GUI and then put the calculated values back into the GUI.
As a small note, your output_lcs proc has the return type string, but never writes to it, so it always returns an empty string when using echo.
Now let's come back to the question. One solution would be always return the concatenated results of the recursive calls, like so:
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:
result.add output_lcs(backtrack, v, i-1, j)
elif backtrack[i][j] == 2:
result.add output_lcs(backtrack, v, i, j-1)
else:
result.add output_lcs(backtrack, v, i-1, j-1)
result.add v[i-1]
The only thing left to do, is to remove the result = "" in the calling proc, so the last statement can count as an implicit return(we could also prepend the call by a return, but this way it's cleaner)
Alternatively we could also pass a string as a var parameter, so we can modify the passed variable:
proc output_lcs(backtrack: seq[seq[int]], v: string, i: int, j: int, result: var string)=
if i == 0 or j == 0:
return
if backtrack[i][j] == 1:
output_lcs(backtrack, v, i-1, j)
elif backtrack[i][j] == 2:
output_lcs(backtrack, v, i, j-1)
else:
output_lcs(backtrack, v, i-1, j-1)
result.add v[i-1]
In case we use this method, we also have to change the initial call, so that the recursive proc writes into the result variable of lcs_backtrack:
output_lcs(backtrack, v, vlen, wlen, result)
The latter solution is more efficient, since it only modifies the output the string when needed, though it doesn't really matter in this situation, because the bottlenecks lie in other places.