Su desafío es interpretar un diagrama de circuito, completo con puertas lógicas.

Puertas lógicas (en realidad no necesita saber qué hacen / son para completar este desafío):

• y puerta: a
• o puerta: o
• puerta nand: A
• ni puerta: O
• puerta xor: x
• puerta xnor: X
• no puerta: ~

Cada puerta pero la última toma dos entradas. Las entradas provienen de a .en las esquinas superior izquierda e inferior izquierda del cuadrado de 3 por 3 centrado en la puerta. Para no, la entrada está directamente a su izquierda. La salida es a .directamente a la derecha.

Los cables están representados por -|\/.=

• - contacta dos cables, uno a la derecha y otro a la izquierda: c-c

• | contacta dos cables, uno arriba y otro abajo:

  c
  |
  c
  

• /y \trabajar de la siguiente manera:

  c        c
   \      /
    c    c
  

• . contacta cada cable circundante:

  ccc
  c.c
  ccc
  

• =es especial; conecta cables adyacentes a través de él:

  -=-
  

  conecta los dos cables En el siguiente

  \|/
  -=-
  /|\
  

  cada cable opuesto está conectado entre sí, pero no con los demás (aquí es donde difiere .).

• Para que la corriente fluya, dos cables deben estar conectados al otro, por lo tanto |-, la corriente no fluye.

Ejemplo de cableado:

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

la entrada se divide en dos cables y luego se divide en tres. En esta división, el cable inferior se mueve hacia el centro, y la división hacia abajo del cable superior aparece en la parte inferior. A continuación, la parte superior de los tres cables se mueve hacia el centro.

Ejemplo de cableado con puertas:

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

Formato de entrada:

• cada cable de entrada se etiquetará con un dígito. Al final (justo antes de salto de línea), cada salida será etiquetado con :(y el cable siempre irá derecho en él, es decir, -:o .:o =:)
• la entrada siempre será válida; No habrá bucles ni cables que se unan sin una puerta. Tenga en cuenta que puede haber cables con extremos sueltos.
• = se usará solo cuando sea necesario.

Formato de salida:

• cada entrada se referencia con el número correspondiente.
• Se emite una expresión. Por ejemplo, si los cables calculan la entrada 1 y la entrada 2, la salida es 1a2.
• cualesquiera funciones que se generen deben corresponder a las puertas lógicas al principio.
• para mostrar no, ponga el ~antes del lugar correcto.

• para múltiples funciones, use paréntesis para mostrar el orden de ejecución. Los paréntesis también se pueden usar cuando hay una sola función. Por ejemplo,

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

  tiene una salida posible de ~((2x3)A(~1))

• las salidas múltiples deben estar separadas por una nueva línea (o equivalente)

Entrada de muestra:

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

Una posible salida correspondiente:

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

Python 2488 1567 806 706 697 657 653

Yay para 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=='))

Limitaciones y suposiciones.

Tal como está, solo se admiten hasta 9 entradas: varios dígitos no se manejan correctamente. Como la especificación indica que las entradas están etiquetadas con un dígito , no un número , esto está permitido.

Entrada y salida

La entrada se toma a través de la entrada estándar y la salida se realiza a través de la salida estándar.

Pruebas

Muestra de entrada y salida:

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)))))

Probado aquí: http://ideone.com/gP4CIq

El algoritmo

Es básicamente un DFS bastante ingenuo de las salidas. Para cada salida, comienza desde el carácter uno a su izquierda y traza el cable, bifurcando (y agregando a la expresión) en cada puerta. Cuando llega a una entrada, la agrega a la expresión y retrocede hasta el último punto en el que se bifurcó, ya que podemos estar seguros de que la bifurcación no es posible sin una puerta. Y, por supuesto, se descartan todos los casos no válidos. Nada realmente especial, y por lo tanto es probable que sea más largo de lo que podría haber sido.

Notas

El tamaño probablemente podría reducirse un poco con cierta reestructuración, pero he dedicado suficiente tiempo a esto por hoy. La versión de golf manual fue la comprimida.

La compresión gzip hace que el golf sea interesante, porque cierto almacenamiento en caché (por ejemplo d=(-1,0,1)) en realidad ocupa más espacio que dejar que el algoritmo de compresión se encargue de ello. Sin embargo, opté por jugar al golf la versión manual en la medida de lo posible en lugar de optimizar la compresión.

Golf manual ( 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])

Completo sin golf (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)

Java: 1523 1512 caracteres

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

Da esta salida para la entrada de muestra:

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

Para exprimir su tamaño:

• No realiza ninguna comprobación de errores, manejo de errores o validación de entrada, suponiendo que la entrada siempre sea válida.
• Está limitado a 99 líneas de entrada.
• Su archivo de entrada debe llamarse solo r, sin ninguna extensión de archivo en el nombre.
• No hace ningún esfuerzo para detectar si los paréntesis son o no necesarios. Se supone que siempre son necesarios, y dado que esta suposición es falsa, hay muchos más paréntesis de los necesarios, pero dado que esto no hace que falle la especificación de todos modos, no hay problema.
• El orden de los parámetros para cada operador binario es en general impredecible, ya que depende de la velocidad a la que se propagan los valores y del orden de exploración de la celda. Pero como todos los operadores binarios son conmutativos, esto no debería ser un problema.

Estoy seguro de que debería ser posible reducirlo más, pero solo un poco.

El intérprete se implementa en forma de algún tipo de autómata celular. Escanea todos los valores de configuración del campo, repitiéndolo tantas veces como sea necesario hasta que no se detecten cambios.

Aquí hay una versión sin golf:

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