ASCII topology pt 1: Can I count on you?

Question

I have a serious problem. I have some text files where I keep my very important numbers -- all of the important ones! And twos, and threes..

These numbers were so important that I couldn't entrust them to those newfangled decimal or binary number systems. I kept each number encoded in unary, as so:

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

Simple and reliable: two ASCII loops for the number 2. Unfortunately, these things tend to get tangled up over time and now I have a hard time figuring out how many loops are in each file. Here are some examples that I worked out by hand:

One:

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

Three:

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

Four:

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

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

Five:

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

Can you help me count my loops?

Here are the rules:

• Since I store everything in ASCII-encoded unary, space efficiency is very important to me. Therefore, this is code golf. The smallest program in bytes wins.
• Loops are drawn with the characters +, -, |. Every corner in the loop is drawn unambiguously: exactly one of the characters above and below the + will be |, and exactly one to the right or left will be -. Two + marks are never adjacent.
• Strands may pass over and under each other. When strands cross, you'll be able to see the "under" strand immediately on both sides of the "over" strand.
• Your program should take a string representation of the loop (either from stdin or as a function parameter) and produce a number (either to stdout or as a return value).
• Line lengths may not be uniform in the loop drawing and there may be trailing spaces on each line.
• You may assume that there is at least one loop in the input.

I'm counting on you!

Answer 1

SnakeEx - 98 bytes with Javascript, 44 without

This looked like a good problem to try my language from the Fortnightly Challenge on:

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

The best place to try this out is my online interpreter.

SnakeEx matches patterns in text by using "snakes" that move around the text matching regexes. The code reads kind of like a regex, except:

• The <T> instruction. That is a direction command that branches the snake left and right from its current direction.
• {e<>PE} is like a subroutine call. It that spawns a snake with definition e moving forward (<>) and with parameters P (piggyback - the spawning snake follows the new snake) and E (exclusive - don't match anything that's already been matched). This exclusive check is the only thing that stops the snake from looping infinitely.
• The prefix ` at the end indicates that what follows should be matched only if it has already been matched, which we can use to force the loop to close.

Because SnakeEx is like regex and doesn't technically output the results as desired by itself, I guess we need to wrap it in some Javascript calling the interpreter:

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

Edit: fixed it up to work with blutorange's additional test cases

Answer 2

C# - 338 388 433 bytes

Saved a bunch of bytes by changing to a 1-dimensional array.

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

First it reads in the input, and makes it nice and rectangular, with a " " border so we don't have to do any bounds checking on the horizontal (cheaper to do the checking on the vertical than to put in the extra line). Then it looks back through the rectangle, so it always hits a right-bottom corner. When it hits one of these, it directs itself up, following any +s it meets, and clearing them as it goes (with a space). It stops following when it meets a space. Tested on the five given examples.

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

Answer 3

Slip, 51 41 + 2 = 43 bytes

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

(Now updated to work with @blutorange's test case at a major cost)

Since @BMac used SnakeEx for this challenge, I thought I'd try and use my 2D pattern-matching language submission, Slip. But because Slip didn't have the features necessary to solve this problem, I've been adding them in over the past few days. In other words, this submission is not eligible to win.

Run with the n flag for number of matches, e.g.

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

Try it online.

---

Explanation

Due to the plethora of new features in this submission, this is a good opportunity to showcase them.

$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 tries to match starting from every position, and only returns unique matches. Note that we use [^ +] — while using [-|] would theoretically save two bytes, unescaped - at the beginning/end of character classes is not yet implemented in Slip.

Answer 4

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}

Try it online: http://ideone.com/kIKELi (I added a #to_a call on the first line, because ideone.com uses Ruby 1.9.3, which does not support #size for Enumerables. In Ruby 2.1.5+ the code runs OK.)

The approach is the following:

• make a list of all the + signs in the input and consider each of them a distinct shape
• find horizontal and vertical lines that link two + signs and combine their shapes into one
• in the end, the number of distinct shapes matches the result

Here's a more readable 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

Answer 5

Ruby, 178 187 199 212

Better ruby version, creates a function F. Now with more delicious interpreter warnings constantly.

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

Test it online: ideone

Basically, function b starts at any +, recursively goes through the loop, setting all + to u. Thus one loop gets removed each time b is called. Function F just tries how often we need to call b until there aren't any loops remaining.

Answer 6

JavaScript (ES6) 190 197 202 215 235 289 570

Edit Single dimension array instead of 2 dimension, max row size 999 chars (but can be more at no cost, e.g. 1e5 instead of 999)

Edit Added animated code snippet, see below

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 first try

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
}

Animated snippet

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,steps.push(z.map(c=>c?c!=','?c:'':0).join(''))},n=0)|n
    
function go(){var g=grid.value;steps=[];Num.value=F(g);a=_=>{g=steps.shift();if(g){grid.value=g;setTimeout(a, 100)}};a()}

textarea { width: 500px;  height: 500px; }
input {width: 80px}

Better viewed full page<br>Input (paste input text - enlarge if needed)<button onclick="go()">Process</button>Loop count:<input readonly id=Num /><br><textarea id=grid></textarea><br>

Test In Firefox/FireBug console

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

Answer 7

Python 2 - 390

Takes a string with newlines from stdin. It's a pretty simple method golfed a fair bit, but I'm sure not as much as it could be considering how long it is.

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

Answer 8

Python 2 - 346 bytes

Implemented as a function c that takes the file data as input and returns the number of loops.

First, the function decomposes the data to a mapping of loop element locations to the element type at that location (e.g. {(0,0): '+'}). Then, it uses two mutually-recursive internal functions. The first removes a loop segment from the mapping and decides which locations to check for the subsequent segment. The second checks what kind of loop element is in the selected locations and, if it is compatible with what is expected, calls the first to remove the newly found section.

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