Domino-Schaltungen

36

Anzeigetafel

Hier sind die Rohwerte (dh Domino-Werte) für die Einreichung von VisualMelon. Ich werde diese Werte in die unten beschriebenen normalisierten Werte umwandeln, wenn weitere Antworten eingehen. Die vorhandene Lösung kann jetzt alle Schaltkreise im Benchmark lösen:

 Author       Circuit:   1   2   3   4    5    6   7    8   9  10  11  12   13  14   15   16   17   18  19   20   21  22   23   24    25   26   27   28    29    30    31    32   33   34    35    36     37      38   39
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
VisualMelon             39  45  75  61  307  337  56  106  76  62  64  62  182  64  141  277  115  141  92  164  223  78  148  371  1482  232  107  782  4789  5035  1314  3213  200  172  1303  3732  97596  156889  857
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Legend:
  I - invalid circuit
  B - circuit too big
  W - circuit computes wrong function
  T - exceeded time limit

Die Herausforderung

Es ist möglich , einfache Logikgatter aus Dominosteinen zu bauen. Durch Kombinieren dieser oder anderer Funktionen können daher beliebige Binärfunktionen mit Dominosteinen berechnet werden.

Aber natürlich hat jeder, der mit Dominosteinen gespielt hat (mit Ausnahme von Robin Paul Weijers), die Enttäuschung erlebt, wenn er davonläuft. Daher möchten wir unsere Dominosteine ​​so effizient wie möglich einsetzen, damit wir mit dem vorhandenen Material einige wirklich interessante Berechnungen durchführen können.

Beachten Sie, dass Sie keine Nicht-Null-Ausgabe aus der Null-Eingabe per se erzeugen können. Daher müssen wir eine "Stromleitung" hinzufügen, die entlang Ihres Setups verläuft und von der Sie jederzeit 1s abrufen können.

Deine Aufgabe

Erstellen Sie bei einer Booleschen Funktion mit MEingängen und NAusgängen ( f: {0,1}^M --> {0,1}^Nfür die mathematisch geneigten) eine Domino-Schaltung mit möglichst wenigen Dominosteinen, die diese Funktion berechnet. Hier finden Sie die Symbole verwenden |, -, /,\ Dominosteine in verschiedenen Orientierungen zu vertreten.

Eingang

Sie erhalten Eingaben über Befehlszeilenargumente:

[command for your solver] M N f

wo Mund Nsind positive ganze Zahlen und fist das Komma getrennt Wahrheitstabelle in kanonischer Reihenfolge. Das heißt, fenthält 2^MWerte der Länge N. ZB wenn M = N = 2und das erste Bit in der Ausgabe die UND-Funktion war, während das zweite Bit die ODER-Funktion war, fwürde gelesen

00,01,01,11

Ausgabe

Schreiben Sie in STDOUT ein ASCII-Raster, das das Domino-Setup darstellt. Ihr Setup muss in das folgende Framework passen

/////.../////
 ????...????
I????...????O
I????...????O
.............
.............
I????...????O
I????...????O
I????...????O
  • Die oberste Reihe besteht ganz aus /und der Domino ganz links wird garantiert zu Beginn umgestürzt - das ist Ihre Stromleitung.
  • Die äußerste linke Spalte enthält Ihre Eingaben. Jedes Ikann entweder ein Leerzeichen oder ein sein |, so dass es genau M |s gibt.
  • Die Spalte ganz rechts enthält Ihre Ausgaben. Jedes Okann entweder ein Leerzeichen oder ein sein |, so dass es genau N |s gibt.
  • Beachten Sie, dass |in der Eingabe oder Ausgabe mindestens ein Leerzeichen vor dem ersten vorhanden ist .
  • Die .anzeigen , dass das Raster beliebig groß sein kann.
  • Sie können die Felder ?nach Belieben ausfüllen .

Beachten Sie, dass sich die Eingabe unten am schnellsten ändert, während Sie die Wahrheitstabelle durchlaufen, während sich die Eingabe oben 0auf die erste Hälfte der Ausgaben und bezieht1 für die zweite Hälfte gilt.

Regeln

Dominosteine ​​vermehren sich wie in " Golfen am Domino-Tag" angegeben . Kurz gesagt, wenn wir die fallenden Richtungen als Buchstaben darstellen

Q W E
A   D
Z X C

Dann sind dies alles einzigartige Kombinationen, die sich ausbreiten können (sowie ihre Rotationen und Reflexionen):

D|   ->    DD          D\   ->    DE          D/   ->    DC

C|   ->    CD          C/   ->    CC

C    ->    C           C    ->    C           C    ->    C
 |          D           -          X           /          C

Alle oben genannten Regeln werden bei jedem Zeitschritt gleichzeitig angewendet. Wenn zwei dieser Regeln in Konflikt stehen (dh ein Plättchen wird gleichzeitig in zwei gültige entgegengesetzte Richtungen verschoben), fällt das betroffene Plättchen nicht herunter und wird für den Rest der Simulation effektiv in seiner Position verriegelt.

