Jedną z moich ulubionych matematycznych rozrywek jest narysowanie prostokątnej siatki, a następnie znalezienie wszystkich prostokątów widocznych na tej siatce. Proszę, odpowiedz na to pytanie i zaryzykuj dla siebie!

Czy potrafisz policzyć liczbę prostokątów?

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

Całkowita liczba prostokątów dla tej planszy do gry w mini-gry 4 x 4 jest dokładnie

100

Czy miałeś rację?

^{Powiązana matematyka: ile prostokątów jest na szachownicy 8 × 8?}

Wyzwanie

Napisz najkrótszą funkcję / program, który zlicza całkowitą liczbę widocznych prostokątów na nie-toroidalnej siatce / obrazie .

^{Powiązane wyzwania: Policz unikalne prostokąty! , Znajdź liczbę prostokątów w tablicy bajtów 2D .}

Format wejściowy

Twoja funkcja lub program może współpracować z wprowadzaniem tekstowym lub graficznym.

Wprowadzanie tekstu

Kratownica będzie M -by- N ( m rzędów n kolumn ASCII) siatkę składającą się z następujących postaci:

• spacje,
• - dla części poziomego odcinka linii,
• | dla części pionowego odcinka linii oraz
• + na zakręty.

Możesz wprowadzić tę siatkę ASCII jako dane wejściowe / argument do swojego programu / funkcji w postaci

• pojedynczy ciąg rozdzielany podziałami linii,
• ciąg bez znaków nowej linii, ale z jedną lub dwiema liczbami całkowitymi kodującymi wymiary siatki, lub
• tablica ciągów.

^{Uwaga: Dane tekstowe zawierają co najmniej 1 wiersz i co najmniej 1 kolumnę.}

Dane graficzne

Alternatywnie, siatki są kodowane jako czarno-białe obrazy PNG o szerokości 5 * n pikseli i wysokości 5 * m pikseli. Każdy obraz składa się z bloków 5 pikseli * 5 pikseli, które odpowiadają wprowadzeniu ASCII przez:

• Spacje są konwertowane na białe bloki. Te bloki nazywane są blokami białych znaków .
• Segmenty linii i narożniki są przekształcane w niewyspecjalizowanych bloków -whitespace. Środkowy piksel takich bloków jest czarny.
• Edycja: Jeśli dwa rogi (na wejściu ASCII) są połączone segmentem linii, odpowiednie środki bloków (na wejściu graficznym) również powinny być połączone czarną linią.

Oznacza to, że każdy blok można wybrać tylko z (Kliknij tutaj, aby powiększyć obraz) .

^{Uwaga: Niebieskie granice służą wyłącznie celom ilustracyjnym. Dane graficzne mają co najmniej 5 pikseli szerokości i 5 pikseli wysokości. Możesz przekonwertować dane graficzne na dowolny obraz monochromatyczny, potencjalnie inny format pliku obrazu. Jeśli zdecydujesz się na konwersję, podaj w odpowiedzi. Nie ma kary za nawrócenie.}

Format wyjściowy

Jeśli piszesz program, musi on wyświetlać nieujemną liczbę wskazującą całkowitą liczbę prostokątów na wejściu.

Jeśli piszesz funkcję, powinna również zwrócić nieujemną liczbę wskazującą całkowitą liczbę prostokątów na wejściu.

Przykłady przypadków

Przypadek 1, grafika: ( 30 px * 30 px), ASCII: ( 6 rzędów, 6 kol.)

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

Oczekiwany wynik: 3

Przypadek 2, grafika: ( 20 pikseli * 20 pikseli), ASCII: ( 4 rzędy, 4 kolumny)

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

Oczekiwany wynik: 6

Przypadek 3, grafika: ( 55 pikseli * 40 pikseli), ASCII: ( 8 rzędów, 11 kol.)

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

Oczekiwany wynik: 9

Przypadek 4, grafika: ( 120 pikseli * 65 pikseli), ASCII: ( 13 wierszy, 24 kolumny)

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

Oczekiwany wynik: 243

Przypadek 5, grafika: ( 5 pikseli * 5 pikseli. Tak, jest tam!), ASCII: Tylko jedna spacja.

Oczekiwany wynik: 0

Przypadek 6, grafika: ( 35 pikseli * 20 pikseli), ASCII: ( 4 rzędy, 7 kolumn)

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

Oczekiwany wynik: 5

Założenia

