# HackerRank Crossword Puzzle Interview preparation kit solution

In this HackerRank Crossword Puzzle Interview preparation kit problem you need to Complete the crosswordPuzzle function. It should return an array of strings, each representing a row of the finished puzzle.

## Problem solution in Python programming.

```from copy import deepcopy

def fill_board(board, words):
if len(words) == 0:
for a in board:
for b in a:
print(b, end="")
print("")
first_open_space = open_space_finder(board)
result = word_placer(first_open_space, board, words)
if not result:
return False

def open_space_finder(board):
for a in range(len(board)):
for b in range(len(board[a])):
if board[a][b] == '-':
return word_finder([a, b], board)

def word_finder(open_space, board):
word_place =[]
x = open_space[0]
y = open_space[1]
if x in range(1, len(board)-1):
if look_up(x,y,board):
word_place.append([x-1, y])
word_place.append(open_space)
return fill_down(word_place, board)
if look_down(x,y,board):
word_place.append(open_space)
word_place.append([x+1, y])
return fill_down(word_place, board)
elif x == 0:
if look_down(x,y,board):
word_place.append(open_space)
word_place.append([x+1, y])
return fill_down(word_place, board)

if y in range(1, len(board[y])-1):
if look_left(x,y,board):
word_place.append([x, y-1])
word_place.append(open_space)
return fill_across(word_place, board)
if look_right(x,y, board):
word_place.append(open_space)
word_place.append([x, y+1])
return fill_across(word_place, board)
elif y == 0:
if look_right(x,y, board):
word_place.append(open_space)
word_place.append([x, y+1])
return fill_across(word_place, board)

def look_up(x, y, board):
return board[x-1][y]!='+'

def look_down(x, y, board):
return board[x+1][y]!='+'

def look_left(x, y, board):
return board[x][y-1]!='+'

def look_right(x, y, board):
return board[x][y+1] != '+'

def fill_down(place_list, board):
where_to_start = place_list[len(place_list)-1]
x =where_to_start[0]+1
y= where_to_start[1]
while x<len(board):
if board[x][y]!='+':
place_list.append([x,y])
x += 1
else:
x=len(board)
return place_list

def fill_across(place_list, board):
where_to_start = place_list[len(place_list)-1]
x = where_to_start[0]
y = where_to_start[1]+1
while y<len(board[x]):
if board[x][y] != '+':
place_list.append([x,y])
y += 1
else:
y = len(board[x])
return place_list

def word_placer(place_list, board, words):
words_that_fit = [X for X in words if len(X) == len(place_list)]

for a in words_that_fit:
board1 = deepcopy(board)
words1 = deepcopy(words)
for index in range(len(a)):
x = place_list[index][0]
y = place_list[index][1]
if board[x][y] == '-':
board1[x][y] = a[index]
else:
if board[x][y] != a[index]:
break
if index == len(a)-1:
words1.remove(a)
buzz = fill_board(board1, words1)
break
return False
first_board = []
for x in range(10):
string = input()
string_list =list(string)
first_board.insert(x, string_list)
words = input().split(';')
fill_board(first_board, words)```

## Problem solution in Java Programming.

