fillBlanks.js

export function fillBlanks( { index=0, structure, matrix, words }) {
  const { col , row, length, horizontal } = structure[index];
  const spaceStatus = getSpaceStatus({ matrix, length, col, row, horizontal });
  const validWords = getPossibleWords({ words : words[length], spaceStatus });
  if ( validWords.length ) {
    return tryAllWords({ validWords, words, structure, index : index+1, matrix, col , row, length, horizontal });
  }
  return 0;
}

function tryAllWords({ validWords, words, structure, index, matrix, col , row, length, horizontal }) {
  if ( index >= structure.length ) {
    return validWords.length;
  }
  let combinations = 0;
  for ( const word of validWords ) {
    const newWords = cloneObjOfArray(words);
    // Remove the used word
    newWords[word.length].splice(newWords[word.length].indexOf(word),1);
    // Insert the word in the matrix
    const newMatrix = insertOnMatrix({ matrix, word, col, row, horizontal });
    combinations += fillBlanks({
      matrix: newMatrix,
      words : newWords,
      index,
      structure
    });
  }
  return combinations;
}

fillBlanks3.js

export function fillBlanks( { index=0, structure, matrix, words, position=false, totalPositions, usedGroups }) {
  const { col , row, length, horizontal, intersections } = structure[index];
  const pointStatus = getPointStatus({ matrix, intersections });
  // Make return only the first valid word to try
  let validWords = pointStatus.length ?
                    getPossibleWords({ words : words[length], pointStatus })
                    : words[length];
  if ( validWords.length ) {
    let validGroups = groupWords({ words : validWords, intersections });
    if ( position !== false ) {
      const vG = {};
      const groups = Object.keys(validWords).filter( ( word, index ) => index%totalPositions === position );
      for ( const group of groups ) {
        vG[group] = validWords[group];
      }
      validWords = vG;
    }
    if ( Object.keys(validGroups).length ) {
      return tryAllWordsGroups({ validGroups, words, structure, index, matrix, col , row, length, horizontal, usedGroups });
    }
  }
}

getIntersections.js

function getIntersections( structure ) {
  for ( let i=0;i<structure.length-1;i++) {
    for ( let j=i+1;j<structure.length;j++) {
      const structA = structure[i];
      const structB = structure[j];
      if ( structA.horizontal !== structB.horizontal ) {
        if ( structA.horizontal ) {
          if ( structB.col >= structA.col && structB.col <= structA.col+structA.length
             && structA.row >= structB.row && structA.row <= structB.row+structB.length ){
            // They intersect
            structA.intersections.push({
              col : structB.col,
              row : structA.row,
              point : structB.col-structA.col
            });
            structB.intersections.push({
              col : structB.col,
              row : structA.row,
              point : structA.row-structB.row
            });
          }
        } else {
          if ( structB.row >= structA.row && structB.row <= structA.row+structA.length
            && structA.col >= structB.col && structA.col <= structB.col+structB.length ){
            // They intersect
            structA.intersections.push({
              col : structA.col,
              row : structB.row,
              point : structB.row-structA.row
            });
            structB.intersections.push({
              col : structA.col,
              row : structB.row,
              point : structA.col-structB.col
            });
          }
        }
      }
    }
  }
  return structure;
}

getPointStatus2.js

function getPointStatus( { matrix, intersections }) {
  const pointStatus = [];
  for ( const intersection of intersections ) {
    const char = matrix[intersection.row][intersection.col];
    if ( matrix[intersection.row][intersection.col] !== emptyCharacter ) {
      pointStatus.push({
        pos : intersection.point,
        char
      });
    }
  }
  return pointStatus;
}

getSpaceStatus.js

function getSpaceStatus( { matrix, length, col, row, horizontal }) {
  let x = col, y = row;
  if ( horizontal ) {
    return matrix[y].substr(x,length);
  } else {
    let word = '';
    const end = y+length;
    for ( ; y<end; y++ ) {
      word+=matrix[y][x];
    }
    return word;
  }
}

getStructure.js

const blackCharacter = '#';

