Your task is to write a function which counts the number of squares contained in an ASCII art picture.

The input pictures contain rectangles---some of them squares---drawn with the characters `-`, `|`, and `+`, where `-` and `|` are used to represent horizontal and vertical sides, and `+` is used to represent corners and intersections. Each picture may contain multiple, possibly overlapping, rectangles.

A simple example input looks like this:

    +--+  +----+
    |  |  |    |    +-+
    |  |  +----+    | |
    +--+            +-+
    
There are two squares and one rectangle in this picture, so your function should return 2 for this input.

The following picture does not contain any squares, so the answer for this one is 0:

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

Here is another, more complex input:

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

The answer for this one is 3: two big squares, and a smaller square formed by the intersection of the two bigger ones. Similarly, the answer for the following picture is 5:

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

You are going to implement a function `count_squares()` which takes an ASCII art picture as input and returns the number of squares the picture shows. The input to that function is an array of strings, where each string corresponds to a line of the ASCII art picture. Each string is guaranteed to contain only the characters `-`, `|`, `+`, and `` `` (space).

The smallest valid square has a side length of 2 and is represented by four `+` characters arranged in a square; a single `+` character is not considered a square.

Have fun!

Difficulty: introductory

Starter code:

def count_squares(lines):
	

Solutions:
def count_squares(lines):
    def s(i, j, z):
        try:
            return (
                '+' == lines[i+z][j] == lines[i][j+z] == lines[i+z][j+z]
                and all(lines[i][c]   in '-+' for c in range(j+1, j+z))
                and all(lines[i+z][c] in '-+' for c in range(j+1, j+z))
                and all(lines[r][j]   in '|+' for r in range(i+1, i+z))
                and all(lines[r][j+z] in '|+' for r in range(i+1, i+z))
            )
        except IndexError:
            return 0
    return sum(
        x == '+' and sum(s(i, j, z) for z in range(1, min(len(lines)-i, len(row)-j)))
        for i, row in enumerate(lines[:-1])
        for j, x in enumerate(row[:-1])
    )


import re
def count_squares(lines):
    h, w = len(lines), max(map(len, lines))
    grid = "\t".join(line.ljust(w) for line in lines)

    return sum(
        len(re.findall(r"(?=\+[-+]{%d}\+.{%d}(?:[|+].{%d}[|+].{%d}){%d}\+[-+]{%d}\+)"
                        % (i, w+1-i-2, i, w+1-i-2, i, i), grid))
        for i in range(0, min(w,h)-1)
    )

def count_squares(img):
  h,w,r=len(img),max([len(s) for s in img]),0
  img=[s+" "*(w-len(s)) for s in img]
  for i in range(h): 
    for j in range(w):
      if img[i][j]=="+":
        for k in range(1,min(h-i,w-j)):
          if img[i+k][j+k]=="+" and img[i+k][j]=="+" and img[i][j+k]=="+":
            s1=img[i][j+1:j+k]+img[i+k][j+1:j+k]
            s2="".join([x[j] for x in img])[i+1:i+k]+"".join([x[j+k] for x in img])[i+1:i+k]
            if not (" " in s1+s2 or "|" in s1 or "-" in s2): r+=1
  return r

def count_squares(lines):
    print('\n'.join(lines))
    tot=0
    for l in range(len(lines)):
        for i in range(len(lines[l])-1):
            if lines[l][i]!='+': continue
            for j in range(i+1,len(lines[l])):
                if lines[l][j]=='+':
                    try:
                        n=j-i
                        if lines[l+n][i]=='+'==lines[l+n][j] \
                        and all(lines[m][i] not in ' -' for m in range(l+1,l+n)) \
                        and all(lines[m][j] not in' -' for m in range(l+1,l+n)) \
                        and all(lines[l][m] not in ' |' for m in range(i+1,j)) \
                        and all(lines[l+n][m] not in ' |' for m in range(i+1,j)):
                            tot+=1
                    except:
                        pass
    return tot

import re
def count_squares(shapes):
    squares = 0
    for i, j in enumerate(shapes):
        ind = [k for k, l in enumerate(j) if l == '+']
        for o in range(len(ind)):
            for p in range(o + 1, len(ind)):
                
                k, l = ind[o], ind[p]
                width = l - k
                if i + width >= len(shapes): continue
                
                upper_line = j[k:l + 1]
                left_line = ''.join([n[k] if k < len(n) else ' ' for n in shapes[i:i + width + 1]])
                right_line = ''.join([n[l] if l < len(n) else ' ' for n in shapes[i:i + width + 1]])
                bottom_line = shapes[i + width][k:l + 1]
              
                if all(re.fullmatch(r'\+[{}]*\+'.format(ch), seq) for seq, ch in \
                            zip([upper_line, left_line, right_line, bottom_line], '\+\- |\+ |\+ \-\+'.split())):
                    squares += 1
    return squares

