Skip to content

Instantly share code, notes, and snippets.

@rystsov
Created Jan 21, 2017
Embed
What would you like to do?
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment