As a software engineer, I always enjoy solving problems and that’s why I sometimes go to the coding challenge websites like hackerrank and pick one problem to solve. This time I searched in functional programming category and crosswords-101 caught my eye and I decided to solve it in Scala in a very clean and understandable way and not in a contest style way of programming!
This article is going to reveal how I solved this puzzle. But before continue, please read the problem definition and try to solve it by yourself or at least think about the way of solving it and then continue reading.
Model
Whenever you write software the good model is crucial part for your application. If your model is good then your program is very clean, easy to understand and also maintainable. That’s why I started the solution with defining modeles. The first model that I wrote was Placeholder.
Placeholder
Placeholder is a place for inserting words. For instance below you can find two placeholders:
case class Placeholder(size: Int, direction: Direction)
For placeholders that have assigned a word, there is a currentValue property that you can set. It accepts Option[String]:
val ph = Placeholder(size = 7,
direction = Horizontal,
candidateValue = Set("England", "IRELAND"))
val all: List[Placeholder] = ph.allPossibilities
all contains these placeholders:
Crosswords
No one likes a single placeholder only. That’s why we need another model for a collection of placeholders. We call this model Crosswords. Crosswords is a collection of placeholders with additional property like number of rows and columns:
case class Crosswords(rows: Int, cols: Int, placeholders: List[Placeholder]) {
// code removed for brevity
}
For instance for defining this crosswords that has 2 placeholders:
We can declare:
val cw = Crosswords(rows = 5, cols = 9, placeholders = List(
Placeholder(size = 7, direction = Horizontal, startPosition = Point(1,1)),
Placeholder(size = 3, direction = Vertical), startPosition = Point(1,1))
)
Notice about startPosition. It specifies the position of placeholder in the crosswords. It will be used by rendering the crosswords later. But what about the intersection? As you can see there is intersection between these two placeholders at first character. How can we define these intersections? We need a way to select two placeholder somehow and tell that at which index there is an intersection with other placeholder’s index. So we need an id for each placeholder for refereeing it later:
val cw = Crosswords(rows = 5, cols = 9, placeholders = List(
Placeholder(id = "ph1", size = 7, direction = Horizontal, ...),
Placeholder(id = "ph2", size = 3, direction = Vertical, ...),
))
now we can define intersections:
cw.addIntersection(from = ("ph1",0), to = ("ph2",0))
// order does not matter
// you can add ph2 first!
// for instance:
// cw.addIntersection(from = ("ph2",0), to = ("ph1",0))
Now that we have all the building blocks for creating a crosswords, how we can solve it?
How to Solve
Imagine we have two placeholders without any intersection in the crosswords. The picture below show them with their candidate values. How many possible valid solution exists?
val solutions: List[Crosswords] = cw.solveAllPossibilities
// assert(solutions.size == 8)
To get each crosswords output representation, you can call stringRepresentation, so to render all the solutions to the standard output, you can write:
solutions.foreach { crosswords =>
println(crosswords.stringRepresentation)
println("------------------------------"
}
With Intersection
But what about crosswords with intersection? Imaging we have a crosswords with 2 placeholders: ph1 and ph2 and there exists an intersection:
cw.addIntersection(from = ("ph1",2), to = ("ph2",1))
The picture below depicts the idea:
Build crosswords from string
Now that we have our models, how we can build crosswords from input string? CrosswordsBuilder.buildFrom comes to rescue.if we have a string like +- - - - -++++, we know that there exists a horizontal placeholder with size 5. findAllPlaceholders is a method that accepts a string and find all placeholders. But what about columns like:
+
+
-
-
-
+
If we can rotate it, then it becomes something like ++- - - + and now we can pass it to findAllPlaceholders method, but this time with paramter Vertical. That’s why there is a method for swaping rows with columns called swapRowsWithColumns.
So far we have found all horizontal and vertical placeholders but we have no idea about intersections between them. Since intersection can only happens between horizontal and vertical placeholders, I ‘ve defined a method called findIntersectionsBetween that accepts a list of vertical placeholders, a list of horizontal placeholders and returns all intersection between them.
Find intersections
Given two placeholder, how can you find intersection between them? For instance:
val ph1 = Placeholder(size = 5, direction = Horizontal, startPosition = (2,1))
val ph2 = Placeholder(size = 4, direction = Vertical, startPosition = (1,3))
The clue is startPosition. Each placeholder has getPositionPoints that returns all the cell position that this placeholder has occupied:
ph1.getPositionPoints
// returns List(Point(2,1), Point(2,2), Point(2,3), Point(2,4), Point(2,5))
ph2.getPositionPoints
// returns List(Point(1,3), Point(2,3), Point(3,3), Point(4,3))
And if
(ph1.getPositionPoints intersect ph2.getPositionPoints).size > 0
We are sure that there is an intersection. But we are not done yet. After finding an intersection, we should call Crosswords.addIntersection and this method does not accept (row,col) index, instead it accepts placeholder’s local index. The picture below depicts the idea:
Done!
That was the most important aspects of the code. Of course there are some details that I didn’t mention in this article. You can find the full source code on my github repository.