Grid Based Digital Logic (Duodyadic Tiles)

Question

Duodyadic tiles are kinds of square function blocks that take two inputs, one from their top side and one from their left side, and have two outputs, one on their right side and one on their bottom side. Each of their outputs is a separate function of both of their inputs.

For example, if # represents a generic tile, the right output R is a function f of inputs T and L, and the bottom output B is another function g of T and L:

 T
L#R         R = f(T, L)
 B          B = g(T, L)

^{(The tiles are termed "duo" since there are two functions, and "dyadic" since both functions have two arguments.)}

Tiles can then be composed together on a grid, the outputs of one tile going directly into the inputs of the tiles it neighbors. Here for example, the right output of the left # goes into the left input of the right #:

 AB         D = f(f(A, C), B)
C##D        E = g(A, C)
 EF         F = g(f(A, C), B)

You can imagine that given a set of duodyadic tiles, each with specific functionality, complex (and potentially useful) compositions could be made.

In this challenge, we'll only be concerned with the traditional set of ten logic based duodyadic tiles, where all the inputs and outputs are single-bit binary numbers (zeros or ones). We'll use a separate ASCII character to denote each type of tile.

The tile characters and their input-output relations are as follows:
(T is for top input, L for left input, R for right output, B for bottom output.)

1. Zero: 0 or (space) → R = 0, B = 0
2. One: 1 → R = 1, B = 1
3. Cross: + → R = L, B = T
4. Mirror: \ → R = T, B = L
5. Top only: U → R = T, B = T
6. Left only: ) → R = L, B = L
7. Not: ! → R = not L, B = not T
8. And: & → R = L and T, B = L and T
9. Or: | → R = L or T, B = L or T
10. Xor: ^ → R = L xor T, B = L xor T

Challenge

Write a program or function that takes in a rectangular grid of the characters 0 1+\U)!&|^ that represents a "circuit" made using the ten logic based duodyadic tiles. You also need to take in two strings of 0's and 1's; one will be the left input column and one will be the top input row. Your program/function needs to print/return the bottom output row and the right output column (also in 0's and 1's).

For example, in this grid

+++
+++

all the inputs flow straight across the grid to the outputs

 ABC
D+++D
E+++E
 ABC

so an input of 010/01 would have output 010/01:

 010
0+++0
1+++1
 010

The exact output of your program would be [bottom output row]\n[right output column] or [bottom output row]/[right output column]:

010
01

or

010/01

If you wrote a function, you could return the two strings in a tuple or list (or still print them).

Details

• Take the three inputs as strings in any reasonable manner (preferably in the order grid, top row, left column): command line, text file, sdtin, function arg.
• You can assume the input row and column lengths will match the grid dimensions and will only contain 0's and 1's.
• Your grid must use the proper characters (0 1+\U)!&|^). Remember that 0 and mean the same thing.

Test Cases

(Read I/O as top/left → bottom/right.)

Nand:

&!

00/0 → 01/1
00/1 → 01/1
10/0 → 01/1
10/1 → 11/0

All ones:

1111
1\+\
1+\+
1\+\

Any input should result in 1111/1111.

Xor from Nand: (note the column of trailing spaces)

\)+\ 
U&!& 
+! ! 
\&!& 
   ! 

00000/00000 → 00000/00000
00000/10000 → 00010/00000
10000/00000 → 00010/00000
10000/10000 → 00000/00000

Zig zag:

+++\00000000
000\!!!!\000
00000000\+++

The first bit of the left input becomes the last bit of the right output. Everything else is 0.

000000000000/000 → 000000000000/000
000000000000/100 → 000000000000/001

Propagation:

)))
UUU
U+U
U+U
UUU

The first bit of the left input goes to all the outputs.

000/00000 → 000/00000
000/10000 → 111/11111

Here's a pastebin of all 1×1 grid test cases.

Scoring

The shortest submission in bytes wins.

Bonus: What cool "circuits" can you make?

^{P.S. Don't bother Googling "duodyadic tiles". I made them up yesterday ;D
If you want to discuss expanding this idea into a full-fledged programming language, come to this chatroom.}

Answer 1

Pyth, 122

Kind of a monster. Uses simply recursion, nothing fancy like dynamic programming.

