Crosswords-101 – HackerRank Solution

In this post, we will solve Crosswords-101 HackerRank Solution. This problem (Crosswords-101) is a part of HackerRank Functional Programming series.

Task

A 10 x 10 Crossword grid is provided to you, along with a set of words (or names of places) which need to be filled into the grid.
The cells in the grid are initially, either + signs or - signs.
Cells marked with a + have to be left as they are. Cells marked with a - need to be filled up with an appropriate character.

Input Format

The input contains 10 lines, each with 10 characters (which will be either + or – signs).
After this follows a set of words (typically nouns and names of places), separated by semi-colons (;).

Constraints

There will be no more than ten words. Words will only be composed of upper-case A-Z characters. There will be no punctuation (hyphen, dot, etc.) in the words.

Output Format

Position the words appropriately in the 10 x 10 grid, and then display the 10 x 10 grid as the output. So, your output will consist of 10 lines with 10 characters each.

Sample Input 0

+-++++++++
+-++++++++
+-++++++++
+-----++++
+-+++-++++
+-+++-++++
+++++-++++
++------++
+++++-++++
+++++-++++
LONDON;DELHI;ICELAND;ANKARA

Sample Output 0

+L++++++++
+O++++++++
+N++++++++
+DELHI++++
+O+++C++++
+N+++E++++
+++++L++++
++ANKARA++
+++++N++++
+++++D++++

Sample Input 1

+-++++++++
+-++++++++
+-------++
+-++++++++
+-++++++++
+------+++
+-+++-++++
+++++-++++
+++++-++++
++++++++++
AGRA;NORWAY;ENGLAND;GWALIOR

Sample Output 1

+E++++++++
+N++++++++
+GWALIOR++
+L++++++++
+A++++++++
+NORWAY+++
+D+++G++++
+++++R++++
+++++A++++
++++++++++

Solution – Crosswords-101 – HackerRank Solution

Scala

import java.util.Scanner

object Solution {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)

    val size = 10

    val field = (0 until size).map(_ => sc.nextLine.toIndexedSeq)
    val words = sc.nextLine.split(';')
      .groupBy(_.length)
      .map { case (len, list) => len -> list.toSet }

    sc.close()

    val plus = '+'

    def isWall(x: Int, y: Int) = x < 0 || x >= size || y < 0 || y >= size || field(y)(x) == plus

    case class Coord(x: Int, y: Int)
    case class Cross(coord: Coord, letterIndex: Int)
    case class Item(len: Int, head: Coord, isHorizontal: Boolean, crosses: List[Cross])
    object Item {
      def of(x: Int, y: Int, isHorizontal: Boolean): Item = {
        def inner(xx: Int, yy: Int): Item = if (isWall(xx, yy)) Item(0, Coord(x, y), isHorizontal, Nil) else {
          val (dx, dy) = if (isHorizontal) (1, 0) else (0, 1)

          val isCross = !isWall(xx + dy, yy + dx) || !isWall(xx - dy, yy - dx)
          val preItem = inner(xx + dx, yy + dy)

          Item(preItem.len + 1, Coord(x, y), isHorizontal, if (isCross) Cross(Coord(xx, yy), if (isHorizontal) xx - x else yy - y) :: preItem.crosses else preItem.crosses)
        }

        inner(x, y)
      }
    }

    val items: List[Item] = field.indices.flatMap(y => {
      field(y).indices.flatMap(x => {
        (if (isWall(x - 1, y) && !isWall(x, y) && !isWall(x + 1, y)) List(Item.of(x, y, isHorizontal = true)) else List[Item]()) ++
          (if (isWall(x, y - 1) && !isWall(x, y) && !isWall(x, y + 1)) List(Item.of(x, y, isHorizontal = false)) else List[Item]())
      })
    }).toList

    case class Pair(item: Item, word: String)

    def solve(items: List[Item], words: Map[Int, Set[String]], acc: List[Pair]): List[Pair] = items match {
      case Nil =>
        val isCorrect = acc.flatMap(pair => pair.item.crosses.map(cross => cross.coord -> pair.word(cross.letterIndex)))
          .groupBy { case (coord, _) => coord }
          .map { case (_, list) => list.map { case (_, c) => c }.toSet.size == 1 }
          .reduce(_ && _)

        if (isCorrect) acc else Nil
      case item :: rest =>
        words(item.len).map(word => {
          solve(rest, words.updated(item.len, words(item.len) - word), Pair(item, word) :: acc)
        })
          .reduce((a, b) => if (a.isEmpty) b else a)
    }

    val answer = Array.fill(size, size)(plus)
    solve(items, words, Nil)
      .foreach { case Pair(item, word) =>
        val (dx, dy) = if (item.isHorizontal) (1, 0) else (0, 1)
        word.indices.foreach(i => answer(item.head.y + dy * i)(item.head.x + dx * i) = word(i))
      }

    println(answer.map(_.mkString("")).mkString("\n"))
  }
}

Note: This problem (Crosswords-101) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.