Topologi ASCII hal 1: Dapatkah saya mengandalkan Anda?

28

Saya punya masalah serius. Saya memiliki beberapa file teks di mana saya menyimpan nomor saya yang sangat penting - semua yang penting! Dan dua, dan bertiga ..

Angka-angka ini sangat penting sehingga saya tidak bisa mempercayakan mereka ke sistem angka desimal atau biner yang baru. Saya menyimpan setiap nomor yang disandikan di unary, seperti:

            +--+
            |  |
+---+  +----+  |
|   |  |       |
+---+  +-------+
   ~/two.txt

Sederhana dan dapat diandalkan: dua loop ASCII untuk nomor 2. Sayangnya, hal-hal ini cenderung menjadi kusut dari waktu ke waktu dan sekarang saya mengalami kesulitan mencari tahu berapa banyak loop dalam setiap file. Berikut adalah beberapa contoh yang saya kerjakan dengan tangan:

Satu:

   +---+
   |   |
+--+   |
|      |
+--+   |
   |   |
   |   |
   |   |
+--+   +--+
|         |
+---------+

Tiga:

+---------+
| +-----+ |
| | +-+ | |
| | | | | |
| | +-+ | |
| +-----+ |
+---------+

Empat:

  +--------------+
  |  +--+  +--+  |
  |  |  |  |  |  |
+-|-----|-----|----+
| |  |  |  |  |  | |
| +--+  +--+  +--+ |
+------------------+

              +------------+
              |            |
        +-----+  +-----+   |
        |        |     |   |
  +-----|-----------+  |   |
  |     |  +--+  |  |  |   |
  +-+   +--|--|--+  +---------+
    |      |  +-+      |   |  |
    +------+    |      |   |  |
                +-------+  |  |
                       ||  |  |
                       |+-----+
                       |   |
                       +---+

Lima:

+--------+  +--------+  +--------+
|        |  |        |  |        |
|     +--|-----+  +--|-----+     |
|     |  |  |  |  |  |  |  |     |
+-----|--+  +-----|--+  +--------+
      |        |  |        |
      +--------+  +--------+

Bisakah Anda membantu saya menghitung loop saya?

Berikut aturannya:

  • Karena saya menyimpan segala sesuatu di ASCII-encodeed unary, efisiensi ruang sangat penting bagi saya. Karena itu, ini adalah kode golf. Program terkecil dalam byte menang.
  • Loop ditarik dengan karakter +, -, |. Setiap sudut dalam loop digambar dengan jelas: tepat salah satu karakter di atas dan di bawah + akan |, dan tepat satu ke kanan atau ke kiri akan -. Dua tanda + tidak pernah berdekatan.
  • Helai dapat melewati dan di bawah satu sama lain. Saat untaian menyeberang, Anda akan dapat melihat untaian "bawah" segera di kedua sisi untai "atas".
  • Program Anda harus mengambil representasi string dari loop (baik dari stdin atau sebagai parameter fungsi) dan menghasilkan angka (baik untuk stdout atau sebagai nilai balik).
  • Panjang garis mungkin tidak seragam dalam gambar lingkaran dan mungkin ada spasi tambahan di setiap garis.
  • Anda dapat berasumsi bahwa setidaknya ada satu loop di input.

Aku mengandalkan mu!

Matt Noonan
sumber
Bisakah salah satu sisi dari 'untai' menjadi +?
feersum
@feersum: Tidak, dua tepi yang melekat pada + akan selalu terlihat.
Matt Noonan
1
@ Martin: Aku takut tidak. Ruang penyimpanan saya sangat mahal, jadi saya tidak bisa menyimpan semua ruang ekstra itu.
Matt Noonan
Saya pikir Anda harus menambahkan ini ( pastebin ) sebagai test case kecuali saya kehilangan sesuatu dan itu bukan input yang valid. Ada 6 loop; Saya hanya mengujinya secara daring dengan solusi SnakeEx dan hasilnya 12.
blutorange
1
Mungkin Anda harus secara eksplisit melarang atau mengizinkan loop yang melintas sendiri (misalnya pastebin.com/5RLZuULG ) Saat ini, mereka terdeteksi oleh solusi ruby, tetapi tidak oleh solusi SnakeEx.
blutorange