export function getStructure( matrix ) {
  const lineLength = matrix.length && matrix[0].length;
  const dictionary = [];
  for ( let i=0; i<matrix.length; i++) {
    for ( let j=0; j<lineLength; j++ ) {
      // Horizontal
      if ( j==0 || matrix[i][j-1] === blackCharacter && matrix[i][j] !== blackCharacter ) {
        let a=j;
        // Find last blackCharacter of the row
        for ( ; a<lineLength && matrix[i][a] !== blackCharacter; ) { a++; }
        const wordLength = a-j;
        if ( wordLength > 1 ) {
          dictionary.push({
            col : j,
            row : i,
            length : wordLength,
            horizontal : true
          });
        }
      }
      // Vertical
      if ( i==0 || matrix[i-1][j] === blackCharacter && matrix[i][j] !== blackCharacter ) {
        let a=i;
        // Find last blackCharacter of the col
        for ( ; a<lineLength && matrix[a][j] !== blackCharacter; ) { a++; }
        const wordLength = a-i;
        if ( wordLength > 1 ) {
          dictionary.push({
            col : j,
            row : i,
            length : wordLength,
            horizontal : false
          });
        }
      }
    }
  }
  return dictionary;
}

getValidWords.js

function isAValidWord( spaceStatus ) {
  const { length } = spaceStatus;
  return ( word ) => {
    for ( let i=0; i<length; i++ ) {
      if ( spaceStatus[i] !== emptyCharacter && spaceStatus[i] !== word[i]) {
        return false;
      }
    }
    return true;
  };
}

function getPossibleWords({ words, spaceStatus }) {
  return words.filter(isAValidWord(spaceStatus));
}

groupWords.js

function groupWords({ words , intersections }) {
  const groups = {};
  for ( const word of words ) {
    let intId = '';
    for ( const { point } of intersections ) {
      intId += word[point];
    }
    if ( !groups[intId] ) {
      groups[intId] = [];
    }
    groups[intId].push(word);
  }
  return groups;
}

inserWord.js

// Insert the word and return the new matrix
function insertOnMatrix( { matrix, word, col, row, horizontal }) {
  const newMatrix = matrix.slice(0);
  let x = col, y = row;
  if ( horizontal ) {
    newMatrix[y] = newMatrix[y].substr(0,x) + word + newMatrix[y].substr(x+word.length);
  } else {
    for ( let i=0; i<word.length; i++) {
      newMatrix[y+i] = newMatrix[y+i].substr(0,x) + word[i] + newMatrix[y+i].substr(x+1);
    }
  }
  return newMatrix;
}

isAValidWord2.js

function isAValidWord(pointStatus) {
  return ( word ) => {
    for ( const status of pointStatus ) {
      if ( word[status.pos] !== status.char ) {
        return false;
      }
    }
    return true;
  };
}

master.js

import fs from 'fs';
import cluster from 'cluster';
import os from 'os';
import readline from 'readline';
import yargs from 'yargs';

const { wordFile } = yargs
  .option('w', {
    alias: 'wordFile',
    type: 'string',
    default: 'words.italian.txt'
  })
  .argv;

const inputFile = fs.readFileSync('input.txt','utf8');
const matrix = inputFile.split('\n').filter( line => line.trim().length);
const totalPositions = os.cpus().length;

if (cluster.isMaster) {

  const structure = getStructure(matrix);

  let combinations_found = 0, workers_alive = 0;

  for ( let i=0; i<totalPositions; i++ ) {
    const worker = cluster.fork();
    workers_alive++;
    worker.on('online', ( ) => {
      worker.send({
        structure,
        i
      });
    });
    worker.on('message', ( combinations ) => {
      combinations_found += combinations;
      workers_alive--;
      if ( !workers_alive ) {
        console.log(`Combinations found ${combinations_found}`);
      }
    });
  }
}

readWords.js

import fs from 'fs';
import readline from 'readline';

const words = {};
const wordReader = readline.createInterface({
  input: fs.createReadStream('words.italian.txt','utf8')
});

wordReader.on('line',( word ) => {
  if ( word.length ) {
    if ( !words[word.length] ) {
      words[word.length] = [];
    }
    words[word.length].push(word);
  }
});

wordReader.on('close', () => {
  console.log('Readed all!');
});