Crossword Formation

Description

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] 4 seconds (js)
[input] integer 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.

[JavaScript (ES6)] Syntax Tips

1
2
3
4
5
6
// Prints help message to the console
// Returns a string
function helloWorld(name) {
console.log("This prints to the console when you Run Tests");
return "Hello, " + name;
}

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
function crosswordFormation(words) {
  var permutations = permute(words);
  return permutations.reduce((acc, p) => acc + countSolutions(p), 0);
}

function countSolutions(words) {
  var count = 0;
  for (var i = 0; i < words[0].length; i++) {
    var j = words[1].indexOf(words[0][i]);
    while (j >= 0) {
      for (var k = i + 2; k < words[0].length; k++) {
        var l = words[2].indexOf(words[0][k]);
        while (l >= 0) {
          for (var m = j + 2; m < words[1].length; m++) {
            var n = words[3].indexOf(words[1][m])
            while (n >= 0) {
              if (words[3].length - n > k - i &&
                words[2].length - l > m - j &&
                words[3][k - i + n] == words[2][m - j + l]) {
                count++;
              }
              n = words[3].indexOf(words[1][m], n + 1)
            }
          }
          var l = words[2].indexOf(words[0][k], l + 1);
        }
      }

      j = words[1].indexOf(words[0][i], j + 1);
    }
  }
  return count;
}

var permArr = [];
var usedWords = [];
function permute(input) {
  var i, w;
  for (i = 0; i < input.length; i++) {
    w = input.splice(i, 1)[0];
    usedWords.push(w);
    if (input.length == 0) {
      permArr.push(usedWords.slice());
    }
    permute(input);
    input.splice(i, 0, w);
    usedWords.pop();
  }
  return permArr
};

Codefights

A way to improve your programming skills.

Crossword Formation

Description

Solution