Eine meiner mathematischen Lieblingsbeschäftigungen ist es, ein rechteckiges Gitter zu zeichnen und dann alle Rechtecke zu finden, die in diesem Gitter sichtbar sind. Hier, nimm diese Frage und wage es selbst!

Können Sie die Anzahl der Rechtecke zählen?

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

Die Gesamtzahl der Rechtecke für dieses 4 x 4 Minischachbrett ist genau

100

Hattest du recht

^{Verwandte Mathematik: Wie viele Rechtecke befinden sich auf einem 8 × 8-Schachbrett?}

Die Herausforderung

Schreiben Sie die kürzeste Funktion / das kürzeste Programm , das die Gesamtzahl der sichtbaren Rechtecke auf einem nicht torusförmigen Gitter / Bild zählt .

^{Verwandte Herausforderungen: Zähle die einzigartigen Rechtecke! , Finden Sie die Anzahl der Rechtecke in einem 2D-Byte-Array .}

Eingabeformat

Ihre Funktion oder Ihr Programm kann entweder mit textbasierter Eingabe oder mit grafischer Eingabe arbeiten.

Textbasierte Eingabe

Das Raster ist ein m- by- n ( m Zeilen, n Spalten) ASCII-Raster, das aus den folgenden Zeichen besteht:

• Räume,
• - für Teile eines horizontalen Liniensegments,
• | für Teile eines vertikalen Liniensegments und
• + für ecken.

Sie können dieses ASCII-Raster als Eingabe / Argument in Ihr Programm / Ihre Funktion in Form von einfügen

• eine einzelne Zeichenfolge, die durch Zeilenumbrüche begrenzt ist,
• eine Zeichenfolge ohne Zeilenumbrüche, jedoch mit ein oder zwei Ganzzahlen, die die Dimensionen des Rasters codieren, oder
• ein Array von Zeichenfolgen.

^{Hinweis: Die textbasierte Eingabe enthält mindestens 1 Zeile und mindestens 1 Spalte.}

Grafische Eingabe

Alternativ werden die Gitter als Schwarzweiß- PNG- Bilder mit einer Breite von 5 · n Pixeln und einer Höhe von 5 · m Pixeln codiert . Jedes Bild besteht aus 5 px * 5 px- Blöcken, die der ASCII-Eingabe entsprechen durch:

• Leerzeichen werden in weiße Blöcke umgewandelt. Diese Blöcke werden als Whitespace- Blöcke bezeichnet.
• Liniensegmente und Ecken werden in Blöcke ohne Leerzeichen konvertiert . Das zentrale Pixel solcher Blöcke ist schwarz.
• Bearbeiten: Wenn zwei Ecken (in der ASCII-Eingabe) durch ein Liniensegment verbunden sind, sollten die entsprechenden Blockmitten (in der grafischen Eingabe) ebenfalls durch eine schwarze Linie verbunden werden.

Dies bedeutet, dass jeder Block nur ausgewählt werden kann (Klicken Sie hier für ein größeres Bild) .

^{Hinweis: Die blauen Grenzen dienen nur zur Veranschaulichung. Die grafische Eingabe ist mindestens 5 px breit und 5 px hoch. Sie können die grafische Eingabe in ein beliebiges monochromes Bild konvertieren (möglicherweise in ein anderes Bilddateiformat). Wenn Sie konvertieren möchten, geben Sie dies bitte in der Antwort an. Es gibt keine Konversionsstrafe.}

Ausgabeformat

Wenn Sie ein Programm schreiben, muss es eine nicht negative Zahl anzeigen, die die Gesamtzahl der Rechtecke in der Eingabe angibt.

Wenn Sie eine Funktion schreiben, sollte auch eine nicht negative Zahl zurückgegeben werden, die die Gesamtzahl der Rechtecke in der Eingabe angibt.

Beispielfälle