Beschränkungen

  • M und N wird nie mehr als 6.
  • Ihr Solver muss innerhalb von N * 2 M Sekunden einen Stromkreis erzeugen .
  • Ihr Solver darf nicht mehr als 1 GB Arbeitsspeicher verwenden . Dies ist eine weiche Grenze, da ich dies manuell überwachen und Ihren Prozess beenden werde, wenn er diese Grenze signifikant / kontinuierlich überschreitet.
  • Kein Stromkreis darf mehr als 8.000.000 Zellen oder 1.000.000 Dominosteine ​​enthalten .
  • Ihre Vorlage muss deterministisch sein . Sie dürfen Pseudozufallszahlengeneratoren verwenden, diese müssen jedoch einen fest codierten Startwert verwenden (den Sie nach Belieben optimieren können).

Wertung

DGeben Sie für jede Runde die Gesamtzahl der Dominosteine ​​in Ihrer Runde und Bdie niedrigste Anzahl der Dominosteine ​​an, mit denen diese Runde gelöst wurde (von Ihnen oder einem anderen Teilnehmer). Dann ist Ihre Punktzahl für diese Strecke gegeben durch10,000 * B / D Abrunden angegeben. Wenn Sie die Schaltung nicht gelöst haben, ist Ihre Punktzahl 0. Ihre Gesamtpunktzahl ist die Summe über einem Benchmark-Satz von Testfällen. Schaltungen, die noch von niemandem gelöst wurden, werden nicht in die Gesamtpunktzahl einbezogen.

Jeder Teilnehmer kann einen Testfall zum Benchmark hinzufügen (und alle anderen Einsendungen werden neu bewertet, einschließlich des neuen Testfalls).

Die Benchmark-Datei finden Sie auf GitHub .

Beispiele

Hier einige nicht optimal gelöste Beispiele.

Konstante 1

1 1
1,1

///////
   /
|   |||

Domino-Anzahl: 12

ODER Tor

2 1
0,1,1,1

///////////

|||||/
      |||||
|||||\

Domino-Anzahl: 28

UND Tor

2 1
0,0,0,1

///////////////////

       \-/
       - -
|||||/|\ /|||/
      /      -
       -    \-
      \-   \ -
|||||\ /  \  /
        |\    |||||

Domino-Anzahl: 62

Fahrspuren tauschen

2 2
00,10,01,11

////////////

||||/  \||||
     /\
     \/
||||\  /||||

Domino-Anzahl: 36

Zusätzliche Bemerkungen

Die Ausbreitungsregeln sind so, dass sich diagonale Bahnen mit einer Rautenform kreuzen können (siehe letztes Beispiel), auch wenn eine vor der anderen fällt (im Gegensatz zu echten Dominosteinen).

Als Ausgangspunkt können Sie die (nicht minimierten) logischen Gatter in dieser Übersicht verwenden und versuchen, so wenig wie möglich davon zu kombinieren. Für eine einfache (nicht optimale) Möglichkeit, beliebige Boolesche Funktionen aus UND-, ODER- und NICHT-Gattern zu erstellen, werfen Sie einen Blick auf Konjunktive und disjunktive Normalformen.

Es gibt einen Prüfer für dieses GitHub-Repository , um Ihren Code zu testen, der auch zum Bewerten aller Einsendungen verwendet wird. Dadurch werden die Rohwerte (Domino-Werte) ausgegeben und in einer Datei gespeichert, die von einem separaten Scorer (ebenfalls in diesem Repository) verarbeitet wird, um die Endwerte zu erhalten.

Allgemeine Dokumentation finden Sie in den beiden Ruby-Dateien, die jedoch controller.rbzwei Befehlszeilenoptionen vor der Benchmark-Datei benötigt:

  • -v Sie erhalten mehr Ausgabe, einschließlich der von Ihrem Solver tatsächlich erzeugten Schaltungen.
  • -cMit dieser Option können Sie eine Teilmenge des Benchmarks auswählen, den Sie testen möchten. Geben Sie die gewünschten Schaltkreise als durch Kommas getrennte Liste von 1-basierten Indizes an. Sie können auch Ruby-Bereiche verwenden, sodass Sie beispielsweise Folgendes tun können -c 1..5,10,15..20.

Bitte geben Sie in Ihrer Antwort an:

  • Dein Code
  • Ein Befehl zum (Kompilieren und) Ausführen Ihres Codes. Ich frage Sie, wo Sie die erforderlichen Übersetzer / Dolmetscher bekommen, wenn ich sie nicht habe.
  • Eine zusätzliche Wahrheitstabelle mit einem Namen, die als Testfall zum Benchmark hinzugefügt werden soll. (Dies ist optional, wird jedoch dringend empfohlen.)

Ich werde alle Einsendungen unter Windows 8 testen.

Martin Ender
quelle
Alle gleichzeitig geschoben?
14 m²,
@ l4m2 Ja, die Eingänge in der Spalte ganz links werden gleichzeitig gestürzt.
Martin Ender

Antworten:

33

Massive, langsame und ineffiziente Lösung

Geständnis: schrieb diese Lösung vor einiger Zeit, als die Frage noch im Sandkasten war, aber es ist nicht sehr gut: Sie können es besser machen!

Bearbeiten: Die langweilige Lösung wurde durch eine weniger langweilige, flexiblere und allgemein bessere Methode ersetzt

Sie führen das Programm aus, indem Sie beispielsweise mit csc dominoPrinter.csder ausführbaren Datei (dem 4-Bit-Prime-Checker) kompilieren und dann Argumente übergeben:

dominoPrinter.exe 4 1 0,0,1,1,0,1,0,1,0,0,0,1,0,1,1,1

Erläuterung:

Der "Domino-Drucker" ist ein dreistufiges Programm:

Stufe 1 : Der "Löser" generiert einen Ausdrucksbaum aus "ifnot" und "oder" binären Operationen mit den angegebenen Eingaben und einer "1" von der Stromleitung. Dies erfolgt auf zwei Arten, abhängig von der Anzahl der Eingaben:

  • Wenn weniger als 4 Eingaben vorhanden sind, bietet das Programm eine Lösung mit der geringsten Anzahl von Operationen

  • Wenn es 4 oder mehr Eingänge gibt, brutet das Programm jeden 8-Bit-Ausgang und kombiniert dann die Ergebnisse, um den gewünschten Ausgang zu erhalten. Die brutalen Bits sind flexibel: Je mehr brutale Bits vorhanden sind, desto kleiner ist die Lösung, desto länger ist jedoch die Laufzeit.

Der "Solver" ist das, was die ganze Zeit (oder zumindest früher) dauert und auch den größten Teil des Codes ausmacht. Ich glaube, es gibt eine gut dokumentierte, schnelle, nicht so speicherhungrige und wahrscheinlich optimale Lösung für dieses Problem, aber wo würde es Spaß machen, danach zu suchen?

Der (brutale) Ausdrucksbaum für den 4-Bit-Prim Checker lautet

((2 or 1) ifnot (((0 ifnot 1) or ((1 ifnot 0) or (0 ifnot 2))) ifnot 3))

Dabei sind die Zahlen die Indizes der Eingaben.

Stufe 2 : Der "Organisator" nimmt den Ausdrucksbaum als Eingabe und setzt ein "Gerüst" -Layout zusammen, das genau ein Domino-Layout beschreibt, das aus einem Satz von 4 × 5 überlappenden Zellen besteht. Unten sehen Sie das Grundgerüst für den brachialen 4-Bit-Prim-Checker (Sie müssen die bruteBaseGanzzahlvariable in Zeile 473 auf 4 (oder größer) ändern , um dieses Ergebnis zu erhalten).

18 9
I ___ _ _______  O
 v _ X X ____  uu 
I X X X u    UU/  
 v X X v ___///   
I X X \ u   //    
 v X \ v __//     
I_X \ \_u  /      
   \ \ ___/       
    \_U 

Diese Ausgabe besteht effektiv aus zwei Teilen, dem "Evaluator" auf der rechten Seite, der aus dem Ausdrucksbaum von Stufe 1 erstellt wird, und der "Schalttafel" auf der linken Seite, die die Eingaben so vertauscht und aufteilt, dass sie in der Tabelle eintreffen Die richtigen Stellen für den "Evaluator".

Es gibt an dieser Stelle einen erheblichen Spielraum für die Komprimierung des Layouts, aber das Programm erledigt derzeit nur sehr wenige derartige Arbeiten. Der Code für diese Stufe ist schrecklich, aber darunter ziemlich einfach (siehe "orifnot" -Methode). Die Ausgabe wird an Stufe 3 übergeben.

Stufe 3 : Der "Drucker" nimmt die Ausgabe vom "Organizer" und druckt die entsprechenden 4x5 überlappenden "Zellen" zusammen mit der Stromleitung. Unten sehen Sie eine Animation des brachialen 4-Bit-Prime-Checkers, der prüft, ob 5 ein Prime ist.

Anscheinend ist 5 Primzahl

Code der Mangel an Einrücken ist über die SE 30k Zeichenbegrenzung zu vermeiden , gehen die es sonst der Fall wäre :

using System;
using System.Collections.Generic;

namespace dominoPrinter
{
 class Program
 {
  static string bstring(bool[] barr)
  {
   string str = "";
   foreach (bool b in barr)
    str += b?1:0;
   return str;
  }

  public static void Main(string[] args)
  {

   int inputCount;
   val[] vals = resolveVals(args[0], args[1], args[2], out inputCount);

   System.IO.StringWriter sw = new System.IO.StringWriter();
   orifnot(inputCount, vals, sw);
   System.IO.StringReader sr = new System.IO.StringReader(sw.ToString());

   printDominoes(sr, Console.Out, args.Length > 3 && args[3] == "quite");
  }

