Домино Схемы

Табло

Вот приблизительные оценки (то есть количество домино) для представления VisualMelon. Я превращу их в нормализованные оценки, описанные ниже, когда придет больше ответов. Существующее решение теперь может решить все схемы в тесте:

 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

Соревнование

Это является возможным строить простые логические ворота от домино. Следовательно, комбинируя эти или иные, произвольные двоичные функции могут быть вычислены с помощью домино.

Но, конечно же, каждый, кто играл с домино (кроме Робина Пола Вейерса), испытывал разочарование, когда заканчивал их. Следовательно, мы хотим максимально эффективно использовать наши домино, чтобы мы могли сделать некоторые действительно интересные вычисления с имеющимся у нас материалом.

Обратите внимание, что вы не можете производить ненулевой вывод из нулевого ввода как такового, поэтому нам нужно добавить «линию питания», которая идет по вашей настройке и из которой вы можете получить 1s в любое время.

Твое задание

Учитывая булеву функцию с Mвходами и Nвыходами ( f: {0,1}^M --> {0,1}^Nдля математически наклонных), создайте схему домино с как можно меньшим количеством домино, которое вычисляет эту функцию. Вы будете использовать символы |, -, /, \представлять домино в различных направлениях.

вход

Вы получите ввод через аргументы командной строки:

[command for your solver] M N f

где Mи N- положительные целые числа и fтаблица истинности, разделенная запятыми, в каноническом порядке. То есть fбудут содержать 2^Mзначения длины N. Например, если M = N = 2и первый бит на выходе был функцией И, а второй бит был функцией ИЛИ, fчитал бы

00,01,01,11

Выход

Запишите в STDOUT сетку ASCII, представляющую установку домино. Ваша установка должна вписываться в следующую структуру

/////.../////
 ????...????
I????...????O
I????...????O
.............
.............
I????...????O
I????...????O
I????...????O

• Верхний ряд целиком состоит из /самого нижнего домино, который гарантированно будет опрокинут в самом начале - это ваша линия электропередачи.
• Крайний левый столбец состоит из ваших входных данных. Каждый Iможет быть либо пробелом, либо a |, таким, что есть ровно M |s.
• Крайний правый столбец состоит из ваших выводов. Каждый Oможет быть либо пробелом, либо a |, таким, что есть ровно N |s.
• Обратите внимание, что перед |входом или выходом есть хотя бы один пробел перед первым .
• Это .указывает на то, что сетка может быть сколь угодно большой.
• Вы можете заполнить ?любым способом.

Обратите внимание, что нижний вход является самым быстро меняющимся, пока вы идете по таблице истинности, в то время как верхний вход - 0для первой половины выходов и 1для второй половины.

правила

Домино размножается, как указано в разделе «Гольф для дня домино» . Короче говоря, если мы представляем падающие направления в виде букв

Q W E
A   D
Z X C

тогда это все уникальные комбинации, которые могут распространяться (а также их вращения и отражения):

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

C|   ->    CD          C/   ->    CC

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

Все вышеперечисленные правила применяются одновременно на каждом временном шаге. Если два из этих правил находятся в конфликте (т. Е. Плитка перемещается в два действительных противоположных направления одновременно), затронутая плитка не упадет и будет эффективно заблокирована в положении для остальной части симуляции.

ограничения

• Mи Nникогда не будет превышать 6.
• Ваш решатель должен создать цепь в течение N * 2 ^M секунд .
• Ваш решатель не должен использовать более 1 ГБ памяти . Это мягкий предел, так как я буду следить за этим вручную и уничтожать ваш процесс, если он значительно / постоянно превышает этот предел.
• Ни одна цепь не может содержать более 8 000 000 ячеек или 1 000 000 домино .
• Ваше представление должно быть детерминированным . Вам разрешено использовать генераторы псевдослучайных чисел, но они должны использовать жестко закодированное начальное число (которое вы можете оптимизировать столько, сколько захотите).

счет

Для каждого контура, пусть Dбудет общее количество домино в вашем контуре и Bнаименьшее количество домино, с которым этот контур был решен (вами или любым другим участником). Тогда ваш счет для этой схемы определяется 10,000 * B / Dокруглением в меньшую сторону. Если вам не удалось решить схему, ваша оценка равна 0. Ваша общая оценка будет суммой по сравнению с набором контрольных тестов. Схемы, которые еще никто не решал, не будут включены в общий счет.

Каждый участник может добавить один контрольный пример в тест (и все другие материалы будут переоценены, включая этот новый контрольный пример).

Файл эталонных тестов можно найти на GitHub .

Примеры

Вот несколько неоптимально решенных примеров.

Постоянная 1

1 1
1,1

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

Количество домино: 12

ИЛИ ворота

2 1
0,1,1,1

