nkbl.cs

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        ForceVsIntelligence();
        Console.WriteLine("Intelligence won!");
    }

    static void ForceVsIntelligence() {
        var random = new Random();

        for (var i=0;i<100;i++) {
            var boundary = GetRandomBoundary(random:random, length:6, limit:8);
            var force = BruteForce(boundary);
            var intelligence = PureIntelligence(boundary);
            if (Evaluate(force) != Evaluate(intelligence)) {
                throw new Exception("WTF?!");
            }
        }
    }

    static int Evaluate(int[] candidate) {
        var result = 0;
        for (int i=1;i<candidate.Length;i++) {
            result += Math.Abs(candidate[i-1] - candidate[i]);
        }
        return result;
    }

    static int[] BruteForce(int[] boundary) {
        int max = -1;
        int[] winner = null;
        foreach (var candidate in Candidates(boundary)) {
            var evaluation = Evaluate(candidate);
            if (evaluation > max) {
                max = evaluation;
                winner = (int[])candidate.Clone();
            }
        }
        return winner;
    }

    static int[] PureIntelligence(int[] boundary) 
    {
        var tsorted = new int[boundary.Length * 2];
        var weight = new int[boundary.Length * 2];
        var ancestor = new int[boundary.Length * 2];
        for (var i = 0; i < tsorted.Length; i++) 
        {
            tsorted[i] = i % 2 == 0 ? 1 : boundary[i / 2];
            weight[i] = i/2 == 0 ? 0 : -1;
            ancestor[i] = -1;
        }
        for (var i = 0; i < tsorted.Length - 2; i++) 
        {
            var descendants = new int[] { 2*(i/2 + 1), 2 * (i / 2 + 1) + 1 };
            foreach (var descendant in descendants) 
            {
                var length = weight[i] + Math.Abs(tsorted[i] - tsorted[descendant]);
                if (weight[descendant] < length) 
                {
                    weight[descendant] = length;
                    ancestor[descendant] = i;
                }
            }
        }
        var tail = weight.Length;
        tail += weight[tail - 1] > weight[tail - 2] ? -1 : -2;
        var result = new Stack<int>();
        while (tail != -1) 
        {
            result.Push(tsorted[tail]);
            tail = ancestor[tail];
        }
        return result.ToArray();
    }

    static int[] GetRandomBoundary(Random random, int length, int limit) {
        var result = new int[length];
        for (int i=0;i<length;i++) {
            result[i] = 1 + random.Next(limit);
        }
        return result;
    }

    static IEnumerable<int[]> Candidates(int[] boundary) {
        var candidate = new int[boundary.Length];
        for (var i=0;i<boundary.Length;i++) {
            candidate[i] = 1;
        }
        do {
            yield return candidate;
        } while (InplaceInc(candidate, boundary));
    }

    static bool InplaceInc(int[] candidate, int[] boundary) {
        var p = 0;
        while (p < boundary.Length) {
            if (candidate[p]==boundary[p]) {
                candidate[p] = 1;
                p++;
                continue;
            }
            candidate[p]++;
            return true;
        }
        return false;
    }
}