# Is my kids' alphabet mat properly grouped by colors?

My kids have an alphabet mat to play with, something like this: After months with the tiles of the mat randomly placed, I got tired and placed all the tiles of the mat grouped by sections according to their background colors. So, if the letters represent the background color, I got a mat like this:

AABBCDDDE
ABBCCCDEE
ABCCCCDDE
AACCCDDEE
AAAACCCCE
AAAAAACCC


So, for colors A, B, C, D and E there is always a way to connect all the tiles with the same background color either horizontally or vertically in the mat. That's what I call a mat properly grouped by colors. You can see the groups for the previous example in the following tables:

AA
A
A
AA
AAAA
AAAAAA

BB
BB
B

C
CCC
CCCC
CCC
CCCC
CCC

DDD
D
DD
DD

E
EE
E
EE
E


Also, there is only one group for every color, so this would not be valid:

ABA
ABA


Because color A tiles are not grouped in only one group. This also would not be valid because the tiles do not connect either horizontally or vertically:

AB
BA


### The challenge

Given a 2-dimensional array of characters in the printable ASCII range (does not need to be a square one as long as the size of both dimensions are equal to or greater than 1), check if the array represents a mat properly grouped by colors (each different character in the array represents a different color). Input may be in any reasonable format as long as it represents a 2-dimensional array of characters (2D char array, array of strings of the same length, and so on), and output must be a pair of truthy and falsey values (0/1, 't'/'f', true/false, whatever as long as something is returned and the return values are consistent across inputs).

This is code-golf, so may the shortest program/function/method/lambda for each language win!

### Examples

A    truthy

AB
AB   truthy

AB
BA   falsey

ABCDE    truthy

ABCDC    falsey

**::dd22
***:d222
*:::::22    truthy

