<Codesignal> Crossword Formation

Medium

You're a crossword fanatic, and have finally decided to try and create your own. However, you also love symmetry and good design, so you come up with a set of rules they should follow:

• the crossword must contain exactly four words;
• these four words should form four pairwise intersections;
• all words must be written either left-to-right or top-to-bottom;
• the area of the rectangle formed by empty cells inside the intersections isn't equal to zero.

Given 4 words, find the number of ways to make a crossword following the above-described rules. Note that two crosswords which differ by rotation are considered different.

Example

For words = ["crossword", "square", "formation", "something"], the output should be
crosswordFormation(words) = 6.

The six crosswords can be formed as shown below:

Input/Output

• [execution time limit] 0.5 seconds (c)

• [input] array.string words

  An array of distinct strings, the words you need to use in your crossword.

  Guaranteed constraints:
  words.length = 4,
  3 ≤ words[i].length < 15.

• [output] integer

  The number of ways to make a correct crossword of the desired formation.

[C] Syntax Tips

// Prints help message to the console
// Returns a string
char * helloWorld(char * name) {
    char * answer = malloc(strlen(name) + 8);
    printf("This prints to the console when you Run Tests");
    strcpy(answer, "Hello, ");
    strcat(answer, name);
    return answer;
}

---

Solution

// Arrays are already defined with this interface:
// typedef struct arr_##name {
//   int size;
//   type *arr;
// } arr_##name;
//
// arr_##name alloc_arr_##name(int len) {
//   arr_##name a = {len, len > 0 ? malloc(sizeof(type) * len) : NULL};
//   return a;
// }
//
//
int crosswordFormation(arr_string words)
{
	int row[4], col[4], count=0;

	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
			if(j!=i)
				for(row[0]=0;row[0]<strlen(words.arr[i]);row[0]++)
					for(col[0]=0;col[0]<strlen(words.arr[j]);col[0]++)
						if(words.arr[i][row[0]]==words.arr[j][col[0]])
							for(int k=0;k<4;k++)
								if(k!=i&&k!=j)
									for(row[1]=0;row[1]<strlen(words.arr[k]);row[1]++)
										for(col[1]=col[0]+2;col[1]<strlen(words.arr[j]);col[1]++)
											if(words.arr[k][row[1]]==words.arr[j][col[1]])
												for(int l=0;l<4;l++)
													if(l!=i&&l!=j&&l!=k)
														for(col[2]=0;col[2]<strlen(words.arr[l]);col[2]++)
															for(row[2]=row[0]+2;row[2]<strlen(words.arr[i]);row[2]++)
																if(words.arr[i][row[2]]==words.arr[l][col[2]])
																{
																	col[3]=col[2]+col[1]-col[0];
																	row[3]=row[2]+row[1]-row[0];
																	if(col[3]<strlen(words.arr[l])&&row[3]<strlen(words.arr[k]))
																		if(words.arr[k][row[3]]==words.arr[l][col[3]])
																			count++;
																}

	return count;
}