August 27, 2024
P99 - Crossword puzzle.
Given an empty (or almost empty) framework of a crossword puzzle and a set of words the problem is to place the words into the framework. The particular crossword puzzle is specified in a text file which first lists the words (one word per line) in an arbitrary order. Then, after an empty line, the crossword framework is defined.
In this framework specification, an empty character location is represented by a dot .. In order to make the solution easier, character locations can also contain predefined character values.
The crossword showed below is defined in the file p99a.dat, other examples are p99b.dat and p99d.dat. There is also an example of a puzzle (p99c.dat) which does not have a solution.
Content of p99a.dat:
LINUX
PROLOG
PERL
ONLINE
GNU
XML
NFS
SQL
EMACS
WEB
MAC
...... .
. . . .
. ..... .
. . . ...
. ... .
...
Words are strings of at least two characters. A horizontal or vertical sequence of character places in the crossword puzzle framework is called a site. Our problem is to find a compatible way of placing words onto sites.
kotlin
package org.kotlin99.misc
import com.natpryce.hamkrest.assertion.assertThat
import com.natpryce.hamkrest.equalTo
import org.junit.Assert.assertFalse
import org.junit.Assert.assertTrue
import org.junit.Test
import org.kotlin99.common.transpose
import org.kotlin99.misc.Crossword.Cell
import org.kotlin99.misc.Crossword.Cell.Companion.none
import org.kotlin99.misc.Crossword.Cell.Companion.vacant
import org.kotlin99.misc.Crossword.Site
import java.io.File
class CrosswordFileReader(private val filePath: String) {
fun readWords(): List<String> =
File(filePath).readLines().takeWhile { it != "" }
fun readCrossword(): Crossword =
Crossword.parse(File(filePath).readLines().dropWhile { it != "" }.drop(1))
}
data class Crossword(val sites: List<Site>) {
fun solve(words: List<String>, i: Int = 0): Sequence<Crossword> {
if (isInvalidFor(words)) return emptySequence()
if (siteToFill().isEmpty()) return sequenceOf(this)
if (i == words.size || words.size - i < siteToFill().size) return emptySequence()
return siteToFill().filter { it.fits(words[i]) }.asSequence().flatMap { site ->
copy().let { crossword ->
crossword.sites.find { it == site }!!.fill(words[i])
crossword.solve(words, i + 1)
}
} + solve(words, i + 1)
}
private fun siteToFill() = sites.filter { !it.filled }
private fun isInvalidFor(words: List<String>) =
sites.any { it.filled && !words.contains(it.word) } ||
sites.any { !it.filled && words.none { word -> it.fits(word) } }
private fun copy(): Crossword {
val cells = sites.flatMap { it.cells }.distinct()
val copyByCell = cells.associateWith { it.copy() }
return Crossword(sites.map { site ->
Site(site.cells.map { copyByCell.getValue(it) })
})
}
override fun toString(): String {
val cells = sites.flatMap { it.cells }
val maxX = cells.maxOf { it.x }
val maxY = cells.maxOf { it.y }
return (0..maxY).joinToString("\n") { y ->
(0..maxX).map { x -> cells.find { it.x == x && it.y == y } }
.map { it?.c ?: none.c }
.joinToString("").trimEnd()
}
}
companion object {
fun parse(lines: List<String>): Crossword {
val maxWidth = lines.maxOf { it.length }
val paddedLines = lines.map { it.padEnd(maxWidth + 1, ' ') } + "".padEnd(maxWidth + 1, ' ')
val cells = paddedLines.mapIndexed { row: Int, line: String ->
line.mapIndexed { col: Int, c: Char ->
if (c != ' ') Cell(col, row, c) else none
}
}
val horizontalSites = consumeSites(cells.flatten())
val verticalSites = consumeSites(cells.transpose().flatten())
val sites = (horizontalSites + verticalSites).filter { it.cells.size >= 2 }
return Crossword(sites)
}
private fun consumeSites(cells: List<Cell>): List<Site> {
if (cells.isEmpty()) return emptyList()
if (cells.first() == none) return consumeSites(cells.dropWhile { it == none })
val site = Site(cells.takeWhile { it != none })
return listOf(site) + consumeSites(cells.dropWhile { it != none })
}
}
data class Site(val cells: List<Cell>) {
constructor(vararg cells: Cell): this(cells.toList())
val word: String
get() = cells.map { it.c }.joinToString("")
val filled: Boolean
get() = cells.all { it.c != vacant }
fun add(cell: Cell) = Site(cells + cell)
fun fits(word: String): Boolean {
if (cells.size != word.length) return false
return cells.indices.all { i ->
cells[i].c == vacant || cells[i].c == word[i]
}
}
fun fill(word: String) {
word.forEachIndexed { i, c -> cells[i].c = c }
}
override fun toString(): String {
val x = cells.first().x
val y = cells.first().y
val word = cells.map { it.c }.joinToString("")
return "Site($x,$y,$word)"
}
}
data class Cell(val x: Int, val y: Int, var c: Char) {
override fun toString() = "($x,$y,$c)"
companion object {
val none = Cell(-1, -1, ' ')
const val vacant = '.'
}
}
}
class P99Test {
@Test fun `read crossword file`() {
val reader = CrosswordFileReader("data/p99a.dat")
val words = reader.readWords()
val crossword = reader.readCrossword()
assertThat(words, equalTo(listOf(
"LINUX", "PROLOG", "PERL", "ONLINE", "GNU", "XML", "NFS", "SQL", "EMACS", "WEB", "MAC"
)))
assertThat(crossword.toString(), equalTo("""
|...... .
|. . . .
|. ..... .
|. . . ...
| . ... .
| ...
""".trimMargin()))
}
@Test fun `parse minimal crossword as set of sites`() {
val crossword = parseCrossword("""
|..
|.
""")
assertThat(crossword.sites, equalTo(listOf(
Site(Cell(0, 0, '.'), Cell(1, 0, '.')),
Site(Cell(0, 0, '.'), Cell(0, 1, '.'))
)))
}
@Test fun `changed cell affects all sites`() {
val crossword = parseCrossword("""
|..
|.
""")
crossword.sites.first().let {
it.cells[0].c = 'a'
it.cells[1].c = 'b'
}
assertThat(crossword.sites, equalTo(listOf(
Site(Cell(0, 0, 'a'), Cell(1, 0, 'b')),
Site(Cell(0, 0, 'a'), Cell(0, 1, '.'))
)))
}
@Test fun `changed cell affects all sites in crossword copy`() {
val crossword = parseCrossword("""
|..
|.
""")
crossword.sites.first().let {
it.cells[0].c = 'a'
it.cells[1].c = 'b'
}
assertThat(crossword.sites, equalTo(listOf(
Site(Cell(0, 0, 'a'), Cell(1, 0, 'b')),
Site(Cell(0, 0, 'a'), Cell(0, 1, '.'))
)))
}
@Test fun `site can determine if word fits in and be filled`() {
val site = Site(Cell(0, 0, 'a'), Cell(1, 0, 'b'), Cell(2, 0, '.'))
assertFalse(site.fits("ab"))
assertFalse(site.fits("Abc"))
assertFalse(site.fits("abcd"))
assertTrue(site.fits("abc"))
site.fill("abc")
assertThat(site, equalTo(Site(Cell(0, 0, 'a'), Cell(1, 0, 'b'), Cell(2, 0, 'c'))))
}
@Test fun `solve one-word crossword`() {
val crossword = parseCrossword("ab.")
val solvedCrossword = crossword.solve(listOf("ab", "Abc", "abcd", "abc")).first()
assertThat(solvedCrossword.toString(), equalTo("abc"))
}
@Test fun `solve two-words crossword`() {
val crossword = parseCrossword("""
|ab.
|.
""")
val solvedCrossword = crossword.solve(listOf("ab", "Abc", "abcd", "abc")).first()
assertThat(solvedCrossword.toString(), equalTo("""
|abc
|b
""".trimMargin()))
}
@Test fun `solve crossword where several word fits several sites`() {
val crossword = parseCrossword("""
|...
|.
|...
|h
""")
val solvedCrossword = crossword.solve(listOf("abc", "efg", "adeh")).first()
assertThat(solvedCrossword.toString(), equalTo("""
|abc
|d
|efg
|h
""".trimMargin()))
}
@Test fun `solve crossword from p99a file`() {
val reader = CrosswordFileReader("data/p99a.dat")
val crossword = reader.readCrossword().solve(reader.readWords()).first()
assertThat(crossword.toString(), equalTo("""
|PROLOG E
|E N N M
|R LINUX A
|L I F MAC
| N SQL S
| WEB
""".trimMargin()))
}
@Test fun `solve crossword from p99b file`() {
val reader = CrosswordFileReader("data/p99b.dat")
val crossword = reader.readCrossword().solve(reader.readWords()).first()
assertThat(crossword.toString(), equalTo("""
|P TUEBINGEN TRAUBENZUCKER
|R A E A R I
|O TEMPERAMENT FORTUNA V
|T T F E N I
|EGERIA ZEUS T SAMPAN K E
|K R E T U E R
|T S WALZER LIANE MADONNA
|O A A A TAL N U K
|RELIGION R N R TIARA
|A L G K U I S I S
|T O E STOIKER L S
| GRANAT F L E OSTEN
| E S F L I C
| G TURKMENEN VENDETTA H
| I B N R L T T R
| ISEL T U H STETTIN T O
|S T A E P I T DER N
|E E S R E BRIEFTAUBE A O
|KARRE T L T A I K G
|U A E AAL M T T R
|N ALLENSTEIN N I A I A
|D L T K S L O P
|EOSIN USAMBARA SERBIEN H
| E H R R E I
|HANNIBAL MELASSE NONNE
""".trimMargin()))
}
@Test fun `solve crossword from p99c file`() {
val reader = CrosswordFileReader("data/p99c.dat")
val solution = reader.readCrossword().solve(reader.readWords())
assertThat(solution.toList(), equalTo(emptyList()))
}
@Test fun `solve crossword from p99d file`() {
val reader = CrosswordFileReader("data/p99d.dat")
val crossword = reader.readCrossword().solve(reader.readWords()).first()
assertThat(crossword.toString(), equalTo("""
|BARKASSE REAKTION SIDERIT
|E N I R I E A
|T F A AUSTRALIEN G K U
|ERRATEN T A A BEDANKEN
|I A O G E A N T L D R U
|L G M O TRANIG A E A S
|I M I L P ERLASSEN W
|G E EKARTE A L I O T A U
|E N A E S T M T N
|NATTER NESSEL A M AZETAT
| O T E E E E R E E
|GELEISE A N U TERRIER R
|A S K M E S
|R S ERREGER UEBERALL T
|A A L N G A
|NENNER A HAENDEL VERGEBEN
|T T L A N A D
|I A BULLAUGEN M T S
|E N E S E E U SESAM
| D N OSTEREI R E A
|OBERHAUSEN Z S I N
|R R T L BESTELLEN A
|A VERBERGEN A E N G
|D I N N R E E
|EINLADEN AFRIKANER ANKER
""".trimMargin()))
}
private fun parseCrossword(s: String): Crossword = Crossword.parse(s.trimMargin().split("\n"))
}
Be first to comment