Jawaban:

19

SnakeEx - 98 byte dengan Javascript, 44 tanpa

Ini tampak seperti masalah yang baik untuk mencoba bahasa saya dari Fortnightly Challenge pada:

m:({e<>PE}\-[|\-]*<T>\+|[|\-]*<T>)+`\+
e:\+

Tempat terbaik untuk mencoba ini adalah juru bahasa online saya .

SnakeEx mencocokkan pola dalam teks dengan menggunakan "ular" yang bergerak di sekitar regex pencocokan teks. Kode dibaca seperti regex, kecuali:

  • The <T>instruksi. Itu adalah perintah arah yang bercabang ular kiri dan kanan dari arah saat ini.
  • {e<>PE}seperti panggilan subrutin. Ini yang memunculkan ular dengan definisi yang ebergerak maju ( <>) dan dengan parameter P(dukung kuda - ular pemijahan mengikuti ular baru) dan E(eksklusif - tidak cocok dengan apa pun yang sudah cocok). Pemeriksaan eksklusif ini adalah satu-satunya hal yang menghentikan ular dari perulangan tanpa batas.
  • Awalan `di bagian akhir menunjukkan bahwa yang berikut harus dicocokkan hanya jika sudah cocok, yang dapat kita gunakan untuk memaksa loop untuk menutup.

Karena SnakeEx seperti regex dan tidak secara teknis menampilkan hasil seperti yang diinginkan dengan sendirinya, saya kira kita perlu membungkusnya dalam beberapa Javascript memanggil interpreter:

function e(s){return snakeEx.run('m:({e<>PE}\\-[|\\-]*<T>\\+|[|\\-]*<T>)+`\\+\ne:\\+',s,1).length}

Sunting : perbaiki untuk bekerja dengan kasus uji tambahan blutorange

BMac
sumber
1
+1 Saya sangat suka ini, mungkin karena saya bisa mencobanya secara online dan mendapatkan loop yang disorot. Tetapi Anda mungkin ingin memeriksa dua test case ini: 1 , 2
blutorange
@blutorange Tangkapan yang bagus. Saya menambahkan sedikit perbaikan untuk loop self-crossing. Saya harus memikirkan soal uji 1 sedikit lagi.
BMac
Itu yang mudah untuk diperbaiki, ganti saja [^ ]dengan [|\-];)
blutorange
Hah, butuh waktu lama untuk mencari tahu mengapa itu terjadi. Panggilan yang bagus.
BMac
Ini luar biasa!
Ingo Bürk
10

C # - 338 388 433 byte

Menyimpan banyak byte dengan mengubah ke array 1 dimensi.

using C=System.Console;using System.Linq;class P{static void Main(){var D=C.In.ReadToEnd().Split('\n');int z,w=D.Max(m=>m.Length)+1,d,c=0;var E=D.SelectMany(l=>l.PadRight(w)).ToList();for(z=E.Count;z-->1;)if(E[z-1]==43)for(d=1,c++;E[z+=d%2<1?w*d-w:d-2]>32;)if(E[z]<44){E[z]=' ';d=d%2>0?z<w||E[z-w]<99?2:0:E[z+1]!=45?1:3;}C.WriteLine(c);}}

Pertama ia membaca di input, dan membuatnya bagus dan persegi panjang, dengan perbatasan "" jadi kita tidak perlu melakukan batasan memeriksa horizontal (lebih murah untuk melakukan pengecekan pada vertikal daripada memasukkan garis tambahan) . Kemudian terlihat kembali melalui persegi panjang, sehingga selalu menyentuh sudut kanan bawah. Ketika hits salah satu dari ini, itu mengarahkan dirinya, mengikuti + s apa pun yang ditemuinya, dan membersihkan mereka saat berjalan (dengan spasi). Itu berhenti mengikuti ketika bertemu ruang. Diuji pada lima contoh yang diberikan.

using C=System.Console;
using System.Linq;

