Interpret a circuit diagram

Question

Your challenge is to interpret a circuit diagram, complete with logic gates.

Logic gates (you don't actually need to know what these do / are to complete this challenge):

• and gate: a
• or gate: o
• nand gate: A
• nor gate: O
• xor gate: x
• xnor gate: X
• not gate: ~

Each gate but the last one takes two inputs. Inputs are from a . in the top left and bottom left corners of the 3 by 3 square centered on the gate. For not, the input is directly to its left. Output is to a . directly to the right.

Wires are represented by -|\/.=

• - contacts two wires, one to the right, and one to the left: c-c

• | contacts two wires, one above, and one below:

  c
  |
  c
  

• / and \ work as follows:

  c        c
   \      /
    c    c
  

• . contacts every surrounding wire:

  ccc
  c.c
  ccc
  

• = is special; it connects adjacent wires across it:

  -=-
  

  connects the two wires. In the following

  \|/
  -=-
  /|\
  

  each opposite wire is connected with each other, but not the others (this is where it differs from .).

• In order for current to flow, two wires must both be connected to the other one, so in |-, current does not flow.

Example of wiring:

      .-.
     =   \
 .--. .---=---
-.   =     .--
 .--. .-------

the input is split into two wires and then split into three. In this split, the bottom wire moves to the middle, and the downwards split of the top wire appears on the bottom. Next, the top of the three wires is moved to the middle.

Sample wiring with gates:

--.
   o..~..
--.      o.---
   a.---.
--.

Input format:

• each input wire will be labeled with a digit. At the end (right before newline), each output will be labeled with : (and the wire will always go right into it, ie -: or .: or =:)
• the input will always be valid; there will be no loops or wires joining together without a gate. Note that there can be wires with loose ends.
• = will be used only when necessary.

Output format:

• each input is referenced with the corresponding number.
• an expression is outputted. For example, if the wires compute input 1 and input 2, the output is 1a2.
• whatever functions outputted must correspond to the logic gates at the beginning.
• to show not, put the ~ before the correct place.

• for multiple functions, use parentheses to show the order of execution. Parentheses can also be used when there is only a single function. For example,

  1-.~.-.
         A.~.-:
        .
  2-.  /
     x.
  3-.
  

  has one possible output of ~((2x3)A(~1))

• multiple outputs must be separated by a newline (or equivalent)

Sample input:

1--.---.
    x.  \
2--.  x.-=---------.
     .    .~.       X.--.
3---. .      a.----.   /
       O.~.-.       \ /
      .              =
4-.  /              / .-:
   X.              .----:
5-.

One possible corresponding output:

(~1)a(~(3O(4X5))
((1x2)x3)X((~1)a(~(3O(4X5))))

Answer 1

Java: 1523 1512 chars

import java.util.*;class W{int v=99;Map<Integer,String>t;boolean k;public static void main(String[]y){new W().d();}W(){try{java.io.InputStream i=new java.io.File("r").toURL().openStream();t=new HashMap<>();int a=0,x=0,y=0;while((a=i.read())>-1){if(a==10){y++;x=0;continue;}q(x,y,(a>47&a<58?"!":"")+(char)a);x++;}}catch(Exception e){}}void d(){while(!k){k=!k;for(Map.Entry<Integer,String>g:t.entrySet())e(g.getKey(),g.getValue());}for(String b:t.values())if(b.startsWith("$"))System.out.println(b.substring(1));}void e(int a,String s){if(s==null||!s.startsWith("!"))return;int x=a/v,y=a%v;s=s.substring(1);b(s,x,y,x-1,y+1);b(s,x,y,x,y+1);b(s,x,y,x+1,y+1);b(s,x,y,x-1,y);b(s,x,y,x+1,y);b(s,x,y,x-1,y-1);b(s,x,y,x,y-1);b(s,x,y,x+1,y-1);}void b(String p,int m,int n,int x,int y){String s=t.get(x*v+y);if(s==null)return;boolean g=y==n+1;boolean h=y==n-1;boolean i=x==m+1;boolean j=x==m-1;if(z(s,"-=")&n==y){if(i)b(p,x,y,x+1,y);if(j)b(p,x,y,x-1,y);}if(z(s,"|=")&m==x){if(g)b(p,x,y,x,y+1);if(h)b(p,x,y,x,y-1);}if(z(s,"/=")){if(j&g)b(p,x,y,x-1,y+1);if(i&h)b(p,x,y,x+1,y-1);}if(z(s,"\\=")){if(i&g)b(p,x,y,x+1,y+1);if(j&h)b(p,x,y,x-1,y-1);}if(z(s,".")){q(x,y,"!"+p);u();}if(z(s,"~")){q(x,y,"!~("+p+")");u();}if((s.charAt(0)=='%'&n==y-1)|(s.charAt(0)=='&'&n==y+1)){q(x,y,"!("+p+")"+s.charAt(1)+"("+s.substring(2)+")");u();}if(z(s,"OoAaXx")){q(x,y,(n==y+1?"%":"&")+s+p);u();}if(z(s,":")){q(x,y,"$"+p);u();}}void q(int x,int y,String z){t.put(x*v+y,z);}void u(){k=false;}boolean z(String s,String c){return c.indexOf(s)>-1;}}

It gives this output for the sample input:

(~(((5)X(4))O(3)))a(~(1))
((~(((5)X(4))O(3)))a(~(1)))X(((2)x(1))x(3))

In order to squeeze its size:

• It does not do any error checking, error handling or input validation, assuming that the input is always valid.
• Is limited to 99 lines of input.
• Its input file must be called just r, without any file extension in the name.
• It does not makes any effort to detect if the parenthesis are or aren't necessary. It assumes that they always are necessary, and since this assumption is false, there is a lot more parenthesis than needed, but since this does not makes it fail the spec anyway, it is no problem.
• The order of the parameters to each binary operator is in general unpredictable, as it depends on the velocity that the values are propagated and from cell scanning order. But since all the binary operators are commutative, this should be no problem.

I am sure that it should be possible to reduce it more, but just a bit.

The interpreter is implemented in the form of some sort of cellular automata. It scans the entire field setting values, repeating it as many times as needed until no changes are detected.

Here is an ungolfed version:

import java.util.*;

class Wiring {

    int maxLines = 99;
    Map<Integer, String> circuitState;
    boolean finished;

    public static void main(String[] args) {
        new Wiring().interpret();
    }

    Wiring() {

        try {
            // Always read the input from the "r" file, and do not check if it even
            // exists. BTW, the toURL() method is deprecated, but we don't care about
            // this in code-golfing.
            java.io.InputStream stream = new java.io.File("r").toURL().openStream();

            circuitState = new HashMap<>();
            int byteRead = 0, cellX = 0, cellY = 0;

            while ((byteRead = stream.read()) > -1) {

                // Check for line break;
                if (byteRead == 10) {
                    cellY++;
                    cellX = 0;
                    continue;
                }

                // Populate the circuit cell. Precede numbers with an exclamation mark.
                setCircuitCell(cellX, cellY, (byteRead >= '0' & byteRead <= '9' ? "!" : "") + (char) byteRead);
                cellX++;
        } catch (Exception e) {
        }
    }

    void interpret() {
        while (!finished) {
            finished = !finished; // i.e. finished = false;
            for (Map.Entry<Integer, String> entry : circuitState.entrySet()) {
                analyzeCell(entry.getKey(), entry.getValue());
            }
        }

        // Now print the output. To do that scan for cells marked with "$".
        for (String cell : circuitState.values()) {
            if (cell.startsWith("$")) System.out.println(cell.substring(1));
        }
    }

    void analyzeCell(int cellIndex, String cellValue) {
        // Only the cells with a value marked with "!" are worth to analyze.
        if (cellValue == null || !cellValue.startsWith("!")) return;

        // Convert the cellIndex to a bidimensional coordinate.
        int x = cellIndex / maxLines, y = cellIndex % maxLines;

        // Remove the "!".
        cellValue = cellValue.substring(1);

        // Propagate the cell value to neighbouring cells.
        propagateCellData(cellValue, x, y, x - 1, y + 1);
        propagateCellData(cellValue, x, y, x, y + 1);
        propagateCellData(cellValue, x, y, x + 1, y + 1);
        propagateCellData(cellValue, x, y, x - 1, y);
        propagateCellData(cellValue, x, y, x + 1, y);
        propagateCellData(cellValue, x, y, x - 1, y - 1);
        propagateCellData(cellValue, x, y, x, y - 1);
        propagateCellData(cellValue, x, y, x + 1, y - 1);
    }

    void propagateCellData(String cellValue, int sourceX, int sourceY, int targetX, int targetY) {
        String targetContent = circuitState.get(targetX * maxLines + targetY);

        // If the target cell does not exist, just ignore.
        if (targetContent == null) return;

        boolean targetBelowSource = targetY == sourceY + 1;
        boolean targetAboveSource = targetY == sourceY - 1;
        boolean targetRightToSource = targetX == sourceX + 1;
        boolean targetLeftToSource = targetX == sourceX - 1;

        // Propagate horizontally through wires.
        if (isStringContained(targetContent, "-=") & sourceY == targetY) {
            if (targetRightToSource) propagateCellData(cellValue, targetX, targetY, targetX + 1, targetY);
            if (targetLeftToSource) propagateCellData(cellValue, targetX, targetY, targetX - 1, targetY);
        }

        // Propagate vertically.
        if (isStringContained(targetContent, "|=") & sourceX == targetX) {
            if (targetBelowSource) propagateCellData(cellValue, targetX, targetY, targetX, targetY + 1);
            if (targetAboveSource) propagateCellData(cellValue, targetX, targetY, targetX, targetY - 1);
        }

        // Propagate in the diagonal x=-y.
        if (isStringContained(targetContent, "/=")) {
            if (targetLeftToSource & targetBelowSource) {
                propagateCellData(cellValue, targetX, targetY, targetX - 1, targetY + 1);
            }
            if (targetRightToSource & targetAboveSource) {
                propagateCellData(cellValue, targetX, targetY, targetX + 1, targetY - 1);
            }
        }

        // Propagate in the diagonal x=y.
        if (isStringContained(targetContent, "\\=")) {
            if (targetRightToSource & targetBelowSource) {
                propagateCellData(cellValue, targetX, targetY, targetX + 1, targetY + 1);
            }
            if (targetLeftToSource & targetAboveSource) {
                propagateCellData(cellValue, targetX, targetY, targetX - 1, targetY - 1);
            }
        }

        // If we got a dot, store the value there.
        // Do not forget to mark it with "!", so we can rescan it later.
        if (isStringContained(targetContent, ".")) {
            setCircuitCell(targetX, targetY, "!" + cellValue);
            markThatStateChanged();
        }

        // If we got a "~", store the inverted value there.
        // Do not forget to mark it with "!", so we can rescan it later.
        if (isStringContained(targetContent, "~")) {
            setCircuitCell(targetX, targetY, "!~(" + cellValue + ")");
            markThatStateChanged();
        }

        // If we found a binary logical port with one of the values set and
        // we can set the another value, do it. Use "%" and "&" to know which
        // one was already defined.
        // BTW, do not forget to mark it with "!", so we can rescan it later.
        if ((targetContent.charAt(0) == '%' & sourceY == targetY - 1)
                | (targetContent.charAt(0) == '&' & sourceY == targetY + 1))
        {
            setCircuitCell(targetX, targetY,
                    "!(" + cellValue + ")"
                    + targetContent.charAt(1)
                    + "(" + targetContent.substring(2) + ")");
            markThatStateChanged();
        }

        // Found a binary logical port without any value setted, so set it.
        // Use "%" and "&" to mark which one was setted.
        if (isStringContained(targetContent, "OoAaXx")) {
            setCircuitCell(targetX, targetY, (sourceY == targetY + 1 ? "%" : "&") + targetContent + cellValue);
            markThatStateChanged();
        }

        // If we found an output, store the value there.
        // Mark it with "$", so we will print it in the future.
        if (isStringContained(targetContent, ":")) {
            setCircuitCell(targetX, targetY, "$" + cellValue);
            markThatStateChanged();
        }
    }

    void setCircuitCell(int cellX, int cellY, String cellContents) {
        circuitState.put(cellX * maxLines + cellY, cellContents);
    }

    void markThatStateChanged() {
        finished = false;
    }

    boolean isStringContained(String searchingString, String searchTarget) {
        return searchTarget.indexOf(searchingString) > -1;
    }
}

Answer 2

Python 2488 1567 806 706 697 657 653

Yay for gzip + exec!

import zlib,base64;exec zlib.decompress(base64.b64decode('eNp1U8FuqzAQvPMV7sm2gBSuuFupX9BLD5UoBxNMMAkEgQmJVPXb364Daiu9ntaznt2dWYzthvPo2HSbgsrU7E3so0FmAWtgnyeFshjSImC2Zs1Tws4js/fQPMPJ9KKTlFrPeVPIbDRuHnvOA3YByuS2UCNwrloYqOMRQ1ooDY0qwaoKRJxGSZRKP+QCwBn/0YRyzPYcYq77irUATVbGcIytGkN4E7mOyiLayx/MT888AthMx9DGDTLj/zIfPz44emUGqC/Zoio1UdFzohzFp0TNNA7xQhFxDWJiNGNG98L54yLVYUsv3+kZx9G8/uyEoQFk8NELrDeIIggf5Cb3b3/I3nnFNdZe0QOrCHl4+4ZsgVyH16gMb4XHq4IrwA0gkV7kAwyZH7Fs7f0S/O7IbnZX7jelzy+v13f8LsAFD0kVfrQyTklZyCUPL+F2Ef66WHug7i9f/bWyfnOIsrNTZQ/WCXxCcAnY/QmwMeggLwIyeCKD+FB3k6tsj/K6nR4G01fiZCcnTlIGBkw/d2bUzvgSG2kqMvhOkU+ZNirvGS1XgyWKy/xS2TDa3uE/kNuoJX0UC/kP8j/kmA=='))

---

Limitations and assumptions

As it is, only up to 9 inputs are supported - multiple digits are not handled correctly. As the spec indicates that inputs are labelled with a digit, not a number, this is allowed.

---

Input and output

Input is taken via standard in, and output is via standard out.

---

Testing

Sample input and output:

1--.---.
    x.  \
2--.  x.-=---------.
     .    .~.       X.--.
3---. .      a.----.   /
       O.~.-.       \ /
      .              =
4-.  /              / .-:
   X.              .----:
5-.

(~(1))a(~((3)O((4)X(5))))
(((1)x(2))x(3))X((~(1))a(~((3)O((4)X(5)))))

Tested here: http://ideone.com/gP4CIq

---

The algorithm

It's basically a rather naive DFS from the outputs. For each output, it starts from the character one to its left and traces the wire, branching (and adding to the expression) at every gate. When it reaches an input, it adds it to the expression and backtracks to the last point it branched, since we can be sure that branching is not possible without a gate. And of course any invalid cases are discarded. Nothing really special to it - and therefore it's likely longer than it could have been.

---

Notes

Size could probably be reduced a fair bit with some restructuring, but I've spent enough time on this for today. The manually golfed version was the one compressed.

The gzip compression makes golfing interesting, because certain caching (e.g. d=(-1,0,1)) actually takes more space than letting the compression algorithm take care of it. However, I opted to golf the manual version as far as possible rather than optimising for compression.

---

Manually golfed (909 895 840 803):

import sys
def T(c,p):
 h=c[0];i=c[1]
 if h<0 or i<0 or h>=len(m)or i>=len(m[h]):return''
 v=m[h][i];r='';j=p[0];k=p[1];a=h;b=i;d=(-1,0,1)
 if v==' ':return''
 if v in'=-'and j==h:b-=k-i;r+=T([a,b],c)
 if v in'=|'and k==i:a-=j-h;r+-T([a,b],c)
 if v in'=/\\':
  e=j==h or k==i;s=j-h>0;t=j-h<0;u=k-i>0;w=k-i<0;f=(s and u)or(t and w);g=(s and w)or(t and u)
  if not(e or v=='/'and f or v=='\\'and g):a-=j-h;b-=k-i;r+=T([a,b],c)
 if v=='.':
  for x in d:
   for y in d:
    w=[a+x,b+y]
    if not(x==y==0)and w!=p:r+=T(w,c)
 if j==h and k-i>0:
  if v in'aoAOxX':r='('+T([a-1,b-1],c)+')'+v+'('+T([a+1,b-1],c)+')'
  if v=='~':r='~('+T([a,b-1],c)+')'
 if v.isdigit():r=v
 return r
m=[]
for l in sys.stdin:
 m.append(list(l))
e=enumerate
for i,a in e(m):
 for j,b in e(a):
  if b==':':
   print T([i,j-1],[i,j])

Full ungolfed (2488):

import sys

def findOuts(c):
    for i, iVal in enumerate(c):
        for j, jVal in enumerate(iVal):
            if jVal == ':':
                yield [i, j]

def trace(pos, prev):
    if pos[0] < 0 or pos[1] < 0 or pos[0] >= len(circuit) or pos[1] >= len(circuit[pos[0]]):
        return ''
    val = circuit[pos[0]][pos[1]]
    if val == ' ':
        return ''
    next = pos[:]
    ret = ''
    if val in '=-':
        if prev[0] == pos[0]:
            next[1] -= prev[1] - pos[1]
            ret += trace(next, pos)
    if val in '=|':
        if prev[1] == pos[1]:
            next[0] -= prev[0] - pos[0]
            ret += trace(next, pos)
    if val in '=/\\':
        # top-bottom, left-right
        tblr = prev[0] == pos[0] or prev[1] == pos[1]
        # top-left, bottom-right
        tlbr = (prev[0] - pos[0] == 1 and prev[1] - pos[1] == 1) or (prev[0] - pos[0] == -1 and prev[1] - pos[1] == -1)
        # top-right, bottom-left
        trbl = (prev[0] - pos[0] == 1 and prev[1] - pos[1] == -1) or (prev[0] - pos[0] == -1 and prev[1] - pos[1] == 1)
        if not ((val == '/' and (tlbr or tblr)) or (val == '\\' and (trbl or tblr)) or (val == '=' and tblr)):
            next[0] -= prev[0] - pos[0]
            next[1] -= prev[1] - pos[1]
            ret += trace(next, pos)

    if val == '.':
        for x in (-1,0,1):
            for y in (-1,0,1):
                if x == y == 0:
                    continue

                w = [next[0] + x, next[1] + y]
                if w == prev:
                    continue

                # only one of them should return anything
                ret += trace(w, pos)

    # assumption that a logic gate always has a . on its connections, as according to spec
    if val in 'aoAOxX':
        # only from the right/output
        if not (prev[0] == pos[0] and prev[1] == pos[1] + 1):
            return ret
        ret = '(' + trace([next[0] - 1, next[1] - 1], pos) + ')' + val + '(' + trace([next[0] + 1, next[1] - 1], pos) + ')'

    if val == '~':
        # only from the right/output
        if not (prev[0] == pos[0] and prev[1] == pos[1] + 1):
            return ret
        ret = '~(' + trace([next[0], next[1] - 1], pos) + ')'

    if val in '123456789':
        ret = val

    return ret

circuit = []
for line in sys.stdin.readlines():
    # padding added to prevent index out of bounds later
    circuit.append(list(line))

for out in findOuts(circuit):
    next = out[:]
    next[1] -= 1
    print trace(next, out)