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))) {
matching.add(word);
}
}
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) {
words.add(matched);
} 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);
Collections.addAll(list, words);
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('readable', () => _input += process.stdin.read() || '');
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'));
});
