P,MTHBGWB

From Progteam

Revision as of 22:33, 8 February 2008 by MuGMaN (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by Eric.



P,MTHBGWB
Problem Number 1051
Sorter: Uncategorized
Source: Greater New York 2001
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1051




P,MTHBGWB is problem number 1051 on the Peking University ACM site.


Contents

Problem Information

Problem Name: P,MTHBGWB
Problem Number on PKU: 1051
Synopsis: Decryption using Morse code by Ohaver's Scheme.
Ohaver's scheme has three steps, the same for encryption and decryption:

  1. Convert the text to Morse code without pauses but with a string of numbers to indicate code lengths
  2. Reverse the string of numbers
  3. Convert the dots and dashes back into to text using the reversed string of numbers as code lengths


Solver Information

Solver: Eric Hong
Date: February 08, 2008

Trivia

The title P,MTHBGWB becomes PROBLEM_B when it is decoded using Ohaver's Scheme.

General Strategy

  1. Using Scanner, take the input.
  2. Instantiate and initialize two hashtables for Alphabet to Morse Code and Morse Code to Alphabet.
  3. Using A2C Hashtable, convert alphabets to Morse code, while finding and storing the length of each Morse code in an array.
  4. Reverse the order of length String.
  5. Following each digit of length String, splice the Morse code into N substrings and store them in an array.
  6. Using C2A Hashtable, convert each substring Morse code into an alphabet.
  7. Print out the results.


Solution

import java.util.*;

public class Main
{
    public static Scanner in;
    public static Hashtable<Character, String> hashA2C = new Hashtable<Character, String>();
    public static Hashtable<String, Character> hashC2A = new Hashtable<String, Character>();
    public static String[][] temp;

    public static void main(String[] args)
    {
        in = new Scanner(System.in);
        
        initA2C();
        initC2A();
        
        doStuff();
    }

    public static void doStuff()
    {
        int N = in.nextInt();
        temp = new String[N][2];

        for (int i = 0; i < N; i++)
        {
            solve(i);
            decode(i);
        }
    }

    public static void solve(int i)
    {
        String line = in.next();
        String converted = "";
        String conLength = "";
        int len = line.length();
        
        for (int j = 0; j < len; j++)
        {
            char ch = line.charAt(j);
            
            String tempConv = hashA2C.get(ch);
            String tempLen = "" + tempConv.length();
            
            converted = converted + tempConv;
            conLength = conLength + tempLen;
        }
        
        temp[i][0] = converted;
        temp[i][1] = reverse(conLength);
    }
    
    public static void decode(int i)
    {
        String line = temp[i][0];
        String leng = temp[i][1];
        String conv = "";
        int prevIndex = 0;
        
        int len = leng.length();
        String[] tempArray = new String[len];
        
        for (int j = 0; j < len; j++)
        {
            int digit = leng.charAt(j) - '0';
            tempArray[j] = line.substring(prevIndex, prevIndex + digit);
            prevIndex = prevIndex + digit;
        }
        
        for (int j = 0; j < tempArray.length; j++)
        {
            conv = conv + "" + hashC2A.get(tempArray[j]);
        }
        
        System.out.println((i + 1) + ": " + conv);  
    }

    public static void initA2C()
    {
        hashA2C.put('A', ".-");
        hashA2C.put('B', "-...");
        hashA2C.put('C', "-.-.");
        hashA2C.put('D', "-..");
        hashA2C.put('E', ".");
        hashA2C.put('F', "..-.");
        hashA2C.put('G', "--.");
        hashA2C.put('H', "....");
        hashA2C.put('I', "..");
        hashA2C.put('J', ".---");
        hashA2C.put('K', "-.-");
        hashA2C.put('L', ".-..");
        hashA2C.put('M', "--");
        hashA2C.put('N', "-.");
        hashA2C.put('O', "---");
        hashA2C.put('P', ".--.");
        hashA2C.put('Q', "--.-");
        hashA2C.put('R', ".-.");
        hashA2C.put('S', "...");
        hashA2C.put('T', "-");
        hashA2C.put('U', "..-");
        hashA2C.put('V', "...-");
        hashA2C.put('W', ".--");
        hashA2C.put('X', "-..-");
        hashA2C.put('Y', "-.--");
        hashA2C.put('Z', "--..");
        hashA2C.put('_', "..--");
        hashA2C.put('.', "---.");
        hashA2C.put(',', ".-.-");
        hashA2C.put('?', "----");
    }

    public static void initC2A()
    {
        hashC2A.put(".-", 'A');
        hashC2A.put("-...", 'B');
        hashC2A.put("-.-.", 'C');
        hashC2A.put("-..", 'D');
        hashC2A.put(".", 'E');
        hashC2A.put("..-.", 'F');
        hashC2A.put("--.", 'G');
        hashC2A.put("....", 'H');
        hashC2A.put("..", 'I');
        hashC2A.put(".---", 'J');
        hashC2A.put("-.-", 'K');
        hashC2A.put(".-..", 'L');
        hashC2A.put("--", 'M');
        hashC2A.put("-.", 'N');
        hashC2A.put("---", 'O');
        hashC2A.put(".--.", 'P');
        hashC2A.put("--.-", 'Q');
        hashC2A.put(".-.", 'R');
        hashC2A.put("...", 'S');
        hashC2A.put("-", 'T');
        hashC2A.put("..-", 'U');
        hashC2A.put("...-", 'V');
        hashC2A.put(".--", 'W');
        hashC2A.put("-..-", 'X');
        hashC2A.put("-.--", 'Y');
        hashC2A.put("--..", 'Z');
        hashC2A.put("..--", '_');
        hashC2A.put("---.", '.');
        hashC2A.put(".-.-", ',');
        hashC2A.put("----", '?');
    }
    
    public static String reverse(String arg)
    {
        String tmp = null;
        
        if (arg.length() == 1)
        {
            return arg;
        }
        else
        {
            String lastChar = arg.substring(arg.length()-1,arg.length());
            String remainingString = arg.substring(0, arg.length() -1);
    
            tmp = lastChar + reverse(remainingString);
            
            return tmp;
        }
    }
}


Additional Remarks

Memory: 2532K
Time: 125MS

This solution may not be as efficient as it can be. If at all possible, can someone suggest how to make it more efficient?

Personal tools