  public abstract class val
  {
   public int size;
   public bool[] rs;
   public abstract string strness();
  }

  public class baseVal : val
  {
   public bool b;
   public int id;

   public baseVal(int idN)
   {
    id = idN;
    size = 1;
   }

   public override string strness()
   {
    return id.ToString();
   }
  }

  public abstract class biopVal : val
  {
   public val a, b;

   public biopVal(val aN, val bN)
   {
    a = aN;
    b = bN;
    size = a.size + b.size;
   }

   public bool buildCheckApply(nodev ntree)
   {
    nodev cur = ntree;
    rs = new bool[a.rs.Length];
    bool notOK = true;
    for (int i = 0; i < rs.Length; i++)
    {
     bool r = rs[i] = go(a.rs[i], b.rs[i]);
     if (notOK)
     {
      if (r)
      {
       if (cur.a == null)
        notOK = false;
       else
       {
        cur = cur.a;
        if (cur == nodev.full)
         return false;
       }
      }
      else
      {
       if (cur.b == null)
        notOK = false;
       else
       {
        cur = cur.b;
        if (cur == nodev.full)
         return false;
       }
      }
     }
    }

    ntree.apply(this, 0);
    return true;
   }

   public abstract bool go(bool a, bool b);
  }

  public class ifnotVal : biopVal
  {
   public override bool go(bool a, bool b)
   {
     return a ? false : b; // b IF NOT a, else FALSE
   }

   public ifnotVal(val aN, val bN) : base(aN, bN)
   {
   }

   public override string strness()
   {
    return "(" + b.strness() + " ifnot " + a.strness() + ")";
   }
  }

  public class orval : biopVal
  {
   public override bool go(bool a, bool b)
   {
    return a || b; // a OR b
   }

   public orval(val aN, val bN) : base(aN, bN)
   {
   }

   public override string strness()
   {
    return "(" + b.strness() + " or " + a.strness() + ")";
   }
  }

  static bool boolCompare(bool[] a, bool b)
  {
   for (int i = 0; i < a.Length; i++)
   {
    if (a[i] != b)
    {
     return false;
    }
   }
   return true;
  }

  static bool boolFlat(bool[] a)
  {
   bool p = a[0];
   for (int i = 1; i < a.Length; i++)
   {
    if (a[i] != p)
     return false;
   }
   return true;
  }

  static bool boolCompare(bool[] a, bool[] b)
  {
   if (a.Length != b.Length)
    return false; // let's do this proeprly
   for (int i = 0; i < a.Length; i++)
   {
    if (a[i] != b[i])
    {
     return false;
    }
   }
   return true;
  }

  // solver

  // these is something VERY WRONG with the naming in this code
  public class nodev
  {
   public static nodev full = new nodev();

   public nodev a, b;

   public nodev()
   {
    a = null;
    b = null;
   }

   public bool contains(bool[] rs)
   {
    nodev cur = this;
    if (cur == full)
     return true;

    for (int i = 0; i < rs.Length; i++)
    {
     if (rs[i])
     {
      if (cur.a == null)
       return false;
      cur = cur.a;
     }
     else
     {
      if (cur.b == null)
       return false;
      cur = cur.b;
     }

     if (cur == full)
      return true;
    }
    return true;
   }

   public bool contains(val v)
   {
    nodev cur = this;
    if (cur == full)
     return true;

    for (int i = 0; i < v.rs.Length; i++)
    {
     if (v.rs[i])
     {
      if (cur.a == null)
       return false;
      cur = cur.a;
     }
     else
     {
      if (cur.b == null)
       return false;
      cur = cur.b;
     }

     if (cur == full)
      return true;
    }
    return true;
   }

   // returns whether it's full or not
   public bool apply(val v, int idx)
   {
    if (v.rs[idx])
    {
     if (a == null)
     {
      if (idx == v.rs.Length - 1)
      { // end of the line, fellas
       a = full;
       if (b == full)
        return true;
       return false;
      }
      else
      {
       a = new nodev();
      }
     }
     if (a.apply(v, idx + 1))
      a = full;
     if (a == full && b == full)
      return true;
    }
    else
    {
     if (b == null)
     {
      if (idx == v.rs.Length - 1)
      { // end of the line, fellas
       b = full;
       if (a == full)
        return true;
       return false;
      }
      else
      {
       b = new nodev();
      }
     }
     if (b.apply(v, idx + 1))
      b = full;
     if (a == full && b == full)
      return true;
    }
    return false;
   }
  }

  public static void sortOutIVals(baseVal[] ivals, int rc)
  {
   for (int i = 0; i < ivals.Length; i++)
   {
    ivals[i].rs = new bool[rc];
    ivals[i].b = false;
   }

   int eri = 0;

   goto next;
  again:
   for (int i = ivals.Length - 1; i >= 0; i--)
   {
    if (ivals[i].b == false)
    {
     ivals[i].b = true;
     goto next;
    }
    ivals[i].b = false;
   }

   return;
  next:
   for (int i = ivals.Length - 1; i >= 0; i--)
   {
    ivals[i].rs[eri] = ivals[i].b;
   }

   eri++;
   goto again;
  }