class P
{
    static void Main()
    {
        // read in
        var D=C.In.ReadToEnd().Split('\n');

        int z, // z is position in E
        w=D.Max(m=>m.Length)+1, // w is width
        d, // d is direction of travel (1 == horizontal?, 2 == down/right?)
        c=0; // c is loop count

        // make all the lines the same length
        var E=D.SelectMany(l=>l.PadRight(w)).ToList(); // say no to horizontal bounds checking

        // consume +s
        for(z=E.Count;z-->1;)
            if(E[z-1]==43) // right-most lower-most +
                for(d=1,c++; // go left, increment counter
                    E[z+=d%2<1?w*d-w:d-2]>32 // move z, then check we havn't hit a space (when we do, z is basiclly z - 1)
                    ;)
                    if(E[z]<44) // +
                    {
                        E[z]=' '; // toodles

                        d=
                            d%2>0? // currently horizontal, must go vertical
                                z<w||E[z-w]<99?2 // can't go up, must go down
                                :0 // can go up, go up
                            : // currently vertical, must go horizontal
                                E[z+1]!=45?1 // can't go right, must go left
                                :3 // can go right, go right
                            ;
                    }

        // output result
        C.WriteLine(c);
    }
}
VisualMelon
sumber
Wow. Itu mengesankan: o
Metoniem
6

Slip , 51 41 + 2 = 43 byte

$a(`+`-[^ +]*`+(<|>)`|[^ +]*`+#(<|>))+?$A

(Sekarang diperbarui untuk bekerja dengan test case @ blutorange dengan biaya besar)

Karena @BMac menggunakan SnakeEx untuk tantangan ini, saya pikir saya akan mencoba dan menggunakan pengiriman bahasa pencocokan pola 2D , Slip. Tetapi karena Slip tidak memiliki fitur yang diperlukan untuk menyelesaikan masalah ini, saya telah menambahkannya selama beberapa hari terakhir. Dengan kata lain, pengiriman ini tidak memenuhi syarat untuk menang .

Jalankan dengan nbendera untuk jumlah pertandingan, mis

py -3 slip.py regex.txt input.txt n

Cobalah online .


Penjelasan

Karena kebanyakan fitur baru dalam pengiriman ini, ini adalah kesempatan yang baik untuk memamerkannya.

$a                Set custom anchor at current position
(
  `+`-            Match '+-'
  [^ +]*          Match any number of '|' or '-'
  `+              Match a '+'
  (<|>)           Either turn left or turn right
  `|              Match a '|'
  [^ +]*          Match any number of '|' or '-'
  `+              Match a '+'
  #               Prevent next match from moving the match pointer (doubling up on '+')
  (<|>)           Either turn left or turn right
)
+?                Do the above at least once, matching lazily
$A                Make sure we're back where we started

Slip mencoba mencocokkan mulai dari setiap posisi, dan hanya mengembalikan yang unik. Perhatikan bahwa kita menggunakan [^ +]- saat menggunakan [-|]secara teoritis akan menghemat dua byte, tidak terhapus -pada awal / akhir kelas karakter belum diimplementasikan dalam Slip.

Sp3000
sumber
1
@blutorange threejuga memiliki +s yang bukan satu -, satu |dan 2 spasi, jadi saya berasumsi itu bukan kesalahan
Sp3000
5

Ruby 295

F=->i{l=i.lines
g={}
l.size.times{|y|i.size.times{|x|l[y][x]==?+&&g[[y,x]]=[[y,x]]}}
c=->a,b{w=g[b]+g[a];w.map{|x|g[x]=w}}
k=g.keys
k.product(k).map{|n,o|
r,p=n
s,q=o
((r==s&&p<q&&l[r][p...q]=~/^\+-[|-]*$/)||(p==q&&r<s&&l[r...s].map{|l|l[p]||c}.join=~/^\+\|[|-]*$/))&&c[n,o]}
g.values.uniq.size}

Cobalah online: http://ideone.com/kIKELi ( Saya menambahkan #to_apanggilan di baris pertama, karena ideone.com menggunakan Ruby 1.9.3, yang tidak mendukung #sizeuntuk Enumerables. Di Ruby 2.1.5+ kode berjalan OK . )

Pendekatannya adalah sebagai berikut:

  • buat daftar semua +tanda di input dan anggap masing-masing dari mereka bentuk yang berbeda
  • temukan garis horizontal dan vertikal yang menghubungkan dua +tanda dan menggabungkan bentuk mereka menjadi satu
  • pada akhirnya, jumlah bentuk berbeda sesuai dengan hasilnya

