5 kyu
Longest Common Subsequence
2,041 of 6,945xDranik
Loading description...
Strings
Algorithms
View
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
Random tests in Haskell could use some work:
Char
, leading to pairs of strings like"G8\1100651\95058\SUB\\A\b"
and"\n\n"
expected: 0 but got: 3
, with no indication of what the numbers indicate.expected: True but got: False
, which again does not tell the solver what the actual problem is.I've made a fork that addresses all of these along with updating the reference solution to be much more efficient.
Remember to not make the refsol a spoiler for the performance version.
It seems that the performance version has looser performance requirements than I expected, because my refsol only performs a single optimization to trim the search space for common subsequences instead of the full DP implementation.
I've forked my fork, reverting the reference solution.
Interesting kata, if only you could add Kotlin :)
Are you volunteering to translate it? 😆
Nice one, quite challenging kata.
'notatest' should equal 'nottest'
This is wrong, since:
"A subsequence is different from a substring. The terms of a subsequence need not be consecutive terms of the original sequence."
Since it does not have to be in consecutive terms, why is
a
excluded fromanothertest
andnotatest
? They both only have onea
.Correct me if I'm wrong, I'm passing all the other random tests and basic tests, except for this one case.
You are wrong, because you can't reorder the letters:
With that definition it means
not
andtest
can have some other letters in the middle like in this casea
in the second string orher
in the first one.2/2 A subsequence must be delivered in order. You can say on the instructions that you want it not to be ordered, or it is, or this is and that is not, it is your choice. That you cannot do is require in the test that the string is ordered if it is made up of numbers and not if it is made up of letters without saying anything about this on the instructions...
Where do you see that, in which language?
i dont remember, but the language was Javascript
This comment has been hidden.
TWO ISSUES
1/2 - You must add that although they do not have to be consecutive, they must maintain the direction towards the end of the array, that is, if the first matching term is at index 3 of the longest string, the second cannot be at an index less than 3 ... Your instructions lead to error, non-consecutive does not imply that it must have an address, and you require it in LCD("anothertest", "notatest") ...
I don't get what the issue is here. The
n
is at index 1 in the first string (the longest in your example) and in the index 0 of the second one. What do you mean with what your wrote?This kata allows code that doesn't return the longest subsequence to pass. I noticed this after trying the 4 kyu performance version, which has an extra initial test: lcs("abcdefghijklmnopq", "apcdefghijklmnobq"), which should return "acdefghijklmnoq". My Python solution returns "abq" for that test but still passes this kata. You should add that test (and maybe some other similar ones) to prevent incorrect code from passing.
java no random tests, check this solution
C++ translation has been made https://www.codewars.com/kumite/62ffd7f3fab8d20975599eb7
This comment has been hidden.
Your code not working is not a kata issue.
This comment has been hidden.
That Java assertion is fine, see this discourse to see why lcs of
"anothertest"
and"notatest"
is"nottest"
Why is there no kata in c++?
Because nobody has created a C++ translation yet.
Great kata.. I relly enjoyed this one !
This comment has been hidden.
x: anothertest y: notatest My result: notatest exepted: nottest why is the correct anwser is nottest it should be notatest??
you're supposed to search subsequences, meaning you cannot swap letters in one of the inputs
This comment has been hidden.
No, the test is ok. Why do you think it could be wrong?
Would really like to try this in C#. Hopefully a beautiful mind could hook a brother up?
Ruby 3.0 should be enabled.
Enabled in this fork
This comment has been hidden.
For example, ... ? Go has ~120 completions, so I doubt it.
This comment has been hidden.
You can print the input to console. I don't do Go, so I can't fully understand your code.
Yep. The example given with numbers should make it clear.
Right good idea, I'll print the input :) Thanks!
elo if x,y is anothertest , notatest why i get 'aenost' should equal 'nottest' isn't wrong ?
finaltest zzzfinallyzzz 'afiln' should equal 'final'
is f - i subsequence or a -f is more logic cuz we sorting it as subsequence of letters (a-z) or numbers(0-9) not making usfull words and final got 0 subsequence of letters
You don't need to sort anything, that's the point. This kata isn't about longest sorted common subsequence.
Anyway, not a kata issue, so closing...
ya my bad thanks.
lcs(anothertest, notatest) should return test. But the assert test is expecting 'nottest' in python
The test is ok.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Not a kata issue, you need to return a subsequence (the order matters), not a subset.
I would propose to add a couple hard coded test cases. I managed to pass by luck on the randomly generated but my solution doesn't always returns the optimal solution. Here are a couple :
eidhacgfb
gifbcdaeh
BEST: idh
MINE: da
dgafceihb
adgebichf
BEST: dgeih
MINE: aeih
fbedgicha
aebchifdg
BEST: fdg
MINE: ei
This comment has been hidden.
There's a small mistake in the description section of the python translation of this kata:
Example subsequence
Subsequences of "abc" = "a", "b", "c", "ab", "ac", "bc" and "abc".
"ac" is not a subsequence of "abc" :)
This is okay, because of this part of the kata description:
Ahh you're right :) my mistake
This comment has been hidden.
That your code returned only
"a"
instead of"ac"
, read the instructions again, they are subsequences, not substrings, so"a"
and"c"
could be not next to each other.This comment has been hidden.
The test is saying that the Longest Common Subsequence of "anothertest" and "notatest" is the substring "nottest". Please explain how this is correct. It makes absolutely no sense.
Same issue. Which exmample in the description? - EDIT - a commment further down explained what the problem is.
This kata might as well just be the link to the wikipedia page and that's it.
Feels like school :(
So I've solve the Kata! However on submit I was sent to blocked solutions page. I'm wondering whats gone wrong here. Quite possible my solution just sucked horribly and did not deserve the on honor of seeing the solutions. Or is this a bug?
On further thoughts, maybe the codewars servers are just struggling to update quick enough. Along side the horde's of coders using codewars.
It's a known bug. https://github.com/Codewars/codewars.com/issues/311
My appologies if someone has already pointed this out, but I noticed that the tests do not cover cases where two strings are of equal length, many solutions pass because they get "lucky".
Test.assertEquals(LCS("132535365", "123456789"), "12356") // Test Passed: Value == '12356' Test.assertEquals(LCS("123456789", "132535365"), "12356") // Expected: '12356', instead got: '1356'
I have a problem : expected: not[]test but was:not[a]test I don't know what I am doing wrong :(
print the inputs to the console.
I don't know the input, because it is the RandomTest. I hope that someone had the same or similar problem.
That's precisely the reason why I told you to... print the inputs... from inside your code! x)
(or are they so big that you reach the max buffer limit before you see the actual inputs? In the 5kyu version of the problem, that shouldn't be a trouble, iirc).
This comment has been hidden.
print it to the console.
This comment has been hidden.
Fixed. Upgraded to python3.8
You need to add more sample cases. You are wasting people's time by not adding
Test.assertEquals(LCS("anothertest","notatest") , "nottest);
Your Kata is just making alot of people frustrated. Having only 2 test shown is lazy.
Lazy is looking at all kinds of tests instead of thinking about all the cases when the problem is already completely defined. (It's not that the tests must not be added, but they don't have to.)
I have get in Java version result of test expected: <a[c]> but was:<a[]> Result must be String. What does it mean a[c]? String "a" or "c" ? Correct wrong result usually look like this : expected:<[ab]> but was:<[abc]>
Brackets signifies the difference between both results.
Thank you. The first time I haven't understood the instructions correctly
The tests are REALLY tolerable. I see a couple of quite stupid Haskell solutions. Makes me feel kind of discouraged.
X="anothertest" Y="notatest" Expected: 'nottest', instead got: 'anotetst'. I don't understand. Why the "a" is not included?
'anotetst'
is not a subsequence of'notatest'
order matters.You can skip some chars, not rearrange them.
https://www.codewars.com/kata/reviews/5275754fa4bf4a81f7000304/groups/52fa94ddae9cf038070000ff Apparently tests are not covering longest solution possible. Please add 2 cases: 'bert' == LCS 'berta', 'albert' 'bert' == LCS 'albert', 'berta'
getting error: expected:<not[test]> but was:<not[aes]>
where can I see input parameters values for this sample test?
This comment has been hidden.
This comment has been hidden.
Scala translation submitted, can someone have a look ?
The tests for submission should show input and output, because it's pretty much impossible to debug without seeing what my function is outputting (I pass all tests accept the last one).
Should pass, since it's the same combination
The order matters, they're subsequences, not subsets.
Description says
Also
No.
Test case: "anothertest" "notatest" fails with
Why? "anothertest" has all of the characters of "notatest". This means any combination of "notatest" characters is correct.
No, order matters. A subsequence can skip some chars, but not rearrange them.
IN THE FINAL TEST, THE KATA GIVES:
anothertest notatest
AND RESPONCE:
'test' should equal 'nottest'
IS 'nottest' A SUB?
['n', 'no', 'not', 'nota', 'notat', 'notate', 'notates', 'notatest', 'o', 'ot', 'ota', 'otat', 'otate', 'otates', 'otatest', 't', 'ta', 'tat', 'tate', 'tates', 'tatest', 'a', 'at', 'ate', 'ates', 'atest', 't', 'te', 'tes', 'test', 'e', 'es', 'est', 's', 'st', 't']
description:
My solution passes, but shouldn't.
In this other kata there's the test of:
abcdefghijklmnopq
vsapcdefghijklmnobq
, which should beacdefghijklmnoq
. That's not what my code produces because it doesn't do a deeper search of skipping certain matches to get a longer subsequence.I don't understand why this is 4 kyu. Are the test cases so simplistic that I am actually doing something I shouldn't?
This comment has been hidden.
A bit of an ordeal trying to figure out what a "subsequence" is. It's not explained in the description or the wikipedia entry, as far as I can see. I'd recommend explicitly stating that each character of the LCS should be found after the previous character within each string.
.
This comment has been hidden.
not should equal "nottest". Woah, what a nice fail statement. Really makes me want to rate this zero.
Sick of solving katas, only to discover they cannot be beaten due to some bullshit assert statement.
Add test cases to "prevent" solutions like https://www.codewars.com/kata/reviews/5486115fd8325ec04c0001ea/groups/55988c1318b9e971f300001a or https://www.codewars.com/kata/reviews/5486115fd8325ec04c0001ea/groups/57cd9854fa9fc50f580002b7 which do not preserve the order of the input strings.
E.g. lcs "12345" "45321" == "45"
Also, a property test could be added to verify that lcs x y == lcs y x
I'm receiving an error that says 'a' should not in the expected results. Doing a console log of the two sequences reveals that it should be included. I'm not sure why or what to do about it. Hope to hear from you soon! :)
Example subsequence
Subsequences of "abc" = "a", "b", "c", "ab", "ac", "bc"
"ac"!
This is far too easy for 4 kyu. Very long strings should be added to the tests to avoid solving it by brute force. If you have to use recursion and memoization to first find the lcs length this could be accepted as difficulty 4.
Haskell
Imho this is too easy for 4kyu. Some nice solutions though.
What is the third test case? My function works for all the tests before it, just not that one. It says "Expected: ac, instead got: a".
you can write:
console.log(x); console.log(y);
at the beginning of your function,then you can see the parameters when you run test cases
I got same problem on same test case, after print out x and y. x = 'abc', y = 'ac', instead of accept 'a' or 'c',
Result: Expected: ac, instead got: c
is this correct?
Yes.
As noted by @computerguy103 7 months ago, this kata really needs improvement - it must have more complicated test cases with intermittent subsequences.
This is critical to improve right now, because this kata will soon reach 500 solutions and then test cases will become permanent.
Contributors, please add more test cases ASAP!
Ruby translation submitted :)
Python translation complete.
Approved some time ago
It would help if there was another test cases to possibly trap solutions which don't correctly look ahead to find the longest common subsequence.
It's possible that some solutions (this one, for instance) would return either
"apq"
or"abq"
, depending on which string they're using as the basis to match characters into the other string.Also, that appears to be a difficult test case to compute - many of the solutions took around 3-3.5 seconds on my machine, and one took more than 2 minutes. It could be a good test of the solution's efficiency, causing inefficient solutions to time out.
This comment has been hidden.
hi, one of the tests are failing for me (nottest != notatest), the one thing I don't love about this Kata is that I don't even really know where to start when trying to debug that problem as many different combinations can yield the result nottest :\
This comment has been hidden.
This is still an issue today. I guess this issue will not be fixed. :/
Although I understand that the LCS problem could figure on Codewars for completeness sake, the kata itself doesn't introduce any new element to it. This leaves mainly three options:
I prefer katas where the solution to the problem is not immediately obvious. Calling the problem "LCS" and asking for a straightforward implementation is not very challenging.
Understanding the problem and how the algorithm is supposed to work is a challenge. No one can stop you from googling the answer, but sitting down and figuring it out without google, in my opinion, is definitely a challenge.
How many people do you know that are capable of finding LCS by themselves if they don't know the algorithm before? The challenge should be to adapt LCS to a new situation and not to simply regurgitate a "classic" algorithm.
There are LOTS of resources that explain how the algorithm works. The two resources I provided in the description should be enough to get you going. The algorithm isn't an easy one, so not everyone will be capable of coding it up. There are many challenges with algorithms that people already know how to solve. I love not knowing how the algorithm works. It makes it an even greater challenge :)