逆向工程师支架矩形

Question

每个程序员都知道矩形□非常有趣。为了加剧这种乐趣，这些可爱而模糊的图表可以转换成一组交织在一起的括号。

这个挑战是逆我以前的。

假设您有一组联锁矩形，如下所示：

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

附加说明：

• 没有两位+s会毗邻
• 任何两个矩形都不会共享边或角。
• 每列最多只有一条垂直边。

第一步是查看任何矩形的最左边的边缘。给它分配四种括号类型中的一种({[<。我选择[。

   +------------+
   |            |
[--+-]     +----+-+
[  | ]     |    | |
[  | ] +---+--+ | |
[  | ] |   |  | | |
[--+-] | +-+--+-+-+-+
   |   | | |  | | | |
   |   | | |  | | | |
   |   | | |  | | | |    +-+
   |   +-+-+--+ | | |    | |
   |     | |    | | |  +-+-+-+
   +-----+-+----+ | |  | | | |
         | |      | |  | +-+ |
         | +------+ |  |     |
         |          |  |     |
         +----------+  +-----+

现在看第二个最左边的矩形。由于它与[矩形重叠，所以它必须是不同的类型。我选择(。

   (------------)
   (            )
[--(-]     +----)-+
[  ( ]     |    ) |
[  ( ] +---+--+ ) |
[  ( ] |   |  | ) |
[--(-] | +-+--+-)-+-+
   (   | | |  | ) | |
   (   | | |  | ) | |
   (   | | |  | ) | |    +-+
   (   +-+-+--+ ) | |    | |
   (     | |    ) | |  +-+-+-+
   (-----+-+----) | |  | | | |
         | |      | |  | +-+ |
         | +------+ |  |     |
         |          |  |     |
         +----------+  +-----+

下一个最左边的矩形不与以前的任何矩形相交，而是在前一个矩形内嵌套。我选择再次指定它为(。如果可能的话，给矩形分配与其嵌套类型相同的类型通常是一个很好的猜测，但有时需要回溯。

   (------------)
   (            )
[--(-]     +----)-+
[  ( ]     |    ) |
[  ( ] (---+--) ) |
[  ( ] (   |  ) ) |
[--(-] ( +-+--)-)-+-+
   (   ( | |  ) ) | |
   (   ( | |  ) ) | |
   (   ( | |  ) ) | |    +-+
   (   (-+-+--) ) | |    | |
   (     | |    ) | |  +-+-+-+
   (-----+-+----) | |  | | | |
         | |      | |  | +-+ |
         | +------+ |  |     |
         |          |  |     |
         +----------+  +-----+

可以再次为下一个矩形分配[。

   (------------)
   (            )
[--(-]     +----)-+
[  ( ]     |    ) |
[  ( ] (---+--) ) |
[  ( ] (   |  ) ) |
[--(-] ( [-+--)-)-+-]
   (   ( [ |  ) ) | ]
   (   ( [ |  ) ) | ]
   (   ( [ |  ) ) | ]    +-+
   (   (-[-+--) ) | ]    | |
   (     [ |    ) | ]  +-+-+-+
   (-----[-+----) | ]  | | | |
         [ |      | ]  | +-+ |
         [ +------+ ]  |     |
         [          ]  |     |
         [----------]  +-----+

下一个长方形很有趣。它与(和[矩形相交，所以我可以称它为{矩形(或<，但没有人喜欢这些矩形)。

   (------------)
   (            )
[--(-]     {----)-}
[  ( ]     {    ) }
[  ( ] (---{--) ) }
[  ( ] (   {  ) ) }
[--(-] ( [-{--)-)-}-]
   (   ( [ {  ) ) } ]
   (   ( [ {  ) ) } ]
   (   ( [ {  ) ) } ]    +-+
   (   (-[-{--) ) } ]    | |
   (     [ {    ) } ]  +-+-+-+
   (-----[-{----) } ]  | | | |
         [ {      } ]  | +-+ |
         [ {------} ]  |     |
         [          ]  |     |
         [----------]  +-----+

最后两个长方形没那么差。它们可以是任意两种不同的类型。

   (------------)
   (            )
[--(-]     {----)-}
[  ( ]     {    ) }
[  ( ] (---{--) ) }
[  ( ] (   {  ) ) }
[--(-] ( [-{--)-)-}-]
   (   ( [ {  ) ) } ]
   (   ( [ {  ) ) } ]
   (   ( [ {  ) ) } ]    {-}
   (   (-[-{--) ) } ]    { }
   (     [ {    ) } ]  <-{-}->
   (-----[-{----) } ]  < { } >
         [ {      } ]  < {-} >
         [ {------} ]  <     >
         [          ]  <     >
         [----------]  <----->

读取矩形，我得到[(]([{))}]<{}>**.**，这将是上面输入的一个可能的输出。下面列出了许多可能的选择，但并非详尽无遗：

[(]([{))}]<{}>
<(>(<{))}>{()}
{<}[{(]>)}[<>]
any of the 4! permutations of ([{<, you get the idea...

输入

ASCII-艺术矩形，假设它们是明确的(见上面的注释)，可以正确地转换成一个括号字符串。您可以假设没有尾随空格或填充到矩形，并带有可选的尾换行符。将没有前导空格。

输出

任何一个有效的括号字符串，它们都遵守矩形的相交限制。除了可选的尾换行符之外，不应该有除括号以外的其他字符。主要规则是，如果两个正方形相交，那么它们应该被指定不同的括号类型。

目标

这是代码-高尔夫，(缺乏)数量超过质量。

Answer 1

Python3519字节

def c(i):
 a,b,c,d={},0,[],{}
 for e in map("".join,zip(*i.split("\n"))):
  if"+"in e:
   f=e.index("+"),e.rindex("+")
   if f in a:j=a.pop(f);d[j]=f+(d[j],len(c));c.append(j)
   else:a[f]=b;d[b]=len(c);c.append(b);b+=1
 g,h={},0
 while d:
  i={list(d)[0]};
  for j,(k,l,m,n)in d.items():
   for(o,p,q,r)in(d[v]for v in i):
    if not(m>r or n<q or k>p or l<o or(q<m<n<r and o<k>l<p)):break
   else:i.add(j)
  for j in i:del d[j];g[j]=h
  h+=1
 s,u=set(),""
 for t in c:u+="[{(<]})>"[g[t]+4*(t in s)];s.add(t)
 return u

这是解决方案的第一次尝试。所使用的算法纯粹查看图表中的角点，滥用了一个事实，即在列中只能出现一条垂直线，因此列中的第一个和最后一个+必须是矩形的角。然后，它收集所有矩形，并对无冲突组执行天真(且有些不确定)的搜索。我不确定这是否总能找到最理想的解决方案，但它适用于我迄今尝试过的所有例子。或者，可以用蛮力搜索最少的群体来代替它。

输入:包含ascii艺术的字符串。没有尾随换行符，所有行都必须使用空格填充到相同的长度。如果你不把“S”或-“S”放进去，那也是完全没有问题的，因为它只是看着角落。

由于高尔夫是相当简单的(只是空格最小化和变量重命名大部分)，它可能会更短，但由于没有其他的答案，但我将保留到目前为止。