logo标签列表

代码高尔夫：识别ASCII艺术框

language-agnosticcode-golfascii-art
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
1
不充分。‘+’符号是否可以成为多个矩形的一部分？输出顺序是否重要？ - Brian
@Brian，1a：不需要更改；1b：只要输出格式的更改是微不足道的就可以了；2：我想集中精力研究算法，而不是输入/输出。 - David X
@Mark，相邻的矩形将有一个（实际上是2个）+，它们都是它们的一部分，所以不行。我会让实现决定是否要处理嵌套的矩形，但允许它们应该不难。 - David X
1
大矩形能够包含小矩形吗？ - Brian
2
Ascii艺术？你想让我们编程让计算机成为一个艺术评论家吗？哈哈哈！<G> - Loren Pechtel
显示剩余5条评论
10个回答
7

Perl, 167 165 159个字符

(如果不将stdin读入@a中，则仅有156个字符，只需删除最后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=<>


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


超级测试用例：

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


++ +-+ ++     +-+   +- + +--+ +--+ +--+
|| +-+ ++   +-+-+   |  | |  | |    |  |
++          | |     |  | |  | |  |    |
            +-+     +--+ + -+ +--+ +--+
我没有Perl解释器来测试。所以，请解释一下，$i 的初始化在哪里？Perl是否允许注意到所有变量在开始时都是0？ - Nakilon
some_loop_construct{$l=$i++;...} 是我压缩后的 $l=0;some_loop_construct{...;$l++} 版本。在 Perl 中，变量在赋值之前是未定义的，这会导致像 (1,0;0,2) 这样的坐标打印为 (1,;,2)（当作为数字使用时，undef 被视为 0，当作为字符串使用时，被视为空字符串）。 - ninjalj
6

Perl - 216

这是一个高压缩版本的Perl代码（换行不重要）：

$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模式从行的开头开始搜索。有没有人有修复这个问题的建议？

在 /\|.+?\|/g 模式的开头添加一些 . 应该可以解决对垃圾 | 的处理问题，但我不太了解 Perl 如何实现。 - David X
利用松散的输出限制，节省了一些字符。 - Jon Purdy
6

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}$/}}}}
你能解释一下这段代码发生了什么吗？另外，->语法是什么意思？它是声明匿名函数的一种方式吗？ - barjak
在 Ruby 中，你不能将函数（例如 map）定义为变量吗？ - chelmertz
@barjak：1）f（或当前版本中的g）在字符串中生成+---+子字符串列表；程序为原始输入和转置生成这些映射，然后分析它们。2）是的，这是匿名函数。f=-> {}只是比def f end更短。 - Nakilon
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及以上的矩形。

每个警报框中数字的顺序（对应一个矩形）是左侧、顶部、宽度、高度。如果矩形向上延伸，代码会出错，但所有需要的坐标已经输出（根据规范：“对于无效输入或格式错误的矩形，您不必(sic)提供任何有用的信息...”）

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

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

应该是--y而不是y--吗？ - ninjalj
任何一种都可以；只是要看是否可以接受代码在有效输入时抛出错误。我正在更改上面的代码以避免这种情况。 - PleaseStand
4

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

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

程序的输出为：

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

Python 2.6

我来晚了，但还是想分享一些有趣的东西。使用正则表达式在 Python 中可以省略一些 print 语句，并且比 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) 是第二个方框的顶部，以此类推。

2.6（或您的Python安装）有什么奇怪的问题吗？我在2.5和2.7上得到了一个空列表。 - David X
@DavidX：没什么奇怪的，你是对的。我以为是因为在输入字符串开头插入了一个换行符，但即使我修复了它，还是出了问题。现在我从我的源代码中重新复制了所有内容，看起来一切都正常了。 - MattiaG
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

评估结果为：

Vector((0,0,3,3), (4,0,4,5))
< p > for表达式评估答案（Vector对象），这就是我只计算此部分的原因（删除空格）。如果这是正确的计数方式，请告诉我。

工作原理

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

我认为有一种简化模式v1 == 45 && v2 == 45的方法，但我找不到。有什么想法吗？ - barjak
v1 == v2 == 45 有意义吗？我几乎不会读Scala，所以我不知道如何将其塞进去。 - Esko
@Esko 在Scala中没有复合条件，这样是行不通的。我在考虑一个算术技巧或位运算，但是找不到一个。 - barjak
1
v1*256 + v2 == ... 或者甚至可以写成 v1<<8 | v2 == ... - Nakilon
3

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]

评估结果为：

[(0, 0, 3, 3), (4, 0, 4, 5)]
+1 因为你和我使用了相同的算法，所以你有很好的品味！ - barjak
括号可以省略 w,h = len(a[0]),len(a)。赋值 r=range 并调用 r() 代替...但这有点不完整...关于 a 的代码在哪里？ - st0le
a与Scala代码相同。我已经修复了，谢谢。 - Niavok
你可以链接比较，例如'+'==a[y][x]==a[v][x]==a[y][u]==a[v][u]可以节省一些字符。 - John La Rooy
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,'')

您可以通过设置变量$i为输入的行数（使用XQSharp）来运行此操作。

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

2 0 3 2  0 1 3 3

我认为可以这样说，declare variable $i external;只是设置输入，并不增加计数，因此275个字符

这是一个非常不错的测试用例。希望你不介意我在我的答案中使用它作为测试用例。 - ninjalj
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]<-' '

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

1
这将为无效的矩形生成输出，例如“-”或“|”字符不存在，或者左侧或底部不存在。 - Andrew Cooper
2
规范不允许这样做。它说：“'+' 只能作为一个有效矩形的一部分出现”。这似乎意味着没有任何与无效/不完整的矩形相连的 '+' 字符。 - Brian
我读到的意思是，这句话的意思是没有第二个包含相同+的有效矩形。它并没有说没有其他出现（作为无效矩形的一部分，作为有效三角形的一部分，独立存在等）。 - Nas Banov
@Nas Banov，这就是我想说的，但显然比我预期的要难做到。 - David X
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接