dc20120809

gistfile1.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace Application
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            int ret1 = Max_trace_AllCheck();
            sw.Stop();
            Console.WriteLine(string.Format("All Check({0}ms): {1}", sw.ElapsedMilliseconds, ret1));

            /*
            sw.Reset();
            sw.Start();
            List<IEnumerable<int>> l = new List<IEnumerable<int>>();
            foreach (var el in enumerate(0, 1, new int[] {0})) {  }
            sw.Stop();
            Console.WriteLine(string.Format("Enumerate({0}ms)", sw.ElapsedMilliseconds)); // about 58ms
            */

            sw.Reset();
            sw.Start();
            int ret2 = Max_trace_fromBottom();
            sw.Stop();
            Console.WriteLine(string.Format("From Bottom({0}ms): {1}", sw.ElapsedMilliseconds, ret2));

            sw.Reset();
            sw.Start();
            int ret3 = Max_trace_CutOff();
            sw.Stop();
            Console.WriteLine(string.Format("Cut Off({0}ms): {1}", sw.ElapsedMilliseconds, ret3));
        }

        // Enumerate all patterns and get max
        private static int Max_trace_AllCheck()
        {
            return enumerate(0, 1, new int[] {0}).Select(indexes => indexes.Select((val, i) => DATA[i][val]).Sum()).Max();

        }
        private static IEnumerable<IEnumerable<int>> enumerate(int i, int depth, IEnumerable<int> val)
        {
            if (depth == DATA_ROW_NUM - 1) {
                yield return val.Concat(new int[] {i});
                yield return val.Concat(new int[] {i + 1});
            }
            else {
                foreach (var el in enumerate(i, depth + 1, val.Concat(new int[] {i}))) {
                    yield return el;
                }
                foreach (var el in enumerate(i + 1, depth + 1, val.Concat(new int[] {i + 1}))) {
                    yield return el;
                }
            }
        }

        private static int Max_trace_fromBottom()
        {
            var maxList = new List<int>(DATA[DATA_ROW_NUM - 1]);
            for (int i = DATA_ROW_NUM - 2; i >= 0; i--) {
                List<int> newList = new List<int>();
                for (int j = 0; j <= i; j++) {
                    int max = DATA[i][j] + Math.Max(maxList[j], maxList[j + 1]);
                    newList.Add(max);
                }
                maxList = newList;
            }
            return maxList[0];
        }

        private static int Max_trace_CutOff()
        {
            // Find max of each row
            int[] CUTOFF_TABLE = new int[DATA_ROW_NUM];
            for (int i = 0; i < DATA_ROW_NUM; i++) {
                CUTOFF_TABLE[i] = DATA[i].Max();
            }

            for (int i = DATA_ROW_NUM - 2; i >= 0; i--) {
                CUTOFF_TABLE[i] += CUTOFF_TABLE[i + 1];
            }

            int max = -1;
            foreach (var indexes in enumerate(0, 1, new int[] {0})) {
                int sum = 0;
                int i = 0;
                foreach (var index in indexes) {
                    sum += DATA[i][index];
                    if (i < DATA_ROW_NUM - 1 && sum + CUTOFF_TABLE[i + 1] < max) { break; }
                    ++i;
                }
                max = Math.Max(max, sum);
            }

            return max;
        }

        private static readonly int[][] DATA = {
            new int[] {75},
            new int[] {95, 64},
            new int[] {17, 47, 82},
            new int[] {18, 35, 87, 10},
            new int[] {20, 04, 82, 47, 65},
            new int[] {19, 01, 23, 75, 03, 34},
            new int[] {88, 02, 77, 73, 07, 63, 67},
            new int[] {99, 65, 04, 28, 06, 16, 70, 92},
            new int[] {41, 41, 26, 56, 83, 40, 80, 70, 33},
            new int[] {41, 48, 72, 33, 47, 32, 37, 16, 94, 29},
            new int[] {53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14},
            new int[] {70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57},
            new int[] {91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48},
            new int[] {63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31},
            new int[] {04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23}
        };
        private static readonly int DATA_ROW_NUM = 15;
    }
}

// All Check(436ms): 1074
// From Bottom(4ms) : 1074
// Cut Off(306ms): 1074