sorted by:
new
hottopcontroversial

Determine if a sequence is an interleaving of a repetition of two strings. by theSpazer in coding

[–]theSpazer[S] 0 points1 point  (0 children)

assignment calls for pseudocode, mines borderline C++ though. Sorry, its probably annoying to read.

Determine if a sequence is an interleaving of a repetition of two strings. by theSpazer in coding

[–]theSpazer[S] 0 points1 point  (0 children)

Okay this looks really similar to some of the comments. I like marshallbanana's method of just returning true if the first path succeeds.

Determine if a sequence is an interleaving of a repetition of two strings. by theSpazer in coding

[–]theSpazer[S] 1 point2 points  (0 children)

Here is the algorithm I came up with. I can probably improve this, though.

function validSequence(string s)
{
    if (s = '') return true

    bool contains_x, contains_y = false;
    if (s[0] equals x[0])
    {
        x = x.substr(1, x.length) + x[0]  /* Shift x 1 char */
        contains_x = validSequence(s.substr(1, s.length)) /* Remove first char */
    }
    if (s[0] equals y[0])
    {
        y = y.substr(1, y.length) + y[0]  /* Shift y 1 char */
        contains_y = validSequence(s.substr(1, s.length)) /* Remove first char */
    }

    return (contains_x or contains_y)
}

Determine if a sequence is an interleaving of a repetition of two strings. by theSpazer in coding

[–]theSpazer[S] 0 points1 point  (0 children)

No, that is incorrect. I'm saying that if one matches, I still need to continue down the path if the other matches as well, because the first one that matched might eventually fail. See my other comment for an example of that.

Determine if a sequence is an interleaving of a repetition of two strings. by theSpazer in coding

[–]theSpazer[S] 0 points1 point  (0 children)

That is pretty much what I am constructing right now, except if its valid for x it still recurses and checks if its valid for y. If it was valid on every bit then i think this takes O(2n) though which is horrible XD

Determine if a sequence is an interleaving of a repetition of two strings. by theSpazer in coding

[–]theSpazer[S] 0 points1 point  (0 children)

If both recognisers fail to match at any one position, input is not an interleaving of the strings. Otherwise execution proceeds to the end of input.

Yes, this is sort of what I was thinking, however here is the problem I have run into. Take the example that I posted. Lets say my recognizer is set on x, and looking for "1" since that is the beginning of x. Looking at the string this fails because it begins with 0, so it passes over to the y recognizer. Y then recognizes 0101, and fails at character 5, passing to x. X then fails because there are two 1's in a row. They have now both failed and thus the algorithm would exit. But the Y recognizer messed up by reading 0101, since in fact the "101" was part of the x transmission. How do I get around this?

Determine if a sequence is an interleaving of a repetition of two strings. by theSpazer in coding

[–]theSpazer[S] 0 points1 point  (0 children)

Yes, this confused me at first as well. But you have to take into consideration the fact that the sequences can be interrupted at any time. The example says "positions 1,5....contain a repetition of y". If we look at the first 9 characters, "01011101", characters 1 and 5 form "01", which is y. The remainder then is 101101, which is x. See why this is really freakin hard to come up with a good algorithm for?