$$%%%&&$$%%&&&&
&&$$%&& falsey AABBCDDDE ABBCCCDEE ABCCCCDDE AACCCDDEE AAAACCCCE AAAAAACCC truthy AABB ABBA AAAA truthy AAAB AAAA AAAA truthy  ### My mat properly grouped by colors (I still have to fix those borders...) • Out of curiosity, why wouldn't you arrange the mat in alphanumerical order? Nothing to do with the challenge of course, just wondering Nov 23, 2017 at 17:04 • @cairdcoinheringaahing because then my particular OCD would not be satisfied. :-) Nov 23, 2017 at 17:11 • Your kids continue to be a source of inspiration for code golf challenges :-) Nov 23, 2017 at 17:52 • Why do the colours have to be represented by characters rather than some other input (like integers or even pixels maybe)? Nov 23, 2017 at 22:22 • speaking of ocd, this challenge won’t be complete without a picture of the mat properly grouped Nov 24, 2017 at 2:16 ## 7 Answers # MATL, 16 15 bytes 1e"G@=4&1ZI1>vzg  Input is a 2D char array (with rows separated by ;). Output is 0 if input qualifies, or 1 otherwise. ### Explanation The code essentialy checks if each char in the input has only one connected component, considering 4-connectivity (that is, no diagonals). Repeated chars are processed repeatedly (which is golfier than deduplicating). 1e % Implicit input. Reshape into a row vector of chars " % For each char G % Push input again @ % Push current char = % Equal (element-wise)? Gives a matrix of zeros and ones, where one % represents the presence of the current char 4 % Push 4. This will indicate 4-connectivity &1ZI % Matrix with labels of connected componnents. Inputs are a number (4) % to indicate connectivity, and a binary matrix. The output is a matrix % the same size as the input where each connected componnent of ones % in the input is replaced by a different integer starting at 1 1> % Greater than 1 (element-wise)? The result is a matrix. If the result % is true for some entry the input doesn't qualify v % Concatenate vertically with results from previous iterations z % Number of nonzero/true values g % Logical. Converts nonzero to true % Implicit end. Implicit display. False / true are displayed as 0 / 1  # Befunge-93, 317 bytes Edit: Fixed for proper byte-count. Also could be golfed further 93+:10pv +93p01+1g01_ v@.1< gp00g1+>00p~1+:93+!#^_1-00g10 50p93+:vv_v#!:gg03:p02:<>40p# !g01: <>\ 1+:vvp05:+<@^p03_^# v93_v# !- g00<4v04g<^1<vp06:< >+\!\>\ 3v> 40v0>g-v^<.g>:70vp 07_v#:<^ >#+0# g#\< 10\v4gg<^ !#v _^ g03p <\ v1_#:^5>0g - < ^ g02p1< >-:#^_^#:g05 -1< ^p\g06\0\+1:\g06\-1:\g06:\+1g06:g07  Prints 1 as the truthy, 0 as the falsey Try It Online Here's a visualisation of the path the pointer takes Note: this is for an old version # How it works Here's some quick and dirty pseudocode a = 2Darray() # from 12,12 down and to the right arrayLocation = 12 x = arrayLocation #stored at 0,0 y = arrayLocation #stored at 1,0 i = input() #stored in the stack while (i != 0): if (i == 10): y++ x = init else a[x][y] = i x++ i = input new.x = init #stored at 2,0 new.y = init #stored at 3,0 currentChar = 0 #stored at 4,0 chars = array() #stored at 1,1 onwards charnum = 0 #stored 5,0 ToCheck = array() #stored in the stack current.x = null #stored at 6,0 current.y = null #stored at 7,0 while (new.y < y): if (a[new] != 0) currentChar = a[new] toCheck[] = new while (toCheck) current = toCheck.pop() if (a[current] == currentChar) toCheck.append(adjacent(current)) a[current] = 0 foreach (chars as char) if (char == currentChar) return 0 charNum++ chars[charNum] = char new.x++ if (new.x > x) new.x = init new.y++ return 1  Basically, after storing the input, it goes through the whole thing, checking each space. When it finds a space with a character in it it adds the coordinates to the stack. Then it checks the spaces around it for the same character recursively, setting each space to 0. When it has exhausted that character's section, it checks whether that character has already had a section. If so, return 0. If not, add it to the array of characters. Once it has gone through the whole grid with no duplicates, it returns 1. For people familiar with Befunge, here's a spaced out version of the code 96+:10p v +69p01+1g01_v +96:+1~p00<+1g00pg01g00-1_^# v < >40p50p96+:v ^ v @.1< > >:10g #^_30p:20p:30gg:#v_>1+:00g-!#v_0 >30g+ v < ^ >96+1^ >40p30gv ^ >:!#v_70p:60p:70gg40 g-!#v_> v ^ > ^ 1:\g06\+1:g 07\g07\-1:\g07\ +1: <^p\g06\0\- v < ^ >50gv >5\g1+:50p40g\1p20g^ >:!#^_:1g40g-!#v_1- >0.@  • to be honest, I feel like you should count it as 337 bytes. Otherwise, how do you specify the dimensions of the code within the file itself? The newlines should count too. – Maya Dec 20, 2017 at 16:04 • @NieDzejkob Yeah, I’ve since changed how I count bytes and conformed to whatever TIO says. Also I had the line count wrong anyway? Maybe tomorrow I’ll have a go at shortening it a bit further – Jo King Dec 20, 2017 at 16:22 # J, 66 bytes c=.1=+/@,+.]-:]*[:*@+/((,|."1)0,.1 _1)&(|.!.0) [:*/[:c"2[="_ 0~.@,  c defines a verb that tells you if a matrix of ones and zeros is connected. It treats singleton ones as a special case of true. Otherwise it takes an orthogonal neighbor count of every cell, then the signum of that count, then multiplies that with the original matrix: if that product equals the original matrix, then it's connected. The neighbor count is achieved by shifting in all 4 directions, then summing. The 4 direction shift is achieved using the "x-arg can by a table" feature of rotate/shift |. Finally, the answer itself achieved by creating a ones/zeros matrix for every unique ~. element of the input, and then ensuring that all of those matrices are connected. This is the verb in the second line. Try it online! # JavaScript (ES6), 114 bytes Takes input as an array of strings. Returns 0 or 1. a=>(C={},F=x=>!C[c=a[y][x]]|(g=v=>(a[y+v]||[])[x]==c)(-1)|g(1)|g(0,x--)|g(0,x+=2)?a[y+=!c]?F(C[c]=c?x:0):1:0)(y=0)  ### Test cases let f = a=>(C={},F=x=>!C[c=a[y][x]]|(g=v=>(a[y+v]||[])[x]==c)(-1)|g(1)|g(0,x--)|g(0,x+=2)?a[y+=!c]?F(C[c]=c?x:0):1:0)(y=0) console.log(f([ // 1 "A" ])) console.log(f([ // 1 "AB", "AB" ])) console.log(f([ // 0 "AB", "BA" ])) console.log(f([ // 1 "ABCDE" ])) console.log(f([ // 0 "ABCDC" ])) console.log(f([ // 1 "**::dd22", "***:d222", "*:::::22" ])) console.log(f([ // 0 "$$$%%%&&", "$$%%&&&&", "&&$$$%&&"
]))

