ASCII-Topologie Teil 1: Kann ich auf Sie zählen?

28

Ich habe ein ernstes Problem. Ich habe einige Textdateien, in denen ich meine sehr wichtigen Nummern aufbewahre - alle wichtigen! Und zwei und drei ..

Diese Zahlen waren so wichtig, dass ich sie nicht diesen neuen Dezimal- oder Binärzahlensystemen anvertrauen konnte. Ich habe jede Zahl in Unary verschlüsselt, so:

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

Einfach und zuverlässig: zwei ASCII-Schleifen für die Nummer 2. Leider verwickeln sich diese Dinge mit der Zeit, und jetzt fällt es mir schwer, herauszufinden, wie viele Schleifen sich in jeder Datei befinden. Hier einige Beispiele, die ich von Hand ausgearbeitet habe:

Eins:

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

Drei:

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

Vier:

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

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

Fünf:

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

Können Sie mir helfen, meine Schleifen zu zählen?

Hier sind die Regeln:

  • Da ich alles in ASCII-kodiertem Unary speichere, ist mir die Raumeffizienz sehr wichtig. Daher ist dies Codegolf. Das kleinste Programm in Bytes gewinnt.
  • Schleifen werden mit den Zeichen +, -, | gezeichnet. Jede Ecke in der Schleife ist eindeutig gezeichnet: genau eines der Zeichen über und unter dem + ist | und genau eines nach rechts oder links ist -. Zwei + Zeichen sind niemals benachbart.
  • Stränge können untereinander und untereinander verlaufen. Wenn sich die Litzen kreuzen, können Sie die "Unter" -Litze sofort auf beiden Seiten der "Über" -Litze sehen.
  • Ihr Programm sollte eine Zeichenfolgendarstellung der Schleife (entweder von stdin oder als Funktionsparameter) nehmen und eine Zahl erzeugen (entweder zu stdout oder als Rückgabewert).
  • Die Linienlängen in der Loop-Zeichnung sind möglicherweise nicht einheitlich, und auf jeder Linie befinden sich möglicherweise nachgestellte Leerzeichen.
  • Sie können davon ausgehen, dass der Eingang mindestens eine Schleife enthält.

Ich zähle auf dich!

Matt Noonan
quelle
Kann eine der Seiten eines Unterstranges eine sein +?
Feersum
@feersum: Nein, die beiden am + angebrachten Kanten sind immer sichtbar.
Matt Noonan
1
@ Martin: Ich fürchte nicht. Mein Speicherplatz ist wirklich knapp, so dass ich nicht all diese zusätzlichen Räume sparen kann.
Matt Noonan
Ich denke, Sie sollten dieses ( Pastebin ) als Testfall hinzufügen, es sei denn, mir fehlt etwas und es ist keine gültige Eingabe. Es gibt 6 Schleifen; Ich habe es nur online mit der SnakeEx-Lösung getestet und es gibt 12.
blutorange
1
Vielleicht sollten Sie Schleifen, die sich kreuzen, explizit verbieten oder zulassen (z. B. pastebin.com/5RLZuULG ). Derzeit werden sie von der Ruby-Lösung erkannt, aber nicht von der SnakeEx-Lösung.
Blutorange

Antworten:

19

SnakeEx - 98 Bytes mit Javascript, 44 ohne

Dies schien ein gutes Problem zu sein, um meine Sprache von der Fortnightly Challenge an zu testen :

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

Der beste Ort, um dies auszuprobieren, ist mein Online-Dolmetscher .

