12
\$\begingroup\$

This challenge is inspired by a picture that often roams on Facebook that looks like this. Except our base square will look more like this:

┌─┬───┬─┐
├─┼─┬─┼─┤
├─┼─┴─┼─┤
├─┼─┬─┼─┤
└─┴─┴─┴─┘

The square is made out of n x m 1x1 square, you have to count how many sub-squares (1x1, 2x2, 3x3, 4x4, 5x5, etc.) can fit within that square. Squares can be missing some grid lines (like in the example above) or be complete like in the example bellow. Which means a mathematical breakdown is not possible (as far as I know).

Inputs:

  • The amount of lines (n) of input to build the square;
  • A square made from the following characters: | across n lines of input.

Output:

  • The amount of squares of any size that can fit within the input square (we only want a single number here, not a number for each size).

Winning criterion:

The smallest answer (number of bytes) wins.

Test Cases:

In:

5
┌─┬─┬─┬─┐
├─┼─┼─┼─┤
├─┼─┼─┼─┤
├─┼─┼─┼─┤
└─┴─┴─┴─┘

Out: 30


In:

3
┌─┬─┐
├─┼─┤
└─┴─┘

Out: 5


In:

5
┌─┬─┐
├─┴─┤
├───┤
├─┬─┤
└─┴─┘

Out: 7


In:

4
┌─┬─┬─┬─┬─┬─┐
├─┼─┼─┼─┼─┼─┤
├─┼─┼─┼─┼─┼─┤
└─┴─┴─┴─┴─┴─┘

Out: 32


In:

2
┌─┐
└─┘

Out: 1


In:

4
┌─┬─┬─┬─┬─┬─┐
├─┴─┼─┼─┼─┴─┤
├─┬─┼─┼─┼─┬─┤
└─┴─┴─┴─┴─┴─┘

Out: 22

\$\endgroup\$
  • 3
    \$\begingroup\$ I didn't count the bigger ones, but doesn't the third one have 11 squares in it? \$\endgroup\$ – Value Ink May 15 '16 at 8:37
  • \$\begingroup\$ @KevinLau-notKenny You're right I made a mistake. \$\endgroup\$ – Simon Landry May 15 '16 at 8:39
  • \$\begingroup\$ I think is too simple, it is counted via a combinatoric form, would you rather prefer to consider the picture format of facebook? \$\endgroup\$ – Abr001am May 15 '16 at 8:45
  • 1
    \$\begingroup\$ For reference, the rectangular case is A271916, which gives m*(m+1)*(3*n-m+1)/6 for an m by n rectangle with n >= m (dimensions offset by one since the entry speaks of points rather than the squares themselves) \$\endgroup\$ – Sp3000 May 15 '16 at 9:20
  • 1
    \$\begingroup\$ @SimonLandry i didnt mean combinatorics in pure sens, i think sp3000 just pointed that out already, the first version of your puzzle (before edit) was open for a simple mathematical breakthrough \$\endgroup\$ – Abr001am May 15 '16 at 9:44
2
\$\begingroup\$

JavaScript (ES6), 292 bytes 306 325

Edit I did the byte count totally wrong, corrected now thx http://bytesizematters.com/ correct for the last time I hope thx Cᴏɴᴏʀ O'Bʀɪᴇɴ see https://goo.gl/LSHC1U (and 1 byte less using a literal newline insteads of '\n')

(h,z)=>(o=>{r=p=>" ),┌(─┐┬'└│├┘┴┤┼".search(z[p]);for(q=s=0;++s<o/2&s<h;)for(y=0;y<(h-s)*o;y+=o)for(x=0;x<o-s*2;q+=!n,x+=2)for(n=i=0,t=x,u=y;i<=s;t+=2,u+=o,i++)n|=i<s&(!(r(t+y)&r(t+y+s*o)&1)|!(r(x+u)&r(x+u+s*2)&2))|i>0&(!(r(t+y)&r(t+y+s*o)&4)|!(r(x+u)&r(x+u+s*2)&8))})(-~z.search`
`)|q

