Code Golf: recognize ascii art boxes

Question

Came up with this a while ago while doing some data structure work, though it'd make a good code golf: Given a two dimensional array of characters containing ascii art rectangles, produce a list of coordinates and sizes for the rectangles.

• Any trivially convertable input or output format is fine (eg: char**, list of strings, lines on standard input; list of four ints, struct, fixed amount +/- for the size; etc).
• Similarly, output need not be in any particular order.
• You dont have to anything useful for invalid input or malformed rectangles, but you shouldnt to produce valid-looking coordinates for a rectangle that isnt in the input.
• No two valid rectangles share a + (though + may appear not only as part of rectangle)
• You can assume that all rectangles are at least 3x3: each side has a - or | in it.

Examples:

"        "
"  +-+ | "
"  | | \-"
"  +-+   "
(2,1;3,3)

"+--+  +--+"
"|  |  |  |"
"+--+  +--+"
(0,0;4,3), (6,0;4,3)

"  +---+  "
"->|...|  "
"  +---+  "
(2,0;5,3)

"+-+ +--+  +--+"
"| | |  |  |  |"
"+-+ |  |  + -+"
"    |  |      "
"    +--+  +-+ "
"  +--+    |   "
"  +--+    +-+ "
(0,0;3,3), (4,0;4,5) # (2,5;4,2) is fine, but not needed

Answer 1

F#, 297 chars

Kinda lame, but simple.

let F a=
 for x=0 to Array2D.length1 a-1 do
  for y=0 to Array2D.length2 a-1 do
  if a.[x,y]='+' then
   let mutable i,j=x+1,y+1
   while a.[i,y]<>'+' do i<-i+1
   while a.[x,j]<>'+' do j<-j+1
   printfn"(%d,%d;%d,%d)"x y (i-x+1)(j-y+1)
   a.[i,y]<-' '
   a.[x,j]<-' '
   a.[i,j]<-' '

Look for a plus. Find the one to the right of it. Find the one below it. Print out this rectangle's info, and 'null out' the pluses we already used. Since each plus is only a part of one valid rectangle, that's all we need to do.

Answer 2

Ruby — 306 260 245 228 168

