Obwody Domino

36

Tablica wyników

Oto surowe wyniki (tj. Liczby domino) dla przesłania VisualMelon. Zamienię je w znormalizowane wyniki opisane poniżej, gdy pojawi się więcej odpowiedzi. Istniejące rozwiązanie może teraz rozwiązać wszystkie obwody w teście:

 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

Wyzwanie

To jest możliwe budowanie prostych bramek logicznych z domino. Stąd, łącząc te lub w inny sposób, dowolne funkcje binarne można obliczyć za pomocą domina.

Ale oczywiście każdy, kto grał w domino (z wyjątkiem Robina Paula Weijers) doświadczył rozczarowania, gdy ich zabrakło. Dlatego chcemy korzystać z naszych domino tak wydajnie, jak to możliwe, abyśmy mogli wykonać naprawdę interesujące obliczenia z posiadanego materiału.

Zauważ, że nie możesz wytworzyć niezerowego wyjścia z zerowego wejścia per se, więc będziemy musieli dodać „linię zasilania”, która biegnie wzdłuż twojej konfiguracji i z której możesz wyciągnąć 1s w dowolnym momencie.

Twoje zadanie

Biorąc pod uwagę funkcję boolowską z Mwejściami i Nwyjściami ( f: {0,1}^M --> {0,1}^Ndla nachylenia matematycznego), stwórz obwód domina z możliwie najmniejszą liczbą domino, który oblicza tę funkcję. Będziesz za pomocą symboli |, -, /, \do reprezentowania w domino w różnych orientacjach.

Wkład

Otrzymasz dane za pomocą argumentów wiersza poleceń:

[command for your solver] M N f

gdzie Mi Nsą dodatnimi liczbami całkowitymi i fjest tabelą prawdy oddzieloną przecinkami w porządku kanonicznym. Oznacza to, że fbędzie zawierać 2^Mwartości długości N. Np. Gdyby M = N = 2i pierwszy bit na wyjściu był funkcją AND, podczas gdy drugi bit był funkcją OR, fodczytałby się

00,01,01,11

Wydajność

Napisz do STDOUT siatkę ASCII reprezentującą konfigurację domina. Twoja konfiguracja musi mieścić się w następujących ramach

/////.../////
 ????...????
I????...????O
I????...????O
.............
.............
I????...????O
I????...????O
I????...????O
  • Górny rząd składa się całkowicie z /, a na lewo domino z pewnością zostanie przewrócone na początku - to twoja linia energetyczna.
  • Lewa kolumna zawiera twoje dane wejściowe. Każda Imoże być spacją lub a |, tak że istnieją dokładnie M |s.
  • Prawa kolumna składa się z twoich wyników. Każda Omoże być spacją lub a |, tak że istnieją dokładnie N |s.
  • Zauważ, że przed pierwszym |wejściem lub wyjściem jest co najmniej jeden pusty .
  • .Wskazują, że siatka może być dowolnie duża.
  • Możesz wypełnić ?w dowolny sposób.

Zauważ, że dolne dane wejściowe zmieniają się najszybciej podczas przeglądania tabeli prawdy, podczas gdy górne dane wejściowe dotyczą 0pierwszej połowy danych wyjściowych i 1drugiej połowy.

Zasady

Domino rozprzestrzeniają się, jak określono w Golfing for Domino Day . Krótko mówiąc, jeśli przedstawiamy spadające kierunki jako litery

Q W E
A   D
Z X C

to są wszystkie unikalne kombinacje, które mogą się rozprzestrzeniać (jak również ich rotacje i odbicia):

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

C|   ->    CD          C/   ->    CC

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

Wszystkie powyższe zasady są stosowane jednocześnie na każdym etapie. Jeśli dwie z tych reguł są w konflikcie (tj. Płytka jest jednocześnie popychana w dwóch ważnych przeciwnych kierunkach), dotknięta płytka nie spadnie i zostanie skutecznie zablokowana na pozostałą część symulacji.

