Kattis challenge, processing string with special characters and conditions

Question

I'm new to programming challenges and I'm attempting the following Kattis challenge Sim.

This problem is an extension of another Kattis problem - backspace. In that problem, every time we see a character ‘<’, it actually means that the ‘Backspace’ key is pressed and we undo the last character that was just typed.

The extension is as follows: Now, pressing a ‘<’ (the ‘Backspace’ key) when the (typing) cursor is at the front of the line does nothing. Now if we see a character ‘[’, it actually means that the ‘Home’ key is pressed and we move the (typing) cursor to the front of the line. Similarly, if we see a character ‘]’, it actually means that the ‘End’ key is pressed and we move the (typing) cursor the back of the line. For all other valid character in the input, it actually means that the corresponding key is pressed, we insert that character at the (typing) cursor position, and advance one position to the right the cursor accordingly.

Input The input starts with a line containing just one integer T(1≤T≤10), denoting the number of test cases.Each test case is a line containing the string that was written in the Text Editor Sim (Steven IMproved). The length of the string is at most 1.000.000, and it will only contain lowercase letters from the English alphabet [‘a’…‘z’], digits [‘0’…‘9’], spaces, as well as some of the three special characters: ‘<’, ‘[’, or ‘]’.

Output For each test case, output one line containing the final string that is displayed on screen.

The test cases are divided in 3 groups where

• group 1: with at most 1000 bytes string and no '['
• group 2: with at most 1000 bytes string with '['
• group 3: with at most 1000000 bytes string.

Given that premise, I made a program in c# to solve it. When the solution is submitted, I pass group 1 and group 2 with no problems, but the very first test case of group 3 returns a Time Limit Exceeded.

This is the solution I did:

    using System;
    using System.Collections.Generic;
    using System.Diagnostics;
    using System.IO;
    
    namespace Sim
    {
    public class NoMoreTokensException : Exception
    {
    }

    public class Tokenizer
    {
        string[] tokens = new string[0];
        private int pos;
        StreamReader reader;

        public Tokenizer(Stream inStream)
        {
            var bs = new BufferedStream(inStream);
            reader = new StreamReader(bs);

        }

        public Tokenizer() : this(Console.OpenStandardInput())
        {
            // Nothing more to do
        }

        private string PeekNext()
        {
            if (pos < 0)
                // pos < 0 indicates that there are no more tokens
                return null;
            if (pos < tokens.Length)
            {
                if (tokens[pos].Length == 0)
                {
                    ++pos;
                    return PeekNext();
                }
                return tokens[pos];
            }
            string line = reader.ReadLine();
            if (line == null)
            {
                // There is no more data to read
                pos = -1;
                return null;
            }
            // Split the line that was read on white space characters
            tokens = line.Split("dont split omg");
            pos = 0;
            return PeekNext();
        }

        public bool HasNext()
        {
            return (PeekNext() != null);
        }

        public string Next()
        {
            string next = PeekNext();
            if (next == null)
                throw new NoMoreTokensException();
            ++pos;
            return next;
        }
    }


    public class Scanner : Tokenizer
    {

        public int NextInt()
        {
            return int.Parse(Next());
        }

        public long NextLong()
        {
            return long.Parse(Next());
        }

        public float NextFloat()
        {
            return float.Parse(Next());
        }

        public double NextDouble()
        {
            return double.Parse(Next());
        }
    }


    public class BufferedStdoutWriter : StreamWriter
    {
        public BufferedStdoutWriter() : base(new BufferedStream(Console.OpenStandardOutput()))
        {
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            List<string> Result = new List<string>();
            string craftSentence = "";
            string leftSidedSentence = "";
            Scanner scan = new Scanner();
            int tc = scan.NextInt();
            bool foward = true;
            string input;
            

            while (tc != 0)
            {
                craftSentence = "";
                input = scan.Next();
                foreach (char c in input.ToCharArray())
                {
                    switch (c)
                    {
                        case '[':
                            foward = false;
                            if (leftSidedSentence != "") 
                            {
                                craftSentence = leftSidedSentence + craftSentence;
                                leftSidedSentence = "";
                            }

                            break;
                        case ']':
                            foward = true;
                            if (leftSidedSentence != "")
                            {
                                craftSentence = leftSidedSentence + craftSentence;
                                leftSidedSentence = "";
                            }
                            break;
                        case '<':
                            if (craftSentence.Length == 0 && foward) { break; }
                            if (foward)
                            {
                                craftSentence = craftSentence.Substring(0, craftSentence.Length - 1);
                            }
                            else if (leftSidedSentence.Length != 0)
                            {
                                leftSidedSentence = leftSidedSentence.Substring(0, leftSidedSentence.Length - 1);
                            }
                            break;
                        default:
                            if (foward)
                            {
                                craftSentence += c;
                            }
                            else
                            {
                                leftSidedSentence += c;
                            }
                            break;
                    }
                }
                craftSentence = leftSidedSentence + craftSentence;
                Result.Add(craftSentence);
                tc--;
            }

            foreach (string r in Result)
            {
                Console.WriteLine(r);
            }
        }
        
    }
}