  public static val[] resolve(int inputCount, int c, bool[][] erss, out baseVal[] inputs)
  {
   val[] res = new val[erss.Length];

   List<List<val>> bvals = new List<List<val>>();
   nodev ntree = new nodev();

   List<val> nvals = new List<val>();

   baseVal tval = new baseVal(-1);
   baseVal fval = new baseVal(-2);
   baseVal[] ivals = new baseVal[inputCount];
   inputs = new baseVal[inputCount + 2];

   for (int i = 0; i < inputCount; i++)
   {
    ivals[i] = new baseVal(i); // value will change anyway
    inputs[i] = ivals[i];
   }
   inputs[inputCount] = fval;
   inputs[inputCount + 1] = tval;

   sortOutIVals(ivals, c);

   for (int i = 0; i < inputCount; i++)
   {
    nvals.Add(ivals[i]);
   }

   tval.rs = new bool[c];
   fval.rs = new bool[c];
   for (int i = 0; i < c; i++)
   {
    tval.rs[i] = true;
    fval.rs[i] = false;
   }

   nvals.Add(tval);
   nvals.Add(fval); // ifnot and or do nothing with falses

   bvals.Add(new List<val>());

   foreach (val v in nvals)
   {
    ntree.apply(v, 0);
    if (!boolFlat(v.rs))
     bvals[0].Add(v); // I trust these are distinct..
   }

   Func<biopVal, bool> checkValb = (v) =>
   {
    if (!v.buildCheckApply(ntree))
    {
     return false;
    }
    bvals[v.size-1].Add(v);
    return true;
   };

   Action<biopVal, List<val>> checkVal = (v, li) =>
   {
    if (checkValb(v))
     li.Add(v);
   };

   int maxSize = 1;

  again:
   for (int i = 0; i < erss.Length; i++)
   {
    bool[] ers = erss[i];
    if (res[i] == null && ntree.contains(ers))
    {
     // there is a reason this is separate... I'm sure there is....
     foreach (val rv in nvals)
     {
      if (boolCompare(rv.rs, ers))
      {
       res[i] = rv;
       break;
      }
     }
    }
   }

   for (int i = 0; i < erss.Length; i++)
   {
    if (res[i] == null)
     goto notoveryet;
   }
   return res;

  notoveryet:

   maxSize++;
   bvals.Add(new List<val>()); // bvals[maxSize-1] always exists

   nvals.Clear();
   long cc = 0;

   List<val> sbvals = bvals[maxSize - 2];
   // NOTs have a habit of working out, get it checked first
   for (int i = sbvals.Count - 1; i >= 0; i--)
   { // also known as nvals, but let's ignore that
    val arv = sbvals[i];
    checkVal(new ifnotVal(arv, tval), nvals);
    cc += 1;
   }

   for (int s = 1; s < maxSize; s++)
   {
    List<val> abvals = bvals[s - 1];
    int t = maxSize - s;
    if (t < s)
     break;
    List<val> bbvals = bvals[t - 1];

    for (int i = abvals.Count - 1; i >= 0; i--)
    {
     val arv = abvals[i];

     int jt = t == s ? i : bbvals.Count - 1;
     for (int j = jt; j >= 0; j--)
     {
      val brv = bbvals[j];

      checkVal(new ifnotVal(brv, arv), nvals);
      checkVal(new ifnotVal(arv, brv), nvals);
      checkVal(new orval(brv, arv), nvals); // don't technically need ors, but they are good fun
      cc += 3;
     }
    }
   }

   int bc = 0;
   foreach (List<val> bv in bvals)
    bc += bv.Count;
   goto again;
  }

  public static val[] resolveVals(string mStr, string nStr, string erStr, out int inputCount)
  {
   int ic = int.Parse(mStr);
   int oc = int.Parse(nStr);
   inputCount = ic;
   int bruteBase = 3;
   if (inputCount <= bruteBase)
    return resolveVals(ic, oc, erStr);
   else
    return resolveValFours(bruteBase, ic, oc, erStr);
  }

  public static val joinVals(val low, val high, baseVal inp, baseVal tval, baseVal fval)
  {
   val lowCut = low == fval ? (val)fval : low == tval ? (val)new ifnotVal(inp, tval) : (val)new ifnotVal(inp, low);

   val highCut = high == fval ? (val)fval : high == tval ? (val)inp : (val)new ifnotVal(new ifnotVal(inp, tval), high);

   if (highCut == fval)
    return lowCut;
   if (lowCut == fval)
    return highCut;
   return new orval(highCut, lowCut);
  }

