Menafsirkan diagram sirkuit

12

Tantangan Anda adalah menafsirkan diagram sirkuit, lengkap dengan gerbang logika.

Gerbang logika (Anda sebenarnya tidak perlu tahu apa yang harus dilakukan untuk menyelesaikan tantangan ini):

  • dan gerbang: a
  • atau gerbang: o
  • gerbang nand: A
  • atau gerbang: O
  • gerbang xor: x
  • gerbang xnor: X
  • bukan gerbang: ~

Setiap gerbang tetapi yang terakhir membutuhkan dua input. Input berasal dari .di sudut kiri atas dan kiri bawah dari 3 oleh 3 persegi yang berpusat di gerbang. Karena tidak, input langsung ke kiri. Output adalah .langsung ke kanan.

Kabel diwakili oleh -|\/.=

  • - kontak dua kabel, satu ke kanan, dan satu ke kiri: c-c
  • | kontak dua kabel, satu di atas, dan satu di bawah:

    c
    |
    c
    
  • /dan \bekerja sebagai berikut:

    c        c
     \      /
      c    c
    
  • . kontak setiap kawat di sekitarnya:

    ccc
    c.c
    ccc
    
  • =spesial; itu menghubungkan kabel yang berdekatan di atasnya:

    -=-
    

    menghubungkan dua kabel. Berikut ini

    \|/
    -=-
    /|\
    

    masing-masing kabel berlawanan terhubung satu sama lain, tetapi tidak yang lain (di sinilah berbeda dari .).

  • Agar arus mengalir, dua kabel harus keduanya terhubung ke yang lain, sehingga |-, arus tidak mengalir.

Contoh pemasangan kabel:

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

input dibagi menjadi dua kabel dan kemudian dibagi menjadi tiga. Dalam perpecahan ini, kawat bawah bergerak ke tengah, dan perpecahan ke bawah dari kawat atas muncul di bagian bawah. Selanjutnya, bagian atas dari tiga kabel dipindahkan ke tengah.

Contoh kabel dengan gerbang:

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

Masukkan format:

  • setiap kabel input akan diberi label dengan digit. Pada akhir (tepat sebelum baris baru), setiap output akan diberi label dengan :(dan kawat akan selalu pergi tepat ke dalamnya, yaitu -:atau .:atau =:)
  • input akan selalu valid; tidak akan ada loop atau kabel bergabung bersama tanpa gerbang. Perhatikan bahwa mungkin ada kabel dengan ujung longgar.
  • = akan digunakan hanya jika diperlukan.

Format output:

  • setiap input direferensikan dengan nomor yang sesuai.
  • sebuah ekspresi dikeluarkan. Misalnya, jika kabel menghitung input 1 dan input 2, hasilnya adalah 1a2.
  • fungsi apa pun yang dikeluarkan harus sesuai dengan gerbang logika di awal.
  • untuk tidak menunjukkan, letakkan ~sebelum tempat yang benar.
  • untuk beberapa fungsi, gunakan tanda kurung untuk menunjukkan urutan eksekusi. Kurung juga dapat digunakan ketika hanya ada satu fungsi. Sebagai contoh,

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

    memiliki satu kemungkinan keluaran ~((2x3)A(~1))

  • banyak output harus dipisahkan oleh baris baru (atau setara)

Input sampel:

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

Satu kemungkinan output yang sesuai:

(~1)a(~(3O(4X5))
((1x2)x3)X((~1)a(~(3O(4X5))))
Justin
sumber
Oooohhhh, menarik! Saya akan mencobanya.
cjfaure
5
Saya melihat exolang yang menarik keluar dari ini, jika kita memperluasnya dengan cara membuatnya Turing-lengkap.
Victor Stafusa
Dalam hal terjadi "kesalahan kompiler" (mis. Kabel masukan salah bentuk) apa yang harus dilakukan penerjemah?
Victor Stafusa
Dan, jika saya menghubungkan langsung dua input? Atau hubungkan langsung dua output? Atau masukan jalur terbuka ke output?
Victor Stafusa
1
@ Viktor Ini sudah mirip. Tetapi saya terus maju dan menciptakan yang lain
Justin

Jawaban:

4

Python 2488 1567 806 706 697 657 653

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

Keterbatasan dan asumsi

Karena itu, hanya hingga 9 input yang didukung - banyak digit tidak ditangani dengan benar. Karena spek menunjukkan bahwa input diberi label dengan digit , bukan angka , ini diizinkan.


Masukan dan keluaran

Input diambil melalui standar masuk, dan keluaran melalui standar keluar.


Pengujian

Input dan output sampel:

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

Diuji di sini: http://ideone.com/gP4CIq


Algoritma

Ini pada dasarnya DFS agak naif dari output. Untuk setiap output, ia mulai dari karakter satu ke kiri dan menelusuri kawat, bercabang (dan menambahkan ke ekspresi) di setiap gerbang. Ketika mencapai input, itu menambahkannya ke ekspresi dan backtracks ke titik terakhir bercabang, karena kita bisa yakin bahwa percabangan tidak mungkin tanpa gerbang. Dan tentu saja setiap kasus yang tidak valid dibuang. Tidak ada yang benar-benar istimewa - dan karena itu kemungkinan lebih lama dari yang seharusnya.


Catatan

Ukuran mungkin bisa dikurangi sedikit dengan restrukturisasi, tapi saya sudah menghabiskan cukup waktu untuk ini untuk hari ini. Versi golf secara manual adalah yang dikompresi.

Kompresi gzip membuat golf menjadi menarik, karena caching tertentu (misalnya d=(-1,0,1)) sebenarnya membutuhkan lebih banyak ruang daripada membiarkan algoritma kompresi mengatasinya. Namun, saya memilih golf versi manual sejauh mungkin daripada mengoptimalkan kompresi.


Bermain golf secara 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])

Ungolfed penuh (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)
Bob
sumber
Apa itu DFS? Juga, bekerja mundur dari output adalah persis apa yang saya pikirkan.
Justin
@Quincunx Kedalaman-pencarian pertama. Pada dasarnya, rekursi (atau menggunakan konstruksi LIFO, tumpukan) dan melakukan perjalanan sejauh mungkin di sepanjang jalan sampai menyentuh jalan buntu atau tujuan, di mana titik itu kembali ke titik divergensi terakhir dan mencoba jalur lain.
Bob
Asumsi bagus pada input. Itulah yang saya maksudkan (dan saya mencoba mengatakannya untuk menyarankan itu). Namun, apakah program Anda berfungsi dengan 0angka? Bagaimana kalau bertukar pemesanan sehingga 2datang sebelumnya 1, dll.
Justin
@ Quincunx Saya menggunakan Python .isdigit(), yang secara efektif setara dengan regex [0-9]sejauh yang saya tahu. Apakah itu benar menurut spesifikasi Anda? Apa yang Anda maksud dengan bertukar pemesanan? Cara ini diterapkan, itu akan menuju cabang atas dari setiap gerbang logika pertama, tetapi tidak ada jaminan pemesanan input.
Bob
isdigit()konsisten. Urutan bertukar berarti sesuatu seperti 2input pertama, dan 1sebagai input kedua (diurutkan secara vertikal).
Justin
6

Jawa: 1523 1512 karakter

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

Ini memberikan output ini untuk input sampel:

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

Untuk memeras ukurannya:

  • Itu tidak melakukan pengecekan kesalahan, penanganan kesalahan atau validasi input, dengan asumsi bahwa input selalu valid.
  • Terbatas hingga 99 baris input.
  • File inputnya harus dipanggil adil r, tanpa ekstensi file apa pun dalam namanya.
  • Itu tidak berusaha untuk mendeteksi apakah tanda kurung diperlukan atau tidak. Ini mengasumsikan bahwa mereka selalu diperlukan, dan karena asumsi ini salah, ada kurung lebih banyak dari yang dibutuhkan, tetapi karena ini tidak membuatnya gagal spec, itu tidak masalah.
  • Urutan parameter untuk setiap operator biner secara umum tidak dapat diprediksi, karena tergantung pada kecepatan nilai-nilai tersebut diperbanyak dan dari urutan pemindaian sel. Tetapi karena semua operator biner bersifat komutatif, ini seharusnya tidak menjadi masalah.

Saya yakin itu mungkin untuk mengurangi lebih banyak, tetapi hanya sedikit.

Penerjemah diimplementasikan dalam bentuk semacam automata seluler. Ini memindai seluruh nilai pengaturan bidang, mengulanginya sebanyak yang diperlukan hingga tidak ada perubahan yang terdeteksi.

Ini adalah versi yang tidak dikoleksi:

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;
    }
}
Victor Stafusa
sumber
Tiny sedikit lebih murah untuk digunakan try{}catch(Exception e){}daripada dua throws Exception. Mungkin ada hal-hal lain, tetapi saya tidak tahu cara bermain golf Jawa.
Bob
@ Bob Terima kasih, saran Anda membuat saya mengurangi 7 karakter. Juga, saya bisa mengurangi 4 lagi.
Victor Stafusa