```import java.util.*;

public class CrosswordPuzzle {

private static final StringBuilder output = new StringBuilder();

private static boolean solve(char[][] board, List<String> words) {
Location start = null;
StringBuilder prefixBuilder = new StringBuilder();
Direction direction = null;
int expectedSize = 0;
int col = -1;
int row = -1;
for (int i = 0; i < board.length && row < 0; i++) {
for (int j = 0; j < board[i].length && col < 0; j++) {
if (board[i][j] == '-') {
row = i;
col = j;
}
}
}

if (col + 1 < board[row].length && board[row][col + 1] == '-') {
direction = Direction.RIGHT;
int start1 = col;
for (int j = col - 1; j >= 0 && board[row][j] != '+'; j--) {
prefixBuilder.append(board[row][j]);
expectedSize++;
start1 = j;
}
prefixBuilder.reverse();
for (int j = col; j < board[row].length && board[row][j] != '+'; j++) {
expectedSize++;
}
start = new Location(row, start1);
} else {
direction = Direction.DOWN;
int start1 = row;
for (int i1 = row; i1 < board.length && board[i1][col] == '-'; i1++) {
expectedSize++;
}
for (int i1 = row - 1; i1 >= 0 && board[i1][col] != '+'; i1--) {
prefixBuilder.append(board[i1][col]);
expectedSize++;
start1 = i1;
}
prefixBuilder.reverse();
start = new Location(start1, col);
}

String prefix = prefixBuilder.toString();
List<String> matching = new ArrayList<>();
for (String word : words) {
if (word.length() == expectedSize && (prefix.isEmpty() || word.startsWith(prefix))) {
}
}
if (matching.isEmpty()) {
return false;
}

for (String matched : matching) {
words.remove(matched);

if (direction == Direction.RIGHT) {
for (int i = 0; i < matched.length(); i++) {
board[start.row][start.col + i] = matched.charAt(i);
}
} else {
for (int i = 0; i < matched.length(); i++) {
board[start.row + i][start.col] = matched.charAt(i);
}
}

char[][] clone = clone(board);
boolean result = true;
if (!words.isEmpty()) {
result = solve(clone, words);
}
if (!result) {
} else {
print(clone);
return true;
}
}
return words.isEmpty();
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
char[][] board = new char[10][];
for (int i = 0; i < 10 && scanner.hasNextLine(); i++) {
String str = scanner.nextLine();
board[i] = str.toCharArray();
}

String[] words = scanner.nextLine().split(";");
List<String> list = new ArrayList<>(words.length);
solve(board, list);
System.out.println(output);
}

private static void print(char[][] board) {
if (output.length() > 0) {
return;
}

for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
output.append(board[i][j]);
}
output.append(System.lineSeparator());
}
}

private static char[][] clone(char[][] board) {
char[][] result = new char[board.length][];
System.arraycopy(board, 0, result, 0, board.length);
return result;
}

private static class Location {
private final int row;
private final int col;

public Location(int row, int col) {
this.row = row;
this.col = col;
}
}

private enum Direction {
LEFT, RIGHT, UP, DOWN
}
}```

### Problem solution in C++ programming.

