Letter Stamper

Дата публикации: 04.11.2013 8:57:56

I found some interesting programming tasks and challenges on the Code Jam site and decided to implement the first one I came across. It was Letter Stamper.

Roland is a high-school math teacher. Every day, he gets hundreds of papers from his students. For each paper, he carefully chooses a letter grade: 'A', 'B' or 'C'. (Roland's students are too smart to get lower grades like a 'D' or an 'F'). Once the grades are all decided, Roland passes the papers onto his assistant - you. Your job is to stamp the correct grade onto each paper.

You have a low-tech but functional letter stamp that you use for this. To print out a letter, you attach a special plate to the front of the stamp corresponding to that letter, dip it in ink, and then apply it to the paper.

The interesting thing is that instead of removing the plate when you want to switch letters, you can just put a new plate on top of the old one. In fact, you can think of the plates on the letter stamp as being a stack, supporting the following operations:

• • Push a letter on to the top of the stack. (This corresponds to attaching a new plate to the front of the stamp.)

  • Pop a letter from the top of the stack. (This corresponds to removing the plate from the front of the stamp.)

  • Print the letter on the top of the stack. (This corresponds to actually using the stamp.) Of course, the stack must actually have a letter on it for this to work.

Given a sequence of letter grades ('A', 'B', and 'C'), how many operations do you need to print the whole sequence in order? The stack begins empty, and you must empty it when you are done. However, you have unlimited supplies of each kind of plate that you can use in the meantime.

It took me 15 minutes to draft a prototype that solved all the following test examples:

import java.io.FileInputStream; import java.io.IOException; import java.io.InputStream; import java.net.URL;  public class LetterStamper {      public static void main(String[] args) throws IOException {         switch (args.length) {             case 0:                 parse(System.in);                 break;             case 1:                 parse(args[0]);                 break;             default:                 for (String arg : args) {                     System.out.println("<<< " + arg);                     parse(arg);                     System.out.println();                 }                 break;         }     }      private static void parse(String filename) throws IOException {         InputStream stream;         try {             stream = new URL(filename).openStream();         }         catch (IOException exception) {             stream = new FileInputStream(filename);         }         try {             parse(stream);         }         finally {             stream.close();         }     }      private static void parse(InputStream stream) throws IOException {         int count = 0;         int letter = stream.read();         if ((letter < '1') || ('9' < letter)) {             throw new IOException("expected non-zero digit");         }         do {             count = count * 10 + letter - '0';             letter = stream.read();         }         while (('0' <= letter) && (letter <= '9'));          for (int i = 1; i <= count; i++) {             if (letter == '\r') {                 letter = stream.read();             }             if (letter == '\n') {                 letter = stream.read();             }             else {                 throw new IOException("expected end of line");             }             letter = parse(stream, letter, i);         }     }      private static int parse(InputStream stream, int letter, int id) throws IOException {         int prev = 0;         int count = 0;         while (('A' <= letter) && (letter <= 'C')) {             int next = letter - 'A' + 1;             count += 1 + Math.abs(prev - next);             prev = next;             letter = stream.read();         }         count += prev;         System.out.println("Case #" + id + ": " + count);         return letter;     } } 

If arguments are not passed to the program, it expects data input from the standard input stream. Files can be loaded not only from the local drive, but also via the network. The first line of the input stream contains the number of expected lines, which are parsed as characters appear.

The algorithm I developed seemed rather simple. However, it couldn't pass the competitive tests. Guess why? First, I decided that letters can be passed to a stamp only in the strict order of priority: A, B, C. Apparently, it was because of the test sample provided. In fact, you can put any letters into a stamp, in any order, although, it is not recommended to put identical ones. Second, I missed that is it permissible to use the unlimited number of characters. It was the key phrase! It helped me understand that for some sequences of letters it is better to push a letter that has been already added to the stamp. I had to spend more time and rework the algorithm.

    private static int parse(InputStream stream, int letter, int id) throws IOException {         Queue queue = new Queue(8);         Stack stack = new Stack(8);         int count = 0;         while (('A' <= letter) && (letter <= 'C')) {             int index = queue.size() - 1;             if ((index < 0) || (letter != queue.get(index))) {                 queue.push(letter);             }             while (1 + stack.size() < queue.size()) {                 count += print(queue, stack);             }             count++; // print every letter             letter = stream.read();         }         while (0 < queue.size()) {             count += print(queue, stack);         }         count += stack.size(); // pop the rest         System.out.println("Case #" + id + ": " + count);         return letter;     }      private static int print(Queue queue, Stack stack) {         int letter = queue.pop();         int depth = stack.find(letter);         if ((depth > 1) && compare(queue, stack)) {             depth = -1;         }         if (depth < 1) {             stack.push(letter); // push current letter             return 1;         }         for (int i = 0; i < depth; i++) {             stack.pop(); // pop unnecessary letters         }         return depth;     }      private static boolean compare(Queue queue, Stack stack) {         // compare sizes:         int qs = queue.size();         int ss = stack.size();         if (qs > ss) {             return true;         }         // compare contents:         ss--;         while (0 < qs--) {             int ch = queue.get(qs);             while (ch != stack.get(ss)) {                 if (0 == ss--) {                     return true;                 }             }         }         return ss == 0; // because pop before!     } 

My algorithm reads characters from the input stream skipping the identical ones. As soon as the queue's size exceeds the stack's size, or no more characters are detected in the input stream, next character is extracted from the queue for processing. If several calls of the pop() method are required, and the stack cannot be used to process the whole queue, it is recommended to call the push() method one time.

This algorithm does not require to read the entire string at once. You just need to emulate two linear data structures: the stack and the input queue:

    private abstract static class LinearData {         private int[] array;         private int index;          public LinearData(int size) {             if (size <= 0) {                 throw new IllegalArgumentException("size");             }             this.array = new int[size];             this.index = -1;         }          public int size() {             return this.index + 1;         }          public int get(int index) {             if ((index < 0) || (this.index < index)) {                 throw new IndexOutOfBoundsException("index");             }             return this.array[this.index - index];         }          public int pop() {             if (this.index < 0) {                 throw new IllegalStateException("empty");             }             return this.array[this.index--];         }          public void push(int letter) {             if (++this.index == this.array.length) {                 int[] array = new int[2 * this.index];                 System.arraycopy(this.array, 0, array, 0, this.index);                 this.array = array;             }             push(this.array, this.index, letter);         }          protected abstract void push(int[] array, int index, int letter);     }      private final static class Stack extends LinearData {         public Stack(int size) {             super(size);         }          @Override         protected void push(int[] array, int index, int letter) {             array[index] = letter;         }          public int find(int letter) {             for (int i = 0; i < size(); i++) {                 if (letter == get(i)) {                     return i;                 }             }             return -1;         }     }      private final static class Queue extends LinearData {         public Queue(int size) {             super(size);         }          @Override         protected void push(int[] array, int index, int letter) {             System.arraycopy(array, 0, array, 1, index);             array[0] = letter;         }     } 

I think this program can be easily modified to use extended sets of letters, for example, A, B, C, D, E. The changes will affect only one code line that validates the letters.

Having reviewed some applications, I discovered that they tended using mathematical approaches. This leads to increasing memory use and heavy decrease in performance, when you enlarge the string's length or extend the number of letters. Most of all, I like the elegant solution in C++ by Marek Cygan (#5).