C#
Almost entirely random and raw assembly solution. As far as C# and pretty much any other platform goes, this is as low level as possible. Luckily, C# allows you to define methods during runtime in IL (IL is intermediate language, the byte-code of .NET, similar to assembly). The only limitation of this code is that I chose some opcodes (out of hundreds) with an arbitrary distribution which would be necessary for the perfect solution. If we allow all opcodes, chances of a working program are slim to none, so this is necessary (as you can imagine, there are many many ways that random assembly instructions can crash, but luckily, they don't bring down the whole program in .NET). Other than the range of possible opcodes, it's completely random slicing and dicing IL opcodes without any kind of hinting. I am pretty surprised but this actually seems to work, some generated programs do not crash and do produce results!
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);
}
}
}
}
Sorry I have no results so far because even with testing for 1..99 (instead of 1..9999) is pretty slow and I am too tired. Will get back to you tomorrow.
EDIT: I finished the program and tweaked it a lot. Now, if you press CTRL-C, it will finish the current run and output the results in files. Currently, the only viable solutions it produces are programs which always return a constant number. I'm starting to think that the chances of a more advanced working program are astronomically small. Anyway I will keep it running for some time.
EDIT: I keep tweaking the algorithm, it's a perfect toy for a geek like me. I once saw a generated program which actually did some random math and didn't always return a constant number. It would be awesome to run it on a few million CPU's at once :). Will keep running it.
EDIT: Here's the result of some completely random math. It jumps around and stays at 17 for the rest of the indices. It won't become conscious anytime soon.
EDIT: It's getting more complicated. Of course, as you would expect, it looks nothing like the proper digitsum algorithm, but it's trying hard. Look, a computer generated assembly program!
no librariesallowed mean no libc? \$\endgroup\$no librariesas it would be to complex imo, so the voters can decide if there are to many libraries used! \$\endgroup\$