Aby ułatwić Ci życie, masz gwarancję, że:

• Ponieważ nie jest toroidalna , siatka nie zawija się ani w poziomie, ani w pionie.
• Nie ma luźnych końcówek, np . +---Lub +- -+. Wszystkie segmenty linii mają dwa końce.
• Dwie linie, które się spotykają, +muszą się przecinać w tym punkcie.
• Nie musisz się martwić o nieprawidłowe dane wejściowe.

Obowiązują zasady dotyczące standardowych luk. Traktuj kwadraty jak prostokąty. Opcjonalnie możesz usunąć końcowe spacje w każdym rzędzie siatki.

^{To jest golf golfowy , więc postaraj się , aby Twój wpis był jak najkrótszy. Rozwiązania tekstowe i graficzne będą ze sobą konkurować.}

Tabela liderów

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>

Grime , 31 28 bajtów

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

Wypróbuj online!

Pobiera dane wejściowe w formacie ASCII.

Wyjaśnienie

Składnia Grime'a jest bardzo zbliżona do wyrażeń regularnych. Każda linia określa wzór, który może, ale nie musi, pasować do prostokąta znaków. Tpasuje do prostokąta, którego górny rząd i lewa kolumna wyglądają na prawidłowe.

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

Drugi rząd to „program główny”.

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

JavaScript (ES6), 176 171 bajtów

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>

Pobiera dane wejściowe jako tablicę ciągów o równej długości. Objaśnienie: Tworzy serię wyrażeń regularnych, które pasują do prostokątów o wszystkich możliwych szerokościach i wysokościach (i niektórych niemożliwych szerokościach i wysokościach, ale dla ciebie to kod golfowy) i zlicza, ile pasują wszystkie one. Ponieważ nie jest to grupa przechwytywania w regexp, splitpowraca 2n+1do nmeczów, więc przesunięcie w prawo o 1, aby uzyskać liczbę meczów, jak zapisuje bajt ponad dokonywania grupie bez przechwytywanie.

J , 103 95 86 80 76 70 bajtów

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

Wypróbuj online!

Pobiera dane wejściowe jako tablicę ciągów ze spacjami końcowymi (tak, aby każdy ciąg był tego samego rozmiaru). Używa operatora pełnej podtablicy ;._3do iteracji po każdym możliwym rozmiarze podtablicy większym niż 2 x 2 i zlicza podtablice, które są poprawnymi prostokątami. Prawie natychmiast wykonuje wszystkie przypadki testowe.

Mathematica, 136 134 132 bajtów

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}]&

Użycie: (dla starej 136-bajtowej wersji, ale nowa wersja jest w zasadzie identyczna)

Uwaga:

• Działa to w czasie O (m ² n ² max (m, n)), więc używaj tylko małych danych wejściowych.
• Chociaż ma to działać z obrazami binarnymi, najwyraźniej może działać z obrazami niebinarnymi. (ale czarny musi być identycznie zero)
• Grafika niekoniecznie musi być zbudowana z bloków 5x5, bloki mogą być mniejsze.
• @*jest nowy w wersji 10. W starszych wersjach użyj Tr~Composition~Flattenzamiast Tr@*Flatten.

Galareta ,  60 53 52 51  50 bajtów

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

Pełny program akceptujący listę ciągów (wiersze o równej długości) i drukujący liczbę.

Wypróbuj online!
... lub na łatwość kopiowania i wklejania wykorzystane doświadczenia to pełny program (z dodatkowym bajt do linii Split)
- Należy pamiętać, że linie mają obowiązek zawierać spacje dla programu funkcjonować poprawnie chociaż.

W jaki sposób?

Ñ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

Poślizg , 32 29 bajtów

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

Wypróbuj online!

27 bajtów kodu + 2 bajty dla flag ni o. Pobiera dane wejściowe w tym samym formacie, który podano w pytaniu (tj. Blok linii rozdzielany znakiem nowej linii).

Haskell, 180 167 166 bajtów

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]

Wypróbuj online!

Przejdź przez wszystkie możliwe pozycje narożne za pomocą czterech zagnieżdżonych pętli i sprawdź, czy wszystkie znaki na liniach między nimi składają się z +-(poziomej) lub +|(pionowej).

Galaretka , 41 39 34 33 bajtów

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

Wypróbuj online! lub Wyświetl wszystkie skrzynki.

Na podstawie mojej odpowiedzi w J.

Wyjaśnienie

,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