Problem 18: Maximum Path Sum I

Problem:

Please find the problem here.

Solution:

Instead of solving it by brute force, I think it is easier to solve it with dynamic programming. First, let generalize the problem by asking the question - what is the maximum route from an arbitrary node to bottom? The base case is really simple. If you are trying to go from the bottom row to the bottom row, there is only one route with one node, and therefore the maximum total is the node value itself. Now, if we want to reach the node 2 (1st in the 3rd row) in the first triangle, we will pick the left route because 2 + 8 has a bigger sum than 2 + 5. The rule generally applies. If we want to go to 7 (the 1st in the 2nd row), we pick from its children the one with maximum total.

That translate to a dynamic programming algorithm as follow:

maximum_total_cost(last_row) = last_row value
maximum_total_cost(any node n ) = n + max(maximum_total_cost(left_child) + maximum_total_cost(right_child)).

Without further ado, here is the code for the problem:

namespace Euler
{
    using System;
    using System.Linq;
    using System.Numerics;

    internal static partial class Program
    {
        public static void Problem018()
        {
            string input = ReadResourceAsString("Euler.Problem018.txt");
            int[] inputParsed = input.Replace('\r', ' ').Replace('\n', ' ').Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => Int32.Parse(x)).ToArray();
            int numRows = 15;

            // answer(row, column) = data[row, column] + max(answer(row + 1, column), answer(row + 1, column + 1));

            int[,] answer = new int[numRows, numRows];
            for (int i = 1; i <= numRows; i++)
            {
                answer[i - 1, numRows - 1] = inputParsed[i + numRows * (numRows - 1) / 2 - 1];
            }
            for (int currentRow = numRows - 1; currentRow > 0; currentRow--)
            {
                for (int currentColumn = 1; currentColumn <= currentRow; currentColumn++)
                {
                    int currentValue = inputParsed[currentColumn + currentRow * (currentRow - 1) / 2 - 1];
                    answer[currentColumn - 1, currentRow - 1] = currentValue + Math.Max(answer[currentColumn - 1, currentRow + 1 - 1], answer[currentColumn + 1 - 1, currentRow + 1 - 1]);
                }
            }
            Console.WriteLine(answer[0, 0]);
        }
    }
}

Answer: 1074

Problem 17: Number letter counts

Problem:

Please find the problem here.

Solution:

Just implement the rules - nothing special about this problem, here is the code. Note that ToEnglishString() works only if the input is between 1 to 1000, which is enough for the purpose.

namespace Euler
{
    using System;
    using System.Linq;

    internal static partial class Program
    {
        public static void Problem017()
        {   
            Console.WriteLine(Enumerable.Range(1, 1000).Select(i => ToEnglishString(i).Replace(" ", string.Empty).Length).Aggregate((x, y) => x + y));
        }

        static string ToEnglishString(int i)
        {
            string ONE = "one";
            string TWO = "two";
            string THREE = "three";
            string FOUR = "four";
            string FIVE = "five";
            string SIX = "six";
            string SEVEN = "seven";
            string EIGHT = "eight";
            string NINE = "nine";
            string TEN = "ten";
            string ELEVEN = "eleven";
            string TWELVE = "twelve ";
            string THIRTEEN = "thirteen";
            string FOURTEEN = "fourteen";
            string FIFTEEN = "fifteen";
            string SIXTEEN = "sixteen";
            string SEVENTEEN = "seventeen";
            string EIGHTEEN = "eighteen";
            string NINETEEN = "nineteen";
            string TWENTY = "twenty";
            string THIRTY = "thirty";
            string FORTY = "forty";
            string FIFTY = "fifty";
            string SIXTY = "sixty";
            string SEVENTY = "seventy";
            string EIGHTY = "eighty";
            string NINETY = "ninety";
            string HUNDRED = "hundred";
            string THOUSAND = "thousand";
            switch (i)
            {
                case 1000: return ONE + " " + THOUSAND;
                case 1: return ONE;
                case 2: return TWO;
                case 3: return THREE;
                case 4: return FOUR;
                case 5: return FIVE;
                case 6: return SIX;
                case 7: return SEVEN;
                case 8: return EIGHT;
                case 9: return NINE;
                case 10: return TEN;
                case 11: return ELEVEN;
                case 12: return TWELVE;
                case 13: return THIRTEEN;
                case 14: return FOURTEEN;
                case 15: return FIFTEEN;
                case 16: return SIXTEEN;
                case 17: return SEVENTEEN;
                case 18: return EIGHTEEN;
                case 19: return NINETEEN;
                case 20: return TWENTY;
                default:
                    string result = string.Empty;
                    int remaining;
                    int hundredthDigit = i / 100;
                    remaining = i - hundredthDigit * 100;
                    if (hundredthDigit != 0)
                    {
                        result += ToEnglishString(hundredthDigit) + " " + HUNDRED;
                        if (remaining == 0)
                        {
                            return result;
                        }
                        else
                        {
                            result = result + " and ";
                        }
                    }

                    int tenthDigit = remaining / 10;
                    remaining = remaining - tenthDigit * 10;

                    switch (tenthDigit)
                    {
                        case 1:
                            switch (remaining)
                            {
                                case 0: result = result + TEN; break;
                                case 1: result = result + ELEVEN; break;
                                case 2: result = result + TWELVE; break;
                                case 3: result = result + THIRTEEN; break;
                                case 4: result = result + FOURTEEN; break;
                                case 5: result = result + FIFTEEN; break;
                                case 6: result = result + SIXTEEN; break;
                                case 7: result = result + SEVENTEEN; break;
                                case 8: result = result + EIGHTEEN; break;
                                case 9: result = result + NINETEEN; break;

                            };
                            remaining = 0;
                            break;
                        case 2: result = result + TWENTY; break;
                        case 3: result = result + THIRTY; break;
                        case 4: result = result + FORTY; break;
                        case 5: result = result + FIFTY; break;
                        case 6: result = result + SIXTY; break;
                        case 7: result = result + SEVENTY; break;
                        case 8: result = result + EIGHTY; break;
                        case 9: result = result + NINETY; break;
                    }
                    if (tenthDigit != 0)
                    {
                        result = result + " ";
                    }
                    if (remaining != 0)
                    {
                        result = result + ToEnglishString(remaining);
                    }
                    return result;
            }

        }
    }
}

Answer: 21224

Problem 16: Power Digit Sum

Problem:

Please find the problem here.

Solution:

Just compute it with BigInteger in C#. Here is the code:

namespace Euler
{
    using System;
    using System.Linq;
    using System.Numerics;

    internal static partial class Program
    {
        public static void Problem016()
        {
            BigInteger p = BigInteger.Pow(new BigInteger(2), 1000);
            Console.WriteLine(p.ToString().Select(x => x - '0').Aggregate((x, y) => (x + y)));
        }
    }
}

Answer: 1366