Ograniczenia

  • Mi Nnigdy nie przekroczy 6.
  • Twój solver musi wytworzyć obwód w ciągu N * 2 M sekund .
  • Twój solver nie może zużywać więcej niż 1 GB pamięci . To jest miękki limit, ponieważ będę go monitorował ręcznie i zabiję twój proces, jeśli znacznie / stale przekroczy ten limit.
  • Żaden obwód nie może zawierać więcej niż 8 000 000 komórek lub 1 000 000 domino .
  • Twoje zgłoszenie musi być deterministyczne . Dozwolone jest używanie generatorów liczb pseudolosowych, ale muszą one używać zakodowanego ziarna (które można dowolnie optymalizować).

Punktacja

Dla każdego obwodu niech Dbędzie łączna liczba domino w twoim obwodzie i Bnajniższa liczba domino z tym obwodem została rozwiązana (przez ciebie lub innego uczestnika). Następnie twój wynik dla tego obwodu jest 10,000 * B / Dzaokrąglany w dół. Jeśli nie udało Ci się rozwiązać obwodu, twój wynik wynosi 0. Twój ogólny wynik będzie sumą ponad zestaw testów przypadków. Obwody, które nie zostały jeszcze rozwiązane przez nikogo, nie zostaną uwzględnione w całkowitej punktacji.

Każdy uczestnik może dodać jeden przypadek testowy do testu porównawczego (a wszystkie pozostałe zgłoszenia zostaną ponownie ocenione, w tym nowy przypadek testowy).

Plik testu porównawczego można znaleźć na GitHub .

Przykłady

Oto kilka nieoptymalnie rozwiązanych przykładów.

Stała 1

1 1
1,1

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

Liczba domino: 12

LUB brama

2 1
0,1,1,1

///////////

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

Liczba domino: 28

I brama

2 1
0,0,0,1

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

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

Liczba domino: 62

Zamień pasy

2 2
00,10,01,11

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

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

Liczba domino: 36

Dodatkowe uwagi

Reguły propagacji są takie, że linie ukośne mogą się krzyżować przy użyciu rombu (patrz ostatni przykład), nawet jeśli jeden z nich upada przed sobą (w przeciwieństwie do prawdziwych domino).

Na początek możesz użyć (nie zminimalizowanych) bramek logicznych w tej siatce i spróbować połączyć ich jak najmniej. Przez proste (non-optymalny) sposób budowania dowolnych funkcji logicznych z AND, OR i NOT bram, rzucić okiem na koniunkcyjnej i dysjunktywny Normal Form.

W repozytorium GitHub znajduje się weryfikator do testowania kodu, który będzie również używany do oceny wszystkich zgłoszeń. To generuje surowe wyniki (liczba domino) i zapisuje je w pliku do przetworzenia przez osobnego strzelca (także w tym repozytorium) w celu uzyskania ostatecznych wyników.

Dokumentacja ogólna znajduje się w dwóch plikach Ruby, ale controller.rbzajmuje dwa przełączniki wiersza poleceń przed plikiem testu:

  • -v daje ci więcej mocy wyjściowej, w tym rzeczywiste obwody produkowane przez twój solver.
  • -cpozwala wybrać podzbiór testu, który chcesz przetestować. Podaj żądane obwody jako listę oddzielonych przecinkami indeksów 1. Możesz także użyć zakresów Rubiego, abyś mógł zrobić coś takiego -c 1..5,10,15..20.

Podaj w swojej odpowiedzi:

  • Twój kod
  • Polecenie (skompiluj i) uruchom kod. Zapytam cię, gdzie uzyskać niezbędne kompilatory / tłumacze, jeśli ich nie mam.
  • Dodatkowa tabela prawdy z nazwą, która zostanie dodana jako przypadek testowy do testu porównawczego. (Jest to opcjonalne, ale zdecydowanie zalecane).

Będę testować wszystkie zgłoszenia w systemie Windows 8.

Martin Ender
źródło
Wszystko pchane w tym samym czasie?
l4m2
@ l4m2 Tak, wejścia w lewej kolumnie są obalane jednocześnie.
Martin Ender

Odpowiedzi:

33

C # - rozwiązanie masywne, powolne i nieefektywne

Spowiedź: napisałem to rozwiązanie jakiś czas temu, gdy pytanie wciąż było w piaskownicy, ale nie jest zbyt dobre: możesz zrobić lepiej!