D:NGHR@Cm+d[1HG&GH|GHxGH0),[GH!G)[HG!H)x"+\\!1U)&|^"N#aYw)M:@@YGH?hgGtHHv@eYG?egtGHGv@ePYHjkm+0egtleYklePYjkm+0hgbtlePYleY

Online demonstration.

Input is in the following way: First the grid (no escaping, no extra symbols) and then the two lines of input, e.g. (Zig zag)

+++\00000000
000\!!!!\000
00000000\+++
000000000000
100

Answer 2

Mathematica, 331 276 270 267 264 262 252 250 bytes

Print@@@{#[[2;;,-1,2]],#[[-1,2;;,1]]}&@MapIndexed[h=Characters;({r@#2,b@#2}=<|##|>&@@Thread[h@"0 1+\\)U!&|^"->{0,0,1,i={##},{#2,#},##,1-i,1##,Max@i,(#-#2)^2}]&[r[#2-{1,0}],b[#2-{0,1}]]@#{1,1})&,Join[h@{"0"<>#3},h@StringSplit[#2<>"
"<>#,"
"]],{2}]&

The  is a private-use Unicode character which Mathematica uses as a superscript T, i.e. it's the transposition operator.

Here is a more readable version:

Print @@@ {#[[2 ;;, -1, 2]], #[[-1, 2 ;;, 1]]} &@
  MapIndexed[h = Characters;
   (
     {r@#2, b@#2} = <|##|> & @@ Thread[
            h@"0 1+\\)U!&|^" -> {
              0,
              0,
              1,
              i = {##},
              {#2, #},
              ##,
              1 - i,
              1 ##,
              Max@i,
              (# - #2)^2
              }] & [
          r[#2 - {1, 0}],
          b[#2 - {0, 1}]
          ] @ # {1, 1}
     ) &,
   Join[
    h@{"0" <> #3},
    h@StringSplit[#2 <> "\n" <> #, "\n"]\[Transpose]
   ],
   {2}] &

This is an unnamed function which takes the three strings for grid, top and left inputs and prints the bottom and right outputs.

Explanation

Let's go through this step by step (I'll try not to assume any Mathematica knowledge). You sort of need to read the code back to front. The basic algorithm just sweeps through the lines computing each function and storing the results in f to be accessed by subsequent tiles.

Input processing

That's this bit:

Join[
  h@{"0" <> #3},
  h@StringSplit[#2 <> "\n" <> #, "\n"]\[Transpose]
]

This merely splits the grid into a nested list of characters (note that I defined h as an alias for Character somewhere in the code) and then prepends a row and a column with the inputs. This works, because 1 and 0 are also the names of the constant-function tiles, so actually putting them on the has the same effect as feeding the inputs in manually. Since these are functions they will technically take their input from outside the grid, but since they are constant functions that doesn't matter. The top left corner gets a 0 but this is fairly arbitrary since the results of that tile are never used.

Also note the transposition. Adding columns takes more characters than adding rows, so I transpose the grid after adding the top row. This means that top/bottom and left/right are swapped for the main part of the program, but they're completely exchangeable so it doesn't matter. I just need to make sure to return the results in the correct order.

Solving the grid

(This section is slightly outdated. Will fix once I'm really sure I'm done golfing.)

Next up, we run MapIndexed over the inner level of this nested list. This calls the anonymous function provided as the first argument for each character in the grid, also giving it a list with the current two coordinates. The grid is traversed in order, so we can safely calculate each cell based on the previous ones.

We use the variables r(ight) and b(ottom) as lookup tables for the results of each cell. Our anonymous function has the current coordinates in #2, so we get the inputs to any cell with

r[#2 - {1, 0}],
b[#2 - {0, 1}]

Note that in the first row and column this will access undefined values of r and b. Mathematica doesn't really have a problem with that and will just give you back your coordinates instead, but we discard this result anyway, since all tiles in that row/column are constant functions.

Now this thing:

<|##|> & @@ Thread[
  h@"0 1+\\U)!&|^" -> {
     z = {0, 0}, z, o = 1 + z, {##}, ...
  }] &

Is a golfed form of

<|"0" -> (z = {0, 0}), " " -> z, "1" -> (o = 1 + z), "+" -> {##}, ... |> &

Which in turn is a function which, given the two tile inputs, returns an Association (you'd call it a hashmap or a table in other languages), that contains all the possible tile results for these two inputs. To understand, how all the functions are implemented, you need to know that the first argument of such a function can be accessed with # and the second with #2. Furthermore, ## gives you a sequence of both arguments which can be used to "splat" the arguments.

• 0: is straightforward, we just return a constant {0, 0} and also assign this to z for future use (e.g. in the space tile).
• 1: is essentially just {1,1}, but having z this is shortened to 1+z. We also save this in o, because it'll come in handy for all the tiles where both outputs are identical.
• +: Here we make use of the sequence. {##} is the same as {#,#2} and passes both inputs through unchanged.
• \: We swap the two arguments, {#2,#}.
• U: Now we can make use of o. o#2 means {1,1}*#2 so we just put the top argument into both outputs.
• ): Analogously for the left argument: o#.
• !: Bitwise not is annoying in Mathematica, but since we only ever have 0 and 1, we can simply subtract both inputs from 1 (thereby inverting them) and pass them on: 1-{##}.
• &: This one is quite nifty. First we notice that bitwise and for 0 and 1 is identical to multiplication. Furthermore, o## is the same as o*#*#2.
• |: Again, we use an equivalent function. Bitwise or is the same as Max in this case, so we apply Max to the input arguments and multiply the result into {1,1}.
• ^: The shortest I've found for xor is to take the difference and square it (to ensure positivity), so we've got o(#-#2)^2.

After this function completes and returns the full association we use the current cell's character to pull out the element we're interested in and store it in r and b. Note that this is also the return value of the anonymous function used in MapIndexed, so the mapping will actually give me a grid of all the results.

Output processing

MapIndexed returns a 3D grid, where the first dimension corresponds to the horizontal grid coordinate (remember the earlier transposition), the second dimension corresponds to the vertical grid coordinate and the third indicates whether we've got a bottom or a left output. Note that this also contains the input row and column which we need to get rid of. So we access the bottom row's bottom output with

#[[2;;,-1,2]]

and the final column's right output with

#[[-1,2;;,1]]

Note that 2;; is a range from the second to the last element.

Lastly, we apply Print to both of those (using @@@ as the syntactic sugar for second-level Apply), which just prints all of its arguments back-to-back (and since it's applied to two separate expressions, there will be a newline between bottom and right output).

Answer 3

C, 332 309 272 270 266 259 247 225 bytes

#define C(x)*c-x?
i,k,T,L,m;f(c,t,l)char*c,*t,*l;{while(L=l[i]){for(k=0;T=t[k];c++)L=C(49)C(43)C(92)C(85)C(41)C(33)C(38)C('|')C(94)T=48:(T^=L-48):(T|=L):(T&=L):(T^=1,L^1):(T=L):T:(m=T,T=L,m):L:(T=49),t[k++]=T;c++;l[i++]=L;}}

View results online here!

This defines a function void f(char*, char*, char*), which should take the board as its first input, then the top row of input, and then the left row of input.

Here's what I used to test it:

#include "stdio.h"
int main() {
    char buf[1024],top[33],left[33];
    /* Copy and paste an example circuit as the first input,
       and put a 'Q' immediately after it. 
       Note that the Q is never touched by the function f, and is used
       solely as a delimiter for input. */
    scanf("%[^Q]Q ",buf);
    /* Then enter your top inputs */
    scanf("%[01]%*[^01]", top);
    /* Then your left ones */
    scanf("%[01]", left);
    /* OUTPUT: Bottom\nRight */
    f(buf, top, left);
    return 0;
}

Thus, by inputting Sp3000's 2-bit multiplier:

UUUU))))
UU++)))&
UUU+)  U
UU++&))U
U++&+)^U
U)&\&)UU
   U+^UU
   \&UUUQ
11110000
00000000

We get:

00001001
11111111

On another note, with Sp3000's half adder in mind, I'd like to see a full adder... One of you guys did it! I don't think the system stands on its own as a programming language, but it's been very interesting. This seems like an excellent target for metagolf, though!

A Short Explanation:

Here's the unraveled, commented code:

/* We define the first half of the ?: conditional operator because, well,
   it appears over and over again. */
#define C(x)*c-x?
/* i,k are counting variables
   T,L are *current* top and left inputs */
i,k,T,L,m;
f(c,t,l)char*c,*t,*l;{
    /* The outer loop iterates from top to bottom over l and c */
    while(L=l[i]){
        /* Inner loop iterates from left to right over t and c */
        for(k=0;T=t[k];c++)
            /* This line looks awful, but it's just a bunch of character
            comparisons, and sets T and L to the output of the current c */
            L=C(49)C(43)C(92)C(85)C(41)C(33)C(38)C('|')C(94)T=48:(T^=L-48):(T|=L):(T&=L):(T^=1,L^1):(T=L):T:(m=T,T=L,m):L:(T=49),
            /* Write our output to our input, it will be used for the next row */
            t[k++]=T;
        c++; /*Absorbs the newline at the end of every row */
        /* Keep track of our right-most outputs, 
        and store them in the handy string passed to the function. */
        l[i++]=L;
    }
    /* Bottom output is now stored entirely in t, as is right output in l */        
}

We iterate over c, left to right (then top to bottom), rewriting the t inputs each time and pushing out a right-most output which is shoved into the l string. We can imagine this as replacing the top row of c with 1's and 0's iteratively, and keeping track of the bits that are pushed out at the right.

Here's a more visual sequence, row by row:

 111                                  
1&+^  =>  110 ->0  =>     ->0  =>     0 Thus, "01" has been written to l,
1+&+     1+&+         110 ->1         1
                                  110   And "110" is stored currently in t.

This obviously gets more complicated with different symbols and sizes, but the central idea holds. This works only because data never flows up or left.

Answer 4

Python 2, 316 bytes

This function builds 10 tile lambda functions, then iterates though the grid, updating logic states. The final vertical and horizontal logic states are then printed.

def b(d,j,g):
 h=enumerate;e=dict((s[0],eval('lambda T,L:('+s[1:]+')'))for s in' 0,0#00,0#11,1#+L,T#\\T,L#UT,T#)L,L#!1-L,1-T#&T&L,T&L#|T|L,T|L#^T^L,T^L'.split('#'));j=list(j+'\n');g=list(g)
 for y,k in h(d.split('\n')):
  L=g[y]
  for x,c in h(k):T=j[x];L,B=e[c](int(T),int(L));j[x]=`B`
  g[y]=`L`
 print''.join(j+g)

The ungolfed code including tests:

def logic(grid, top, left):
    loop = enumerate;
    func = dict((s[0], eval('lambda T,L:('+s[1:]+')')) for s in ' 0,0#00,0#11,1#+L,T#\\T,L#UT,T#)L,L#!1-L,1-T#&T&L,T&L#|T|L,T|L#^T^L,T^L'.split('#'));
    top = list(top+'\n');
    left = list(left)
    for y,row in loop(grid.split('\n')):
        L = left[y]
        for x,cell in loop(row) :
            T = top[x];
            L, B = func[cell](int(T), int(L));
            top[x] = `B`
        left[y] = `L`
    print ''.join(top + left)

import re
testset = open('test.txt', 'rt').read().strip()
for test in testset.split('\n\n'):
    if test.endswith(':'):
        print '------------------\n'+test
    elif re.match('^[01/\n]+$', test, re.S):
        for run in test.split():
            top, left = run.split('/')
            print 'test', top, left
            logic(grid, top, left)
    else:
        grid = test

The test.txt file (including 2 other tests by Sp3000):

Nand:

&!

00/0
00/1
10/0
10/1

All ones:

1111
1\+\
1+\+
1\+\

1001/1100

Xor from Nand (note the column of trailing spaces):

\)+\ 
U&!& 
+! ! 
\&!& 
   ! 

00000/00000
00000/10000
10000/00000
10000/10000

Half adder:

+))
U&+
U+^

000/000
000/100
100/000
100/100

Right shift:

\\\
\++
\++

001/110
010/101
101/100

The test output:

------------------
Nand:
test 00 0
01
1
test 00 1
01
1
test 10 0
01
1
test 10 1
11
0
------------------
All ones:
test 1001 1100
1111
1111
------------------
Xor from Nand (note the column of trailing spaces):
test 00000 00000
00000
00000
test 00000 10000
00010
00000
test 10000 00000
00010
00000
test 10000 10000
00000
00000
------------------
Half adder:
test 000 000
000
000
test 000 100
001
101
test 100 000
101
001
test 100 100
110
110
------------------
Right shift:
test 001 110
000
111
test 010 101
101
010
test 101 100
010
110

Answer 5

Python 2, 384 338 325 bytes

def f(G,T,L):
 def g(x,y):
  if x>-1<y:l=g(x-1,y)[1];t=g(x,y-1)[0];r=l,t,1-l,0,0,1,t,l,l&t,l|t,l^t;i="+\\!0 1U)&|^".index(G[y*-~W+x]);return((t,l,1-t)+r[3:])[i],r[i]
  return(int((y<0)*T[x]or L[y]),)*2
 H=G.count("\n")+1;W=len(G)/H;return eval('"".join(map(str,[g(%s]for _ in range(%s)])),'*2%('_,H-1)[0','W','W-1,_)[1','H'))

Seriously CH, if this isn't a toy already you should start ringing up some toy factories.

More golfed and much less efficient now, but still haven't caught up to CarpetPython. Input like f("1111\n1\\+\\\n1+\\+\n1\\+\\","0101","1010"), output is a tuple of two strings. Make sure the board doesn't have a trailing newline though, which will break things.

Test program

def f(G,T,L):
 def g(x,y):
  if x>-1<y:l=g(x-1,y)[1];t=g(x,y-1)[0];r=l,t,1-l,0,0,1,t,l,l&t,l|t,l^t;i="+\\!0 1U)&|^".index(G[y*-~W+x]);return((t,l,1-t)+r[3:])[i],r[i]
  return(int((y<0)*T[x]or L[y]),)*2
 H=G.count("\n")+1;W=len(G)/H;return eval('"".join(map(str,[g(%s]for _ in range(%s)])),'*2%('_,H-1)[0','W','W-1,_)[1','H'))
                              
   
import itertools

G = r"""
+))
U&+
U+^
""".strip("\n")

def test(T, L):
    print f(G, T, L)

def test_all():
    W = len(G[0])
    H = len(G)

    for T in itertools.product([0, 1], repeat=len(G.split("\n")[0])):
        T = "".join(map(str, T))

        for L in itertools.product([0, 1], repeat=len(G.split("\n"))):
            L = "".join(map(str, L))

            print "[T = %s; L = %s]" % (T, L)
            test(T, L)
            print ""

test("000", "000")
test("000", "100")
test("100", "000")
test("100", "100")

You can also test all possible cases with test_all().

Extra test cases

Half adder

Here's a half adder which adds the top left bits, outputting <input bit> <carry> <sum>:

+))
U&+
U+^

