How to solve Rosetta Stone Coding Challenge C#

Question

No matter how much I re-read and try to solve this question I simply cannot wrap my head around it. I don't understand how to make my code translate the needed text without hardcoding the entire thing.

Here is the question:

Rosetta Stone Programming challenge description: The Rosetta stone is an ancient decree written into stone that was used by archeologists to translate between Greek and Ancient Egyptian languages.

Write a program to decode messages using a Rosetta for translation. The "Rosetta" will be a series of character sets paired with English words or characters. If you translate the encrypted message correctly, you will find the hidden message.

HINT: Spaces that are not part of a fragment must be preserved

Input: Multiple lines of input will be given. The first line of input will be the message to translate to English.

All other lines of input will be the Rosetta needed to translate. The fragments of each pair will be separated by a pipe character, one pair per line of input.

For example:

Hola Mundo
Mundo|World
Lunes|Monday
Hola|Hello
Translates:
Hola Mundo

into:

Hello World

Output: The translated text, which will be a real English phrase

Test 1

Test Input

Hola Mundo
Mundo|World
Lunes|Monday
Hola|Hello

Expected Output

Hello World

Test 2 Test Input

mieux vaut prévenir que guérir
merci|thank you
que|than
malade|sick
mieux|better
guérir|to heal
chien|dog
vaut prévenir|to prevent
beurre|butter
s'il vous plaît|please

Expected Output

better to prevent than to heal

Test 3 Test Input

5748494348 574159 544845 57494E44 424C4F5753
41|A
42|B
43|C
44|D
45|E
46|F
47|G
48|H
49|I
4A|J
4B|K
4C|L
4D|M
4E|N
4F|O
50|P
51|Q
52|R
53|S
54|T
55|U
56|V
57|W
58|X
59|Y
5A|Z

Expected Output

WHICH WAY THE WIND BLOWS

Here is my current code:

using System;
using System.IO;
using System.Collections.Generic;
using System.Text;

public static class Program {
  static void Main() 
  {
    using (StreamReader reader = new StreamReader(Console.OpenStandardInput()))
      
    while (!reader.EndOfStream) 
    {
      string input = reader.ReadLine();
      string output = RosettaStoneTranslate(input);
      
      Console.WriteLine(output);
    }
  }
  
  static string RosettaStoneTranslate(string input)
  {
    string[] lines = input.Split('\n');
    string message =lines[0];
    
    //parse Rosetta Stone pairs.  
    Dictionary<string, string> rosettaDict = new Dictionary<string, string>();
    for (int i = 1; i < lines.Length - 1; i++)
    {
      string[] pair = lines[i].Trim().Split('|');
      rosettaDict[pair[0]] = pair[i];
    }
    
    string[] fragments = message.Split(' ');
    List<string> translatedFragments = new List<string>();
    
      foreach (string fragment in fragments)
      {
        if (rosettaDict.TryGetValue(fragment, out string translation))
        {
          translatedFragments.Add(translation);
        }
        else
        {
          translatedFragments.Add(fragment);
        }
      }
      
      //reconstruct translated message.
      string translatedMessage = string.Join(" ", translatedFragments);
        return translatedMessage;
    }
  }

Please could some explain to me the process of how to find a solution!

Answer 1

You have a few issues. One, you need to build a list of lines before calling RosettaStoneTranslate.

Here's the Main method that does that:

static void Main()
{
    var input = new List<string>();
    using (StreamReader reader = new StreamReader(Console.OpenStandardInput()))
    {
        while (!reader.EndOfStream)
        {
            string line = reader.ReadLine();
            if (line == "")
                break;
            input.Add(line);
        }
    }
    Console.WriteLine(RosettaStoneTranslate(input.ToArray()));
}

Then there's a small change to the start of RosettaStoneTranslate as we're sending in the full list instead of a single string.