  public static val resolveValFour(int n, int m, int inputCount, bool[] ers)
  {
   // solves fours
   int fc = ers.Length / m;
   bool[][] fours = new bool[fc][];

   for (int i = 0; i < fc; i++)
   {
    fours[i] = new bool[m];
    for (int j = 0; j < m; j++)
    {
     fours[i][j] = ers[i*m+j];
    }
   }

   baseVal[] inputs;
   val[] fres = resolve(n, m, fours, out inputs);
   baseVal tval = inputs[inputs.Length - 1];
   baseVal fval = inputs[inputs.Length - 2];

   for (int i = 0; i < n; i++)
   {
    inputs[i].id += inputCount - n;
   }

   // assemble
   for (int i = 0, c = 1; c < fc; c *= 2, i++)
   {
    for (int j = 0; j + c < fc; j += c * 2)
    {
     fres[j] = joinVals(fres[j], fres[j+c], new baseVal((inputCount - n - 1) - i), tval, fval);
    }
   }

   return fres[0];
  }

  public static val[] resolveValFours(int n, int inputCount, int outputCount, string erStr)
  {
   int m = 1;
   for (int i = 0; i < n; i++)
    m *= 2;

   val[] res = new val[outputCount];

   string[] data = erStr.Split(',');
   for (int i = 0; i < outputCount; i++)
   {
    bool[] ers = new bool[data.Length];
    for (int j = 0; j < data.Length; j++)
     ers[j] = data[j][i] == '1';
    res[i] = resolveValFour(n, m, inputCount, ers);
   }

   return res;
  }

  public static val[] resolveVals(int inputCount, int outputCount, string erStr)
  {
   val[] res;

   string[] data = erStr.Split(',');
   bool[][] erss = new bool[outputCount][];
   for (int i = 0; i < outputCount; i++)
   {
    bool[] ers = new bool[data.Length];
    for (int j = 0; j < data.Length; j++)
     ers[j] = data[j][i] == '1';
    erss[i] = ers;
   }

   baseVal[] inputs; // no need
   res = resolve(inputCount, data.Length, erss, out inputs);

   return res;
  }

  // organiser
  public class vnode
  {
   private static vnode[] emptyVC = new vnode[0];
   public static vnode oneVN = new vnode('1');
   public static vnode noVN = new vnode(' ');
   public static vnode flatVN = new vnode('_');
   public static vnode moveUpVN = new vnode('/');
   public static vnode moveDownVN = new vnode('\\');
   public static vnode inputVN = new vnode('I');
   public static vnode outputVN = new vnode('O');
   public static vnode swapVN = new vnode('X');
   public static vnode splitDownVN = new vnode('v');

   public int size;
   public vnode[] children;
   public char c;
   public int id = -3;

   public vnode(char cN)
   {
    c = cN;
    children = emptyVC;
    size = 1;
   }

   public vnode(val v)
   {
    biopVal bv = v as biopVal;

    if (bv != null)
    {
     children = new vnode[2];
     children[0] = new vnode(bv.a);
     children[1] = new vnode(bv.b);
     size = children[0].size + children[1].size;

     if (bv is orval)
      c = 'U';
     if (bv is ifnotVal)
      c = 'u';
    }
    else
    {
     children = emptyVC;
     size = 1;
     c = 'I';
     id = ((baseVal)v).id;
    }
   }
  }

  public class nonArray<T>
  {
   public int w = 0, h = 0;
   Dictionary<int, Dictionary<int, T>> map;

   public nonArray()
   {
    map = new Dictionary<int, Dictionary<int, T>>();
   }

   public T this[int x, int y]
   {
    get
    {
     Dictionary<int, T> yd;
     if (map.TryGetValue(x, out yd))
     {
      T v;
      if (yd.TryGetValue(y, out v))
      {
       return v;
      }
     }
     return default(T);
    }
    set
    {
     if (x >= w)
      w = x + 1;
     if (y >= h)
      h = y + 1;
     Dictionary<int, T> yd;
     if (map.TryGetValue(x, out yd))
     {
      yd[y] = value;
     }
     else
     {
      map[x] = new Dictionary<int, T>();
      map[x][y] = value;
     }
    }
   }
  }

  public static int fillOutMap(nonArray<vnode> map, vnode rn, int y, int x)
  {
   if (rn.children.Length == 0)
   {
    map[y,x] = rn;
    return 1;
   }
   else
   {
    map[y+1,x] = rn;
    for (int i = 0; i < rn.children.Length; i++)
    {

     if (i == 0)
     {
      fillOutMap(map, rn.children[i], y, x + 1);
     }

     if (i == 1)
     {
      int ex = x + rn.children[0].size;
      for (int j = 1; j < ex - x; j++)
       map[y - j + 1,ex - j] = vnode.moveUpVN;
      fillOutMap(map, rn.children[i], y, ex);
     }

     y += rn.children[i].size;
    }
   }

   return rn.size;
  }

