14

前段时间在做一些数据结构工作时想到了这个，尽管它会成为一个很好的代码高尔夫：给定一个包含 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
4

10 回答 10

7

Perl，167 165 159 个字符

（156个字符，如果你不把标准输入计算到@a，只需删除最后3个字符并将代表你输入的字符串列表分配给@a）

从标准输入获取输入。换行不重要，为了可读性而添加。注意+++运算符的使用；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|  | | | |  +++   |+-+|   | |  | | |  | || |
+--+  +-+-+-+  +++   ||+||   +-+  +-+-+  +-++-+
        | |          |+-+|   | |
      +-+-+-+        +---+   +-+
      | | | |
      +-+ +-+


++ +-+ ++     +-+   +- + +--+ +--+ +--+
|| +-+ ++   +-+-+   |  | |  | |    |  |
++          | |     |  | |  | |  |    |
            +-+     +--+ + -+ +--+ +--+
于 2010-09-14T18:25:24.130 回答
6

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模式从行首开始搜索。有人对如何解决这个问题有建议吗？

于 2010-09-13T16:39:25.420 回答
6

红宝石 — 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}$/}}}}
于 2010-09-11T09:19:45.960 回答
5

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 正常工作，还需要 14 个字符来修复上述问题和“预期功能”错误。显然，“...可以调用正则表达式的 exec 方法...间接（使用regexp(str)）”（引自 Mozilla 文档）不适用于 IE。

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

每个警报框（对应于一个矩形）中的数字顺序为left、top、width、height。如果矩形从顶部延伸出来，代码会出错，但所有需要的坐标都已经输出（来自规范：“你不必（原文如此）任何对无效输入或格式错误的矩形有用的东西......”）

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

编辑：消除了不必要的变量赋值 编辑 2：避免使用完全有效的输入（--y 而不是 y--）引发错误，阐明代码处理的具体情况

于 2010-09-30T02:39:19.673 回答
4

C（204 186 个字符）

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

字符数是 main() 的主体。此代码将使用e遍历字符串，直到它到达潜在矩形的左上角。然后它将使用c检查边缘并使用o来跟踪右下角。

程序的输出是：

0,0 3,3
4,0 4,5
2,5 4,2
于 2010-09-15T02:59:01.013 回答
3

Python 2.6（251 个字符）

我来的有点晚，反正也挺好玩的。Python，使用正则表达式。为了保存打印 语句并保持比 Fredb219 短，如果您将其作为脚本运行，则不会打印任何内容，但在解释器中一次输入一行将显示结果。不是很可靠，它不会处理嵌套框，也不会处理比 DavidX 给出的更复杂的大多数情况。尚未完成测试，但我认为如果发生“奇怪”的事情，它可能会以错误的顺序显示结果。

import re
l,a,o=s.index("\n")+1,re.finditer,sorted
o(o(set((m.start(),m.end())for m in a(r'\+-* *-*\+',s)for n in a(r'\|.+\|',s)if(m.start()%l,m.end()%l)==(n.start()%l,n.end()%l)if m.start()+l==n.start()or m.start()-l==n.start())),key=lambda x:x[0]%l)

输入是单个字符串，行（长度相同）由换行符分隔。结果是每个“好”框的顶部和底部的字符串切片，从左上角开始。它还允许“破碎”的盒子（即在一侧中间有一些空间，而不是没有整个一侧）。这只是一种修复不良行为的方法，会产生许多全新的副作用！:-)

输入：

>>>s = """+-+ +--+  +--+
| | |  |  |  |
+-+ |  |  + -+
    |  |      
    +--+  +-+ 
  +--+    |   
  +--+    +-+ """

或者：

>>>s = "+-+ +--+  +--+\n| | |  |  |  |\n+-+ |  |  + -+\n    |  |      \n    +--+  +-+ \n  +--+    | \n  +--+    +-+ "

然后：

>>>import re
>>>l,a,o=s.index("\n")+1,re.finditer,sorted
>>>o(o(set((m.start(),m.end())for m in a(r'\+-* *-*\+',s)for n in a(r'\|.+?\|',s)if(m.start()%l,m.end()%l)==(n.start()%l,n.end()%l)if m.start()+l==n.start()or m.start()-l==n.start())),key=lambda x:x[0]%l)

输出：

[(0, 3), (30, 33), (4, 8), (64, 68), (10, 14), (40, 44)]

所以（0,3）第一个盒子的顶部（30,33）同一个盒子的底部，（4,8）第二个盒子的顶部等等。

于 2011-01-19T18:46:28.087 回答
3

蟒蛇 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]

评估为：

[(0, 0, 3, 3), (4, 0, 4, 5)]
于 2010-09-13T13:35:27.907 回答
3

斯卡拉 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

评估为：

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

该for表达式的计算结果为答案（Vector 对象），这就是为什么我只计算了这部分（删除了空格）。让我知道这是否是正确的计数方法。

这个怎么运作

所有可能的矩形（实际上，只有 >= 3x3）的坐标都是由for表达式生成的。这些坐标通过查找 +、- 和 | 进行过滤。在所有矩形的边缘和角落（表达式的if一部分）。for

于 2010-09-11T18:52:37.383 回答
2

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

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

于 2010-09-10T02:19:32.683 回答
2

XQuery（304 个字符）

这是我的解决方案：

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,'')

您可以通过将变量设置为输入的行来运行它（使用XQSharp ）$i

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

2 0 3 2  0 1 3 3

我想有人可能会争辩说这declare variable $i external;只是设置输入，因此不会增加计数，在这种情况下为275 个字符

于 2010-09-13T19:03:26.523 回答