21
\$\begingroup\$

One of my favorite mathematical pastimes is to draw a rectangular grid, then to find all of the rectangles that are visible in that grid. Here, take this question, and venture for yourself!

Can you count the number of rectangles?

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

The total number of rectangles for this 4 x 4 minichess board is exactly

100

Were you correct?

Related math: How many rectangles are there on an 8×8 checkerboard?

The Challenge

Write the shortest function/program that counts the total number of visible rectangles on a non-toroidal grid/image.

Related challenges: Count the Unique Rectangles!, Find number of rectangles in a 2D byte array.

Input Format

Your function or program can choose to work with either text-based input or graphical input.

Text-based Input

The grid will be an m-by-n (m rows, n columns) ASCII grid consisting of the following characters:

  • spaces,
  • - for parts of a horizontal line segment,
  • | for parts of a vertical line segment, and
  • + for corners.

You can introduce this ASCII grid as the input/argument to your program/function in the form of

  • a single string delimited by line-breaks,
  • a string without newlines but with one or two integers encoding the dimensions of the grid, or
  • an array of strings.

Note: The text-based input contains at least 1 row and at least 1 column.

Graphical Input

Alternatively, the grids are encoded as black-and-white PNG images of 5*n pixels wide and 5*m pixels high. Each image consists of 5 px * 5 px blocks that correspond to the ASCII input by:

  • Spaces are converted to white blocks. These blocks are called the whitespace blocks.
  • Line segments and corners are converted to non-whitespace blocks. The center pixel of such blocks are black.
  • Edit: If two corners (in the ASCII input) are connected by a line segment, the corresponding block centers (in the graphical input) should be connected by a black line, too.

This means that each block could only be chosen from Please ignore the blue boundaries. (Click here for larger image).

Note: The blue boundaries are only for illustration purposes. Graphical input is at least 5 px wide and 5 px high. You can convert the graphical input to any monochrome image, potentially of other image file formats). If you choose to convert, please specify in the answer. There is no penalty to conversion.

Output Format

If you are writing a program, it must display a non-negative number indicating the total number of rectangles in the input.

If you are writing a function, it should also return a non-negative number indicating the total number of rectangles in the input.

Example Cases

Case 1, Graphic: Case 1 (30 px * 30 px), ASCII: (6 rows, 6 cols)

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

Expected output: 3

Case 2, Graphic: Case 2 (20 px * 20 px), ASCII: (4 rows, 4 cols)

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

Expected output: 6

Case 3, Graphic: Case 3 (55 px * 40 px), ASCII: (8 rows, 11 cols)

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

Expected output: 9

Case 4, Graphic: Case 4 (120 px * 65 px), ASCII: (13 rows, 24 cols)

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

Expected output: 243

Case 5, Graphic: Case 5 (5 px * 5 px. Yes, it is there!), ASCII: Just a single space.

Expected output: 0

Case 6, Graphic: Case 6 (35 px * 20 px), ASCII: (4 rows, 7 cols)

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

Expected output: 5

Assumptions

To make life easier, you are guaranteed that:

  • By being non-toroidal, the grid does not wrap either horizontally or vertically.
  • There are no loose ends, e.g. +--- or +- -+. All line segments have two ends.
  • Two lines that meet at + must intersect each other at that point.
  • You do not have to worry about invalid inputs.

Rules against standard loopholes apply. Please treat squares as rectangles. Optionally, you could remove the trailing spaces on each row of the grid.

This is , so make your entry as short as possible. Text-based and graphical solutions will compete together.

Leaderboard

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>

\$\endgroup\$
  • \$\begingroup\$ Is monochrome bitmap allowed? \$\endgroup\$ – user202729 Aug 5 '17 at 10:21
  • \$\begingroup\$ @user202729 Yes. If you choose to work with non-PNG images, please specify that in the answer. \$\endgroup\$ – Frenzy Li Aug 5 '17 at 10:23
  • \$\begingroup\$ Is this a valid input? (Rectangle corner touches border of larger rectangle.) If so, consider adding it as a test case. \$\endgroup\$ – Zgarb Aug 5 '17 at 11:09
  • \$\begingroup\$ @Zgarb It is valid input. I'll edit the post, too. \$\endgroup\$ – Frenzy Li Aug 5 '17 at 11:11
  • \$\begingroup\$ Is there a reason you put the expected outputs in spoilers? It seems like it just makes verifying your code slightly more annoying. \$\endgroup\$ – FryAmTheEggman Aug 5 '17 at 17:04
4
\$\begingroup\$

Grime, 31 28 bytes

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

Try it online!

Takes input in ASCII format.

Explanation

Grime's syntax is very close to regular expressions. Each line defines a pattern that may or may not match a rectangle of characters. T matches a rectangle whose top row and left column look valid.

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

The second row is the "main program".

n`T&To2
n`       Print number of rectangles that match
  T      the pattern T
   &     and
    To2  T rotated 180 degrees.
