Um dos meus passatempos matemáticos favoritos é desenhar uma grade retangular e, em seguida, encontrar todos os retângulos visíveis nessa grade. Aqui, faça esta pergunta e aventure-se!

Você pode contar o número de retângulos?

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

O número total de retângulos para este 4 x 4 bordo minichess é exatamente

100

Você estava correto?

^{Matemática relacionada: Quantos retângulos existem em um tabuleiro de xadrez 8 × 8?}

O desafio

Escreva a função / programa mais curta que conte o número total de retângulos visíveis em uma grade / imagem não toroidal .

^{Desafios relacionados: Conte os retângulos exclusivos! , Encontre o número de retângulos em uma matriz de bytes 2D .}

Formato de entrada

Sua função ou programa pode optar por trabalhar com entrada baseada em texto ou gráfica.

Entrada baseada em texto

A grade será uma grade ASCII m- por- n ( m linhas, n colunas), consistindo nos seguintes caracteres:

• espaços,
• - para partes de um segmento de linha horizontal,
• | para partes de um segmento de linha vertical e
• + para cantos.

Você pode introduzir essa grade ASCII como entrada / argumento para seu programa / função na forma de

• uma única sequência delimitada por quebras de linha,
• uma sequência sem novas linhas, mas com um ou dois números inteiros que codificam as dimensões da grade, ou
• uma matriz de seqüências de caracteres.

^{Nota: A entrada baseada em texto contém pelo menos 1 linha e pelo menos 1 coluna.}

Entrada gráfica

Como alternativa, as grades são codificadas como imagens PNG em preto e branco de 5 * n pixels de largura e 5 * m pixels de altura. Cada imagem consiste em blocos de 5 px * 5 px que correspondem à entrada ASCII por:

• Os espaços são convertidos em blocos brancos. Esses blocos são chamados de blocos de espaço em branco .
• Os segmentos de linha e os cantos são convertidos em blocos que não são de espaço em branco. O pixel central desses blocos é preto.
• Editar: Se dois cantos (na entrada ASCII) estiverem conectados por um segmento de linha, os centros de bloco correspondentes (na entrada gráfica) também deverão ser conectados por uma linha preta.

Isso significa que cada bloco só pode ser escolhido (clique aqui para ampliar a imagem) .

^{Nota: Os limites azuis são apenas para fins ilustrativos. A entrada gráfica tem pelo menos 5 px de largura e 5 px de altura. Você pode converter a entrada gráfica em qualquer imagem monocromática, potencialmente em outros formatos de arquivo de imagem). Se você optar por converter, especifique na resposta. Não há penalidade para a conversão.}

Formato de saída

Se você estiver escrevendo um programa, ele deve exibir um número não negativo indicando o número total de retângulos na entrada.

Se você estiver escrevendo uma função, ela também deve retornar um número não negativo, indicando o número total de retângulos na entrada.

Casos de exemplo

Caso 1, Gráfico: ( 30 px * 30 px), ASCII: ( 6 linhas, 6 colunas )

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

Saída esperada: 3

Caso 2, Gráfico: ( 20 px * 20 px), ASCII: ( 4 linhas, 4 colunas )

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

Saída esperada: 6

Caso 3, Gráfico: ( 55 px * 40 px), ASCII: ( 8 linhas, 11 colunas )

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

Saída esperada: 9

Caso 4, Gráfico: ( 120 px * 65 px), ASCII: ( 13 linhas, 24 colunas )

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

Saída esperada: 243

Caso 5, Gráfico: ( 5 px * 5 px. Sim, está lá!), ASCII: Apenas um único espaço.

Saída esperada: 0

Caso 6, Gráfico: ( 35 px * 20 px), ASCII: ( 4 linhas, 7 colunas )

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

Saída esperada: 5

Suposições

Para facilitar a vida, você tem a garantia de que:

• Por não ser toroidal , a grade não quebra horizontalmente ou verticalmente.
• Não há pontas soltas, por exemplo , +---ou +- -+. Todos os segmentos de linha têm duas extremidades.
• Duas linhas que se encontram em +devem se cruzar nesse ponto.
• Você não precisa se preocupar com entradas inválidas.

Aplicam-se regras contra brechas padrão. Por favor, trate os quadrados como retângulos. Opcionalmente, você pode remover os espaços finais em cada linha da grade.

^{Isso é código-golfe , então faça sua entrada o mais curta possível. Soluções gráficas e baseadas em texto competirão juntas.}

Entre os melhores

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 bytes

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

Experimente online!

Recebe entrada no formato ASCII.

Explicação

A sintaxe do Grime está muito próxima das expressões regulares. Cada linha define um padrão que pode ou não corresponder a um retângulo de caracteres. Tcorresponde a um retângulo cuja linha superior e coluna esquerda parecem válidas.

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

A segunda linha é o "programa principal".

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>

Recebe entrada como uma matriz de cadeias de comprimento igual. Explicação: Cria uma série de expressões regulares que correspondem a retângulos de todas as larguras e alturas possíveis (e algumas larguras e alturas impossíveis, mas isso é código de golfe para você) e conta quantas correspondências elas produzem. Como há um grupo de captura na regexp, splitretorna2n+1 para ncorrespondências, então eu desloco à direita 1 para obter o número de correspondências, pois isso economiza um byte em tornar o grupo não capturador.

J , 103 95 86 80 76 70 bytes

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

Experimente online!

Recebe a entrada como uma matriz de cadeias com espaços à direita (para que cada cadeia tenha o mesmo tamanho). Usa o operador de subarray completo;._3 para iterar todos os tamanhos possíveis de subarray maiores que 2 x 2 e conta os subarrays que são retângulos válidos. Conclui todos os casos de teste quase instantaneamente.

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

Uso: (para a versão antiga de 136 bytes, mas a nova versão é basicamente idêntica)

Nota:

• Isso ocorre no tempo O (m ² n ² máx (m, n)), portanto, use apenas entradas pequenas.
• Embora isso deva funcionar com imagens binárias, aparentemente ele pode funcionar com imagens não binárias. (mas o preto deve ser idêntico a zero)
• Os gráficos não são necessariamente construídos com blocos 5x5, os blocos podem ser menores.
• @*é novo na versão 10. Nas versões mais antigas, use em Tr~Composition~Flattenvez de Tr@*Flatten.

Geléia ,  60 53 52 51  50 bytes

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

Um programa completo que aceita uma lista de cadeias (linhas de comprimento igual) e imprime a contagem.

Experimente online!
... ou para facilitar a entrada de copiar e colar, use este programa completo (com um byte extra para dividir linhas)
- observe que as linhas são necessárias para conter espaços à direita para que o programa funcione corretamente.

Quão?

Ñ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

Deslizamento , 32 29 bytes

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

Experimente online!

27 bytes de código + 2 bytes para os sinalizadores ne o. Recebe entrada no mesmo formato fornecido na pergunta (ou seja, bloco de linhas delimitado por nova linha).

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]

Experimente online!

Passe por todas as posições de canto possíveis com quatro loops aninhados e verifique se todos os caracteres nas linhas entre eles consistem em +-(horizontal) ou +|(vertical).

Geléia , 41 39 34 33 bytes

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

Experimente online! ou Exibir todos os casos.

Com base na minha resposta em J.

Explicação

,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