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?