12
\$\begingroup\$

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))))
\$\endgroup\$
12
  • \$\begingroup\$ Oooohhhh, interesting! I'll give it a shot. \$\endgroup\$
    – cjfaure
    Feb 1 '14 at 7:45
  • 5
    \$\begingroup\$ I am foreseeign an interesting exolang coming out of this, if we extend it in a way to make it Turing-complete. \$\endgroup\$ Feb 1 '14 at 8:25
  • \$\begingroup\$ In case of a "compiler error" (i.e. malformed input wiring) what should the interpreter do? \$\endgroup\$ Feb 1 '14 at 8:43
  • \$\begingroup\$ And, if I connect directly two inputs? Or connect directly two outputs? Or input open lines to the output? \$\endgroup\$ Feb 1 '14 at 8:50
  • 1
    \$\begingroup\$ @Victor This is already similar. But I went ahead and created another one \$\endgroup\$
    – Justin
    Feb 2 '14 at 9:41
6
\$\begingroup\$

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;
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Tiny bit cheaper to use try{}catch(Exception e){} rather than two throws Exception. There's probably other things, but I have no idea how to golf Java. \$\endgroup\$
    – Bob
    Feb 3 '14 at 4:48
  • \$\begingroup\$ @Bob Thanks, your suggestion made me reduce it 7 characters. Also, I could reduce further 4 more. \$\endgroup\$ Feb 3 '14 at 13:01
4
\$\begingroup\$

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)
\$\endgroup\$
7
  • \$\begingroup\$ What is DFS? Also, working backwards from the output is exactly what I was thinking of. \$\endgroup\$
    – Justin
    Feb 2 '14 at 16:17
  • \$\begingroup\$ @Quincunx Depth-first-search. Basically, recursion (or otherwise using a LIFO construct, a stack) and travelling as far as possible along a path until it hits a dead end or the goal, at which point it returns to the last point of divergence and tries the other paths. \$\endgroup\$
    – Bob
    Feb 2 '14 at 16:23
  • \$\begingroup\$ Good assumption on the inputs. That is exactly what I meant (and I tried to word it to suggest that). However, does your program work with 0 as a digit? How about swapped ordering so that 2 comes before 1, etc. \$\endgroup\$
    – Justin
    Feb 10 '14 at 19:13
  • \$\begingroup\$ @Quincunx I'm using Python's .isdigit(), which is effectively equivalent to the regex [0-9] as far as I can tell. Is that correct according to your spec? What do you mean by swapped ordering? The way it's implemented, it'll head on the upwards branch of any logic gate first, but there's no guarantee of ordering of inputs. \$\endgroup\$
    – Bob
    Feb 10 '14 at 22:29
  • \$\begingroup\$ isdigit() is consistent. Swapped ordering means something like 2 as the first input, and 1 as the second input (sorted vertically). \$\endgroup\$
    – Justin
    Feb 11 '14 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.