Longest common subsequence test case fails

Question

I have implemented this algorithm for the Longest common subsequence, I have tested it for every possible test case, it works, but when I submit it to the online grader of the course, it says it failed on case 11, I can't think of any possible test case that would break it down. Can you help? It returns idx longest subsequence.

def lcs2(a, b):
    idx = 0
    for i in a:
        if i not in b:
            a.remove(i)
    if len(a) <= len(b):
        for i in a:
           if i in b:
               idx += 1; b = b[b.index(i)+1:]

    else:
        for i in b:
           if i in a:
               idx += 1; a = a[a.index(i)+1:]
    return idx

What is the idx requirement for two mutually exclusive sequences? 0 or some negative value? Same question in case a is empty sequence. — Assafs, Jan 07 '19 at 09:21
How should we know what 'case 11' is? So check the problem description, what values are valid for the parameters and make sure your implementation meets all this constraint. If your implementation still fails, the specification is bad and you should contact the "online grader" for clarification. — MrSmith42, Jan 07 '19 at 09:32
@J.Moh: Yes he found an example. That's what is missing in your question. — MrSmith42, Jan 07 '19 at 10:10
This returns the wrong answer (2 instead of 1) for ("ab","ba"), and just about every other case where the sequences have the same elements in a different order. You said you tested "every possible test case", so I guess you inadvertently limited the system you used to enumerate possible test cases. — Matt Timmermans, Jan 07 '19 at 14:07
please have a look on this https://stackoverflow.com/questions/54120770/longest-common-subsequence-python-greedy — v_head, Jan 10 '19 at 01:26

Index Ama · Answer 1 · 2019-01-07T09:45:28.360

1

I can hack you with a sample: a = [1,2,3,4,5] b = [2,3,4,1,5]

one correct solution is Dynamic Programming

edited Jan 07 '19 at 09:45

answered Jan 07 '19 at 09:22

Index Ama

69
2

1

There is no 'the correct solution'. Even if Dynamic Programming seams to be the best obvious choice, I can think of other attempts that also produce correct results. – MrSmith42 Jan 07 '19 at 09:37
I'm sorry it's not good for my English. Maybe I should use “one correct solution(´･Д･)」 – Index Ama Jan 07 '19 at 09:43
Please take a look at this: https://stackoverflow.com/questions/54120770/longest-common-subsequence-python-greedy – v_head Jan 10 '19 at 01:25
IndexAma@ please if you could hack one more time for the above link – v_head Jan 10 '19 at 01:28

score 1 · Answer 2 · answered Jan 07 '19 at 10:04

1

What you seem to be searching for is not the longest common subsequence, but the length of this longest common subsequence. However, the wrong assumption is that the first of the two lists contains the start of this subsequence at an earlier index than the second list.

The answer supplied already gives an example of where this happens:

a = [1,2,3,4,5]
b = [2,3,4,1,5]

I will expand with:

c = [3,4,2,1,5]

You will see that:

import itertools as it
rets = [lcs2(x,y) for x,y in it.permutations([a,b,c],2)]
combis = [(x,y) for x,y in it.permutations(['a','b','c'],2)]
print(*zip(rets, combis), sep='\n')
#(2, ('a', 'b'))
#(2, ('a', 'c'))
#(4, ('b', 'a'))
#(3, ('b', 'c'))
#(3, ('c', 'a'))
#(4, ('c', 'b'))

In other words, the lcs2 function you defined is a-symmetrical and therefore not correct.

answered Jan 07 '19 at 10:04

Uvar

3,372
12
25

I see, please if you could comment on what I edited, I know DP is the optimal, I just want to see what I can get here. – v_head Jan 07 '19 at 10:30
please if you could take a look at this https://stackoverflow.com/questions/54120770/longest-common-subsequence-python-greedy – v_head Jan 10 '19 at 01:25
I did; and got lost in the fuzzy structuring of your question. It is unclear what you perceive to be the correct answer, what your Coursera thing sees as the correct answer and whether you are aware of the difference between llcs and longest substring. The linked question in the linked question has a correct implementation of both by Martijn Pieters. You just have to copy-paste the right one. Additionally, the algo you came up with yourself appears to do the trick in many cases as well; but be aware you're changing one of the lists you pass to the lcs2 function. So lcs2(a,b); lcs2(a,b) differs – Uvar Jan 10 '19 at 08:58

Longest common subsequence test case fails

2 Answers2