  public static void orifnot(int inputCount, val[] vals, System.IO.TextWriter writer)
  {
   // step one - build weird tree like thing of death
   nonArray<vnode> map = new nonArray<vnode>();

   int curY = 0;
   foreach (val v in vals)
   {
    vnode vnt = new vnode(v);
    map[curY, 0] = vnode.outputVN;
    curY += fillOutMap(map, vnt, curY, 1);
   }

   // step two - build the thing to get the values to where they need to be
   // find Is
   List<int> tis = new List<int>();
   for (int y = 0; y < map.w; y++)
   {
    for (int x = map.h - 1; x >= 0; x--)
    {
     vnode vn = map[y,x];
     if (vn != null && vn.c == 'I')
     {
      tis.Add(vn.id);
      if (vn.id > -2)
      {
       for (;x < map.h; x++)
       {
        map[y,x] = vnode.flatVN;
       }
      }
      goto next;
     }
    }
    tis.Add(-2);
   next:
    continue;
   }

   // I do not like this piece of code, it can be replaced further down for the better if you get round to thinking about it
   // add unused Is
   for (int z = 0; z < inputCount; z++)
   {
    if (!tis.Contains(z))
    {
     int midx = tis.IndexOf(-2);
     if (midx != -1)
     {
      tis[midx] = z;
      map[midx,map.h-1] = vnode.noVN;
     }
     else
     {
      tis.Add(z);
      map[map.w,map.h-1] = vnode.noVN;
     }
    }
   }

   int curX = map.h;

  MORE:
   for (int y = 0; y < map.w; y++)
   {
    if (y == map.w - 1)
    {
     if (tis[y] == -2)
      map[y,curX] = vnode.noVN;
     else
      map[y,curX] = vnode.flatVN;
    }
    else
    {
     int prev = tis[y];
     int cur = tis[y + 1];

     if (cur != -2 && (prev == -2 || cur < prev))
     { // swap 'em
      map[y,curX] = vnode.noVN;
      if (prev == -2)
       map[y+1,curX] = vnode.moveDownVN;
      else
       map[y+1,curX] = vnode.swapVN;
      int temp = tis[y];
      tis[y] = tis[y + 1];
      tis[y + 1] = temp;
      y++; // skip
     }
     else
     {
      if (/*thatThingThat'sAThing*/ prev == cur && cur != -2)
      {
       map[y,curX] = vnode.noVN;
       map[y+1,curX] = vnode.splitDownVN;
       int temp = tis[y];
       tis[y+1] = -2;
       y++; // skip
      }
      else
      {
       if (prev == -2)
        map[y,curX] = vnode.noVN;
       else
        map[y,curX] = vnode.flatVN;
      }
     }
    }
   }

   // check if sorted
   for (int y = 0; y < map.w - 1; y++)
   {
    int prev = tis[y];
    int cur = tis[y + 1];

    if (cur != -2 && (prev == -2 || cur < prev))
     goto NOTSORTED;
   }

   goto WHATNOW;

  NOTSORTED:
   curX++;
   goto MORE;

  WHATNOW:

   tis.Add(-2); // this is to avoid boud checking y+2
   // so... it's sorted now, so add the splits
  morePlease:
   curX++;
   for (int y = 0; y < map.w; y++)
   {
    if (y == map.w - 1)
    {
     if (tis[y] == -2)
      map[y,curX] = vnode.noVN;
     else
      map[y,curX] = vnode.flatVN;
    }
    else
    {
     int prev = tis[y];
     int cur = tis[y + 1];
     int next = tis[y + 2];

     if (cur != -2 && prev == cur && cur != next)
     { // split
      map[y,curX] = vnode.noVN;
      map[y+1,curX] = vnode.splitDownVN;
      tis[y + 1] = -2;
      y++; // skip
     }
     else
     {
      if (prev == -2)
       map[y,curX] = vnode.noVN;
      else
       map[y,curX] = vnode.flatVN;
     }
    }
   }

   // check if collapsed
   for (int y = 0; y < map.w - 1; y++)
   {
    int prev = tis[y];
    int cur = tis[y + 1];

    if (cur != -2 && prev == cur)
     goto morePlease;
   }

   // ok... now we put in the Is and 1
   curX++;
   map[0, curX] = vnode.oneVN;
   int eyeCount = 0;
   int ly = 0;
   for (int y = 0; y < map.w; y++)
   {
    if (tis[y] > -1)
    {
     map[y, curX] = vnode.inputVN;
     eyeCount++;
     ly = y;
    }
   }

   // step three - clean up if we can
   // push back _  esq things to  _
   //           _/               /
   // this /shouldn't/ be necessary if I compact the vals properlu
   for (int y = 0; y < map.w - 1; y++)
   {
    for (int x = 1; x < map.h; x++)
    {
     if (map[y, x] != null && map[y+1, x] != null && map[y+1, x-1] != null)
     {
      char uc = map[y+1, x-1].c;
      if (map[y, x].c == '_' && map[y+1, x].c == '_'
          && (uc == 'U' || uc == 'u'))
      {
       map[y, x] = vnode.noVN;
       map[y, x-1] = vnode.flatVN;
       map[y+1, x] = map[y+1, x-1];
       map[y+1, x-1] = vnode.noVN;
      }
     }
    }
   }

   // step four - write out map
   writer.WriteLine(map.h + " " + map.w);

   for (int y = 0; y < map.w; y++)
   {
    for (int x = map.h - 1; x >= 0; x--)
    {
     vnode vn = map[y,x];
     if (vn != null)
      writer.Write(vn.c);
     else
      writer.Write(' ');
    }
    writer.WriteLine();
   }
  }