SnakeEx gleicht Textmuster mithilfe von "Schlangen" ab, die sich um den zu regulären Texten passenden Text bewegen. Der Code liest sich wie ein regulärer Ausdruck, außer:

  • Die <T>Anweisung. Dies ist ein Richtungsbefehl, der die Schlange von ihrer aktuellen Richtung nach links und rechts abzweigt.
  • {e<>PE}ist wie ein Unterprogrammaufruf. Es, das eine Schlange erzeugt, deren Definition esich vorwärts bewegt ( <>) und deren Parameter P(Huckepack - die laichende Schlange folgt der neuen Schlange) und E(exklusiv - nicht mit etwas übereinstimmen, das bereits übereinstimmt). Diese exklusive Prüfung ist das einzige, was die Schlange davon abhält, sich unendlich zu drehen.
  • Das Präfix `am Ende gibt an, dass das Folgende nur abgeglichen werden soll, wenn es bereits abgeglichen wurde. Mit diesem Präfix können wir das Schließen der Schleife erzwingen.

Da SnakeEx wie Regex ist und die Ergebnisse technisch nicht so ausgibt, wie es von selbst gewünscht wird, müssen wir es vermutlich in ein JavaScript einbinden, das den Interpreter aufruft:

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

Bearbeiten : Es wurde korrigiert, um mit den zusätzlichen Testfällen von blutorange zu arbeiten

BMac
quelle
1
+1 Ich mag das wirklich, vielleicht weil ich es online ausprobieren und die Schleifen hervorheben kann. Aber vielleicht möchten Sie diese beiden Testfälle überprüfen: 1 , 2
blutorange
@blutorange Guter Fang. Ich habe eine leicht hackige Korrektur für sich selbst kreuzende Schleifen hinzugefügt. Über Testfall 1 muss ich allerdings noch etwas nachdenken.
BMac
Das ist die leicht zu beheben, ersetzen Sie einfach [^ ]mit [|\-];)
Blutorange
Hah, ich habe lange gebraucht, um herauszufinden, warum das so war. Guter Anruf.
BMac
Das ist fantastisch!
Ingo Bürk
10

C # - 338 388 433 Bytes

Durch Ändern eines eindimensionalen Arrays wurden eine Reihe von Bytes gespeichert.

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

Zuerst liest es die Eingabe ein und macht sie hübsch und rechteckig mit einem "" Rand, so dass wir keine Begrenzungen in der Horizontalen überprüfen müssen (billiger, als in der Vertikalen zu überprüfen, als die zusätzliche Zeile einzufügen). . Dann schaut es durch das Rechteck zurück und trifft immer auf eine rechte untere Ecke. Wenn es auf eine davon trifft, richtet es sich nach einem beliebigen + auf und löscht sie nach und nach (mit einem Leerzeichen). Es hört auf zu folgen, wenn es auf ein Leerzeichen trifft. Getestet an den fünf angegebenen Beispielen.

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
quelle
Wow. Das ist beeindruckend: o
Metoniem
6

Beleg , 51 41 + 2 = 43 Bytes

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

(Jetzt aktualisiert, um mit @ blutoranges Testfall zu einem hohen Preis zu arbeiten.)

Da @BMac SnakeEx für diese Herausforderung verwendete, dachte ich, ich würde versuchen, meine 2D- Vorlage für die Mustererkennung , Slip, zu verwenden. Da Slip jedoch nicht über die zur Lösung dieses Problems erforderlichen Funktionen verfügt, habe ich sie in den letzten Tagen hinzugefügt. Mit anderen Worten, diese Einsendung ist nicht gewinnberechtigt .

Laufen Sie mit der nFlagge für die Anzahl der Übereinstimmungen, z

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

Probieren Sie es online aus .


Erläuterung

Aufgrund der Vielzahl neuer Funktionen in dieser Einreichung ist dies eine gute Gelegenheit, sie vorzustellen.

$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 versucht, von jeder Position aus eine Übereinstimmung zu finden und gibt nur eindeutige Übereinstimmungen zurück. Beachten Sie, dass wir verwenden [^ +]- während die Verwendung [-|]theoretisch zwei Bytes einsparen würde, ist die -am Anfang / Ende von Zeichenklassen unescaped noch nicht in Slip implementiert.

Sp3000
quelle
1
@ Blutorange threehat auch +s, die nicht eins -, eins |und zwei Leerzeichen sind, also
nehme
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}

Versuchen Sie es online: http://ideone.com/kIKELi ( ich hinzugefügt #to_aAnruf in der ersten Zeile, weil ideone.com verwendet Ruby - 1.9.3, die nicht unterstützt #sizefür Enumerables In Ruby 2.1.5+ der Code ausgeführt wird OK. . )

Der Ansatz ist der folgende:

  • Machen Sie eine Liste aller +Zeichen in der Eingabe und betrachten Sie jedes von ihnen als eine eigene Form
  • Finden Sie horizontale und vertikale Linien, die zwei +Zeichen verbinden, und kombinieren Sie ihre Formen zu einer
  • Am Ende stimmt die Anzahl der verschiedenen Formen mit dem Ergebnis überein

Hier ist eine besser lesbare Version:

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
quelle
5

JavaScript (ES6) 190 197 202 215 235 289 570

Bearbeiten eines eindimensionalen Arrays anstelle von zwei Dimensionen, maximale Zeilengröße 999 Zeichen

Bearbeiten Hinzugefügtes animiertes Code-Snippet, siehe unten

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

Ungolfed ersten Versuch

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
}

Animiertes Snippet

Test In der Firefox / FireBug-Konsole

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
quelle
Sicherlich würden Sie einige Bytes einsparen, indem Sie die Golfversion einfach auskleiden? Sie können auch einfach eine anonyme Funktion erstellen (ich denke, das entspricht den Regeln von Codegolf)
theonlygusti
@theonlygusti die Golf-Version wird als einzeilig gezählt (keine Zeilenumbrüche und Leerzeichen werden gezählt). Mit einer anonymen Funktion spare ich 2 Bytes, vernachlässigbare Einsparung ...
edc65
4

Ruby, 178 187 199 212

Bessere Ruby-Version, schafft eine Funktion F. Jetzt mit leckereren Interpreter-Warnungen ständig.

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

Testen Sie es online: ideone

Grundsätzlich bstartet die Funktion bei jedem +, durchläuft die Schleife rekursiv und setzt alle +auf u. Somit wird bei jedem bAufruf eine Schleife entfernt . Die Funktion Fversucht nur, wie oft wir anrufen müssen, bbis keine Schleifen mehr übrig sind.

blutorange
quelle
2

Python 2 - 390

Nimmt einen String mit Zeilenumbrüchen von stdin. Es ist eine ziemlich einfache Methode, ein gutes Stück Golf zu spielen, aber ich bin mir sicher, dass es nicht so lang ist, wie es sein könnte.

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
quelle
1

Python 2 - 346 Bytes

Implementiert als Funktion c, die die Dateidaten als Eingabe verwendet und die Anzahl der Schleifen zurückgibt.

Zunächst zerlegt die Funktion die Daten in eine Zuordnung von Schleifenelementpositionen zu dem Elementtyp an dieser Position (z {(0,0): '+'}. B. ). Dann werden zwei gegenseitig rekursive interne Funktionen verwendet. Das erste entfernt ein Schleifensegment aus dem Mapping und entscheidet, welche Positionen für das nachfolgende Segment überprüft werden sollen. Die zweite prüft, welche Art von Schleifenelement an den ausgewählten Stellen vorhanden ist, und ruft, wenn es mit den erwarteten kompatibel ist, die erste auf, um den neu gefundenen Abschnitt zu entfernen.

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
quelle