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!

Reply via email to