DO#
Niemal całkowicie losowe i surowe rozwiązanie montażowe. Jeśli chodzi o C # i praktycznie każdą inną platformę, jest to tak niski poziom, jak to możliwe. Na szczęście C # pozwala definiować metody podczas działania w IL (IL to język pośredni, kod bajtowy .NET, podobny do asemblera). Jedynym ograniczeniem tego kodu jest to, że wybrałem niektóre kody (spośród setek) o dowolnej dystrybucji, która byłaby konieczna dla idealnego rozwiązania. Jeśli zezwolimy na wszystkie kody operacyjne, szanse na działający program są niewielkie lub nie ma ich wcale, więc jest to konieczne (jak można sobie wyobrazić, istnieje wiele sposobów, w jakie mogą wystąpić awarie instrukcji montażu, ale na szczęście nie zmniejszają one całego programu w sieci). Poza zakresem możliwych kodów, jest to całkowicie losowe krojenie i krojenie kodów IL bez żadnego podpowiedzi.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection.Emit;
using System.Diagnostics;
using System.Threading;
namespace codegolf
{
class Program
{
// decompile this into IL to find out the opcodes needed for the perfect algo
static int digitsumbest(int i)
{
var ret = 0;
while (i > 0)
{
ret += i % 10;
i /= 10;
}
return ret;
}
delegate int digitsumdelegate(int num);
static Thread bgthread;
// actually runs the generated code for one index
// it is invoked in a background thread, which we save so that it can be aborted in case of an infinite loop
static int run(digitsumdelegate del, int num)
{
bgthread = Thread.CurrentThread;
try
{
return del(num);
}
catch (ThreadAbortException)
{
bgthread = null;
throw;
}
}
// evaluates a generated code for some inputs and calculates an error level
// also supports a full run with logging
static long evaluate(digitsumdelegate del, TextWriter sw)
{
var error = 0L;
List<int> numbers;
if (sw == null) // quick evaluation
numbers = Enumerable.Range(1, 30).Concat(Enumerable.Range(1, 70).Select(x => 5000 + x * 31)).ToList();
else // full run
numbers = Enumerable.Range(1, 9999).ToList();
foreach (var num in numbers)
{
try
{
Func<digitsumdelegate, int, int> f = run;
bgthread = null;
var iar = f.BeginInvoke(del, num, null, null);
if (!iar.AsyncWaitHandle.WaitOne(10))
{
bgthread.Abort();
while (bgthread != null) ;
throw new Exception("timeout");
}
var result = f.EndInvoke(iar);
if (sw != null)
sw.WriteLine("{0};{1};{2};", num, digitsumbest(num), result);
var diff = result == 0 ? 15 : (result - digitsumbest(num));
if (diff > 50 || diff < -50)
diff = 50;
error += diff * diff;
}
catch (InvalidProgramException)
{
// invalid IL code, happens a lot, so let's make a shortcut
if (sw != null)
sw.WriteLine("invalid program");
return numbers.Count * (50 * 50) + 1;
}
catch (Exception ex)
{
if (sw != null)
sw.WriteLine("{0};{1};;{2}", num, digitsumbest(num), ex.Message);
error += 50 * 50;
}
}
return error;
}
// generates code from the given byte array
static digitsumdelegate emit(byte[] ops)
{
var dm = new DynamicMethod("w", typeof(int), new[] { typeof(int) });
var ilg = dm.GetILGenerator();
var loc = ilg.DeclareLocal(typeof(int));
// to support jumping anywhere, we will assign a label to every single opcode
var labels = Enumerable.Range(0, ops.Length).Select(x => ilg.DefineLabel()).ToArray();
for (var i = 0; i < ops.Length; i++)
{
ilg.MarkLabel(labels[i]);
// 3 types of jumps with 23 distribution each, 11 types of other opcodes with 17 distribution each = all 256 possibilities
// the opcodes were chosen based on the hand-coded working solution
var c = ops[i];
if (c < 23)
ilg.Emit(OpCodes.Br_S, labels[(i + 1 + c) % labels.Length]);
else if (c < 46)
ilg.Emit(OpCodes.Bgt_S, labels[(i + 1 + c - 23) % labels.Length]);
else if (c < 69)
ilg.Emit(OpCodes.Bge_S, labels[(i + 1 + c - 46) % labels.Length]);
else if (c < 86)
ilg.Emit(OpCodes.Ldc_I4, c - 70); // stack: +1
else if (c < 103)
ilg.Emit(OpCodes.Dup); // stack: +1
else if (c < 120)
ilg.Emit(OpCodes.Ldarg_0); // stack: +1
else if (c < 137)
ilg.Emit(OpCodes.Starg_S, 0); // stack: -1
else if (c < 154)
ilg.Emit(OpCodes.Ldloc, loc); // stack: +1
else if (c < 171)
ilg.Emit(OpCodes.Stloc, loc); // stack: -1
else if (c < 188)
ilg.Emit(OpCodes.Mul); // stack: -1
else if (c < 205)
ilg.Emit(OpCodes.Div); // stack: -1
else if (c < 222)
ilg.Emit(OpCodes.Rem); // stack: -1
else if (c < 239)
ilg.Emit(OpCodes.Add); // stack: -1
else
ilg.Emit(OpCodes.Sub); // stack: -1
}
ilg.Emit(OpCodes.Ret);
return (digitsumdelegate)dm.CreateDelegate(typeof(digitsumdelegate));
}
static void Main(string[] args)
{
System.Diagnostics.Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.Idle;
var rnd = new Random();
// the first list is just 10 small random ones
var best = new List<byte[]>();
for (var i = 0; i < 10; i++)
{
var initial = new byte[5];
for (var j = 0; j < initial.Length; j++)
initial[j] = (byte)rnd.Next(256);
best.Add(initial);
}
// load the best result from the previous run, if it exists
if (File.Exists("best.txt"))
best[0] = File.ReadAllLines("best.txt").Select(x => byte.Parse(x)).ToArray();
var stop = false;
// handle nice stopping with ctrl-c
Console.CancelKeyPress += (s, e) =>
{
stop = true;
e.Cancel = true;
};
while (!stop)
{
var candidates = new List<byte[]>();
// leave the 10 best arrays, plus generate 9 consecutive mutations for each of them = 100 candidates
for (var i = 0; i < 10; i++)
{
var s = best[i];
candidates.Add(s);
for (var j = 0; j < 9; j++)
{
// the optimal solution is about 20 opcodes, we keep the program length between 15 and 40
switch (rnd.Next(s.Length >= 40 ? 2 : 0, s.Length <= 15 ? 3 : 5))
{
case 0: // insert
case 1:
var c = new byte[s.Length + 1];
var idx = rnd.Next(0, s.Length);
Array.Copy(s, 0, c, 0, idx);
c[idx] = (byte)rnd.Next(256);
Array.Copy(s, idx, c, idx + 1, s.Length - idx);
candidates.Add(c);
s = c;
break;
case 2: // change
c = (byte[])s.Clone();
idx = rnd.Next(0, s.Length);
c[idx] = (byte)rnd.Next(256);
candidates.Add(c);
s = c;
break;
case 3: // remove
case 4: // remove
c = new byte[s.Length - 1];
idx = rnd.Next(0, s.Length);
Array.Copy(s, 0, c, 0, idx);
Array.Copy(s, idx + 1, c, idx, s.Length - idx - 1);
candidates.Add(c);
s = c;
break;
}
}
}
// score the candidates and select the best 10
var scores = Enumerable.Range(0, 100).ToDictionary(i => i, i => evaluate(emit(candidates[i]), null));
var bestidxes = scores.OrderBy(x => x.Value).Take(10).Select(x => x.Key).ToList();
Console.WriteLine("best score so far: {0}", scores[bestidxes[0]]);
best = bestidxes.Select(i => candidates[i]).ToList();
}
// output the code of the best solution
using (var sw = new StreamWriter("best.txt"))
{
foreach (var b in best[0])
sw.WriteLine(b);
}
// create a CSV file with the best solution
using (var sw = new StreamWriter("best.csv"))
{
sw.WriteLine("index;actual;generated;error");
evaluate(emit(best[0]), sw);
}
}
}
}
Niestety nie mam do tej pory żadnych wyników, ponieważ nawet przy testach na 1..99 (zamiast 1..9999) jest dość powolny i jestem zbyt zmęczony. Wrócę do ciebie jutro.
EDYCJA: Skończyłem program i dużo go poprawiałem. Teraz, jeśli naciśniesz CTRL-C, zakończy on bieżący przebieg i wyświetli wyniki w plikach. Obecnie jedynymi możliwymi do rozwiązania rozwiązaniami są programy, które zawsze zwracają stałą liczbę. Zaczynam myśleć, że szanse na bardziej zaawansowany program roboczy są astronomicznie małe. W każdym razie utrzymam go przez jakiś czas.
EDYCJA: Ulepszam algorytm, jest idealną zabawką dla maniaka takiego jak ja. Kiedyś widziałem wygenerowany program, który faktycznie wykonał losową matematykę i nie zawsze zwracał stałą liczbę. Byłoby wspaniale uruchomić go na kilku milionach procesorów jednocześnie :). Nadal go uruchomię.
EDYCJA: Oto wynik jakiejś całkowicie przypadkowej matematyki. Skacze dookoła i pozostaje na poziomie 17 dla pozostałych wskaźników. W najbliższym czasie nie stanie się to świadome.
EDYCJA: Robi się coraz bardziej skomplikowana. Oczywiście, jak można się spodziewać, nie wygląda to jak odpowiedni algorytm cyfry, ale bardzo się stara. Spójrz, wygenerowany komputerowo program asemblacyjny!
no librariesdozwolone oznacza brak libc?