Ini versi yang lebih mudah dibaca:

def ascii_topology_count(input)
  lines = input.lines
  max_length = lines.map(&:size).max

  # hash in which the keys are corners ("+"s), represented by their [y, x] coords
  # and the values are arrays of corners, representing all corners in that group
  corner_groups = {}

  lines.size.times { |y|
    max_length.times { |x|
      if lines[y][x] == ?+
        corner_groups[[y, x]] = [[y, x]]
      end
    }
  }

  # function that combines the groups of two different corners
  # into only one group
  combine_groups =-> c1, c2 {
    g1 = corner_groups[c1]
    g2 = corner_groups[c2]

    g2 += g1
    corner_groups[c1] = g2
    g2.map{|x| corner_groups[x] = g2}
  }

  corner_groups.keys.product(corner_groups.keys).map{|c1, c2|
    y1,x1=c1
    y2,x2=c2
    if y1 == y2 && x1 < x2
      # test horizontal edge
      t = lines[y1][x1...x2]
      if t =~ /^\+-[|-]*$/
        # p "#{c1}, #{c2}, [H] #{t}"
        combine_groups[c1, c2]

      end
    end

    if x1 == x2 && y1 < y2
      # test vertical edge
      t=lines[y1...y2].map{|l|l[x1]||' '}.join

      if t =~ /^\+\|[|-]*$/
        # p "#{c1}, #{c2}, [V] #{t}"
        combine_groups[c1, c2]
      end
    end
  }

  corner_groups.values.uniq.count
end
Cristian Lupascu
sumber
5

JavaScript (ES6) 190 197 202 215 235 289 570

Edit array dimensi tunggal alih-alih 2 dimensi, ukuran baris maksimal 999 karakter (tetapi bisa lebih tanpa biaya, misalnya 1e5, bukan 999)

Edit cuplikan kode animasi yang ditambahkan, lihat di bawah

F=s=>[...s.replace(/.+/g,r=>r+Array(e-r.length),e=999)]
  .map((c,x,z,d=1,f='-',g='|')=>{
    if(c=='+')
      for(++n;z[x+=d]!='+'||([f,g,e,d]=[g,f,d,z[x-e]==g?-e:z[x+e]==g&&e],d);)
        z[x]=z[x]==g&&g
  },n=0)|n

Pertama mencoba ungolfed

f=s=>
{
  cnt=0
  s = (1+s+1).split(/[1\n]/)

  for(;x=-1, y=s.findIndex(r=>~(x=r.indexOf('+-'))), x>=0;++cnt)
  {
    //console.log(y+' '+x+' '+s.join('\n'))
    dx = 1
    for(;dx;)
    {
      a=s[y-1],b=s[y+1],
      r=[...s[y]]
      for(r[x]=' ';(c=r[x+=dx])!='+';)
      {
        if (c=='-')
          if((a[x]||b[x])=='|')r[x]='|';
          else r[x]=' ';
      }  

      if(a[x]=='|')dy=-1;
      else if(b[x]=='|')dy=1;
      else dy=0
      r[x]=' '
      s[y]=r.join('')
      if (dy) {
        for(;y+=dy,r=[...s[y]],(c=r[x])!='+'&c!=' ';)
        {
          if (c=='|') 
            if((r[x-1]||r[x+1])=='-')r[x]='-';
            else r[x]=' ';
          s[y]=r.join('')
        }  
        if(r[x-1]=='-')dx=-1;
        else if(r[x+1]=='-')dx=1;
        else dx=0;
      }
    }  
  }
  return cnt
}

Cuplikan animasi

Uji di Firefox / konsol FireBug

F('\
  +--------------+\n\
  |  +--+  +--+  |\n\
  |  |  |  |  |  |\n\
+-|-----|-----|----+\n\
| |  |  |  |  |  | |\n\
| +--+  +--+  +--+ |\n\
+------------------+\n\
\n\
              +------------+\n\
              |            |\n\
        +-----+  +-----+   |\n\
        |        |     |   |\n\
  +-----|-----------+  |   |\n\
  |     |  +--+  |  |  |   |\n\
  +-+   +--|--|--+  +---------+\n\
    |      |  +-+      |   |  |\n\
    +------+    |      |   |  |\n\
                +-------+  |  |\n\
                       ||  |  |\n\
                       |+-----+\n\
                       |   |\n\
                       +---+')

