8
\$\begingroup\$

Input:

An NxM grid or multi-line string (or other reasonable input-format), containing only printable ASCII (unicode range [32,126]).

Output:

The amount of closed polygons of the same character that can be found, with two special rules:

  • Spaces are wildcards and can be used (multiple times) for any character
  • o, O, and 0 are counted as closed polygons themselves

Challenge rules:

  • (Anti-)Diagonal connections between the same characters (or spaces) are included to form closed polygons.
  • You cannot go over other characters (except for the wild-card spaces). (I.e. in the first test case/example below, you cannot form two triangles with the A's by going over the x.) So all characters used for a closed polygon should be connected (horizontally, vertically, and/or (anti-)diagonally).
  • Polygons are at least three characters (excluding the single characters o, O, 0).
  • Lines of adjacent characters are not closed polygons.
  • The same characters cannot be used for multiple polygons, excluding wildcard spaces.
  • Wildcard spaces cannot be counted as o, O, or 0.
  • Three or more spaces alone cannot form a closed polygon. It should always have at least one non-space (and non o/O/0) character.
  • Input can be in any reasonable format. Can be a character-matrix, new-line delimiter string, string-array, character-array with added integer width, etc.
  • The inputs will always be an N by M rectangle (or square), so no weird input-shapes
  • Since the same characters cannot be used more than once and we want to have as many closed polygons, using multiple characters to form two (or more) closed polygons instead of one larger polygon is of course the intended goal in the counting (which is also why closed polygons formed by o, O, or 0 will never be counted, since they are already closed polygons individually).
  • Uppercase and lowercase letters are of course counted as individual characters.

General rules:

  • This is , so shortest answer in bytes wins.
    Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
  • Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
  • Default Loopholes are forbidden.
  • If possible, please add a link with a test for your code (i.e. TIO).
  • Also, adding an explanation for your answer is highly recommended.

Examples / Test Cases:

Input:

AAAw
AxA4
'AoQ

Output: 2, because these polygons can be formed:
enter image description here


Input:

1822uaslkoo
12*2sl ljoo
a* 0a91)j$*
()*#J9dddj*
*Q#ID dJj!"
*UJD SO&*93

Output: 12, because these polygons can be formed:
enter image description here

Note that:
- The yellow one below is not a polygon, because the o's are already counted as separated polygons
- The purple and brown ones aren't closed
- The red, grey, green, and light-blue use one or more non-space characters that were already used for other closed polygons
enter image description here


Input (dimensions are 2x4):

3  3
  2 

Output: 3, because these polygons can be formed:
enter image description here


Input:

AAAA
AAAA
AAxA

Output: 3, because these polygons can be formed:
enter image description here

Of course other polygons are possible here, but no more than 3. Here another valid example with 3 polygons:
enter image description here


Input:

0QoO

Output: 3, because these polygons can be formed:
enter image description here


Input:

W w
 Ww

Output: 3, because these polygons can be formed:
enter image description here

Note that the top layer space is used for all three polygons. Here are the three polygons individually highlighted:
enter image description here enter image description here enter image description here


Input:

W W
 WW

Output: 3, because the same three polygons as in the previous test can be formed. So no, it's not 2 with these two polygons:
enter image description here


Input:

abcdQefg
hQiQjQQk
QlQmnopQ
QqrstQQu
QvQQQwxy
QQz0QQQQ

Output: 3, because these polygons can be formed:
enter image description here

\$\endgroup\$
  • 2
    \$\begingroup\$ I want to +1 this but I really don't see what special casing the os, Os & 0s adds to the challenge. \$\endgroup\$ – Shaggy Jan 18 at 23:30
  • \$\begingroup\$ It seems like all example polygons are convex. Unless concave polygons are excluded, I'd suggest to add a test case including one. \$\endgroup\$ – Arnauld Jan 19 at 15:53
  • 1
    \$\begingroup\$ @Arnauld Added a test case at the bottom. Not sure if it is sufficient for what you meant, since it only goes inwards once. The grid has to be pretty big to make a concave polygon. If you have any suggested test case I should add in addition, let me know. \$\endgroup\$ – Kevin Cruijssen Jan 19 at 16:23
  • \$\begingroup\$ @Shaggy You're kinda right. When I made the challenge I saw the shape of the o, O, 0 being circles as individual polygons, but in a solution it doesn't add much, except that the o, O, 0 should be avoided when forming larger polygons, and adding a count for them. Too late to change it now, though. \$\endgroup\$ – Kevin Cruijssen Jan 19 at 16:27
4
\$\begingroup\$

Python 2, 714 737 821 bytes

  • -23 bytes thanks to Kevin Cruijssen
M=input()
m=''.join(M)
def P(L):
 if len(L)<2:yield[L];return
 for p in P(L[1:]):
	for n,s in enumerate(p):yield p[:n]+[[L[0]]+s]+p[n+1:]
	yield[[L[0]]]+p
h,w,R,C=len(M),len(M[0]),0,[-1,0,1]
K=[(i,j)for i in range(h)for j in range(w)]
Z=[(i,j)for i,j in K if' '==M[i][j]]
from networkx import*
for l in set(m):
 G,S=[],[]
 if l in'oO0':R+=m.count(l);continue
 for I in K:
  i,j=I
  for p in C:
	for q in C:
	 X=x,y=i+p,j+q
	 if X in K and X!=I and set(M[i][j]+M[x][y])<=set(' '+l):G+=[(I,X)];S+=[I,X]
 B=0
 for L in P(list(set(S))):
  b=0
  for p in L:
	for i,j in p:
	 if' '!=M[i][j]: 
		try:find_cycle(from_edgelist([(I,X)for I,X in G if I in p+Z and X in p+Z]));b+=1
		except:1
		break
	if b>B:B=b
 R+=B
print R

Try it online!

  1. For each letter A (except o, O, and 0) the code build a graph representing the adjacency of the different occurrences of letter A and space in the initial given matrix. Then it computes the set of semi-separated cycles covering the graph when maximizing the number of cycles (separation is based only on the letter A, the same space can be used for several cycles).

  2. The code passes all tests.

  3. Input: the list of lines of the matrix.

  4. More explanation and golfing coming soon.
\$\endgroup\$
  • 1
    \$\begingroup\$ 714 bytes by using a combination of tabs and spaces as indentations, instead of only spaces. \$\endgroup\$ – Kevin Cruijssen Jan 21 at 14:51

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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