using System;

using System.Collections.Generic;

using System.Text.RegularExpressions;

​

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! :)");

    }

​

​

    private static string keyPattern = @"key[0-9]*";

    private static string prpPattern = @"\$PRP:""";

    private static string doubleQuotePattern = @"""";

    private static string notationPattern = String.Concat(prpPattern, keyPattern, doubleQuotePattern);

    private static string parentKey = "";

    private static int depth = 0;

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

    {

        //Console.WriteLine("- trying to resolve value for key " + key);

        //Console.WriteLine("d: " + depth);

        // depth == 0 means that we are on the "top level" trying to resolve the topmost key, here we store the original top level parent Key

        if(depth == 0) parentKey = key;

        // if we are on any level deeper than the "top level" and we try to resolve the topmost key again, we determine a circular reference and don't even try to resolve...

        if(depth > 0 && key.Equals(parentKey)) return "";

        string value = "";

        string pointer = "";

        string childKey = "";

        string childValue = "";

        string replacePattern = "";

        if(data.ContainsKey(key)) { 

            value = data[key];

            MatchCollection matchCollection = MatchPointerKeys(value);

            //Console.WriteLine("-- count of pointers in value: " + matchCollection.Count);

            for (int count = 0; count < matchCollection.Count; count++)  {

                depth++;

                pointer = matchCollection[count].Value;

                //Console.WriteLine("--- found pointer in value: " + pointer);

                childKey = Regex.Match(pointer, keyPattern).ToString();

                //Console.WriteLine("--- found childkey in pointer: " + childKey);

                replacePattern = String.Concat(prpPattern, childKey, doubleQuotePattern);

                //Console.WriteLine(Regex.IsMatch(value, replacePattern));

                childValue = ResolveKey(childKey, data);

                //Console.WriteLine("---> replacing with pattern: '" + replacePattern + "' with content '" + childValue + "' in value string '" + value + "'");

​

                value = Regex.Replace(value, replacePattern, childValue);

                depth--;

            }

        }

        //Console.WriteLine("- returning: '" + value + "' for key '" + key + "'");

        return value;

    }

    private static MatchCollection MatchPointerKeys(string value) {

        Regex notation = new Regex(notationPattern);

        MatchCollection matchedNotations = notation.Matches(value);

​

        return matchedNotations;

    }

}

​