console.log(f([ // 1
"AABBCDDDE",
"ABBCCCDEE",
"ABCCCCDDE",
"AACCCDDEE",
"AAAACCCCE",
"AAAAAACCC"
]))

console.log(f([ // 1
"AABB",
"ABBA",
"AAAA"
]))

console.log(f([ // 1
"AAAB",
"AAAA",
"AAAA"
]))

### Formatted and commented

a => (                            // given an array of strings a
C = {},                         // C = object holding encountered characters
F = x =>                        // F = recursive function taking x:
!C[c = a[y][x]]               //   c = current character; is it a new one?
| (g = v =>                   //   g = helper function taking v
(a[y + v] || [])[x] == c  //       and testing whether a[y + v][x] == c
)(-1)                       //   test a[y - 1][x]
| g(1)                        //   test a[y + 1][x]
| g(0, x--)                   //   test a[y][x - 1]
| g(0, x += 2) ?              //   test a[y][x + 1]; if at least one test passes:
a[y += !c] ?                //     increment y if c is undefined; if a[y] exists:
F(C[c] = c ? x : 0)       //       update C, update x and do a recursive call
:                           //     else:
1                         //       all characters have been processed -> success
:                             //   else:
0                           //     invalid character detected -> failure
)(y = 0)                          // initial call to F, starting with x = y = 0


# Wolfram Language (Mathematica), 96 bytes

And@@(ConnectedGraphQ@Subgraph[GridGraph@Dimensions[t],Tr/@Position[c,#]]&/@(c=Join@@(t=#)))&


Takes input as a 2D list of characters: for example, {{"A","B"},{"C","D"}}.

The  character is \[Transpose].

## How it works

For each character c in the input, takes the Subgraph of the GridGraph of the same Dimensions as the input which corresponds to every Position in which c occurs, and checks if it's a ConnectedGraphQ.

# Python 2, 247 bytes

def f(a):
b=map(list,a.split('\n'));l=len(b)
for c in set(a):i=a.find(c);g(b,i/l,i%l,c)
print all(set(l)<={0}for l in b)
def g(a,i,j,c):
if len(a)>i>-1<j<len(a)and a[i][j]==c:
for x,y in(0,1),(0,-1),(1,0),(-1,0):g(a,i+x,j+y,c);a[i][j]=0


Try it online!

# JavaScript (ES6), 181 bytes

(d,o={})=>{f=(i,j,c,l=d[i])=>{if(c&&l&&l[j]==c){l[j]='';f(i-1,j,c);f(i+1,j,c);f(i,j-1,c);f(i,j+1,c);o[c]=1}};d.map((e,i)=>e.map((c,j)=>o[c]||f(i,j,c)));return!d.some(e=>e.join(''))}


Whenever a new color tile is found, fill the connected ones with empty strings. If the mat is properly grouped by colors, all tiles should be filled with empty strings.

### Test Code

const t =
(d,o={})=>{f=(i,j,c,l=d[i])=>{if(c&&l&&l[j]==c){l[j]='';f(i-1,j,c);f(i+1,j,c);f(i,j-1,c);f(i,j+1,c);o[c]=1}};d.map((e,i)=>e.map((c,j)=>o[c]||f(i,j,c)));return!d.some(e=>e.join(''))}
;

const mat = s=>s.split('\n').filter(l=>l).map(l=>l.split(''));
console.log('true?', t(mat(
A
)));
console.log('true?', t(mat(
AB
AB
)));
console.log('false?', t(mat(
AB
BA
)));
console.log('true?', t(mat(
ABCDE
)));
console.log('false?', t(mat(
ABCDC
)));
console.log('true?', t(mat(
**::dd22
***:d222
*:::::22
)));
console.log('false?', t(mat(
$$%%%&&$$%%&&&&
&&\$%&&
)));
console.log('true?', t(mat(
AABBCDDDE
ABBCCCDEE
ABCCCCDDE
AACCCDDEE
AAAACCCCE
AAAAAACCC
)));
console.log('true?', t(mat(
AABB
ABBA
AAAA
)));
console.log('true?', t(mat(
AAAB
AAAA
AAAA
)));

• How does your program take input? Nov 24, 2017 at 3:22