Need help with implementing the right data structure for this problem

Evening Folks,

I'm trying to solve the Keystrokes Problem on Open Kattis. To explain briefly, the dude in this example types the password in lower characters but also occasionally uses the left arrow key ("L"), right arrow key ("R") and the backspace ("B") to confuse any keylogger on the machine. You have to write a program which given a specific input of his keystrokes (example: iLnLnLeLb), prints the correct password (in this case benni).

I've tried various approaches in Java using Stack and Deque structures but the evaluator fails them with a timeout. Below is the Deque version which I've tried to optimize as much as possible. It works fine on my local machine but when the evaluator runs with larger string inputs, it just fails with a timeout. Where am I going wrong with this?

import java.util.*; class lyklagangriti { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); Deque<Character> l = new ArrayDeque<Character>(); Deque<Character> r = new ArrayDeque<Character>(); for(int i=0;i<s.length();i++) { char c = s.charAt(i); char item; switch(c) { case 'L': item = l.pollLast(); r.addFirst(item); break; case 'R': item =r.pollFirst(); l.addLast(item); break; case 'B': l.pollLast(); break; default: l.addLast(c); } } for(char c : l) { System.out.print(c); } for(char c : r) { System.out.print(c); } System.out.println(""); } }

Please start by explaining what the keystrokes problem is. It is better you explain it rather than simply posting a link because the solution may become obvious as you go.

Why are you using a for loop rather than for‑each? What is supposed to happen when you encounter a B?

Campbell Ritchie wrote:Please start by explaining what the keystrokes problem is. It is better you explain it rather than simply posting a link because the solution may become obvious as you go.

I've updated the post and added a brief description of the problem statement.

Campbell Ritchie wrote:Why are you using a for loop rather than for‑each? What is supposed to happen when you encounter a B?