```#include <cassert>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct Gap
{
Gap(int x, int y, int l, bool acr) : row(x), col(y), len(l), across(acr) {}

int row;
int col;
int len;
bool across;
};

bool operator==(const Gap& lhs, const Gap& rhs)
{
return ((lhs.row == rhs.row) &&
(lhs.col == rhs.col) &&
(lhs.len == rhs.len) &&
(lhs.across == rhs.across));
}

ostream& operator<<(ostream& os, const Gap& g)
{
return os << "{" << g.row << ", " << g.col << ", " << g.len << ", " << g.across << "}";
}

pair<vector<vector<char>>, bool> solve(vector<vector<char>> M, vector<Gap> g, vector<string> w)
{
if (w.empty())
return make_pair(M, true);

// Over all gaps
for (int i = 0; i < g.size(); ++i)
{
// Try every remaining word
for (int j = 0; j < w.size(); ++j)
{
Gap gg = g[i];
if (gg.len != w[j].size())
continue;

// Make a copy of M
vector<vector<char>> MM = M;

// Every character of the gap
if (gg.across)
{
bool success = true;
for (int k = 0; k < gg.len; ++k)
{
if (MM[gg.row][gg.col + k] == '-')
MM[gg.row][gg.col + k] = w[j][k];

else if (MM[gg.row][gg.col + k] != w[j][k])
success = false;
}

if (success)
{
vector<Gap> gg = g;
gg.erase(gg.begin() + i);
vector<string> ww = w;
ww.erase(ww.begin() + j);
pair<vector<vector<char>>, bool> x = solve(MM, gg, ww);
if (x.second == true)
return x;
}
}
else
{
bool success = true;
for (int k = 0; k < gg.len; ++k)
{
if (MM[gg.row + k][gg.col] == '-')
MM[gg.row + k][gg.col] = w[j][k];

else if (MM[gg.row + k][gg.col] != w[j][k])
success = false;
}

if (success)
{
vector<Gap> gg = g;
gg.erase(gg.begin() + i);
vector<string> ww = w;
ww.erase(ww.begin() + j);
pair<vector<vector<char>>, bool> x = solve(MM, gg, ww);
if (x.second == true)
return x;
}
}

}
}

return make_pair(M, false);
}

vector<Gap> find_gaps(const vector<vector<char>>& M)
{
vector<Gap> gaps;

// row wise iteration
for (int row = 0; row < M.size(); ++row)
{
int start = -1;
int stop = -1;
if (M[row][0] == '-')
{
start = 0; stop = 0;
}

int col = 1;
for (col = 1; col < M[row].size(); ++col)
{
if ((M[row][col] != M[row][col - 1]) && (start == -1))
{
start = col;
}
else if (M[row][col] != M[row][col - 1])
{
stop = col - 1;
if (stop > start)
{
gaps.push_back(Gap(row, start, stop - start + 1, true));
}

start = -1;
stop = -1;
}
}

stop = col - 1;
if ((M[row][stop] == '-') && (stop > start))
{
gaps.push_back(Gap(row, start, stop - start + 1, true));
}
}

// column wise iteration
for (int col = 0; col < M[0].size(); ++col)
{
int start = -1;
int stop = -1;
if (M[0][col] == '-')
{
start = 0; stop = 0;
}

int row = 1;
for (row = 1; row < M.size(); ++row)
{
if ((M[row][col] != M[row - 1][col]) && (start == -1))
{
start = row;
}
else if (M[row][col] != M[row - 1][col])
{
stop = row - 1;
if (stop > start)
{
gaps.push_back(Gap(start, col, stop - start + 1, false));
}

start = -1;
stop = -1;
}
}

stop = row - 1;
if ((start > -1) && (M[stop][col] == '-') && (stop > start))
{
gaps.push_back(Gap(start, col, stop - start + 1, false));
}

}

return gaps;
}

vector<string> vectorize(const string& words)
{
int start = 0;
int stop = 0;
vector<string> out;

for (int stop = 0; stop < words.size(); ++stop)
{
if (words[stop] == ';')
{
out.push_back(words.substr(start, stop - start));
start = stop + 1;
stop = stop + 2;
}
}

// Push the last word
out.push_back(words.substr(start, stop - start));

return out;
}

int main()
{
{
// Test vectorize words
string x = "LONDON;DELHI;ICELAND;ANKARA";
vector<string> w = vectorize(x);
assert(w.size() == 4);
assert(w[0] == "LONDON");
assert(w[1] == "DELHI");
assert(w[2] == "ICELAND");
assert(w[3] == "ANKARA");
}

{
// Test find_gaps
vector<vector<char>> M =
{ //0    1    2    3    4    5
{'+', '-', '+', '-', '-', '+'}, // 0,3,2,true; 0,1,3,false; 0,3,3,false
{'-', '-', '-', '-', '+', '+'}, // 1,0,4,true
{'+', '-', '+', '-', '+', '+'}, //
{'+', '+', '+', '+', '+', '+'}, //
{'+', '-', '+', '-', '-', '-'}, // 4,3,3,true; 4,1,2,false
{'+', '-', '+', '+', '+', '+'}
};

vector<Gap> gaps = find_gaps(M);
assert(gaps.size() == 6);
assert(gaps[0] == Gap(0, 3, 2, true));
assert(gaps[1] == Gap(1, 0, 4, true));
assert(gaps[2] == Gap(4, 3, 3, true));
assert(gaps[3] == Gap(0, 1, 3, false));
assert(gaps[4] == Gap(4, 1, 2, false));
assert(gaps[5] == Gap(0, 3, 3, false));
}

vector<vector<char>> M(10, vector<char>(10, ' '));
for (int i = 0; i < 10; ++i)
for (int j = 0; j < 10; ++j)
cin >> M[i][j];

vector<Gap> gaps = find_gaps(M);

string words;
cin >> words;
vector<string> w = vectorize(words);

pair<vector<vector<char>>, bool> x = solve(M, gaps, w);
if (x.second == true)
{
vector<vector<char>>& m = x.first;
for (auto v : m)
{
for (auto c : v)
cout << c;
cout << endl;
}
}
}```