Fall 1, Grafik: ( 30 px * 30 px), ASCII: ( 6 Zeilen, 6 Spalten)

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

Erwartete Ausgabe: 3

Fall 2, Grafik: ( 20 px * 20 px), ASCII: ( 4 Zeilen, 4 Spalten)

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

Erwartete Ausgabe: 6

Fall 3, Grafik: ( 55 px * 40 px), ASCII: ( 8 Zeilen, 11 Spalten)

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

Erwartete Ausgabe: 9

Fall 4, Grafik: ( 120 px * 65 px), ASCII: ( 13 Zeilen, 24 Spalten)

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

Erwartete Ausgabe: 243

Fall 5, Grafik: ( 5 px * 5 px. Ja, es ist da!), ASCII: Nur ein Leerzeichen.

Erwartete Ausgabe: 0

Fall 6, Grafik: ( 35 px * 20 px), ASCII: ( 4 Zeilen, 7 Spalten)

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

Erwartete Ausgabe: 5

Annahmen

Um Ihnen das Leben zu erleichtern, ist Folgendes garantiert:

• Durch die atorischen , wird das Gitter nicht entweder horizontal oder vertikal wickeln.
• Es gibt keine losen Enden, zum Beispiel +--- oder +- -+. Alle Liniensegmente haben zwei Enden.
• Zwei Linien, die sich bei treffen, +müssen sich an diesem Punkt schneiden.
• Sie müssen sich nicht um ungültige Eingaben kümmern.

Es gelten Regeln gegen Standardlücken. Bitte behandeln Sie Quadrate als Rechtecke. Optional können Sie die nachgestellten Leerzeichen in jeder Zeile des Rasters entfernen.

^{Dies ist Code-Golf , also machen Sie Ihre Eingabe so kurz wie möglich. Textbasierte und grafische Lösungen werden miteinander konkurrieren.}

Bestenliste

var QUESTION_ID=137707,OVERRIDE_USER=11933;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Schmutz , 31 28 Bytes

