using System;

using System.Collections.Generic;

using System.Linq;

​

namespace GoogleUnitsConversion

{

    //https://medium.com/@alexgolec/google-interview-problems-ratio-finder-d7aa8bf201e3

    class Program

    {

        static (string source, string destination, double coef)[] coeffs = {

            ("foot", "inch", 12),

            ("hand", "inch", 4),

            ("mile", "foot", 5280),

            ("light year", "km", 9.461e+12),

            ("km", "mile", 0.621371)

        };

        static void Main(string[] args)

        {

            var allCoeffs = Queryable.Union<(string source, string destination, double coef)>(coeffs.AsQueryable(), coeffs.Select(s => (s.destination, s.source, 1 / s.coef))).ToArray();

​

​

            var unit1 = "hand";

            var unit2 = "light year";

            var result = SearchConversion(allCoeffs, unit1, unit2);

​

            Console.WriteLine(result);

        }

​

        private static double SearchConversion((string source, string destination, double coef)[] allCoeffs, string unit1, string unit2)

        {

            var result = 0.0;

            var conversionAdded = allCoeffs.Where(w => w.source == unit1).Select(s => (destination:s.destination, coef:s.coef)).ToDictionary(k => k.destination, e => e.coef);

            bool somethingChanged = true;

            while (somethingChanged)

            {

                somethingChanged = false;

                foreach (var existingConversion in conversionAdded.Keys.ToArray())

                {

                    var nextStep = allCoeffs.Where(w => w.source == existingConversion && !conversionAdded.ContainsKey(w.destination));

                    foreach (var newConversion in nextStep)

                    {

                        if (existingConversion == unit1) continue;

                        var newCoeff = conversionAdded[existingConversion] * newConversion.coef;

                        conversionAdded.Add(newConversion.destination, newCoeff);

                        somethingChanged = true;

                        if (newConversion.destination == unit2)

                        {

                            result = newCoeff;

                            return result;

                        }

​

                    }

                }

            }

            return result;

        }

    }

}

​