from itertools import combinations

def count_squares(lines):
    def is_valid(x, y, size):
        if any([chars.get((nx, y), '@') not in '-+' or chars.get((nx, y+size), '@') not in '-+' for nx in range(x+1, x+size)]):
            return False
        if any([chars.get((x, ny), '@') not in '|+' or chars.get((x+size, ny), '@') not in '|+' for ny in range(y+1, y+size)]):
            return False
        return True

    chars, corners = dict(), [[] for _ in range(len(lines))]
    for y, line in enumerate(lines):
        for x, ch in enumerate(line):
            chars[(x, y)] = ch
            if ch == '+':
                corners[y].append(x)
    return sum(is_valid(tl, y, tr - tl) for y, co in enumerate(corners) for tl, tr in combinations(co, 2)
               if chars.get((tl, y + tr - tl)) == '+' and chars.get((tr, y + tr - tl)) == '+')

from itertools import count

# Optimization, what's that?
def count_squares(lines):
    def check(i, j, k):
        return (lines[i+k][j] == lines[i][j+k] == lines[i+k][j+k] == '+'
            and all(lines[x][j] in "|+" for x in range(i+1, i+k))
            and all(lines[i][x] in "-+" for x in range(j+1, j+k))
            and all(lines[x][j+k] in "|+" for x in range(i+1, i+k))
            and all(lines[i+k][x] in "-+" for x in range(j+1, j+k)))
    res = 0
    for i,row in enumerate(lines):
        for j,c in enumerate(row):
            if c == '+':
                for k in count(1):
                    try: res += check(i, j, k)
                    except: break
    return res

def isInvalid(lines, y, x, chars):
    if y >= len(lines) or x >= len(lines[y]):
        return True
    return lines[y][x] not in chars

def isSquare(lines, x, y, size):
    if isInvalid(lines, y, x, '+') or \
       isInvalid(lines, y+size, x, '+') or \
       isInvalid(lines, y, x+size, '+') or \
       isInvalid(lines, y+size, x+size, '+'):
      return False
    for s in range(size + 1):
        if isInvalid(lines, y, x+s, '+-') or \
           isInvalid(lines, y+s, x, '+|') or \
           isInvalid(lines, y+size, x+s, '+-') or \
           isInvalid(lines, y+s, x+size, '+|'):
            return False
    return True

def count_squares(lines):
    count = 0
    for y in range(len(lines)):
        for x in range(len(lines[y])):
            for s in range(1, min(len(lines)-y, len(lines[y])-x)):
                if isSquare(lines, x, y, s):
                    count += 1
    return count

def count_squares(lines):
    
    sides = {(r, c):v for r, row in enumerate(lines) for c, v in enumerate(row) if v in '+-|'}
    nodes = sorted(k for k, v in sides.items() if v == '+')[::-1]

    sideh = lambda r, c, target: all(sides.get((r, c + cc), ' ') in '+-' for cc in range(target - c))
    sidev = lambda r, c, target: all(sides.get((r + rr, c), ' ') in '+|' for rr in range(target - r))

    t = 0
    while nodes:
        r, c = nodes.pop()
        for cc in [p[1] for p in nodes if r == p[0] and sideh(r, c, p[1])]:
            rr = r + cc - c
            if (rr, c) in nodes and (rr, cc) in nodes and sidev(r, c, rr) and sidev(r, cc, rr) and sideh(rr, c, cc):
                t += 1
    return t

def count_squares(lines):
    def is_topleft(i, j):
        b = lines[i][j] == '+'
        b = b and i+1 < len(lines) and j < len(lines[i+1]) and lines[i+1][j] in '|+' 
        b = b and j+1 < len(lines[i]) and lines[i][j+1] in '-+'
        return b
    def is_square(i, j, k):
        b = i + k < len(lines) and all(j + k < len(lines[r]) for r in range(i, i+k+1))
        b = b and lines[i][j] == lines[i][j+k] == lines[i+k][j] == lines[i+k][j+k] == '+'
        if k > 1:
            b = b and all(lines[r][j] in '+|' and lines[r][j+k] in '+|' for r in range(i, i+k+1))
            b = b and all(lines[i][c] in '+-' and lines[i+k][c] in '+-'for c in range(j, j+k+1))
        return b
    cnt = 0
    for i in range(len(lines)-1):
        for j in range(len(lines[i])-1):
            if is_topleft(i, j):
                for k in range(1, len(lines[i]) - j):
                    if is_square(i, j, k):
                        cnt += 1
    return cnt