4

F('\
+--------+  +--------+  +--------+\n\
|        |  |        |  |        |\n\
|     +--|-----+  +--|-----+     |\n\
|     |  |  |  |  |  |  |  |     |\n\
+-----|--+  +-----|--+  +--------+\n\
      |        |  |        |\n\
      +--------+  +--------+')

5

edc65
sumber
Tentunya Anda akan menghemat beberapa byte dengan melapisi versi golfnya? Anda juga dapat membuat fungsi anonim (saya pikir itu dalam aturan codegolf)
theonlygusti
@ theonlygusti, versi golf dihitung sebagai single-line (tidak ada baris baru dan spasi indentasi dihitung). Dengan fungsi anonim, saya menyimpan 2 byte, dapat diabaikan ...
edc65
4

Ruby, 178 187 199 212

Versi ruby ​​yang lebih baik, menciptakan fungsi F. Sekarang dengan peringatan juru bahasa yang lebih lezat terus-menerus.

b=->n{Q[I]=?~
d=Q[I+n]==(n>1??|:?-)?1:-1
loop{I+=d*n
b[n>1?1:N]if Q[I]==?+
Q[I]<?~?4:break}}
F=->s{N=s.size;Q=s+?\n
Q.gsub!(/^.*$/){$&.ljust N-1}
(0..N).find{!(I=Q=~/\+/)||b[1]}}

Uji secara online: ideone

Pada dasarnya, fungsi bdimulai kapan saja +, secara rekursif melewati loop, mengatur semua +ke u. Dengan demikian satu loop akan dihapus setiap kali bdipanggil. Fungsi Fhanya mencoba seberapa sering kita perlu menelepon bsampai tidak ada loop yang tersisa.

blutorange
sumber
2

Python 2 - 390

Mengambil string dengan baris baru dari stdin. Ini adalah metode yang cukup sederhana bermain golf sedikit adil, tapi saya yakin tidak sebanyak yang bisa mempertimbangkan berapa lama itu.

s=raw_input().split('\n');L=len
def R(x,y):
 b=p,q=x,y;u=v=f=0
 while b!=(p,q)or not f:
    p+=u;q+=v;f=u+v;c=s[q][p]
    if'+'==c:u,v=[(i,j)for i,j in{(-1,0),(1,0),(0,-1),(0,1)}-{(-u,-v)}if 0<=q+j<L(s)and 0<=p+i<L(s[q+j])and s[q+j][p+i]in['-+','|+'][j]][0];s[q]=s[q][:p]+' '+s[q][p+1:]
    if c+s[q+v][p+u]in'-|-':p+=u;q+=v
print L([R(x,y)for y in range(L(s))for x in range(L(s[y]))if'+'==s[y][x]])
KSab
sumber
1

Python 2 - 346 byte

Diimplementasikan sebagai fungsi cyang mengambil data file sebagai input dan mengembalikan jumlah loop.

Pertama, fungsi menguraikan data ke pemetaan lokasi elemen loop ke tipe elemen di lokasi itu (misalnya {(0,0): '+'}). Kemudian, ia menggunakan dua fungsi internal yang saling rekursif. Yang pertama menghapus segmen loop dari pemetaan dan memutuskan lokasi mana yang akan diperiksa untuk segmen berikutnya. Yang kedua memeriksa apa jenis elemen loop di lokasi yang dipilih dan, jika itu kompatibel dengan apa yang diharapkan, memanggil yang pertama untuk menghapus bagian yang baru ditemukan.

e=enumerate
def c(d):
 D={(i,j):k for i,l in e(d.split('\n'))for j,k in e(l)if k in'+-|'}
 def f(r,c,R,C,t):
  if D.get((r,c),t)!=t:g(r,c)
  elif D.get((R,C),t)!=t:g(R,C)
 def g(r,c):
  t=D.pop((r,c))
  if t!='|':f(r,c-1,r,c-2,'|');f(r,c+1,r,c+2,'|')
  if t!='-':f(r-1,c,r-2,c,'-');f(r+1,c,r+2,c,'-')
 n=0
 while D:g(*D.keys()[0]);n+=1
 return n
Mac
sumber