Code Golf:识别ascii艺术盒

Question

不久之前做了一些数据结构工作时提出了这个问题,虽然它是一个很好的代码高尔夫:给定一个包含ascii艺术矩形的二维字符数组,生成一个矩形的坐标和大小列表.

• 任何简单的可转换输入或输出格式都很好(例如:char**,字符串列表,标准输入上的行;四个整数列表,结构,固定数量+/-表示大小;等等).
• 同样,输出不必按任何特定顺序排列.
• 对于无效输入或格式错误的矩形,您没有任何有用的东西,但是您不应该为输入中不存在的矩形生成有效的坐标.
• 没有两个有效的矩形共享一个+(虽然+可能不仅仅是矩形的一部分)
• 您可以假设所有矩形至少为3x3:每个边都有一个-或|在其中.

例子:

"        "
"  +-+ | "
"  | | \-"
"  +-+   "
(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

Perl,167 165 159字符

(156个字符如果你不计算stdin到@a,只需删除最后3个字符并指定一个代表你输入的字符串列表给@a)

从stdin获取输入.新线不重要,为了便于阅读而添加.注意+++操作员的使用; 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=<>

在你接受的版本,170个字符是自由的

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

保守你所接受的版本,177个字符

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

评论版:

@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

超级测试用例:

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


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

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

产生

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

对于t =

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

说明:

# 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 ,.)

更直接的168字符解决方案!

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

Perl - 223 222 216

高尔夫版(换行不重要):

$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"

较旧的脱皮版本:

# 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

请注意,这不会处理矩形左侧的垃圾垂直条,即:

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

两者都会错误地产生2的高度.这是因为/\|.+?\|/g模式从行的开头开始搜索.有人建议如何解决这个问题？

Answer 4

JavaScript - 156个字符*

也可以在http://jsfiddle.net/eR5ee/4/(只有点击链接,如果使用Firefox或Chrome)或http://jsfiddle.net/eR5ee/5/(适用于Safari和Opera):

var A = [
    "+-+ +--+  +--+",
    "| | |  |  |  |",
    "+-+ |  |  + -+",
    "    |  |      ",
    "    +--+  +-+ ",
    "  +--+    |   ",
    "  +--+    +-+ "
    ]; // not counted

for(y=A.length;--y;)for(;m=/\+-*\+/g(A[y]);){
for(w=m[0].length,z=y;A[--z][x=m.index]+A[z][x+w-1]=="||";);
/^\+-*\+$/(A[z].substr(x,w))&&alert([x,z,w,y-z+1])}

• 排除换行符和空白字符,这是完全没必要的.
• 显然,Firefox和Chrome保留了第一个正则表达式的lastIndex.还需要四个字符才能使Safari和Opera无法循环.要使Internet Explorer正常工作,还需要十四个字符才能解决上述问题和"预期的功能"错误.显然,"...正则表达式的exec方法可以被称为...间接(带regexp(str))"(引自Mozilla文档)不适用于IE.

如果没有矩形的底部接触任何其他矩形的顶部或底部或加号或减号且没有重叠,则代码检测所有矩形2x2和​​更大.

每个警报框中的数字顺序(对应于一个矩形)是左,顶部,宽度,高度.如果一个矩形从顶部延伸出来,代码会出错,但是所有需要的坐标都已经输出了(来自规范:"你没有(原文如此)对无效输入或格式错误的矩形有用的东西......")

由于大多数主要的Web浏览器都实现了canvas标记,因此在几行代码中,可以在屏幕上绘制检测到的矩形.http://jsfiddle.net/MquqM/6/适用于除Internet Explorer和Opera之外的所有浏览器.

编辑:删除不必要的变量赋值编辑2:避免使用完全有效的输入抛出错误( - 而不是y--),澄清代码处理的具体情况

Answer 5

F#，297 个字符

有点蹩脚，但很简单。

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

寻找一个加号。找到它右边的那个。找到它下面的那个。打印出这个矩形的信息，并“清空”我们已经使用的加号。由于每个加号只是一个有效矩形的一部分，因此这就是我们需要做的。