using System;

using System.Collections.Generic;

using System.Linq;

​

namespace GoogleKnigthDialer

{

    class Program

    {

        //https://medium.com/hackernoon/google-interview-questions-deconstructed-the-knights-dialer-f780d516f029

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

        }

    }

}

​