T=\+[+\-]*\+/[+|]/+$
n`T&To2

Probieren Sie es online!

Übernimmt Eingaben im ASCII-Format.

Erläuterung

Die Syntax von Grime kommt regulären Ausdrücken sehr nahe. Jede Zeile definiert ein Muster, das mit einem Rechteck von Zeichen übereinstimmen kann oder nicht. TStimmt mit einem Rechteck überein, dessen obere Zeile und linke Spalte gültig aussehen.

T=\+[+\-]*\+/[+|]/+$
T=                    Define T as
  \+[+\-]*\+          a row that matches this regex
            /         and below that
             [+|]/+   a column of + or |
                   $  with anything to its right.

Die zweite Zeile ist das "Hauptprogramm".

n`T&To2
n`       Print number of rectangles that match
  T      the pattern T
   &     and
    To2  T rotated 180 degrees.

JavaScript (ES6), 176 171 Bytes

g=a=>Math.max(...b=a.map(a=>a.length))-Math.min(...b)?``:f(a);f=
a=>a.map((b,i)=>[...b].map((_,j)=>n+=a.join`
`.split(eval(`/\\+(?=[-+]{${j}}\\+[^]{${l=b.length+~j}}([|+].{${j}}[|+][^]{${l}}){${i}}\\+[-+]{${j}}\\+)/`)).length>>1),n=0)|n

<textarea rows=8 cols=8 oninput=o.textContent=g(this.value.split`\n`)></textarea><pre id=o>

Nimmt die Eingabe als Array von Zeichenfolgen gleicher Länge. Erläuterung: Erstellt eine Reihe von regulären Ausdrücken, die mit Rechtecken aller möglichen Breiten und Höhen (und einigen unmöglichen Breiten und Höhen, aber das ist Code Golf für Sie) übereinstimmen, und zählt, wie viele Übereinstimmungen sie alle erzeugen. Da es in der regexp, eine Erfassungsgruppe ist splitRenditen 2n+1für nStreichhölzer, so dass ich Verschiebung nach rechts um 1 die Anzahl der Spiele zu erhalten, da das ein Byte speichert über so dass die Gruppe nicht-Capturing.

J , 103 95 86 80 76 70 Bytes

[:+/@,]*/@('-|++'*/@(e.,&'+')~&>]({.,{:)&.>@;|:;{.;{:);._3"$~2+$#:i.@$

Probieren Sie es online!

Nimmt Eingaben als ein Array von Zeichenfolgen mit nachgestellten Leerzeichen an (sodass jede Zeichenfolge dieselbe Größe hat). Verwendet den vollständigen Subarray-Operator ;._3, um über jede mögliche Subarray-Größe zu iterieren, die größer als 2 x 2 ist, und zählt die Subarrays, die gültige Rechtecke sind. Schließt alle Testfälle fast sofort ab.

Mathematica, 136 134 132 Bytes

S=Tr@*Flatten;S@Table[1-Sign@S@{d[[{i,j},k;;l]],d[[i;;j,{k,l}]]},{i,($=Length)[d=ImageData@#]},{j,i+1,$@d},{k,w=$@#&@@d},{l,k+1,w}]&

Verwendung: (für alte 136-Byte-Version, aber die neue Version ist im Grunde identisch)

Hinweis:

• Dies läuft in der Zeit O (m ² n ² max (m, n)), verwenden Sie also nur kleine Eingänge.
• Obwohl dies mit binären Bildern funktionieren soll, kann es anscheinend mit nicht-binären Bildern funktionieren. (aber schwarz muss gleich null sein)
• Die Grafik muss nicht unbedingt aus 5x5-Blöcken bestehen, die Blöcke können auch kleiner sein.
• @*ist neu in Version 10. In älteren Versionen verwenden Sie Tr~Composition~Flattenanstelle von Tr@*Flatten.

Jelly ,  60 53 52 51  50 Bytes

ÑFQe⁹ṚẆ;W¤
Ḣ,Ṫ
=”+ÇÇ€Ạȧ1ŀ
Zç⁾+-ȧç⁾+|$
Ẇ;"/€Ẇ€Ç€€FS

Ein vollständiges Programm, das eine Liste von Zeichenfolgen (Zeilen gleicher Länge) akzeptiert und die Anzahl ausgibt.

Probieren Sie es online!
... oder verwenden Sie dieses vollständige Programm (mit einem zusätzlichen Byte zum Teilen von Zeilen),um das Kopieren und Einfügen von Eingaben zu vereinfachen.
Beachten Sie jedoch, dass die Zeilen nachgestellte Leerzeichen enthalten müssen, damit das Programm ordnungsgemäß funktioniert.

Wie?

ÑFQe⁹ṚẆ;W¤   - Link 1, sidesAreValid?: list of lists, area; list allowedSideCharacters
Ñ            - call the next link (2) as a monad (get the sides in question
             -   note: these sides do not include the corners since the area was modified
             -   to not include the other sides by the first call to link 2 inside link 3.
 F           - flatten into a single list
  Q          - de-duplicate (unique characters)
         ¤   - nilad followed by link(s) as a nilad:
    ⁹        -   right argument (either "+-"                or "+|"               )
     Ṛ       -   reverse        (either "-+"                or "|+"               )
      Ẇ      -   all sublists   (either ["-","+","-+"]      or ["|","+","|+"]     )
        W    -   wrap           (either ["+-"]              or ["+|"]             )
       ;     -   concatenate    (either ["-","+","-+","+-"] or ["|","+","|+","+|"])
   e         - exists in?

Ḣ,Ṫ          - Link 2, topAndTail helper: list
Ḣ            - head (get the first element and modify the list)
  Ṫ          - tail (get the last element and modify the list)
 ,           - pair (the elements together)

=”+ÇÇ€Ạȧ1ŀ   - Link 3, isPartlyValid?: list of lists, area; list allowedSideCharacters
=”+          - equal to '+'? (vectorises across the whole area, 1 if so, 0 otherwise)
   Ç         - call the last link (2) as a monad (gets the values for two edges)
    Ç€       - call the last link (2) as a monad for €ach (...values for the four corners)
      Ạ      - all? (all corners are '+' 1 if so, 0 if not)
        1ŀ   - call link number 1 as a dyad with sideCharacters as the right argument
             -    ...and the modified area on the left
       ȧ     - logical and (both all corners are '+' and the sides in question look right)

Zç⁾+-ȧç⁾+|$  - Link 4, isValidSquare?: list of lists, area
Z            - transpose
 ç⁾+-        - call the last link (3) as a dyad with right argument "+-"
          $  - last two links as a monad:
      ç⁾+|   -   call the last link (3) as a dyad with right argument "+|"
     ȧ       - logical and (1 if so 0 otherwise)

Ẇ;"/€Ẇ€Ç€€FS - Main Link: list of lists of characters, rows
Ẇ            - all sublists (= all non-zero length runs of rows)
   /€        - reduce €ach by:
  "          -   zip with:
 ;           -     concatenation (= all non-zero length vertical edges)
     Ẇ€      - all sublists for €ach (= all possible areas)
       Ç€€   - call the last link (4) as a monad for €ach for €ach (for each area)
          F  - flatten
           S - sum

Beleg , 32 29 Bytes

$a([+`-]*`+>[+`|]*`+>){2}$A

Probieren Sie es online!

27 Byte Code + 2 Byte für die Flags nund o. Nimmt Eingaben in demselben Format vor, das in der Frage angegeben ist (dh Zeilenblock mit Zeilenumbruch).

Haskell, 180 167 166 Bytes

l=length
a%b=[a..b-1]
h c a g b=all(`elem`c)$g<$>[a..b]
f s|(#)<-(!!).(s!!)=sum[1|y<-1%l s,x<-1%l(s!!0),i<-0%y,j<-0%x,h"+|"i(#x)y,h"+-"j(y#)x,h"+|"i(#j)y,h"+-"j(i#)x]

Probieren Sie es online!

Gehen Sie alle möglichen Eckpositionen mit vier verschachtelten Schleifen durch und prüfen Sie, ob alle Zeichen auf den Linien zwischen ihnen aus +-(horizontal) oder +|(vertikal) bestehen.

Jelly , 41 39 34 33 Bytes

,Z;.ị$⁺€ḟ€"⁾-|Fḟ”+
ẆḊÐfZ€µ⁺€ẎÇÐḟL

Probieren Sie es online! oder Alle Fälle anzeigen.

Basierend auf meiner Antwort in J.

Erläuterung

,Z;.ị$⁺€ḟ€"⁾-|Fḟ”+  Helper. Input: 2d array of characters
 Z                  Transpose
,                   Pair
  ;                   Concatenate with
     $                The tail and head
   .ị                   Select at index 0.5 -> Select at index 0 and 1
                        Jelly uses 1-based modular indexing, so
                        0 means to select the tail
      ⁺€              Repeat on each - This selects the last and first rows,
                      last and first columns, and the 4 corners
           ⁾-|       The string array ['-', '|']
          "          Vectorize
        ḟ€             Filter each
              F      Flatten
                ”+   The character '+'
               ḟ

ẆḊÐfZ€µ⁺€ẎÇÐḟL  Main. Input: 2d array of characters
      µ         Combine into a monad
Ẇ                 Generate all sublists
  Ðf              Filter for the values that are truthy (non-empty)
 Ḋ                  Dequeue
    Z€            Transpose each
       ⁺€       Repeat on each
         Ẏ      Tighten, join all lists on the next depth
          ÇÐḟ   Discard the values where executing the helper returns truthy
             L  Length