Basically what I do:

• If the char is ']' and there is a text written before with '[' char, concatenate to the finished text to the left.
• If the char is '<' we check if we are on the right side, or left side and remove the last char from the specific string.
• After all testcases and chars are processed, print the result.

From what I've tried, I generated a random string (containing said special characters) of a million characters and even just pasting that string on the console takes more than 1 second, (but my pc is slow idk if that's the reason, I've used Kattio.cs for the I/O as stated on their c# help site). Regardless of that I bet that my algorithm is no way optimized (I tried with list and it was even slower) so,

What should I do to improve this algorithm?

Answer 1

I solved this in Node JS -- just barely (0.99s with a TLE of 1s). I appear to be the only person to solve it with Node JS at this time, but SpiderMonkey JS has a 0.32s solution, so there is probably room for optimization. I didn't bother to code it in C#, but I'm pretty sure the algorithm will pass (please let me know if it doesn't).

95% of solving these problems is picking the right data structure, so for difficulty 3 and above, the naive implementation usually won't cut it.

Your current solution is quadratic due to +, += (check out Shlemiel the Painter's algorithm if you're not clear why) and Substring (requires copying up to the entire string), but Kattis wants linear. Right off the bat, any solution based on repeatedly manipulating a plain string is pretty much a non-starter.

Testing it yourself is very good, but you have to think about worst cases designed to break your solution. If the code is 3 million 'a's followed by 3 million '<'s, or a bunch of prepends on a large string, these are worst-case quadratic situations that random testing won't necessarily produce but are pretty likely to show up in a submission.

Based on thinking about these edge cases, I was pretty sure from the start that my data structure would involve lists of chars, or a doubly-linked list that makes it fast to splice characters in and out, which might have been easier than what I did settle on. We're shooting for O(1) for just about all operations to give an overall linear runtime from looping over the input string.

I settled on a nested array/list structure like [[[]], []] and an index to point to one of the 2 lists (I'll explain the extra nested list in the zero-th element later). The motivation can be explained with an execution walkthrough below.

The plan is to walk the input string character by character. We initially start out in the back list (index 1) with a variable pointing to it:

  0    1
[[[]], []]
       ^
    currPart (an index number)

If we get a backspace character '<' on this empty structure, we do nothing.

If we get a plain old alphanumeric character, we append to this list:

  0      1
[[[]], ['a']]
         ^

And another append:

  0      1
[[[]], ['a', 'b']]
         ^

If we receive a delete action '<', we pop the current list if it has elements:

  0      1
[[[]], ['a']]
         ^

If the list was empty, we'd try moving to index 0 and popping from any lists that might have elements there.

Now, let's say we get a '[' character. Move the current index to the first list, and things get a bit tricky:

  0      1
[[[]], ['a']]
  ^

What's up with that nested list at position 0? The motivation for it is that if we have more than two '[' actions in the input, we need to prepend each chunk to the front of the result, so "ab[de[fg" should give "fgdeab". Let's process that case, starting from scratch:

  0     1
[[[]], []]
        ^

After "ab[":

  0      1
[[[]], ['a', 'b']]
   ^

After "de[" (notice the new sublist on the back of currPart = 0 triggered by '['):

  0                 1
[[['d', 'e'], []], ['a', 'b']]
              ^

After "fg":

  0                         1
[[['d', 'e'], ['f', 'g']], ['a', 'b']]
              ^

Once the input string has been visited, the result is built by first reversing parts[0] (a one-time O(n) operation, better than unshifting lists repeatedly on parts[0]):

  0                         1
[[['f', 'g'], ['d', 'e']], ['a', 'b']]

Then flattening and joining: "fgdeab".

---

To summarize the algorithm at a high-level:

• Keep two sublists and an index representing which inner list (a chunk that will eventually become part of the result) we're currently operating on.
• If we receive a backspace, pop off the current list unless it's empty, in which case move back to the previous chunk to see if something can be popped there.
• If we receive a "home" command, go to the first chunk and append an empty inner list to it.
• If we receive a "end" command, go to the second chunk.
• If we receive a character and we're on the first of the two chunks due to a previous '[' command, append the character to the last innermost list of that chunk; otherwise we're on the second chunk and we can append the character to its list.
• When the input string has been totally exhausted, reverse the order of the lists in the first (0th) chunk and flatten and join both lists to produce the result.