Is the speed difference between the two that big? I'm trying to optimize for performance here. "B" is for backspace, it means the character before the cursor gets deleted. To keep track of that, I'm removing the last character from the front of the "left" array (I'm maintaining two arrays called "left" and "right" which correspond to left and right of the cursor).

Your Deque approach  is clever but not efficient. Handling 'L' and 'R' should only involve decrementing or incrementing a cursor and not the moving of characters. I think you'd find manipulating a single ArrayList would be better but I haven't tested it on the website.

Prahlad Yeri wrote:. . . I've updated the post and added a brief description of the problem statement.

Kindly don't. It makes it difficult to know what was asked originally

Agree with Carey.

It's MUCH simpler to solve this issue using a ListIterator.

Deque or Stack are not the right data structures for this problem.

To be fair, I think the two ArrayDeques are more efficient than Carey's suggestion of using an ArrayList (with or without ListIterator), if you're adding characters anywhere besides the end of the string.  But a LinkedList traversed with a ListIterator will be more efficient, and more importantly, simpler to code correctly.

Prahlad Yeri wrote:

Campbell Ritchie wrote:Why are you using a for loop rather than for‑each?

Is the speed difference between the two that big? I'm trying to optimize for performance here.

The speed difference is negligible.  The for-each is just simpler to use and read, and harder to accidentally insert an error into -- thus it's usually preferable unless you have a specific need for something else.

Stephan van Hulst wrote:Agree with Carey.

It's MUCH simpler to solve this issue using a ListIterator.

Deque or Stack are not the right data structures for this problem.

Ah, forgot totally about ListIterator. Works beautifully.

Congratulations on solving it! This is what I came up with using ListIterator, just FYI.
import java.util.LinkedList; import java.util.ListIterator; import java.util.Scanner; public class PuzzleKeystrokes2 { private static final Scanner KBD = new Scanner( System.in ); public static void main( String[] args ) { String input = KBD.nextLine(); System.out.println( encode( input ) ); } private static String encode( String input ) { LinkedList<Character> list = new LinkedList<>(); ListIterator<Character> itr = list.listIterator(0); for( int i = 0 ; i < input.length() ; i++ ) { char c = input.charAt( i ); switch( c ) { case 'L': itr.previous(); break; case 'R': itr.next(); break; case 'B': itr.previous(); itr.remove(); break; default: itr.add( c ); break; } } StringBuilder sb = new StringBuilder( list.size() ); for( Character cc : list ) sb.append( cc ); return sb.toString(); } }

Carey Brown wrote:

Stephan van Hulst wrote:Agree with Carey.

It's MUCH simpler to solve this issue using a ListIterator.

Deque or Stack are not the right data structures for this problem.

Ah, forgot totally about ListIterator. Works beautifully.

Thanks to everyone on this thread. Turns out the issue wasn't with the algorithm at all but rather the way console input was taken and output was printed.

1. Scanner was apparently inefficient for large inputs, so I replaced with BufferedReader.
2. Instead of printing each character one by one for output, I utilized a StringBuilder object to make it efficient.

With these changes, my solution was accepted! Here is the final code:

import java.util.*; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; class lyklagangriti { public static void main(String[] args) throws IOException { //Scanner sc = new Scanner(System.in); BufferedReader bi = new BufferedReader(new InputStreamReader(System.in)); String s = bi.readLine(); //String s = sc.nextLine(); Deque<Character> l = new ArrayDeque<Character>(); Deque<Character> r = new ArrayDeque<Character>(); for(int i=0;i<s.length();i++) { > char c = s.charAt(i); char item; switch(c) { case 'L': item = l.pollLast(); r.addFirst(item); break; case 'R': item =r.pollFirst(); l.addLast(item); break; case 'B': l.pollLast(); break; default: l.addLast(c); } } StringBuilder sb  = new StringBuilder(l.size() + r.size()); for(char c : l) { sb.append(c); } for(char c : r) { sb.append(c); } System.out.println(sb); } }

Congratulations on solving it! I had overlooked the IO performance issue with your code. Good catch. Two posts up is what I came up with using ListIterator.

Prahlad Yeri wrote:Scanner was apparently inefficient for large inputs, so I replaced with BufferedReader.

Wait, who told you that? Please forget it right away. Scanner uses an internal buffer and in theory there shouldn't be a large difference in performance when comparing it to BufferedReader.

Sorry for delay in replying.
A Scanner is usually slower than a Buffered Reader, but that probably has nothing to do with buffers. It is because the Scanner does more with the input. A Buffered Reader returns each line of the input unchanged. It may then be necessary to do more processing to convert the input to an int or some other form of data. A Scanner does that automatically, saving you lots of trouble parsing the input, but that takes time. You will probably find that parsing the lines read by a Buffered Reader will slow your application to the same speed as a Scanner. And there is a risk on introducing errors by writing your own parsing code.
In this case, where you want the individual letters, you are using the whole line, and a Scanner doesn't have a method for that particular manipulation. In which case a Buffered Reader will give you slightly better performance, but not because of the buffer size.
Since both a Buffered Reader and a Scanner often read not more than one line at a time, there is unlikely to be any problem with buffering, as Stephan said yesterday.

It all depends on which methods you use, and what the data is like.  A method like Scanner.nextLine() (used in the solution above) is usually pretty innocuous - but it reads everything up to the next line separator, or EOF.  What if the input doesn't have any newlines, just a really long stream of characters?  Then you're forcing the Scanner to load the whole thing into memory at once.  Whereas with BufferedReader you can break the input up into reasonably-sized chunks.  It may be that the instructor / tester / whatever is using a test framework that intentionally creates a really long input.  They could also run the JVM with a smaller-than-usual heap size, in order to force memory efficiency.  

I think the use of StringBuilder here is still problematic, because just like with ArrayList, there is a  performance issue if you are inserting characters in the front or middle of the StringBuilder.  Inserting at the end is fast, but anywhere else, you're also shifting the contents of everything after your insert.  That's why I advocate using LinkedList.

Still, it seems this issue wasn't big enough to prevent you from a successful submission, so congratulations!

Mike Simmons wrote:I think the use of StringBuilder here is still problematic...

StringBuilder is only using append()s so not a problem.

You're right, I didn't look at the actual usage - I was just reacting to the mention of StringBuilder, and how I imagined using it.    Good catch.