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 (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: (30 px * 30 px), ASCII: (6 rows, 6 cols)
+--+
| |
| ++-+
+-++ |
| |
+--+
Expected output: 3
Case 2, Graphic: (20 px * 20 px), ASCII: (4 rows, 4 cols)
++-+
|+++
+++|
+-++
Expected output: 6
Case 3, Graphic: (55 px * 40 px), ASCII: (8 rows, 11 cols)
+++--+
+-+++ |
| | ++--+
+--+--++ ++
| ||
| ||
++ +--++
++
Expected output: 9
Case 4, Graphic: (120 px * 65 px), ASCII: (13 rows, 24 cols)
+--+--+ +--+ +--+ +--+
| | | | | | | | |
+--+--+ | | | | | |
| | | +--+--+--+--+--+
+--+--+ | | | |
| | | | ++
+-+-+-+-+ +--+ +--+ ++
| | | | |
+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+
Expected output: 243
Case 5, Graphic: (5 px * 5 px. Yes, it is there!), ASCII: Just a single space.
Expected output: 0
Case 6, Graphic: (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 code-golf, 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>