Skip to content

Instantly share code, notes, and snippets.

@tomfuru
Created August 9, 2012 04:26
Show Gist options
  • Save tomfuru/3300971 to your computer and use it in GitHub Desktop.
Save tomfuru/3300971 to your computer and use it in GitHub Desktop.
dc20120809
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment