Interpret a circuit diagram 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))))
Java: 1523 1512 chars

import java.util.*;class W{int v=99;Map&lt;Integer,String&gt;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&lt;&gt;();int a=0,x=0,y=0;while((a=i.read())&gt;-1){if(a==10){y++;x=0;continue;}q(x,y,(a&gt;47&amp;a&lt;58?"!":"")+(char)a);x++;}}catch(Exception e){}}void d(){while(!k){k=!k;for(Map.Entry&lt;Integer,String&gt;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,"-=")&amp;n==y){if(i)b(p,x,y,x+1,y);if(j)b(p,x,y,x-1,y);}if(z(s,"|=")&amp;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&amp;g)b(p,x,y,x-1,y+1);if(i&amp;h)b(p,x,y,x+1,y-1);}if(z(s,"\\=")){if(i&amp;g)b(p,x,y,x+1,y+1);if(j&amp;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)=='%'&amp;n==y-1)|(s.charAt(0)=='&amp;'&amp;n==y+1)){q(x,y,"!("+p+")"+s.charAt(1)+"("+s.substring(2)+")");u();}if(z(s,"OoAaXx")){q(x,y,(n==y+1?"%":"&amp;")+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)&gt;-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&lt;Integer, String&gt; 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&lt;&gt;();
            int byteRead = 0, cellX = 0, cellY = 0;

            while ((byteRead = stream.read()) &gt; -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 &gt;= '0' &amp; byteRead &lt;= '9' ? "!" : "") + (char) byteRead);
                cellX++;
        } catch (Exception e) {
        }
    }

    void interpret() {
        while (!finished) {
            finished = !finished; // i.e. finished = false;
            for (Map.Entry&lt;Integer, String&gt; 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, "-=") &amp; 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, "|=") &amp; 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 &amp; targetBelowSource) {
                propagateCellData(cellValue, targetX, targetY, targetX - 1, targetY + 1);
            }
            if (targetRightToSource &amp; targetAboveSource) {
                propagateCellData(cellValue, targetX, targetY, targetX + 1, targetY - 1);
            }
        }

        // Propagate in the diagonal x=y.
        if (isStringContained(targetContent, "\\=")) {
            if (targetRightToSource &amp; targetBelowSource) {
                propagateCellData(cellValue, targetX, targetY, targetX + 1, targetY + 1);
            }
            if (targetLeftToSource &amp; 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 "&amp;" 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) == '%' &amp; sourceY == targetY - 1)
                | (targetContent.charAt(0) == '&amp;' &amp; 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 "&amp;" to mark which one was setted.
        if (isStringContained(targetContent, "OoAaXx")) {
            setCircuitCell(targetX, targetY, (sourceY == targetY + 1 ? "%" : "&amp;") + 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) &gt; -1;
    }
}