  // printer
  static string up1 = @"      /     /     /     /";
  static string input = @"                    |||||";
  static string output = @"                    |    ";
  static string flat = @"            |/  \  /|\   ";
  static string splitDown = @"|//   / /\  |\/    /     ";
  static string splitUp = @"         \  |/\ \ \/|\\  ";
  static string moveDown = @"|//     /     /    /     ";
  static string moveUp = @"         \    \   \ |\\  ";
  static string swap = @"|/  |  /\   /\   \/ |\  |";
  static string orDown = @"|/    /     |/  \  /|\   ";
  static string orUp = @"|/    /  \  |\  \   |\   ";
  static string ifnotDown = @"|/     /     -   \/ |\  |";
  static string ifnotUp = @"|/  |  /\    -   \  |\   ";

  public static void printDominoes(System.IO.TextReader reader, System.IO.TextWriter writer, bool moreverbosemaybe)
  {
   string line;
   string[] data;

   line = reader.ReadLine();
   data = line.Split(' ');
   int w = int.Parse(data[0]);
   int h = int.Parse(data[1]);

   int ox = 0;
   int oy = 0;
   int cx = 5;
   int cy = 5;

   char[,] T = new char[ox + w * cx, oy + h * (cy - 1) + 1];

   Action<int, int, string> setBlock = (int x, int y, string str) =>
   {
    for (int i = 0; i < cx; i++)
    {
     for (int j = 0; j < cy; j++)
     {
      char c = str[i + j * cx];
      if (c != ' ')
       T[ox + x * cx + i, oy + y * (cy - 1) + j] = c;
     }
    }
   };

   // read and write
   for (int j = 0; j < h; j++)
   {
    line = reader.ReadLine();
    for (int i = 0; i < w; i++)
    {
     if (line[i] != ' ')
     {
      switch (line[i])
      {
       case '1':
        setBlock(i, j, up1);
        break;
       case '_':
        setBlock(i, j, flat);
        break;
       case '^':
        setBlock(i, j, splitUp);
        break;
       case 'v':
        setBlock(i, j, splitDown);
        break;
       case '/':
        setBlock(i, j, moveUp);
        break;
       case '\\':
        setBlock(i, j, moveDown);
        break;
       case 'X':
        setBlock(i, j, swap);
        break;
       case 'U':
        setBlock(i, j, orUp);
        break;
       case 'D':
        setBlock(i, j, orDown);
        break;
       case 'u':
        setBlock(i, j, ifnotUp);
        break;
       case 'd':
        setBlock(i, j, ifnotDown);
        break;
       case 'I':
        setBlock(i, j, input);
        break;
       case 'O':
        setBlock(i, j, output);
        break;
      }
     }
    }
   }

   // end
   for (int i = 0; i < T.GetLength(0); i++)
   {
    T[i, 0] = '/';
   }

   // writeout
   w = T.GetLength(0) - cx + 1;
   h = T.GetLength(1);
   if (moreverbosemaybe)
    writer.Write(w + " " + h + " ");
   for (int j = 0; j < T.GetLength(1); j++)
   {
    for (int i = 0; i < T.GetLength(0) - cx + 1; i++)
    {
     char c = T[i, j];
     writer.Write(c == 0 ? ' ' : c);
    }
    if (!moreverbosemaybe)
     writer.WriteLine();
   }
  }
 }
}

Ein zusätzlicher Testfall:

4 1 0,0,0,1,0,0,1,1,0,0,0,1,1,1,1,1

Dies prüft, ob zwei benachbarte (nicht umschließende) Bits beide 1s sind (z. B. wahr für 0110, aber falsch für 0101 und 1001)

VisualMelon
quelle
2
Das ist schön. Jetzt brauchen wir einen Meta-Domino-Solver, der die Wahrheitstabelle aufnimmt Iund dessen Ausgaben ein neues Domino-Layout
festlegen
Ich bin verwirrt darüber, wie diese Wahrheitstabelle einen Vier-Bit-Prim-Checker darstellt. Sagt es nicht, dass 14 und 15 Primzahlen sind?
Quintopia
@quintopia hat noch einmal nachgesehen ... Sie scheinen recht zu haben, und ES IST meine Schuld, die, die Martin verwendet, ist richtig, aber ich baue den Primechecker jetzt NICHT wieder auf!
VisualMelon