# 228 chars
g=->(s,u='-'){o=[];s.scan(/\+#{u}+\+/){o<<[$`,$`+$&].map(&:size)};o}
b=t.map{|i|i.split''}.transpose.map{|s|g[s*'','\|']}
(1...t.size).map{|i|i.times{|j|(g[t[i]]&g[t[j]]).map{|x,y|p [x,j,y-x,i-j+1]if(b[x]&b[y-1]&[[j,i+1]])[0]}}}

produces

[0, 0, 3, 3]
[4, 1, 4, 3]
[10, 3, 3, 3]

for t=

["+-+       +--+",
"| | +--+  |  |",
"+-+ |  |  + -+",
"    +--+  +-+ ",
"  +--+    | | ",
"  +--+    +-+ "]

Explanation:

# function returns info about all inclusions of "+---+" in string
# "  +--+ +-+" -> [[2,5],[7,9]]
g=->(s,u='-'){o=[];s.scan(/\+#{u}+\+/){o<<[$`,$`+$&].map(&:size)};o}

# mapping transposed input with this function
b=t.map{|i|i.split''}.transpose.map{|s|g[s*'','\|']}
# earlier here was also mapping original input, but later was merged with "analyse"

# "analyse"
# take each pair of lines
(1...t.size).map{|i|i.times{|j|
    # find horizontal sides of the same length on the same positions
    (g[t[i]]&g[t[j]]).map{|x,y|
        # make output if there are correct vertical sides
        p [x,j,y-x,i-j+1]if(b[x]&b[y-1]&[[j,i+1]])[0]
    }
}}

# yeah, some strange +/-1 magick included ,.)

And more straight-forward 168-chars solution!

t.size.times{|i|t[0].size.times{|j|i.times{|k|j.times{|l|p [l,k,j-l+1,i-k+1]if
t[k..i].map{|m|m[j]+m[l]}*''=~/^\+\+\|+\+\+$/&&t[i][l..j]+t[k][l..j]=~/^(\+-+\+){2}$/}}}}

Answer 3

Scala 2.8 - 283 273 269 257

val a = Seq(
    "+-+ +--+  +--+",
    "| | |  |  |  |",
    "+-+ |  |  + -+",
    "    |  |      ",
    "    +--+  +-+ ",
    "  +--+    |   ",
    "  +--+    +-+ "
  )

// begin golf count
val (w,h) = (a(0).size-1,a.size-1)
for (
  x <- 0 to w;
  y <- 0 to h;
  u <- x+2 to w;
  v <- y+2 to h;
  if Set(a(y)(x),a(v)(x),a(y)(u),a(v)(u)) == Set(43)
  && (x+1 to u-1).forall(t => (a(y)(t)<<8|a(v)(t)) == 11565)
  && (y+1 to v-1).forall(t => (a(t)(x)<<8|a(t)(u)) == 31868)
) yield (x,y,u-x+1,v-y+1)
// end golf count

evaluates to :

Vector((0,0,3,3), (4,0,4,5))

The for expression evaluates to the answer (the Vector object), that is why I counted only this part (whitespaces removed). Let me know if this is the correct way to count.

How it works

The coordinates of all possible rectangles (actually, only >= 3x3) are generated by the for expression. These coordinates are filtered by looking for the +, - and | at the edges and corners of all rectangles (the if part of the for expression).

Answer 4

Python 2.6 - 287 263 254

a = [
    "+-+ +--+  +--+",
    "| | |  |  |  |",
    "+-+ |  |  + -+",
    "    |  |      ",
    "    +--+  +-+ ",
    "  +--+    |   ",
    "  +--+    +-+ "
    ]

l=len
r=range
w,h=l(a[0]),l(a)
[(x,y,u,v)for x in r(0,w)for y in r(0,h)for u in r(x+2,w)for v in r(y+2,h)if a[y][x]==a[v][x]==a[y][u]==a[v][u]=='+' and a[y][x+1:u]+a[v][x+1:u]=="-"*2*(u-x-1)and l([c for c in r(y+1,v-y)if a[c][x]==a[c][u]=='|'])==v-y-1]

evaluated to:

[(0, 0, 3, 3), (4, 0, 4, 5)]

Answer 5

Perl - 223 222 216

Golfed version (newlines not significant):

$y=0;sub k{$s=$-[0];"($s,%i;".($+[0]-$s).",%i)"}while(<>){while(/\+-+\+/g){
if(exists$h{&k}){push@o,sprintf k,@{$h{&k}};delete$h{&k}}else{$h{&k}=[$y,2]}}
while(/\|.+?\|/g){++${$h{&k}}[1]if exists$h{&k}}++$y}print"@o\n"

Older de-golfed version:

# y starts at line zero.
$y = 0;

# Abuse Perl's dynamic scoping rules
# to get a key for the hash of current rectangles,
# which indexes rectangles by x and width,
# and is also used as a format string.
sub k {

    # The start of the current match.
    $s = $-[0];

    # $+[0] is the end of the current match,
    # so subtract the beginning to get the width.
    "($s,%i;" . ($+[0] - $s) . ",%i)"

}

# Read lines from STDIN.
while (<>) {

    # Get all rectangle tops and bottoms in this line.
    while (/\+-+\+/g) {

        # If line is a bottom:
        if (exists $h{&k}) {

            # Add to output list and remove from current.
            push @o, sprintf k, @{$h{&k}};
            delete $h{&k}

        # If line is a top:
        } else {

            # Add rectangle to current.
            $h{&k} = [$y, 2]

        }

    }

    # Get all rectangle sides in this line.
    while (/\|.+?\|/g) {

        # Increment the height of the corresponding
        # rectangle, if one exists.
        ++${$h{&k}}[1] if exists $h{&k}

    }

    # Keep track of the current line.
    ++$y

}

# Print output.
print join", ",@o

Note that this does not handle junk vertical bars to the left of the rectangles, that is:

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

Will incorrectly yield a height of 2 for both. This is because the /\|.+?\|/g pattern starts searching from the beginning of the line. Anyone have a suggestion for how to fix this?

Answer 6

XQuery (304 characters)

Here is my solution:

declare variable $i external;let$w:=string-length($i[1]),$h:=count($i)for$y in 1 to$h,$x in 1 to$w,$w in 2 to$w+1 -$x,$h in 1 to$h where min(for$r in (0,$h),$s in 1 to$h return (matches(substring($i[$y+$r],$x,$w),'^\+-*\+$'),matches(substring($i[$y+$s],$x,$w),'^|.*|$')))return ($x -1,$y -1,$w,$h+1,'')

You can run this (with XQSharp) by setting the variable $i to be the lines of the input

>XQuery boxes.xq "i=('  +-+','+-+-+','| |  ','+-+  ')" !method=text

2 0 3 2  0 1 3 3

I suppose one could argue that declare variable $i external; is just setting up the input and so doesn't add to the count, in which case 275 characters

Answer 7

Perl, 167 165 159 chars

(156 chars if you don't count slurping stdin to @a, just remove the last 3 chars and assign a list of strings representing your input to @a)

Gets input from stdin. Newlines not significant, added for readability. Notice the use of the +++ operator ;P

map{$l=$i++;while($c=/\+-+\+/g){$w=$+[0]-2-($x=$-[0]);
$c++while$a[$l+$c]=~/^.{$x}\|.{$w}\|/;
print"($x,$l;",$w+2,",$c)\n"if$a[$c+++$l]=~/^.{$x}\+-{$w}\+/}}@a=<>

Be liberal in what you accept version, 170 chars

map{$l=$i++;while($c=/\+-*\+/g){pos=-1+pos;$w=$+[0]-2-($x=$-[0]);
$c++while$a[$l+$c]=~/^.{$x}\|.{$w}\|/;
print"($x,$l;",$w+2,",$c)\n"if$a[$c+++$l]=~/^.{$x}\+-{$w}\+/}}@a=<>

Be conservative in what you accept version, 177 chars

map{$l=$i++;while($c=/\+-+\+/g){$w=$+[0]-2-($x=$-[0]);
$c++while$a[$l+$c]=~/^.{$x}\|.{$w}\|/;print
"($x,$l;",$w+2,",$c)\n"if$c>1&&$a[$c+++$l]=~s/^(.{$x})\+(-{$w})\+/$1v$2v/}}@a=<>

Commented version:

@a=<>;          # slurp stdin into an array of lines
$l=0;           # start counting lines from zero
map{            # for each line
    while(/\+-+\+/g){               # match all box tops
            $c=1;                           # initialize height

            # x coordinate, width of box - sides
            $w=$+[0]-2-($x=$-[0]);

            # increment height while there are inner parts
            # of a box with x and w coinciding with last top
            # (look into next lines of array)
            $c++  while $a[$l+$c]=~/^.{$x}\|.{$w}\|/;

            # if there is a box bottom on line + height
            # with coinciding x and w, print coords
            # (after incrementing height)
            print "($x,$l;",$w+2,",$c)\n"  
                    if $a[$c+++$l]=~/^.{$x}\+-{$w}\+/
    }
    $l++    # line++
}@a

Mega test case:

+--+  +-+ +-+  +++   +---+   +-+  +-+-+  +-++-+
|SO|  | | | |  +++   |+-+|   | |  | | |  | || |
+--+  +-+-+-+  +++   ||+||   +-+  +-+-+  +-++-+
        | |          |+-+|   | |
      +-+-+-+        +---+   +-+
      | | | |
      +-+ +-+


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

Answer 8

C (204 186 Characters)

    #include<stdio.h>
    char H=7,W=14,*S =
    "+-+ +--+  +--+"
    "| | |  |  |  |"
    "+-+ |  |  + -+"
    "    |  |      "
    "    +--+  +-+ "
    "  +--+    |   "
    "  +--+    +-+ ";
    void main(){
#define F(a,r,t)if(*c==43){while(*(c+=a)==r);t}
char*c,*o,*e=S;while(*(c=e++))
F(1,45,F(W,'|',o=c;F(-1,45,F(-W,'|',c==e-1?
printf("%i,%i %i,%i\n",(c-S)%W,(c-S)/W,(o-c)%W+1,(o-c)/W+1):0;))))
    }

The character count is the body of main(). This code will walk the string with e until it reaches the top-left corner of a potential rectangle. It will then check the edges with c and using o to keep track of the bottom-right corner.

Output of the program is:

0,0 3,3
4,0 4,5
2,5 4,2