LINQ and Algorithmic Tasks

Photo by JJ Ying on Unsplash

A while ago I have found a very interesting blog of a Google interviewer Alex Golec. He has several articles about interview questions with solutions in Python. And I solved the same problems in my favorite C# (without peeping at the answers of course!). And during checking my solution against the provided Python solutions I realized how much LINQ my way of thinking and my way of solving programming tasks.

Let me show what I mean. Here is the first task, Ratio Finder:

You have a set of known conversion rates such as:
— 1 hand equals 4 inches
— 4 inches equals 0.33333 feet
— 0.33333 feet equals 6.3125e-5 miles
— 6.3125e-5 miles equals 1.0737e-17 light years

Given such a list design an algorithm that takes two arbitrary unit values and returns the conversion rate between them.

And here is my solution for the task:
Fiddle

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;
        }

The first thing to mention is that LINQ statements can provide simple one-liners for solution steps. Without LINQ this would require separate methods or blocks of code. For example, here is the addition of reverse conversion to the conversions list:

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

The next good thing is that with LINQ you use iterative approach instead of recursion. With this code I am getting the next portion of conversions (breadth first search):

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

The third thing which is not easy to show but really easy to notice, that LINQ allows you to manipulate your logic for debugging and refactoring. You could split a long expression into several parts. You could use .ToArray() to see results of computations. You cold make data transformation to improve performance (like converting Array to Dictionaly). Or you could even rewrite some portions of LINQ without LINQ to produce more clear and manageable code. By the way, I am really pleased with the named tuples we have now in C#. It really makes code easier to read and implement. And let's check the next interview task, Knight Dialer:

You place a knight chess piece on a phone dial pad.

1 2 3
4 5 6
7 8 9
  0

This chess piece moves in an uppercase “L” shape: two steps horizontally followed by one vertically, or one step horizontally then two vertically.
Suppose you dial keys on the keypad using only hops a knight can make. Every time the knight lands on a key, we dial that key and make another hop. The starting position counts as being dialed.
How many distinct numbers can you dial in N hops from a particular starting position?

A really hard task taking into account performance challenges, but the solution looks simple:
Fiddle

static (char source, char destination)[] moves = {
            ('1','6'),
            ('1','8'),
            ('2','7'),
            ('2','9'),
            ('3','4'),
            ('3','8'),
            ('4','3'),
            ('4','9'),
            ('4','0'),
            ('6','1'),
            ('6','0'),
            ('6','7'),
            ('7','6'),
            ('7','2'),
            ('8','1'),
            ('8','3'),
            ('9','4'),
            ('9','2'),
            ('0','4'),
            ('0','6')
        };

        static void Main(string[] args)
        {
            var unsymmetrical = moves.Where(w => !moves.Where(wi => wi.destination == w.source && wi.source == w.destination).Any());
            if (unsymmetrical.Any())
            {
                Console.WriteLine("Incorrect input");
            }
            int N = 30;
            char original = '0';
            var variantsCounts = new List<(char digit, long count)>();
            variantsCounts.Add((original, 1));
            for (int i = 0; i < N; i++)
            {
                var nextRoundUngrouped = variantsCounts
                       .Join(moves, phone => phone.digit, move => move.source, (phone, move) => (digit: move.destination, count: phone.count)).ToArray();
                var nextRoundGrouped = nextRoundUngrouped.GroupBy(g => g.digit).Select(s => (digit: s.Key, count: s.Sum(v=>v.count))).ToList();
                variantsCounts = nextRoundGrouped;
            }
            var sum = variantsCounts.Sum(s => s.count);
            Console.WriteLine($"Number of phones: {sum}");
        }

And here you can see the same features: easy to read and easy to debug code and iterative approach. I split one LINQ expression which produces the next step data into two:

var nextRoundUngrouped = variantsCounts 
                         .Join(moves, phone => phone.digit, move => move.source, (phone, move) => (digit: move.destination, count: phone.count)).ToArray(); 
var nextRoundGrouped = nextRoundUngrouped
                       .GroupBy(g => g.digit)
                       .Select(s => (digit: s.Key, count: s.Sum(v=>v.count)))
                       .ToList();

This allowed me in debug time to look into the data I have at each step. But it is really easy to put everything back together to get a little bit more of performance:

var nextRoundGrouped = variantsCounts
                       .Join(moves, phone => phone.digit, move => move.source, (phone, move) => (digit: move.destination, count: phone.count))
                       .GroupBy(g => g.digit)
                       .Select(s => (digit: s.Key, count: s.Sum(v=>v.count)))
                       .ToList();

So now it is obvious for me that despite LINQ was introduced mostly to make business logic implementation easier for Enterprise application, it forms a new way of thinking in implementing algorithms. In many cases it allows to produce better code. And of course it is a lot of fun in using simple joins instead of nested loops.