HackerRank Crossword Puzzle 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))) {
                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'));
});