using System;

using System.Text.RegularExpressions;

using System.Linq;

using System.IO;

​

    public static class Program

    {

        private const string input2 = @" 1

                                         8 4

                                         2 6 9

                                         8 5 9 3";

​

        public static void Main(string[] args)

        {

            int[,] convertedTriangle2 = input2.convertTo2DArrayWithoutSpaces(); 

            int maxSum2 = convertedTriangle2.moveDownwards();

​

            Console.WriteLine("The result for Question2 : " + maxSum2);

            if (maxSum2 == 0 || maxSum2 == -1)

                Console.WriteLine("There is no possible path");

        }       

​

        public static int moveDownwards(this int[,] matrixOfTriangle)

        {

            int length = matrixOfTriangle.GetLength(0);

​

            int res = -1;

            for (int i = 0; i < length - 2; i++)

                res = Math.Max(res, matrixOfTriangle[0, i]);

            for (int i = 1; i < length; i++)

            {

                res = -1;

                for (int j = 0; j < length; j++)

                {

                    if (j == 0 && matrixOfTriangle[i, j] != -1)

                    {

                        if (matrixOfTriangle[i - 1, j] != -1)

                            matrixOfTriangle[i, j] += matrixOfTriangle[i - 1, j];

                        else

                            matrixOfTriangle[i, j] = -1;

                    }

                    else if (j > 0 && j < length - 1 && matrixOfTriangle[i, j] != -1)

                    {

                        int tmp = calculateNodeValue(matrixOfTriangle[i - 1, j],

                                   matrixOfTriangle[i - 1, j - 1]);

                        if (tmp == -1)

                        {

                            matrixOfTriangle[i, j] = -1;

                        }

                        else

                            matrixOfTriangle[i, j] += tmp;

                    }

​

                    else if (j > 0 && matrixOfTriangle[i, j] != -1)

                    {

                        int tmp = calculateNodeValue(matrixOfTriangle[i - 1, j],

                                         matrixOfTriangle[i - 1, j - 1]);

                        if (tmp == -1)

                        {

                            matrixOfTriangle[i, j] = -1;

                        }

                        else

                            matrixOfTriangle[i, j] += tmp;

                    }

                    else if (j != 0 && j < length - 1 && matrixOfTriangle[i, j] != -1)

                    {

                        int tmp = calculateNodeValue(matrixOfTriangle[i - 1, j],

                                     matrixOfTriangle[i - 1, j - 1]);

                        if (tmp == -1)

                        {

                            matrixOfTriangle[i, j] = -1;

                        }

                        else

                            matrixOfTriangle[i, j] += tmp;

                    }

                    res = Math.Max(matrixOfTriangle[i, j], res);

                }

            } 

            return res;

        }

​

        public static int[,] convertTo2DArrayWithoutSpaces(this string input)

        {

            string[] array = input.Split(new[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);  //remove spaces

​

            int[,] matrixOfTriangle = new int[array.Length, array.Length + 1];      //converting to a matrix

​

            for (var row = 0; row < array.Length; row++)

            {

                int[] digitsInRow = Regex.Matches(array[row], "[0-9]+")

                    .Cast<Match>()

                    .Select(m => int.Parse(m.Value)).ToArray();

​

                //  int[] digitsInRow = array[row].Split(' ').Select(int.Parse).ToArray();

                for (var column = 0; column < digitsInRow.Length; column++)

                { 

                    matrixOfTriangle[row, column] = digitsInRow[column];

                }

            }

            return matrixOfTriangle.removePrimeNumbers();  // checks non-prime numbers and returns them from converted array

        }

​

        private static int calculateNodeValue(int input1, int input2)  //returns max value

        {

            if (input1 == -1 && input2 == -1 || input1 == 0 && input2 == 0)

                return -1;

            else

                return Math.Max(input1, input2);

        }

​

        private static bool isPrime(this int number)

        {

            if ((number & 1) == 0)

            {

                if (number == 2)

                {

                    return true;

                }

                return false;

            }

            for (var i = 3; (i * i) <= number; i += 2)

            {

                if (number % i == 0)

                {

                    return false;

                }

            }

            return number != 1;

        }

​

        private static int[,] removePrimeNumbers(this int[,] matrixOfTriangle)

        {

            int length = matrixOfTriangle.GetLength(0);

            for (var i = 0; i < length; i++)

            {

                for (var j = 0; j < length; j++)

                {

                    if (matrixOfTriangle[i, j] == 0)

                    {

                        continue;

                    }

                    else if (isPrime(matrixOfTriangle[i, j]))       //replacing prime numbers with -1 in matrix

                    {

                        matrixOfTriangle[i, j] = -1;

                    }

                }

            }

            return matrixOfTriangle;

        }

    }