Chatruka’s Algorithm

Chatruka prefers writing messages in short form. This often creates problem for others to decipher the correct message leading to mismanagement in his kingdom. After several discussion with his advisory board, he finally adopted a method to send his message in a short form. The method although had one disadvantage, no digits could be used in it. According to the method, the message is shortened by creating a list of words from the original message. When a non alphabetic character is encountered in the original message, it is directly copied to the shortened message. When a word is encountered in the original message, it is copied directly into the shortened message only if it is the first occurrence of the word. In such a case, the word is put in front of the list. If it is not the first occurrence, the word is not copied to the shortened message. Instead, its position in the list is copied and the word is moved directly to the front of the list of words. The list starts with the integer 1. This method however being simple created problem for the council member to understand. You are required to write a program so as to help the members get the original message, provided they have the shortened message.

 

Note:

A word is defined as the maximum sequence of lowercase or upper case characters.

The words are case sensitive: message and Message are two different words.

Algo-rithm contains two different words “Algo”, “rithm” separated by a non alphabetic character “-”. Chatruka’s contains two different words “Chatruka”, “s” separated by a non alphabetic character “’”.

 

INPUT:

Input consists of the message in one or more lines. The input is terminated by a ‘0’ on a separate line.

There in no word limit for the input.

 

OUTPUT:

The output should tell the original message.

 

SAMPLE INPUT:

Dear Tunnu,

Please, please do it. It is very, 1 urgent and of much importance.

If you 12 12, I will be 9 obliged to 9.

Thank 2 16 6

0

 

SAMPLE OUTPUT

Dear Tunnu,

Please, please do it. It is very, very urgent and of much importance.

If you do it, I will be much obliged to you.

Thank you very much

 

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;

namespace ConsoleApplication2{
    class Program{
        static void Main(string[] args){
            string message = @"Dear Tunnu, Please, please do it. It is very, very urgent and of much importance. If you do it, I will be much obliged to you. Thank you very much";
            Console.WriteLine(Decode(Encode(message)));
        }
        public static string Encode(string originalMessage){
            string encodedMessage = "";
            List<string> wordList = new List<string>();
            string word = "";
            for (int i = 0; i < originalMessage.Length; i++){
                word = word + originalMessage[i].ToString();
                if(i < originalMessage.Length – 1){
                    if (IsAlphabet(originalMessage[i]) && !IsAlphabet(originalMessage[i + 1])){
                        if (!wordList.Contains(word)){
                            wordList.Insert(0, word);
                            encodedMessage = encodedMessage + word;
                            word = "";
                        }
                        else{
                            encodedMessage = encodedMessage + (wordList.IndexOf(word) + 1).ToString();
                            wordList.Remove(word);
                            wordList.Insert(0, word);
                            word = "";
                        }
                    }
                    else if (!IsAlphabet(originalMessage[i])){
                        encodedMessage = encodedMessage + word;
                        word = "";
                    }
                }
            }
            if (word.Length > 0){
                if (!wordList.Contains(word)){
                    wordList.Insert(0, word);
                    encodedMessage = encodedMessage + word;
                    word = "";
                }
                else{
                    encodedMessage = encodedMessage + (wordList.IndexOf(word) + 1).ToString();
                    wordList.Remove(word);
                    wordList.Insert(0, word);
                    word = "";
                }
            }
            return encodedMessage;
        }
        public static bool IsAlphabet(char c){
            string alphabets = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
            if (alphabets.Contains(c)){
                return true;
            }
            else{
                return false;
            }
        }
        public static bool IsAlphaNumeric(char c){
            string alphabets = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
            if (alphabets.Contains(c)){
                return true;
            }
            else{
                return false;
            }
        }
        public static string Decode(string encodedMessage){
            string decodedMessage = "";
            List<string> wordList = new List<string>();
            string word = "";
            for (int i = 0; i < encodedMessage.Length; i++){
                word = word + encodedMessage[i].ToString();
                if (i < encodedMessage.Length – 1){
                    if (IsAlphaNumeric(encodedMessage[i]) && !IsAlphaNumeric(encodedMessage[i + 1])){
                        if (!wordList.Contains(word)){
                            int flag = 0;
                            for (int j = 0; j < word.Length; j++){
                                if (!char.IsDigit(word[j])){
                                    flag = 1;
                                    break;
                                }
                            }
                            if (flag == 0){
                                decodedMessage = decodedMessage + wordList[int.Parse(word) – 1];
                                string temp = wordList[int.Parse(word) – 1];
                                wordList.RemoveAt(int.Parse(word) – 1);
                                wordList.Insert(0, temp);
                                word = "";
                            }
                            else{
                                wordList.Insert(0, word);
                                decodedMessage = decodedMessage + word;
                                word = "";
                            }
                        }
                        else{
                            decodedMessage = decodedMessage + (wordList.IndexOf(word) + 1).ToString();
                            wordList.Remove(word);
                            wordList.Insert(0, word);
                            word = "";
                        }
                    }
                    else if (!IsAlphaNumeric(encodedMessage[i])){
                        decodedMessage = decodedMessage + word;
                        word = "";
                    }
                }
            }
            if (word.Length > 0){
                if (!wordList.Contains(word)){
                    int flag = 0;
                    for (int j = 0; j < word.Length; j++){
                        if (!char.IsDigit(word[j])){
                            flag = 1;
                            break;
                        }
                    }
                    if (flag == 0){
                        decodedMessage = decodedMessage + wordList[int.Parse(word) – 1];
                        string temp = wordList[int.Parse(word) – 1];
                        wordList.RemoveAt(int.Parse(word) – 1);
                        wordList.Insert(0, temp);
                        word = "";
                    }
                    else{
                        wordList.Insert(0, word);
                        decodedMessage = decodedMessage + word;
                        word = "";
                    }
                }
                else{
                    decodedMessage = decodedMessage + (wordList.IndexOf(word) + 1).ToString();
                    wordList.Remove(word);
                    wordList.Insert(0, word);
                    word = "";
                }
            }
            return decodedMessage;
        }
    }
}

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s