Tests:

000 / 000  ->  000 / 000
000 / 100  ->  001 / 101
100 / 000  ->  101 / 001
100 / 100  ->  110 / 110

Output should be the same even if the second/third bits of the inputs are changed.

Right shift

Given abc / def, this outputs fab / cde:

\\\
\++
\++

Tests:

001 / 110 -> 000 / 111
010 / 101 -> 101 / 010
101 / 100 -> 010 / 110

3-bit sorter

Sorts the first three bits of top into the last three bits of bottom. Right output is junk.

UUU)))
UU)U U
U&UU U
U+|&)U
\UU++|
 \)&UU
  \+|U
   UUU

Tests:

000000 / 00000000 -> 000000 / 00000000
001000 / 00000000 -> 000001 / 11111111
010000 / 00000000 -> 000001 / 00001111
011000 / 00000000 -> 000011 / 11111111
100000 / 00000000 -> 000001 / 00001111
101000 / 00000000 -> 000011 / 11111111
110000 / 00000000 -> 000011 / 00001111
111000 / 00000000 -> 000111 / 11111111

2-bit by 2-bit multiplier

Takes the 1st/2nd bits of top as the first number, and the 3rd/4th bits of top as the second number. Outputs to the last four bits of bottom. Right output is junk.

UUUU))))
UU++)))&
UUU+)  U
UU++&))U
U++&+)^U
U)&\&)UU
   U+^UU
   \&UUU