Longer than I expected (probably a few more byte can be shaved off)

All possible squares are checked and counted.

The r function map each character to a bitmap having

  • 1 : horizontal line center to right
  • 2 : vertical line center to bottom
  • 4 : horizontal line center to left
  • 8 : vertical line center to top

A square of any size must have

  • 4 in all cells except the first in top and bottom row
  • 1 in all cells except the last in top and bottom row
  • 8 in all cells except the first in leftmost and rightmost column
  • 2 in all cells except the last in leftmost and rightmost column

Test

f=(h,z)=>(o=>{r=p=>" ),┌(─┐┬'└│├┘┴┤┼".search(z[p]);k=(p,d,m)=>r(p)&r(p+s*d)&m;for(q=s=0;++s<o/2&s<h;)for(y=0;y<(h-s)*o;y+=o)for(x=0;x<o-s*2;q+=!n,x+=2)for(n=i=0,t=x,u=y;i<=s;t+=2,u+=o,i++)n=n|i<s&(!k(t+y,o,1)|!k(x+u,2,2))|i>0&(!k(t+y,o,4)|!k(x+u,2,8));})(-~z.search`
`)|q

console.log=(...x)=>O.textContent+=x+'\n'

// Less golfed

Uf=(h,z)=>{
  o=-~z.search`\n`;
  w=o/2;
  r=p=>" ),┌(─┐┬'└│├┘┴┤┼".search(z[p]);
  k=(p,d,m)=>r(p)&r(p+s*d)&m;
  for(q=s=0;++s<w&s<h;)
    for(y=0;y<(h-s)*o;y+=o)
      for(x=0;x<(w-s)*2;q+=!n,x+=2)
        for(n=i=0,t=x,u=y;i<=s;t+=2,u+=o,i++)
          n|=i<s&(!k(t+y,o,1)|!k(x+u,2,2))
          |i>0&(!k(t+y,o,4)|!k(x+u,2,8));
  return q
}

;[[5,`┌─┬───┬─┐
├─┼─┬─┼─┤
├─┼─┴─┼─┤
├─┼─┬─┼─┤
└─┴─┴─┴─┘`,20]
,[5,`┌─┬─┬─┬─┐
├─┼─┼─┼─┤
├─┼─┼─┼─┤
├─┼─┼─┼─┤
└─┴─┴─┴─┘`,30]
,[3,`┌─┬─┐
├─┼─┤
└─┴─┘`,5]
,[5,`┌─┬─┐
├─┴─┤
├───┤
├─┬─┤
└─┴─┘`,7]
,[4,`┌─┬─┬─┬─┬─┬─┐
├─┼─┼─┼─┼─┼─┤
├─┼─┼─┼─┼─┼─┤
└─┴─┴─┴─┴─┴─┘`,32]
,[2,`┌─┐
└─┘`,1]
,[4,`┌─┬─┬─┬─┬─┬─┐
├─┴─┼─┼─┼─┴─┤
├─┬─┼─┼─┼─┬─┤
└─┴─┴─┴─┴─┴─┘`,22],
,[6,`┌─┬─────┐
├─┼─┬─┐ │
│ ├─┼─┼─┤
│ └─┼─┼─┤
│   └─┼─┤
└─────┴─┘`,12],  
,[6,`┌─┬─┬─┬─┐
├─┴─┼─┼─┤
│   └─┼─┤
├─┬─┬─┼─┤
├─┼─┼─┼─┤
└─┴─┴─┴─┘`,23]]  
.forEach(t=>{
  var r=t[0],a=t[1],k=t[2],x=f(r,a)
  console.log(x==k?'OK '+x:'KO '+x+' Expected '+k,'\n'+a)
})
<pre id=O></pre>

\$\endgroup\$
  • \$\begingroup\$ I count 307 bytes. \$\endgroup\$ – Conor O'Brien May 15 '16 at 18:11
  • \$\begingroup\$ @Conor Ok thanks for the link \$\endgroup\$ – edc65 May 15 '16 at 20:18

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.