using System;

using System.Collections.Generic;

​

public class Program

{

    /*

    * A data storage has unique string keys that point to 

    * string values (1). The value syntax also allows pointing

    * to another key's value with $PRP:"<key>" syntax (2) for

    * full or partial value.

    * 

    * The task is to write an algorithm than can RESOLVE a value for  

    * a key, i.e. replace $PRP -notations with value the notation is 

    * pointing to. Note than a value may point to value that may point 

    * to value... with arbitrary depth.

    *

    * The algorith must be able to handle possible circular reference

    * case by resolving the value as much as possible while evaluating

    * the "circularity point" as an empty string. (3)

    * If the pointer point to a key that doesn't exists, it should 

    * evaluate to empty string.

    *

    * (1)   key1 -> "hello"

    *       key2 -> "world"

    *

    * (2)   key1 -> "hello"

    *       key2 -> "$PRP:\"key1\" world"   (resolves to "hello world")

    *

    * (3)   key1 -> "$PRP:\"key2\" hey"     (resolves to " world hello hey")

    *       key2 -> "$PRP:\"key3\" hello"   (resolves to " hey world hello")

    *       key3 -> "$PRP:\"key1\" world"   (resolves to " hello hey world")

    * 

    * Implement ResolveKey -function, but don't touch anything else.

    * You may implement as many helper function as you like.

    */

​

    public static Dictionary<string, string> data = new Dictionary<string, string>()

    {

        {"key1", "value1" },

        {"key2", "value2 - $PRP:\"key1\"" },

        {"key3", "$PRP:\"key5\"$PRP:\"key6\"" },

        {"key4", "$PRP:\"key1\"qwerty" },

        {"key5", "ATR " },

        {"key6", "Soft" },

        {"key7", "$PRP:\"key6\"" },

        {"key8", "$PRP:\"key3\" OY $PRP:\"key5\"$PRP:\"key7\"" },

        {"key9", "$PRP:\"key1\" $PRP:\"key2\" $PRP:\"key3\" $PRP:\"key4\" $PRP:\"key5\" $PRP:\"key6\" $PRP:\"key7\" $PRP:\"key8\" $PRP:\"key9\"OMG" },

        {"key10", "Foo $PRP:\"key12\" Hello" },

        {"key11", "Bar $PRP:\"key10\" World" },

        {"key12", "Baz $PRP:\"key11\" :)" },

​

    };

​

    public static Dictionary<string, string> answers = new Dictionary<string, string>()

    {

        {"key1", "value1" },

        {"key2", "value2 - value1" },

        {"key3", "ATR Soft" },

        {"key4", "value1qwerty" },

        {"key5", "ATR " },

        {"key6", "Soft" },

        {"key7", "Soft" },

        {"key8", "ATR Soft OY ATR Soft" },

        {"key9", "value1 value2 - value1 ATR Soft value1qwerty ATR  Soft Soft ATR Soft OY ATR Soft OMG" },

        {"key10", "Foo Baz Bar  World :) Hello" },

        {"key11", "Bar Foo Baz  :) Hello World" },

        {"key12", "Baz Bar Foo  Hello World :)" },

​

    };

​

    public static void Main()

    {

        bool bFailed = false;

​

        foreach (var key in data.Keys)

        {

            if (answers.ContainsKey(key))

            {

                string res = ResolveKey(key, data);

                Console.WriteLine(string.Format("'{0}' -> '{1}'", key, res));

                if (string.Compare(answers[key], res) != 0)

                {

                    bFailed = true;

                    Console.WriteLine(string.Format("\nFAIL! Correct would be\n'{0}' -> '{1}'", key, answers[key]));

                    break;

                }

            }

        }

        if (!bFailed)

            Console.WriteLine("Congratulations! :)");

    }

​

​

​

    public static string ResolveKey(string key, Dictionary<string, string> data)

    {

        List<string> keyMap = new List<string>();

        keyMap.Add(key);

​

        string resolvedString = RecursiveReader(data[key], keyMap);

​

        return resolvedString;

    }

​

    public static string RecursiveReader(string dataStr, List<string> keyList, string result="")

    {

        for(int i=0; i < dataStr.Length; i++)

        {

            // Check if key to read.

            if(i < (dataStr.Length - 5) && dataStr.Substring(i, 5) == "$PRP:")

            {

                // Move read head to key start.

                i += 6;

                string key = "";

​

                // Read to end of key

                while(dataStr[i] != '"')

                {

                    key += dataStr[i];

                    i++;

                }

​

                // If valid key and not circular

                if(data.ContainsKey(key) && !TestCircularity(key, keyList))

                {

                    // Add key to key map

                    keyList.Add(key);

​

                    result += RecursiveReader(data[key], keyList);

                }

​

            }

            else

            {

                result += dataStr[i];

            }

        }

​

​

        return result;

    }

​

    public static List<string> GetKeys(string dataStr)

    {

        List<string> keys = new List<string>();

​

        for (int i = 0; i < dataStr.Length; i++)

        {

            if (i < (dataStr.Length - 5) && dataStr.Substring(i, 5) == "$PRP:")

            {

                // Read key

                i += 6;

                string key = "";

​

                // Read to end of key

                while (dataStr[i] != '"')

                {

                    key += dataStr[i];

                    i++;

                }

​

                keys.Add(key);

            }

        }

​

        return keys;

    }

​

    public static bool TestCircularity(string key, List<string> keyList)

    {

        // Returns true only when at the 'end' of the circle.

​

        // If key not yet in map we are fine.

        if(!keyList.Contains(key)) {

            return false;

        }

        // If value does not contain a key we are also fine.

        else if(!data[key].Contains("$PRP:"))

        {

            return false;

        }

        else

        {

            List<string> keys = GetKeys(data[key]);

​

            foreach(string tempKey in keys)

            {

                if(TestCircularTraverse(data[tempKey], tempKey))

                {

                    return true;

                }

            }

        }

​

        return false;

    }

​

    public static bool TestCircularTraverse(string dataStr, string key)

    {

        // Test if you can find the given key by traversing.

        List<string> keys = GetKeys(dataStr);

        bool result = false;

​

        if(keys.Contains(key))

        {

            return true;

        }

        else

        {

            foreach(string tempKey in keys)

            {

                result = TestCircularTraverse(data[tempKey], key);

            }

        }

​

​

        return result;

    }

}

​