Edit: Golfed out a column and two rows.

Tests:

00000000 / 00000000 -> 00000000 / 00000000
00010000 / 00000000 -> 00000000 / 10000000
00100000 / 00000000 -> 00000000 / 00000000
00110000 / 00000000 -> 00000000 / 10000000
01000000 / 00000000 -> 00000000 / 00000000
01010000 / 00000000 -> 00000001 / 11111111
01100000 / 00000000 -> 00000010 / 00000000
01110000 / 00000000 -> 00000011 / 11111111
10000000 / 00000000 -> 00000000 / 00000000
10010000 / 00000000 -> 00000010 / 10000000
10100000 / 00000000 -> 00000100 / 00000000
10110000 / 00000000 -> 00000110 / 10000000
11000000 / 00000000 -> 00000000 / 00000000
11010000 / 00000000 -> 00000011 / 11111111
11100000 / 00000000 -> 00000110 / 00000000
11110000 / 00000000 -> 00001001 / 11111111

Answer 6

R, 524 517

Probably lots of room to reduce this at the moment, but this has been really interesting to do. There are two functions. Function d is the worker and f is the comparer.

The function d is called with 3 strings, Gates, Top and Left. The Gates are put into a matrix determined by the width.

I=strtoi;S=strsplit;m=matrix;f=function(L,T,G){O=I(c(0,1,L,T,!L,!T,L&T,L|T,xor(L,T)));X=which(S(' 01+\\U)!&|^','')[[1]]==G);M=m(c(1,1,1,2,1,1,3,2,2,4,3,4,5,4,3,6,4,4,7,3,3,8,5,6,9,7,7,10,8,8,11,9,9),nrow=3);return(c(O[M[2,X]],O[M[3,X]]))};d=function(G,U,L){W=nchar(U);H=nchar(L);U=c(list(I(S(U,'')[[1]])),rep(NA,H));L=c(list(I(S(L,'')[[1]])),rep(NA,W));G=m((S(G,'')[[1]]),nrow=W);for(i in 1:H)for(n in 1:W){X=f(L[[n]][i],U[[i]][n],G[n,i]);L[[n+1]][i]=X[1];U[[i+1]][n]=X[2]};cat(U[[H+1]],' / ',L[[W+1]],sep='',fill=T)}

