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)

    {

        // Stack is perfect to detect circular keys within recursivity

        Stack<string> visited = new Stack<string>();

        return ResolveKeyRecursive(key, data, ref visited);

    }

​

    private static string ResolveKeyRecursive(string key, Dictionary<string, string> data, ref Stack<string> visited)

    {

        // If the key is not valid, it should resolve to empty string

        string value = data.ContainsKey(key) ? data[key] : "";

​

        // Handle circular reference stack

        if (visited.Contains(key))

            return ""; 

        visited.Push(key);

        // Extract first possible key pointer from left to right

        int iStart, iEnd;

        string pointedKey = ExtractKey(value, out iStart, out iEnd);

​

        while (pointedKey != null)

        {

            // If exists, resolve that recursively. Append ending if any.

            string ending = iEnd < value.Length ? value.Substring(iEnd + 1) : "";

            // Make the recursive subquery

            string subResolve = ResolveKeyRecursive(pointedKey, data, ref visited);

​

            // Replace the found key with its sub-resolve

            value = value.Substring(0, iStart) + subResolve + ending;

​

            // Extract the next key

            pointedKey = ExtractKey(value, out iStart, out iEnd); 

        }

​

        // No more keys -> return pure value and pop the stack.

        visited.Pop();

        return value;

    }

​

​

    /*

    * Returns first non-null <key> if exists in value

    * with notation $PRP:"<key>". When non-null return,

    * also returns iStart as starting index of the whole 

    * notation and iEnd as ending index of the whole 

    * notation. Returns null if key not found.

    */

    public static string ExtractKey(string value, out int iStart, out int iEnd)

    {

​

        iStart = -1; 

        iEnd = -1;

​

        if (string.IsNullOrWhiteSpace(value))  

            return null;

​

        int iStartLen = "$PRP:\"".Length;

        iStart = value.IndexOf("$PRP:\"");

        if (iStart != -1)

            iEnd = value.IndexOf("\"", iStart + iStartLen);

​

        if (iStart != -1 && iEnd != -1)

            return value.Substring(iStart + iStartLen, iEnd - (iStart + iStartLen));

        return null;

    }

​

}

​