2
\$\begingroup\$

I'm trying to solve this challenge on CodeEval. Quoting:

For example, you can put pieces together and get the original text:
evil pl
vil pla
il plan

The answer is ‘evil plan’.

Your task is to print out the original text. Due to repetitions in the text, you will sometimes get identical pieces. Your program should accept a path to a file as its first argument. Each line in the file is one test case with the pieces of shredded text separated by a pipe. Each test case starts and finishes with symbol '|'.

For example:
|deEva|lan t|to ha|evil |ankin|il-ev|o hac| to h|vil p|an to|The e|CodeE| evil|plan |hack |Eval |ack C|l ran|king.|l-evi|evil-|-evil|l pla|il pl| hack|al ra|vil-e|odeEv|he ev|n to |ck Co|eEval|nking| rank| Code|e evi|ranki|k Cod| plan|val r|

Print to stdout the original text for each test case:
The evil-evil plan to hack CodeEval ranking.

CONSTRAINTS:

For the text with the length t shredded into pieces with the length n, there are t - (n - 1) pieces of text in the input file. Each piece of text is shifted by one character. For example, the word ‘secret’ and n = 4:

secr
ecre
cret

There is only one correct answer for each test case. The minimum number of pieces is 125, the maximum number is 975. The minimum length of a piece of text is 8, the maximum length is 28. The number of test cases is 20.

My algorithm produces correct output but it takes longer than maximum 10 seconds for challenge input. Can't check the input though because it is hidden.

static bool SubstringEquals(StringBuilder s1, string s2, int start1, int start2, int l)
{
    for (var i = 0; i < l; i++)
        if (s1[start1 + i] != s2[start2 + i]) return false;

    return true;
}

static int CompareFragments(StringBuilder s1, string s2, int l)
{
    if (SubstringEquals(s1, s2, 0, s2.Length - l, l)) return -1;
    if (SubstringEquals(s1, s2, s1.Length - l, 0, l)) return 1;
    return 0;
}

static string GlueFragments(List<string> a)
{
    var l = a[0].Length - 1;
    var s = new StringBuilder(a[0], a.Count + l);
    a.RemoveAt(0);

    while (a.Any())
    for (var i = a.Count - 1; i >= 0; i--)
    {
        var j = CompareFragments(s, a[i], l);
        if (j == 1) s.Append(a[i][l]);
        if (j == -1) s.Insert(0, a[i][0]);
        if (j != 0) a.RemoveAt(i);
    }

    return s.ToString();
}

static IEnumerable<string> ParseInput(string s)
{
    int l = s.IndexOf('|', 1) - 1;

    for (var i = 1; i < s.Length; i += l + 1)
        yield return s.Substring(i, l);
}

static void Main(string[] args)
{
    using (var r = File.OpenText(args[0]))
    while (!r.EndOfStream)
    {
        var a = ParseInput(r.ReadLine()).ToList();
        Console.WriteLine(GlueFragments(a));
    }

}

Any tips? Is it possible to achieve less than O(n2) complexity? Maybe there's some data structure that fits this problem perfectly I'm unaware of.

\$\endgroup\$
1
\$\begingroup\$

First of all I don't think the solution is correct. There could be multiple candidates to combine. Consider for example that the file contains, among other, the abc, bcd and bce strings, in this order. Your code unconditionally joins abc and bcd to produce abcd whereas the actual text has abce.

Also, it looks like you assume that at each iteration of the outer loop at least one string is removed. It is not necessarily so. If - due to a wrong candidate selection, see above - you happen to reach a dead end (unable to append or prepend any string), you are in the infinite loop. That explains TLE much better than the quadratic nature of the algorithm.

I am afraid you need some sort of backtracking. Compute the "successor" relation between fragments, and join them in a DFS with backtracking. Keep in mind that succession does not impose a strict order (e.g. aba and bab are each other successors).

\$\endgroup\$
0
\$\begingroup\$

Looking at the input it's possible to construct a directed graph from piece to piece:

|evil pl|vil pla|il plan|

|evil pl| <- 'vil pl' -> |vil pla|
|vil pla| <- 'il pla' -> |il plan|

Now when you have your 2-way directed graph you want to traverse it visiting each edge exactly once. This is known as a Eulerian path.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.