static string RosettaStoneTranslate(string[] lines)
{
    string message = lines[0];

And finally, you had a small bug in the for loop. You needed lines.Length rather than lines.Length - 1.

    for (int i = 1; i < lines.Length; i++)

It now works.

---

It is important to note that "Test 3" relies on pairing characters to do the replacement.

The whole groups, such as 544845, do not appear in your dictionary, and a simple search as replace approach like lines.Skip(1).Select(x => x.Split('|')).Aggregate(lines.First(), (a, x) => a.Replace(x[0], x[1])); does not honour the character boundaries. The 44 in the middle of 544845 shouldn't be replaced.

Answer 2

Other than reading the input, there's also a problem with your approach, which seems to be attempting to only solve problems that look like the first example. In that example, you can take each untranslated word and it will have an entry in the Rosetta list.

However, in the second example, the input shows that spaces are allowed within the Rosetta list.

mieux vaut prévenir que guérir
merci|thank you
que|than
malade|sick
mieux|better
guérir|to heal
chien|dog
vaut prévenir|to prevent // space allowed here
beurre|butter
s'il vous plaît|please

Additionally, in the third example input, the string to translate needs to be done several characters at a time. Translating 5748494348 is done by taking two characters at a time to find WHICH as its full translation.

What the last two examples show is that you need to evaluate the input one character at a time. If we take the second example input, the logic should be something like this:

• Does my Rosetta list have any entries starting with 'm'? Yes (merci, malade, mieux).
• Is 'm' an entry in the Rosetta list? No, continue processing.
• Does my Rosetta list have any entries starting with 'mi'? Yes (mieux).
• Is 'mi' an entry in the Rosetta list? No, continue processing.
• etc

This continues until eventually you get mieux from the input. We can see this is an entry in the Rosetta list, and we place its translation into the output.

Knowing this, the best way to tackle this is with a trie data structure, also known as a prefix tree. The idea is to process all of your items into the tree and then perform a search, one character at a time. The items in this case are the left-side entries in your Rosetta stone.

The tree itself is composed of nodes which only know if they are the ending character of a word, and what characters they are connected to next.

Here's an example implementation of a Trie in C#. Feel free to modify to suit your needs:

public class TrieNode
{
    public bool IsWord { get; set; }
    public Dictionary<char, TrieNode> Children { get; } = new Dictionary<char, TrieNode>();
}

public class Trie
{
    private readonly TrieNode _root = new TrieNode();

    public void AddWord(string word)
    {
        var node = _root;
        foreach (char c in word)
        {
            if (!node.Children.ContainsKey(c))
            {
                node.Children[c] = new TrieNode();
            }
            node = node.Children[c];
        }
        node.IsWord = true;
    }

    public bool Search(string word)
    {
        var node = _root;
        foreach (char c in word)
        {
            if (!node.Children.ContainsKey(c))
            {
                return false;
            }
            node = node.Children[c];
        }
        return node.IsWord;
    }
}

Problems like this can be a fun puzzle, so I'll leave the implementation details to you.

Answer 3

In order to solve this problem in a more robust manner, that correctly handles all three tests, I've put this code together:

IEnumerable<string> Consume(string line, (string @from, string @to)[] mappings)
{
    if (!String.IsNullOrEmpty(line))
    {
        var mapping = mappings.FirstOrDefault(x => line.StartsWith(x.@from));
        if (mapping.@from != null)
        {
            yield return mapping.@to;
            line = line.Substring([email protected]);
        }
        else
        {
            yield return line.Substring(0, 1);
            line = line.Substring(1);
        }
        foreach (var tail in Consume(line, mappings))
            yield return tail;
    }
}

It is consuming the input one element at a time until the string is empty. It's producing a list of strings from the source line as a series of tokens that can easily be concatenated to return the final string.

Here's the code to run it:

    var lines = """
mieux vaut prévenir que guérir
merci|thank you
que|than
malade|sick
mieux|better
guérir|to heal
chien|dog
vaut prévenir|to prevent
beurre|butter
s'il vous plaît|please
""".Split(new[] { Environment.NewLine }, StringSplitOptions.None);

    var line = lines.First();
    var mappings = lines.Skip(1).Select(x => x.Split('|')).Select(x => (@from: x[0], @to: x[1])).ToArray();

    Console.WriteLine(String.Concat(Consume(line, mappings)));

That produces "better to prevent than to heal".

With Test 3 it produces "WHICH WAY THE WIND BLOWS".