HackerRank Crossword Puzzle problem solution

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

HackerRank Crossword Puzzle solution in Python.

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)

Crossword Puzzle solution in Java.

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++.

#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.

#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.

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'));
});