UVA - 213 - Message Decoding 

This article will explain my thought process to solve a problem called Message Decoding (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Encoding, Queue

Objective 

Given:

  1. A header.

  2. List of message segments.

We want to:

  1. Decode the message.

Glossary 

  1. Encoding — The process of converting information from one form or format into another.

  2. Queue — A linear data structure that follows the First In First Out (FIFO) order of insertion and deletion.

Observation 

First, we need to generate a series of keys. The structure of the key is similar to binary, so we can reconstruct the key by retrieving the binary from 0 until 2^8. The key can have length up to 7, so we need to reconstruct the leading zero as well.

Next, we want to map the header into the keys. According to the encoding scheme, the keys must be ordered by length and alphabet. After we have the correct sequence of keys, we can map the header into the keys based on their sequence.

Now, we want to decode the message. Message is divided into multiple segments, and each segment consists of (1) key length, (2) multiple keys with equal length, and (3) end key. The key length can be retrieved by converting the first 3 digits of the segment into an integer. The end key can be identified by checking the existence of 0 on the key. For the rest of the keys, use the header map to decode the message.

Last, the message on the input is partitioned into multiple chunks. The sequence is guaranteed, but the partition can happen at any point of the message. To handle this, we need to use a buffer to store the chunks and decode the message as we load the segment from the buffer.

Algorithm 

The buffer can be implemented using queue. There is 2 types of buffer: (1) for storing every lines of the input, and (2) for storing the unprocessed message. We can retrieve the header from the first buffer, and then transfer the remaining lines (until end of message) to the second buffer for decoding. We want to retrieve the data as needed, and since every part of the message have a clearly defined length, we can use the second buffer to hold each letters of a line.

The time complexity for this solution is O({message length}).

Implementation 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * 213 - Message Decoding
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=149
 */
public class Main {
    public static void main(final String... args) throws IOException {
        final BufferedIO io = new BufferedIO(System.in, System.out);
        final Process process = new Process();

        final LinkedList<String> lines = new LinkedList<>();
        for (String line = io.readLine(); line != null; line = io.readLine()) {
            lines.add(line);
        }

        final Input input = new Input();
        input.lines = lines.toArray(new String[0]);

        final Output output = process.process(input);
        for (final String decodedMessage : output.decodedMessages) {
            io.write("%s\n", decodedMessage);
        }

        io.close();
    }
}

class Input {
    public String[] lines;
}

class Output {
    public String[] decodedMessages;
}

class Process {
    private static final String[] KEYS = createKeys();

    public Output process(final Input input) {
        final Queue<String> lineq = new LinkedList<>(Arrays.asList(input.lines));
        final Queue<Character> messageq = new LinkedList<>();
        final List<String> decodedMessages = new LinkedList<>();

        while (!lineq.isEmpty()){
            final String header = read(lineq);
            final Map<String, Character> decodedKeys = mapDecodedKeys(header);
            final StringBuilder decodedMessage = new StringBuilder();

            while (true) {
                final String encodedLength = read(lineq, messageq, 3);
                final int length = Integer.parseInt(encodedLength, 2);
                if (length == 0) break;

                while (true) {
                    final String key = read(lineq, messageq, length);
                    if (!key.contains("0")) break;
                    final char decodedKey = decodedKeys.get(key);
                    decodedMessage.append(decodedKey);
                }
            }
            decodedMessages.add(decodedMessage.toString());
        }

        final Output output = new Output();
        output.decodedMessages = decodedMessages.toArray(new String[0]);
        return output;
    }

    private Map<String, Character> mapDecodedKeys(final String header) {
        final Map<String, Character> decodedKeys = new HashMap<>(header.length());
        for (int i = 0; i < header.length(); i++) {
            final String key = KEYS[i];
            final char letter = header.charAt(i % header.length());
            decodedKeys.put(key, letter);
        }
        return decodedKeys;
    }

    private static String[] createKeys() {
        final List<String> keys = new LinkedList<>();

        for (int i = 0; Integer.bitCount(i) <= 7; i++) {
            final String binary = Integer.toBinaryString(i);

            final StringBuilder keyBuilder = new StringBuilder();
            keyBuilder.append(binary);
            for (int length = binary.length(); length <= 7; length++) {
                final String key = keyBuilder.toString();
                if (key.contains("0")) {
                    keys.add(key);
                }
                keyBuilder.insert(0, '0');
            }
        }

        final Comparator<String> orderByLengthAndAlphabetical = Comparator
                .comparingInt(String::length)
                .thenComparing(key -> key);

        return keys.stream()
                .distinct()
                .sorted(orderByLengthAndAlphabetical)
                .toArray(String[]::new);
    }

    private static String read(final Queue<String> lineq) {
        return lineq.poll();
    }

    private static String read(final Queue<String> lineq, final Queue<Character> messageq, final int length) {
        final StringBuilder result = new StringBuilder();

        while (messageq.size() < length) {
            final String line = lineq.poll();
            for (final char letter : line.toCharArray()) {
                messageq.add(letter);
            }
        }

        for (int i = 0; i < length; i++) {
            result.append(messageq.poll());
        }

        return result.toString();
    }
}

final class BufferedIO {
    private final BufferedReader in;
    private final BufferedWriter out;

    public BufferedIO(final InputStream in, final OutputStream out) {
        this.in = new BufferedReader(new InputStreamReader(in));
        this.out = new BufferedWriter(new OutputStreamWriter(out));
    }

    public String[] readLine(final String separator) throws IOException {
        final String line = readLine();
        return line == null ? null : line.split(separator);
    }

    public String readLine() throws IOException {
        String line = in.readLine();
        while (line != null && line.isEmpty()) line = in.readLine();
        return line;
    }

    public void write(final String format, Object... args) throws IOException {
        final String string = String.format(format, args);
        write(string);
    }

    public void write(final String string) throws IOException {
        out.write(string);
    }

    public void close() throws IOException {
        in.close();
        out.flush();
        out.close();
    }
}


Powered by Docmost