Edycja: zastąpiono nudne rozwiązanie mniej nudną, bardziej elastyczną i ogólnie lepszą metodą

Uruchamiasz program, kompilując zi csc dominoPrinter.csprzekazując argumenty do pliku wykonywalnego, na przykład (4-bitowy moduł sprawdzający liczbę pierwszą):

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

Wyjaśnienie:

„Drukarka Domino” to 3-etapowy program:

Etap 1 : „Solver” generuje drzewo wyrażeń „ifnot” i „lub” operacji binarnych z podanymi danymi wejściowymi, a „1” z linii energetycznej, są 2 sposoby, w zależności od liczby danych wejściowych:

  • Jeśli jest mniej niż 4 wejścia, program rozwiązuje problem najmniejszej liczby operacji

  • Jeśli są 4 lub więcej wejść, program przerywa każdy 8-bitowy fragment wyjścia, a następnie łączy wyniki w celu uzyskania pożądanego wyjścia. Brutalne bity, jeśli są elastyczne: im więcej brutalnych bitów, tym mniejsze rozwiązanie, ale dłuższy czas pracy.

„Solver” zajmuje cały czas (a przynajmniej kiedyś), a także stanowi większość kodu. Uważam, że istnieje dobrze udokumentowane, szybkie, mało wymagające pamięci i prawdopodobnie optymalne rozwiązanie tego problemu, ale gdzie byłoby zabawę w szukaniu go?

Drzewo wyrażeń (brute) dla 4-bitowego sprawdzania liczb pierwszych jest

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

gdzie liczby są indeksami danych wejściowych.

Etap 2 : „Organizator” pobiera drzewo wyrażeń jako dane wejściowe i składa układ „szkieletu”, który dokładnie opisuje układ domina wykonany z zestawu nakładających się komórek 4x5. Poniżej znajduje się szkielet brutalnego 4-bitowego sprawdzania liczb pierwszych (musisz zmienić bruteBasezmienną całkowitą w linii 473 na 4 (lub większą), aby uzyskać ten wynik).

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 

Dane wyjściowe składają się skutecznie z dwóch części: „ewaluatora” po prawej stronie, który jest tworzony z drzewa wyrażeń ze stopnia 1, oraz „tablicy rozdzielczej” po lewej stronie, która zamienia i dzieli dane wejściowe, tak aby dotarły do właściwe miejsca dla „oceniającego” do obsługi.

W tym momencie istnieje spore pole do kompaktowania układu, ale program wykonuje obecnie bardzo niewiele takich prac. Kod tego etapu jest okropny, ale pod nim dość prosty (patrz metoda „orifnot”). Dane wyjściowe są przekazywane do etapu 3.

Etap 3 : „Drukarka” pobiera dane wyjściowe z „organizera” i drukuje odpowiednie nakładające się na siebie „komórki” 4x5 wraz z linią energetyczną. Poniżej znajduje się animacja brutalnego 4-bitowego sprawdzania liczb pierwszych sprawdzającego, czy 5 jest liczbą pierwszą.

Najwyraźniej 5 jest liczbą pierwszą

Kod braku wcięcia ma na celu uniknięcie przekroczenia limitu znaków SE 30k, który w innym przypadku :

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();
   }
  }
 }
}

Dodatkowy przypadek testowy:

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

To sprawdza, czy dwa sąsiednie (nie zawijające) bity są jednocześnie 1 (np. Prawda dla 0110, ale fałsz dla 0101 i 1001)

VisualMelon
źródło
2
To jest piękne. Teraz potrzebujemy meta solvera domina, który bierze tabelę prawdy Ii której wyniki określają nowy układ domina
wrongu
Jestem zdezorientowany co do tego, jak ta tabela prawdy reprezentuje czterobitowy moduł sprawdzający. Czy nie jest powiedziane, że 14 i 15 są liczbą pierwszą?
kwintopia
@ quintopia po ponownym spojrzeniu ... wydaje się, że masz rację, a JA to moja wina, ta, której używa Martin, jest poprawna, ale NIE od teraz odbudowuję tego sprawdzania!
VisualMelon,