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: EASY
Tags: Geometry

Ad-hoc

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('(?=\\+[-+]{%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('\\+[{}]*\\+'.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

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