### Problem solution in C programming.

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int fill_puzzle(char *puzzle, char words[10][10], int W, int *lengths){
char start,oldentry[10],*c;
int scpos = 0;
while(*(puzzle+scpos)!='-'&& scpos<100) scpos++;
if(scpos==100)return 1;
int length = 0;
int across = 0;
int delta = 10;
if(*(puzzle+scpos+1)=='-') {
across=1; //across clue
delta = 1;
}
while(*(puzzle+scpos+delta*length)!='+' && ((!across && (scpos+delta*length<100)) || (across && (length<10*((scpos/10)+1)-scpos)))) length++;
start = 0;
if((across && scpos%10>0) || (!across && scpos>10)){
if(*(puzzle+scpos-across-(1-across)*10)!='+') { // joined to another word
start = *(puzzle+scpos-across-(1-across)*10);
length++;
scpos -= across+(1-across)*10;
}
}
for(int iw=0;iw<W;iw++){
int startok = 1;
if(start && start!=words[iw][0]) startok = 0;
if(lengths[iw]==length && startok) {
int temp = lengths[iw];
lengths[iw] = 0;
int fitok = 1;
for(int wc=0;wc<length;wc++) {
c = puzzle+scpos+10*wc;
if(across) c = puzzle+scpos+wc;
oldentry[wc] = *c;
if(*c=='-'){
*c = words[iw][wc];
} else {
if(*c!=words[iw][wc])fitok=0;
}
}
if(fitok) fitok = fill_puzzle(puzzle,words,W,lengths);
if(fitok) return 1;
lengths[iw] = temp;
for(int wc=0;wc<length;wc++) {
c = puzzle+scpos+across*wc+(1-across)*10*wc;
*c = oldentry[wc];
}
}
}
return 0;
}

int main() {
char puzzle[100], words[10][10], line[101], eol;
int *lengths = calloc(10,sizeof(int));
for(int i=0;i<10;i++) {
scanf("%s",line);
for(int j=0;j<10;j++) *(puzzle+10*i+j) = line[j];
}
char c = 0;
int wpos = 0;
int nwords = 0;
scanf("%s",line);
for(int i=0;i<strlen(line);i++) {
if(line[i]==';') {
nwords++;
wpos = 0;
} else {
words[nwords][wpos] = line[i];
wpos++;
lengths[nwords]++;
}
}
nwords++;
int fitok = fill_puzzle(puzzle,words,nwords,lengths);
for(int i=0;i<10;i++) {
for(int j=0;j<10;j++)printf("%c",*(puzzle+10*i+j));
printf("\n");
}
return 0;
}```

### Problem solution in JavaScript programming.

```const _ = require('lodash');
const H = Symbol('horizontal');
const V = Symbol('vertical');

// group words by length and sorted by # of occurrences of words of each length
// idea is that lengths with fewer words should be placed first
function groupWords(words) {
return _.flatten(_.values(_.groupBy(words, 'length')).sort((a, b) => a.length - b.length));
}

// returns coords of first blank of specified length
function findBlank(grid, word) {
const desiredLen = word.length;

for (i = 0; i < 10; i += 1) {
for (j = 0; j < 10; j += 1) {

if (grid[i][j] === '-' || grid[i][j] === word[0]) {

if (i < 9 && (i === 0 || grid[i - 1][j] === '+') && (grid[i + 1][j] === '-' || grid[i + 1][j] === word[1])) {
let len = 0;

while (i + len < 10 && (grid[i + len][j] !== '+')) {
len += 1;
}

if (len === desiredLen) {
return { dir: V, i, j }
}
}

if (j < 9 && (j === 0 || grid[i][j - 1] === '+') && (grid[i][j + 1] === '-' || grid[i][j + 1] === word[1])) {
let len = 0;

while (j + len < 10 && (grid[i][j + len] !== '+')) {
len += 1;
}

if (len === desiredLen) {
return { dir: H, i, j }
}
}
}
}
}

return false;
}

function main(grid, words) {
if (words.length === 0) {
return grid;
}

for (let i = 0; i < words.length; i += 1) {
const newWords = words.slice();
const word = newWords.splice(i, 1)[0];

const newGrid = place(grid, word);

if (newGrid) {
const result = main(newGrid, newWords);
if (result) {
return result;
}
}
}

return false;
}

function place(grid, word) {
const len = word.length;
const loc = findBlank(grid, word);

if (!loc) {
return false;
}

const newGrid = grid.slice().map(line => line.split(''));
const iIncr = loc.dir === V ? 1 : 0;
const jIncr = loc.dir === H ? 1 : 0;

let i = loc.i;
let j = loc.j;
let count = 0;

while (count < len) {
if (newGrid[i][j] !== '-' && newGrid[i][j] !== word[count]) {
return false;
}

newGrid[i][j] = word[count];
i += iIncr;
j += jIncr;
count += 1;
}

return newGrid.map(line => line.join(''));
}

process.stdin.setEncoding('ascii');
let _input = '';
process.stdin.on('end', () => {
const grid = _input.split('\n');
const words = grid.pop().split(';');

const result = main(grid, groupWords(words));

//console.log(result); return;

console.log(result.join('\n'));
});```