\$\endgroup\$
6
\$\begingroup\$

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>

Takes input as an array of strings of equal length. Explanation: Creates a series of regular expressions that match rectangles of all possible widths and heights (and some impossible widths and heights, but that's code golf for you) and counts how many matches they all produce. Because there's a capturing group in the regexp, split returns 2n+1 for n matches, so I right shift by 1 to get the number of matches, as that saves a byte over making the group non-capturing.

\$\endgroup\$
  • \$\begingroup\$ Hmm, the code snippet is not working for me [Firefox 54.0.1 (32bit) or Chrome 60.0.3112.90 (64bit) both on Windows (64bit)]. \$\endgroup\$ – Jonathan Allan Aug 5 '17 at 12:21
  • \$\begingroup\$ The snippet It doesn't work on Safari either [Mac (64bit)]. \$\endgroup\$ – Mr. Xcoder Aug 5 '17 at 12:45
  • 2
    \$\begingroup\$ It seems that we have to paste stuff into the text area. Same number of characters per line is required. \$\endgroup\$ – Frenzy Li Aug 5 '17 at 12:53
  • \$\begingroup\$ Ah I see, good spot @FrenzyLi! \$\endgroup\$ – Jonathan Allan Aug 5 '17 at 13:10
4
\$\begingroup\$

J, 103 95 86 80 76 70 bytes

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

Try it online!

Takes input as an array of strings with trailing spaces (so that each string is the same size). Uses the full subarray operator ;._3 to iterate over every possible subarray size larger than 2 x 2, and counts the subarrays that are valid rectangles. Completes all test cases almost instantly.

\$\endgroup\$
  • 1
    \$\begingroup\$ @FrenzyLi Thanks. The function is receiving the input as an array of strings, but I encoded each each array as a flat string reshaped into an array before I stored them in each variable to be used as an argument for the function. \$\endgroup\$ – miles Aug 5 '17 at 13:09
  • \$\begingroup\$ Ahh... Thank you for your explanation. \$\endgroup\$ – Frenzy Li Aug 5 '17 at 13:10
  • \$\begingroup\$ @miles nice. when you say input as array of strings, is each line of the input 1 sting? \$\endgroup\$ – Jonah Aug 7 '17 at 6:01
  • \$\begingroup\$ @Jonah Strings in J are just arrays of chars, so the input is actually a 2d array of chars. \$\endgroup\$ – miles Aug 7 '17 at 6:52
3
\$\begingroup\$

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

Usage: (for old 136-byte version, but the new version is basically identical)

_

Note:

  • This runs in time O(m2 n2 max(m, n)), so only use small inputs.
  • Although this is supposed to work with binary images, apparently it can work with non-binary images. (but black must be identically zero)
  • The graphics doesn't necessarily be constructed with 5x5 blocks, the blocks can be smaller.
  • @* is new in version 10. In older versions, use Tr~Composition~Flatten instead of Tr@*Flatten.
\$\endgroup\$
  • \$\begingroup\$ Which version of MMA is this in? In 9.0, it responds with "Tr@" cannot be followed by "*Flatten". \$\endgroup\$ – Frenzy Li Aug 5 '17 at 10:52
  • 1
    \$\begingroup\$ @FrenzyLi 10.0. Yes, @* (shorthand for Composition)is new in version 10. \$\endgroup\$ – user202729 Aug 5 '17 at 11:23
  • 1
    \$\begingroup\$ Why don't you just use RectangleCount[]? \$\endgroup\$ – MCMastery Aug 6 '17 at 0:46
  • 2
    \$\begingroup\$ @MCMastery Mathematica is famous for having a lot of built-in, but not this one. \$\endgroup\$ – user202729 Aug 6 '17 at 4:20
  • \$\begingroup\$ @user202729 lol yep, im jk \$\endgroup\$ – MCMastery Aug 6 '17 at 4:52
2
\$\begingroup\$

Jelly,  60 53 52 51  50 bytes

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

A full program accepting a list of strings (equal length rows) and printing the count.

Try it online!
...or for ease of copy & pasting input use this full program (with an extra byte to split lines)
- do note the lines are required to contain trailing spaces for the program to function correctly though.

How?

Ñ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
\$\endgroup\$
2
\$\begingroup\$

Slip, 32 29 bytes

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

Try it online!

27 bytes of code + 2 bytes for the n and o flags. Takes input in the same format provided in the question (i.e. newline-delimited block of lines).

\$\endgroup\$
2
\$\begingroup\$

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]

Try it online!

Go through all possible corner positions with four nested loops and check if all the chars on the lines between them consist of +- (horizontal) or +| (vertical).

\$\endgroup\$
1
\$\begingroup\$

Jelly, 41 39 34 33 bytes

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

Try it online! or View all cases.

Based on my answer in J.

Explanation

,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
\$\endgroup\$
  • \$\begingroup\$ Now it's finally starting to feel competitively short at 34 bytes. \$\endgroup\$ – miles Aug 7 '17 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.