///////////

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

Количество домино: 28

И ворота

2 1
0,0,0,1

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

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

Количество домино: 62

Поменять полосы

2 2
00,10,01,11

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

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

Количество домино: 36

Дополнительные замечания

Правила распространения таковы, что диагональные полосы могут пересекаться с использованием ромбовидной формы (см. Последний пример), даже если одна из них падает раньше другой (в отличие от реальных домино).

В качестве отправной точки вы можете использовать (не минимизированные) логические элементы в этой сущности и попытаться объединить как можно меньше из них. Для простого (неоптимального) способа построения произвольных логических функций из вентилей AND, OR и NOT взгляните на конъюнктивные и дизъюнктивные нормальные формы.

В этом репозитории GitHub имеется верификатор для проверки вашего кода, который также будет использоваться для оценки всех представленных материалов. Это выводит необработанные оценки (количество домино) и сохраняет их в файл для обработки отдельным счетчиком (также в этом хранилище) для получения окончательных результатов.

Общая документация может быть найдена в двух файлах Ruby, но она controller.rbзанимает два параметра командной строки перед файлом теста:

• -v дает вам больше выходных данных, включая фактические схемы, созданные вашим решателем.
• -cпозволяет вам выбрать подмножество тестов, которые вы хотите протестировать. Укажите нужные схемы в виде списка разделенных запятыми индексов на основе 1. Вы также можете использовать диапазоны Ruby, чтобы вы могли сделать что-то вроде -c 1..5,10,15..20.

Пожалуйста, включите в свой ответ:

• Ваш код
• Команда (скомпилировать и) запустить ваш код. Я спрошу вас, где взять необходимые компиляторы / интерпретаторы, если у меня их нет.
• Дополнительная таблица истинности с именем, которая будет добавлена ​​в качестве контрольного примера к тесту. (Это необязательно, но настоятельно рекомендуется.)

Я буду тестировать все материалы на Windows 8.

C # - Массивное, медленное и неэффективное решение

Исповедь: написал это решение некоторое время назад, когда вопрос был еще в песочнице, но это не очень хорошо: вы можете сделать лучше!

Изменить: заменить скучное решение на менее скучный, более гибкий и в целом лучший метод

Вы запускаете программу, компилируя, csc dominoPrinter.csа затем передавая аргументы в исполняемый файл, например (4-битная простейшая проверка):

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

Объяснение:

«Domino Printer» - это трехступенчатая программа:

Этап 1 : «решатель» генерирует дерево выражений «ifnot» и «или» бинарных операций с заданными входами и «1» от линии электропередачи, есть 2 способа сделать это, в зависимости от количества входов:

• Если входов меньше, чем 4, программа обрабатывает наименьшее количество операций.

• Если имеется 4 или более входных данных, программа обрабатывает каждый 8-битный блок вывода, а затем объединяет результаты, чтобы получить желаемый результат. Гибкие биты, если они гибкие: чем больше битов, тем меньше решение, но тем дольше время выполнения.

«Решатель» - это то, что занимает все время (или, по крайней мере, раньше), а также большую часть кода. Я полагаю, что есть хорошо документированное, быстрое, не очень требовательное к памяти и, возможно, оптимальное решение этой проблемы, но где было бы весело искать ее?

(Bruted) дерево выражений для 4-битной простой проверки

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

где числа являются индексами входов.

Этап 2 : «Организатор» принимает дерево выражений в качестве входных данных и собирает «скелетный» макет, который точно описывает макет домино, сделанный из некоторого набора перекрывающихся ячеек 4x5. Ниже приведен скелет для 4-битной простой проверки на основе bruted (вам нужно изменить bruteBaseцелочисленную переменную в строке 473 на 4 (или больше), чтобы получить этот результат).

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 

Этот вывод фактически состоит из двух частей: «оценщик» справа, который создается из дерева выражений на этапе 1, и «коммутатор» слева, который меняет местами входы и разделяет их так, чтобы они поступали в правильные места для "оценщика" для обработки.

На данный момент существует много возможностей для сжатия макета, но в настоящее время программа выполняет очень мало такой работы. Код для этого этапа ужасен, но довольно прост (см. Метод «orifnot»). Выходной сигнал передается на этап 3.

Этап 3 : «Принтер» принимает выходные данные «органайзера» и печатает соответствующие перекрывающиеся «ячейки» 4x5 вместе с линией питания. Ниже приведена анимация проверки 4-битного простого критерия, проверяющего, является ли 5 ​​простым числом.

Кодируйте отсутствие отступов, чтобы избежать превышения предела SE 30k символов, который в противном случае был бы :

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

Дополнительный контрольный пример:

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

Это проверяет, являются ли два смежных (без переноса) биты равными 1 (например, true для 0110, но false для 0101 и 1001)