## Friday, April 8, 2016

### Simple Text Editor - HackerRank

https://www.hackerrank.com/challenges/simple-text-editor
In this problem, your task is to implement a simple text editor. Initially, a file contains an empty string $S$. Your task is to perform $Q$ operations consisting of the following $4$ types:
1. append$\left(W\right)$ - Appends the string $W$ at the end of $S$.
2. erase$\left(k\right)$ - Erase the last $k$ character of $S$.
3. get$\left(k\right)$ - Returns the ${k}^{th}$ character of $S$.
4. undo$\left(\right)$ - Undo the last not previously undone operation of type $1$ or $2$, so it reverts $S$ to the state before that operation.
For each operation of type $3$, print a single line with the returned character of that operation.
Sample Input
9
1 abc
3 3
2 3
1 xy
3 2
4
4
3 1

Sample Output
c
y
a
        Scanner sc = new Scanner(System.in);
int Q = sc.nextInt();
sc.nextLine();
StringBuilder s = new StringBuilder();
Stack<String> stack = new Stack<String>();
for(int i=0;i<Q;i++){
String line = sc.nextLine();
String[] split = line.split(" ");
int t = Integer.valueOf(split[0]);
switch(t){
case 1:
String w = split[1];
s.append(w);
stack.push(1+" "+w.length());
break;
case 2:
int k = Integer.valueOf(split[1]);
stack.push(2+" "+s.substring(s.length() - k));
s.setLength(s.length() - k);
break;
case 3:
k = Integer.valueOf(split[1]);
System.out.println(s.charAt(k-1));
break;
case 4:
String undo = stack.pop();
String undoItems[] = undo.split(" ");
if(undoItems[0].equals("1")){
s.setLength(s.length() - Integer.valueOf(undoItems[1]));
} else {
s.append(undoItems[1]);
}
break;
}
}
        Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
Stack<String> st=new Stack<String>();
st.push("");
int k=-1;
String prev="";

for(int i=0;i<n;i++){
int op=sc.nextInt();
switch(op){
case 1:
String newstr=sc.next();
prev=st.peek();
st.push(prev+newstr);
break;

case 2:
k=sc.nextInt();
prev=st.peek();
String temp=prev.substring(0,prev.length()-k);
st.push(temp);
break;

case 3:
k=sc.nextInt();
System.out.println(st.peek().charAt(k-1));
break;

case 4:
st.pop();
break;
}
        Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
Stack<String> stack = new Stack<String>();
String s = "";

for (int x = 0; x < q; x++) {
int ope = sc.nextInt();
switch (ope) {
case 1: //append
stack.push(s);
String append = sc.next();
s += append;
break;
case 2: //erase last x characters
stack.push(s);
int character = sc.nextInt();
s = s.substring(0, s.length() - character);
break;
case 3: //print
int index = sc.nextInt();
System.out.println(s.charAt(index - 1));
break;
case 4: //undo
s = stack.pop();
break;
default:
break;
}
}
http://www.martinkysel.com/hackerrank-simple-text-editor-solution/
I maintain two separate stacks. Self.stack represents the current state of the text. I can read data from this stack by indexing it. Self.cmds keeps the history of commands. Each command type knows how to execute itself and how to revert itself.
class AppendCmd():
    def execute(self, stack, value):
        self.length = len(value)
        stack.extend(value)

    def revert(self, stack):
        for _ in xrange(self.length):
            stack.pop()

class EraseCmd():
    def execute(self, stack, value):
        self.text = stack[-value:]
        for _ in xrange(value):
            stack.pop()

    def revert(self, stack):
        stack.extend(self.text)

class CustomStack:
    def __init__(self):
        self.stack = []
        self.cmds = []

    def push(self, value):
        cmd = AppendCmd()
        cmd.execute(self.stack, value)
        self.cmds.append(cmd)

    def pop(self, value):
        cmd = EraseCmd()
        cmd.execute(self.stack, value)
        self.cmds.append(cmd)

    def get(self, value):
        print self.stack[value]

    def revert(self):
        cmd = self.cmds.pop()
        cmd.revert(self.stack)

def main():

    cs = CustomStack()

    N = int(raw_input())

    for _ in xrange(N):
        unknown = raw_input()

        command = unknown[0]

        if command == '1':
            cmd, value = unknown.split()
            cs.push(list(value))
        elif command == '2':
            cmd, value = map(int, unknown.split())
            cs.pop(value)
        elif command == '3':
            cmd, value = map(int, unknown.split())
            cs.get(value - 1)
        else:
            cs.revert()