Formatted a bit

I=strtoi;S=strsplit;m=matrix;
f=function(L,T,G){
    O=I(c(0,1,L,T,!L,!T,L&T,L|T,xor(L,T)));
    X=which(S(' 01+\\U)!&|^','')[[1]]==G);
    M=m(c(1,1,1,2,1,1,3,2,2,4,3,4,5,4,3,6,4,4,7,3,3,8,5,6,9,7,7,10,8,8,11,9,9),nrow=3);
    return(c(O[M[2,X]],O[M[3,X]]))
};
d=function(G,U,L){
    W=nchar(U);H=nchar(L);
    U=c(list(I(S(U,'')[[1]])),rep(NA,H));
    L=c(list(I(S(L,'')[[1]])),rep(NA,W));
    G=m((S(G,'')[[1]]),nrow=W);
    for(i in 1:H)
        for(n in 1:W){
            X=f(L[[n]][i],U[[i]][n],G[n,i]);
            L[[n+1]][i]=X[1];
            U[[i+1]][n]=X[2]
        };
    cat(U[[H+1]],' / ',L[[W+1]],sep='',fill=T)
}

Some tests

> d('&!','00','0')
01 / 1
> d('&!','00','1')
01 / 1
> d('&!','10','0')
01 / 1
> d('&!','10','1')
11 / 0
> d('\\)+\\ U&!& +! ! \\&!&    ! ','00000','00000')
00000 / 00000
> d('\\)+\\ U&!& +! ! \\&!&    ! ','00000','10000')
00010 / 00000
> d('\\)+\\ U&!& +! ! \\&!&    ! ','10000','00000')
00010 / 00000
> d('\\)+\\ U&!& +! ! \\&!&    ! ','10000','10000')
00000 / 00000
> d('+++\\00000000000\\!!!!\\00000000000\\+++','000000000000','100')
000000000000 / 001
> d('+++\\00000000000\\!!!!\\00000000000\\+++','000000000000','000')
000000000000 / 000
> d('+))U&+U+^','000','000')
000 / 000
> d('+))U&+U+^','000','100')
001 / 101
> d('+))U&+U+^','100','000')
101 / 001
> d('+))U&+U+^','100','100')
110 / 110