Domino Circuits

Question

Scoreboard

Here are the raw scores (i.e. domino counts) for VisualMelon's submission. I'll turn these into the normalised scores described below, when more answers come in. The existing solution can now solve all circuits in the benchmark:

 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

The Challenge

It is possible to build simple logic gates from dominoes. Hence, by combining these or otherwise, arbitrary binary functions can be computed with dominoes.

But of course, everyone who has played with dominoes (except Robin Paul Weijers) has experienced the disappointment when running out of them. Hence, we want to use our dominoes as efficiently as possible, so we can do some really interesting computations with the material we have.

Note, that you cannot produce non-zero output from zero input per se, so we'll need to add a "power line", which falls along your setup, and which you can pull 1s from at any time.

Your task

Given a boolean function with M inputs and N outputs (f: {0,1}^M --> {0,1}^N for the mathematically inclined), produce a domino circuit with as few dominoes as possible which computes that function. You'll be using the symbols |, -, /, \ to represent dominoes in various orientations.

Input

You'll be given input via command-line arguments:

[command for your solver] M N f

where M and N are positive integers and f is the comma separated truth table in canonical order. That is, f will contain 2^M values of length N. E.g. if M = N = 2 and the first bit in the output was the AND function while the second bit was the OR function, f would read

00,01,01,11

Output

Write to STDOUT an ASCII grid representing the domino setup. Your setup has to fit in the following framework

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

• The top row consists entirely of /, and the leftmost domino is guaranteed to be toppled over at the beginning - this is your power line.
• The leftmost column consists of your inputs. Each I may either be a space or a |, such that there are exactly M |s.
• The rightmost column consists of your outputs. Each O may either be a space or a |, such that there are exactly N |s.
• Note that there is at least one blank before the first | in the input or output.
• The . indicate that the grid can be arbitrarily large.
• You can fill ? in any way you want.

Note that the bottom input is the fastest-varying while you go along the truth table, while the top input is the 0 for the first half of the outputs and 1 for the second half.

Rules

Dominoes propagate as specified in Golfing for Domino Day. In short, if we represent the falling directions as letters

Q W E
A   D
Z X C

then these are all unique combinations which can propagate (as well as their rotations and reflections):

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

C|   ->    CD          C/   ->    CC

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

All of the above rules are applied simultaneously at each time step. If two of those rules are in conflict (i.e. a tile is pushed into two valid opposite directions at the same time), the affected tile will not fall, and will effectively be locked into position for the rest of the simulation.

Restrictions

• M and N will never exceed 6.
• Your solver must produce a circuit within N * 2^M seconds.
• Your solver must not use more than 1 GB of memory. This is a soft limit, as I will be monitoring this manually and kill your process if it significantly/continuously exceeds this limit.
• No circuit is permitted to contain more than 8,000,000 cells or 1,000,000 dominoes.
• Your submission must be deterministic. You are allowed to use pseudo-random number generators, but they must use a hardcoded seed (which you are free to optimise as much as you care to).

Scoring

For each circuit, let D be total number of dominoes in your circuit and B the lowest number of dominoes this circuit has been solved with (by you or any other participant). Then your score for this circuit is given by 10,000 * B / D rounded down. If you failed to solve the circuit, your score is 0. Your overall score will be the sum over a benchmark set of test cases. Circuits that have not yet been solved by anyone will not be included in the total score.

Each participant may add one test case to the benchmark (and all other submissions will be re-evaluated including that new test case).

The benchmark file can be found on GitHub.

Examples

Here are some non-optimally solved examples.

Constant 1

1 1
1,1

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

Domino count: 12

OR gate

2 1
0,1,1,1

///////////

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

Domino count: 28

AND gate

2 1
0,0,0,1

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

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

Domino count: 62

Swap lanes

2 2
00,10,01,11

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

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

Domino count: 36

Additional Notes

The propagation rules are such, that diagonal lanes can cross using a diamond shape (see last example) even if one falls before the other (unlike with real dominoes).

As a starting point, you can use the (not minimised) logical gates in this gist and try combining as few of these as possible. For a simple (non-optimal) way to build arbitrary boolean functions from AND, OR and NOT gates, have a look at Conjunctive and Disjunctive Normal Forms.

There is a verifier this GitHub repository to test your code, which will also be used to score all submissions. This outputs the raw scores (domino counts) and saves them to a file to be processed by a separate scorer (also in that repository) to obtain the final scores.

General documentation can be found within the two Ruby files, but the controller.rb takes two command line switches before the benchmark file:

• -v gives you some more output, including the actual circuits produced by your solver.
• -c lets you select a subset of the benchmark you want to test. Provide the desired circuits as a comma-separated list of 1-based indices. You can also use Ruby ranges, so you could do something like -c 1..5,10,15..20.

Please include in your answer:

• Your code
• A command to (compile and) run your code. I'll ask you where to obtain the necessary compilers/interpreters if I don't have them.
• An additional truth table with a name, to be added as a test case to the benchmark. (This is optional, but strongly encouraged.)

I'll be testing all submissions on Windows 8.

Answer 1

C# - Massive, Slow, and inefficient solution

Confession: wrote this solution some time ago when the question was still in the sandbox, but it's not very good: you can do better!

Edit: replaced the boring solving with a less boring, more flexible, and generally better method

You run the program by compiling with csc dominoPrinter.cs and then passing arguments to the executable, for example (the 4-bit prime checker):

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

Explanation:

The "Domino Printer" is a 3-stage program:

Stage 1: The "solver" generates an expression tree of "ifnot" and "or" binary operations with the given inputs, and a "1" from the powerline, there are 2ways this is done, depending on the number of inputs:

• If there are fewer than 4 inputs the program brutes a solution of the fewest number of operations

• If there are 4 or more inputs the program brutes each 8bit chunk of output and then combines the results to give the desired output. The bruted bits if flexible: the more bruted bits, the smaller the solution, but the longer the run-time.

The "solver" is what takes all the time (or at least it used to), and is also most of the code. I believe there is a well documented, fast, not so memory hungry, and probably optimal solution to this problem, but where would the fun be in looking it up?

The (bruted) expression tree for the 4-bit prime checker is

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

where the numbers are the indexes of the inputs.

Stage 2: The "organizer" takes the expression tree as input and assembles a "skeleton" layout, which precisely describes a domino layout made from some a set of 4x5 overlapping cells. Below is the skeleton for the bruted 4-bit prime checker (you'll need to change the bruteBase integer variable on line 473 to 4 (or larger) to get this result).

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 

This output is effectively made up to two parts, the "evaluator" on the right, which is created from the expression tree from stage 1, and the "switchboard" on the left, which swaps and splits the inputs so that they arrive in the right places for the "evaluator" to handle.

There is considerable scope for compacting the layout at this point, but the program currently does very little such work. The code for this stage is horrible, but pretty simple underneath (see the "orifnot" method). The output is passed to stage 3.

Stage 3: The "printer" takes the output from the "organizer" and prints the corresponding 4x5 overlapping "cells" along with the power line. Below is an animation of the bruted 4-bit prime checker checking whether 5 is prime.

Code the lack of indenting is to avoid going over the SE 30k character limit which it would otherwise:

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

An additional test case:

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

This checks whether two adjacent (non-wrapping) bits are both 1s (e.g. true for 0110, but false for 0101 and 1001)