14

少し前にデータ構造の作業を行っているときにこれを思いつきましたが、これは良いコード ゴルフになります。アスキー アートの四角形を含む文字の 2 次元配列が与えられた場合、四角形の座標とサイズのリストを作成します。

  • 自明に変換可能な入力または出力形式であれば問題ありません (例: char**、文字列のリスト、標準入力の行、4 つの int のリスト、構造体、サイズの固定量 +/- など)。
  • 同様に、出力は特定の順序である必要はありません。
  • 無効な入力または不正な形式の四角形に役立つものは何も必要ありませんが、入力にない四角形に対して有効に見える座標を生成するべきではありません。
  • 2 つの有効な長方形が 1 つを共有することはありません+(ただし+、長方形の一部としてのみ表示されるわけではありません)。
  • すべての長方形は少なくとも 3x3 であると想定できます。各辺には-or|があります。

例:

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

( @a への stdin の丸呑みをカウントしない場合は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=<>


コメント付きバージョン:

@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

ルビー— 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 に答える
6

パール - 223 222 216

Golfed バージョン (改行は重要ではありません):

$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 に答える
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 が無限ループに陥らないようにするには、さらに 4 文字必要です。Internet Explorer を動作させるには、上記のエラーと "Function expected" エラーの両方を修正するために、さらに 14 文字が必要です。どうやら、「... 正規表現の exec メソッドを ... 間接的に (with で) 呼び出すことができるregexp(str)」(Mozilla のドキュメントから引用) は IE には適用されません。

四角形の下部が他の四角形の上部または下部、またはプラス記号またはマイナス記号に接しておらず、重なっていない場合、コードは 2x2 以上のすべての四角形を検出します。

各アラート ボックス (長方形に対応) の数字の順序は、lefttopwidthheightです。長方形が上からはみ出している場合、コードはエラーになりますが、必要なすべての座標が既に出力されています (仕様から: 「無効な入力または不正な長方形に役立つものは何もする必要はありません...」)

ほとんどの主要な 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

スカラ 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 に答える
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

Python 2.6 (251 文字)

とにかく、少し遅れて到着します。Python、正規表現を使用。printステートメントを保存し、 Fredb219 のものよりも短くするために、スクリプトとして実行しても何も出力されませんが、インタープリターで一度に 1 行ずつ入力すると、結果が表示されます。あまり堅実ではなく、ネストされたボックスや、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) 1 番目のボックスの上部 (30,33) 同じボックスの下部、(4,8) 2 番目のボックスの上部など。

于 2011-01-19T18:46:28.087 に答える
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 つの有効な四角形の一部に過ぎないため、必要な処理はこれだけです。

于 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 に答える