Penyisihan Indonesia National Contest 2007 :: Problem C - No Pause Telegraph

ACM/ICPC Indonesia National Contest 2007 - Qualification

Problem C

No Pause Telegraph

Time Limit: 1s

Several hundreds years ago in a country, there was a war between the colonialist and the military of the country. In the war, telegraph machine was used to communicate between the country and its allied cities around the country. The Morse code was used to send messages through telegraph machine. In Morse, letters are represented only by "." (dot) and "-" (dash). Between letters there is a pause to avoid mistranslation of letters.

In that era with the popularity of telegraph machine, there was wariness that the enemy could read the messages, if the messages were accidentally sent to them. Being aware of the threat, a machine was created to encode the messages. It was called No Pause Telegraph. This new telegraph machine was similar to the regular machine, only that the machine encoded the messages with no pause between letters.

After doing some researches on old relics, our archeologist has analyzed the code being used successfully. The archeologist so far has found 7 letters that been used on the found relics, those are:

A .-- dot dash dash
B -. dash dot
C --- dash dash dash
D .. dot dot
E --.. dash dash dot dot
F --.- dash dash dot dash
G .-. dot dash dot

Your task is to translate several messages encoded by the machine on the remaining relics. You should be careful that any ambiguousity may arise when translating those messages. For example: If the code for X were "." and the code for Y were "..", then two dots in a row could be either XX or Y. For this particular reason, you should output only the least alphabetical solution.

Input Specification

Each line of input is a code encoded by No Pause Telegraph. The line will consists of only characters of . (dot(s)) and - (dash(es)).

Output Specification

For each line of input, print the least alphabetical possible message in one line. If there is no possible message, print "could not be translated" (without quotes).

Sample Input

.---.-
.---.---..--..--.-.-.

Sample Output

could not be translated
ABCDEFG

---

Problem Setter: Bong Win Ce

---

Pembahasan Problem C - No Pause Telegraph

Soal ini memberikan anda kode morse. Anda harus men-translasi kode tersebut menjadi huruf-huruf sesuai pengkodean berikut:

A  .--
B  -.
C  ---
D  ..
E  --..
F  --.-
G  .-.

Kode morse "jejadian" diatas adalah unik karena tidak ada prefix dari kode morse yang satu merupakan prefix dari kode morse yang lain. Jadi, suatu rangkaian kode-kode morse yang menggunakan pengkodean diatas pasti dapat ditranslasi menjadi hasil yang unik. Untuk melihat soal lengkapnya, silahkan click link problem statement diatas.

Untuk menyelesaikan soal ini, solusinya straight forward: anda bisa men-translasi satu-persatu kode morse di input menjadi huruf dan menampungnya ke dalam suatu temporary variable. Jika ada input yang tidak ada kode morsenya, maka anda tinggal print "could not be translated" dan berhenti. Jika semua input berhasil ditranslasi, maka print-lah temporary variable-nya. Kodenya dapat dilihat dibawah ini, tersedia 2 versi (C dan Java). Kedua source code ini melakukan hal yang sama dan mempunyai function yang sama. Tetapi solusi Java lebih terlihat manusiawi di function getMorse() karena Java mempunyai built-in method startsWith() di object String yang sangat sesuai untuk problem ini (untuk mengecek apakah suatu kode morse merupakan prefix dari input saat ini).

#include <stdio.h>
#include <string.h>

char input[1000], temp[1000];
char *morse[7] = {".--","-.","---","..","--..","--.-",".-."};

int get_morse(int idx){
    int i,a,b;
    for (i=0; i<7; i++){
        for (a=idx,b=0; ; a++,b++){
            if (morse[i][b]=='\0') return i;
            if (input[a]=='\0' || input[a] != morse[i][b]) break;
        }
    }
    return -1; // kode morse tidak ketemu!
}

char* translate(){
    int i,j,k;
    for (i=j=0; input[i]!='\0'; ){
        k = get_morse(i);
        if (k==-1) return "could not be translated";
        temp[j++] = 'A'+k;
        i += strlen(morse[k]);
    }
    temp[j] = '\0';
    return temp;
}

int main(){
    while (gets(input)){
        puts(translate());
    }
}

import java.util.*;

public class NoPause {
    String[] morse = new String[]{".--","-.","---","..","--..","--.-",".-."};

    public int getMorse(String prefix){
        for (int i=0; i<morse.length; i++)
            if (prefix.startsWith(morse[i])) return i;

        return -1; // kode morse tidak ketemu!
    }

    public String translate(String input){
        String temp = "";
        for (int i=0,j=0; i<input.length(); ){
            int k = getMorse(input.substring(i)); 
            if (k==-1) return "could not be translated";
            temp += (char) ('A'+k);
            i += morse[k].length();
        }
        return temp;
    }

    public void solve(){
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextLine())
            System.out.println(translate(scan.nextLine()));
        scan.close();
    }

    public static void main(String[] args){
        new NoPause().solve();
    }
}

Back to Home