Tag Archives: algorithm development

A Stateful Calculator In Scala

Leave a reply

In one of the best books about Cats, Scala with Cats by Welsh & Gurnell, there is an interesting example illustrating how to build a stateful integer calculator using Cats State.

Cats State

The Cats State is a Scala object with the defining apply method:

def apply[S, A](f: S => (S, A)): State[S, A]

that takes a state-transforming function f: S => (S, A) where S represents the state type and A the result type. It returns a State[S, A] which is a type alias of StateT[Eval, S, A] (or equivalently IndexedStateT[Eval, S, S, A]).

StateT[F, S, A] takes a S state and produces an updated state and an A result wrapped in the F context. In this case, Eval which is equipped with stack-safety features is the context.

Other methods in the State object include the following:

def empty[S, A](implicit A: Monoid[A]): State[S, A]
def pure[S, A](a: A): State[S, A]
def get[S]: State[S, S]
def set[S](s: S): State[S, Unit]
def inspect[S, T](f: (S) => T): State[S, T]
def modify[S](f: (S) => S): State[S, Unit]

along with class methods such as run, runS and runA provided by the IndexedStateT class.

A stateful post-order calculator

The simplistic calculator processes a sequence of integer arithmetic operations in a “post-order” manner to return the computed result. In each arithmetic operation, it takes a pair of integer operands followed by an arithmetic operator. For example 1 2 + 3 * would be interpreted as (1 + 2) * 3.

Implementation is straight forward. The input string consisting of the integer operands and operators (+|-|*|/) will be parsed with operands being pushed into a stack and, upon coming across an operator, popped from the stack to carry out the corresponding arithmetics.

Implementation using Scala Cats

// A post-order integer calculator implemented using Scala Cats
// (Source: Scala with Cats by Welsh and Gurnell)

import cats.data.State

def operator(op: (Int, Int) => Int): State[List[Int], Int] = {
  State[List[Int], Int] {
    case x :: y :: ls =>
      val res = op(y, x)
      (res :: ls, res)
    case _ =>
      sys.error("Missing operands error!")
  }
}

def operand(value: String): State[List[Int], Int] = {
  value.toIntOption match {
    case Some(v) =>
      State[List[Int], Int] { ls => (v :: ls, v) }
    case None =>
      sys.error(s"Operand $value type error!")
  }
}

def evalOne(sym: String): State[List[Int], Int] = {
  if (sym == "+") operator(_ + _)
  else if (sym == "-") operator(_ - _)
  else if (sym == "*") operator(_ * _)
  else if (sym == "/") operator(_ / _)
  else operand(sym)
}

def evalAll(instructions: String): State[List[Int], Int] = {
  val list = instructions.split("\\s+").toList
  list.foldLeft(State.pure[List[Int], Int](0)){ (acc, sym) =>
    acc.flatMap(_ => evalOne(sym))
  }
}

// Test running ...

evalOne("30").run(Nil).value
// (List(30),30)

evalAll("10 20 + 15 - 5 / 4 *").run(Nil).value
// (List(12),12)

Using State[List[Int], Int], the operands are being kept in a stack (i.e. List[Int]) within the State structure and will be extracted to carry out the integer arithmetic operations. Method operand() takes a String-typed integer and pushes into the stack, and method operator() takes a binary function (Int, Int) => Int to process the two most recently pushed integers from the stack with the corresponding arithmetic operator.

Using the two helper methods, evalOne() transforms a given operand or operator into a State[List[Int], Int]. Finally, evalAll() takes an input String of a sequence of post-order arithmetic operations, parses the content and compute the result using evalOne iteratively in a fold aggregation.

Implementing with a plain Scala class

Now, what if one wants to stick to using Scala’s standard library? Since the approach of using Cats State structure has just proved itself to be an effective one, we could come up with a simple Scala class to mimic what Cats State[S, A] does.

For what we need, we’ll minimally need a class that takes a S => (S, A) state transformation function and an equivalence of Cats State’s flatMap for chaining of operations.

case class State[S, A](r: S => (S, A)) {
  def result(s: S): (S, A) = r(s)
  def map[B](f: A => B): State[S, B] =
    State(r andThen { case (s, a) => (s, f(a)) })
  def flatMap[B](g: A => State[S, B]): State[S, B] =
    State(r andThen { case (s, a) => g(a).r(s) })
}

As shown in the above snippet, method flatMap is created by composing function r with a partial function via andThen. Though not needed for this particular calculator implementation, we also come up with method map, for completeness if nothing else. Method result is simply for extracting the post-transformation (S, A) tuple.

With the Scala State class, we can implement the calculator’s parsing and arithmetic operations just like how it was done using Cats State.

// A stateful post-order calculator implemented using plain Scala class

case class State[S, A](r: S => (S, A)) {
  def result(s: S): (S, A) = r(s)
  def map[B](f: A => B): State[S, B] =
    State(r andThen { case (s, a) => (s, f(a)) })
  def flatMap[B](g: A => State[S, B]): State[S, B] =
    State(r andThen { case (s, a) => g(a).r(s) })
}

def operator(op: (Int, Int) => Int): State[List[Int], Int] = {
  State[List[Int], Int] {
    case x :: y :: ls =>
      val res = op(y, x)
      (res :: ls, res)
    case _ =>
      throw new Exception("Missing operands error!")
  }
}

def operand(value: String): State[List[Int], Int] = {
  value.toIntOption match {
    case Some(v) =>
      State[List[Int], Int] { ls => (v :: ls, v) }
    case None =>
      throw new Exception(s"Operand $value type error!")
  }
}

def evalOne(sym: String): State[List[Int], Int] = {
  if (sym == "+") operator(_ + _)
  else if (sym == "-") operator(_ - _)
  else if (sym == "*") operator(_ * _)
  else if (sym == "/") operator(_ / _)
  else operand(sym)
}

def evalAll(ops: String): State[List[Int], Int] = {
  val list = ops.split("\\s+").toList
  list.foldLeft(State[List[Int], Int](_ => (Nil, 0))){ (acc, op) =>
    acc.flatMap(_ => evalOne(op))
  }
}

// Test running ...

evalOne("30").result(Nil)
// (List(30),30)

evalAll("10 20 + 15 - 5 / 4 *").result(Nil)  // (List(12),12)
// evalAll("1 2 + 3 4 + *").result(Nil)  // ((List(21),21)

A Crossword Puzzle In Scala

Leave a reply

As a programming exercise, creating and solving a crossword puzzle is a fun one, requiring some non-trivial but reasonable effort in crafting out the necessary programming logic.

The high-level requirements are simple — Given a square-shaped crossword board with intersecting word slots, and a set of words that are supposed to fit in the slots, solve the crossword and display the resulting word-populated board.

Data structure for the crossword board

First, it would help make the implementation more readable by coming up with a couple of inter-related classes to represent the crossword board’s layout:

Class Board represents the crossword board which can be constructed with the following parameters:

  • sz: Size of the square-shaped board with dimension sz x sz
  • bgCh: Background character representing a single cell of the board which can be identified with its XY-coordinates (default ‘.’)
  • spCh: Space character representing a single empty cell of a word slot (default ‘*’)
  • slots: A set of word slots, each of which is represented as an instance of class Slot
  • arr: The “hidden” character array of dimension sz x sz that stores the content (bgCh, spCh (in empty slots) and words)

Class Slot represents an individual word slot with these parameters:

  • start: The XY-coordinates of the starting character of the word slot
  • horiz: A boolean indicator whether a word slot is horizontal (true) or vertical (false)
  • len: Length of the word slot
  • jctIdxs: Indexes of all the junction cells that intersect any other word slots
  • word: A word that fits the slot in length and matches characters that intersect other word slots at its junctions (default “”)

Thus, we have the skeletal classes:

case class Slot(start: (Int, Int), horiz: Boolean, len: Int, jctIdxs: Set[Int], word: String = "")

case class Board private(sz: Int, bgCh: Char = '.', spCh: Char = '*', slots: Set[Slot] = Set()) {
  private val arr: Array[Array[Char]] = Array.ofDim(sz, sz)
}

Next, we expand class Board to include a few methods for recursively filling its word slots with matching words along with a couple of side-effecting methods for displaying board content, error reporting, etc.

case class Board private(sz: Int, bgCh: Char = '.', spCh: Char = '*', slots: Set[Slot] = Set()) {
  private val arr: Array[Array[Char]] = Array.ofDim(sz, sz)

  // Print content of a provided array
  def printArr(a: Array[Array[Char]] = arr): Unit

  // Report error messages
  def logError(msg: String, sList: List[Slot], wMap: Map[Int, Array[String]], jMap: Map[(Int, Int), Char]): Unit

  // Fill slots with words of matching lengths & junction characters
  def fillSlotsWithWords(words: Array[String]): Board

  // Update board array from slots
  def updateArrayFromSlots(): Board
}

To separate initialization tasks from the core crossword solving logic, we add an companion object to class Board.

object Board {
  // Initialize a board's array from provided background char, slot space char & slots
  def apply(sz: Int, bgCh: Char = '.', spCh: Char = '*', slots: Set[Slot] = Set()): Board

  // Convert an index of a slot into coordinates
  def idxToCoords(start: (Int, Int), horiz: Boolean, idx: Int): (Int, Int)

  // Initialize a board and create slots from board array with ONLY layout
  def initBoardLayout(layout: Array[Array[Char]], bg: Char = '.', sp: Char = '*'): Board
    def findSlot(i: Int, j: Int): Option[Slot]
    def createSlots(i: Int, j: Int, slots: Set[Slot], mkCh: Char): Set[Slot]
}

Creating a crossword puzzle

There are a couple of ways to construct a properly initialized Board object:

  1. From a set of pre-defined word slots, or,
  2. From a sz x sz array of the board layout with pre-populated cells of background and empty world slot
object Board {
  // Initialize a board's array from provided background char, slot space char & slots
  def apply(sz: Int, bgCh: Char = '.', spCh: Char = '*', slots: Set[Slot] = Set()): Board = {
    val board = new Board(sz, bgCh, spCh, slots)
    val slotCoords = slots.toList.flatMap{ slot =>
      val (i, j) = idxToCoords(slot.start, slot.horiz, slot.len - 1)
      List(i, j)
    }
    require(slots.isEmpty || slots.nonEmpty && slotCoords.max < sz, s"ERROR: $slots cannot be contained in ${board.arr}!")
    for (i <- 0 until sz; j <- 0 until sz) {
      board.arr(i)(j) = bgCh
    }
    slots.foreach{ slot =>
      val (i, j) = (slot.start._1, slot.start._2)
      (0 until slot.len).foreach{ k =>
        val (i, j) = idxToCoords(slot.start, slot.horiz, k)
        board.arr(i)(j) = if (slot.word.isEmpty) spCh else slot.word(k)
      }
    }
    board
  }

  ...
}

Method Board.apply() constructs a Board object by populating the private array field with the provided character bgCh to represent the background cells. Once initialized, empty slots represented by the other provided character spCh can be “carved out” in accordance with a set of pre-defined word Slot objects.

Example:

val emptySlots = Set(
  Slot((6, 8), false, 4, Set(2), ""),
  Slot((3, 1), true, 6, Set(2, 5), ""),
  Slot((3, 6), false, 7, Set(0, 5), ""),
  Slot((1, 9), false, 5, Set(0), ""),
  Slot((1, 3), false, 5, Set(0, 2, 4), ""),
  Slot((8, 1), true, 8, Set(5, 7), ""),
  Slot((1, 2), true, 8, Set(1, 7), ""),
  Slot((5, 0), true, 4, Set(3), "")
)

val board = Board(sz = 10, slots = emptySlots)

board.printArr()
/*
. . . . . . . . . . 
. . * * * * * * * * 
. . . * . . . . . * 
. * * * * * * . . * 
. . . * . . * . . * 
* * * * . . * . . * 
. . . . . . * . * . 
. . . . . . * . * . 
. * * * * * * * * . 
. . . . . . * . * . 
*/

Alternatively, one could construct a Board by providing a pre-populated array of the board layout.

object Board {
  ...

  // Initialize a board and create slots from board array with ONLY layout
  def initBoardLayout(layout: Array[Array[Char]], bg: Char = '.', sp: Char = '*'): Board = {
    val sz = layout.length
    def findSlot(i: Int, j: Int): Option[Slot] = {
      if (j < sz-1 && layout(i)(j+1) == sp) {  // Horizontal
        val ln = Iterator.from(j).takeWhile(k => k < sz && layout(i)(k) == sp).size
        val js = (0 until ln).collect{
          case k if (i>=0+1 && layout(i-1)(j+k)!=bg) || (i<sz-1 && layout(i+1)(j+k)!=bg) => k
        }.toSet
        Option.when(ln > 1)(Slot((i, j), true, ln, js))
      }
      else {  // Vertical
        val ln = Iterator.from(i).takeWhile(k => k < sz && layout(k)(j) == sp).size
        val js = (0 until ln).collect{
          case k if (j>=0+1 && layout(i+k)(j-1)!=bg) || (j<sz-1 && layout(i+k)(j+1)!=bg) => k
        }.toSet
        Option.when(ln > 1)(Slot((i, j), false, ln, js))
      }
    }
    def createSlots(i: Int, j: Int, slots: Set[Slot], mkCh: Char): Set[Slot] = {
      if (i == sz) slots
      else {
        if (j == sz)
          createSlots(i+1, 0, slots, mkCh)
        else {
          findSlot(i, j) match {
            case Some(slot) =>
              val jctCoords = slot.jctIdxs.map{ idx =>
                Board.idxToCoords(slot.start, slot.horiz, idx)
              }
              (0 until slot.len).foreach { k =>
                val (i, j) = Board.idxToCoords(slot.start, slot.horiz, k)
                if (!jctCoords.contains((i, j)))
                  layout(i)(j) = mkCh
              }
              createSlots(i, j+1, slots + slot, mkCh)
            case None =>
              createSlots(i, j+1, slots, mkCh)
          }
        }
      }
    }
    val mkCh = '\u0000'
    val newBoard = Board(sz, bg, sp).copy(slots = createSlots(0, 0, Set(), mkCh))
    (0 until sz).foreach{ i =>
      newBoard.arr(i) = layout(i).map{ ch => if (ch == mkCh) sp else ch }
    }
    newBoard
  }
}

Method Board.initBoardLayout() kicks off createSlots(), which parses every element of the array to identify the “head” of any word slot and figure out its “tail” and indexes of cells that intersect with other slots. The mkCh character is for temporarily masking off any identified slot cell that is not a intersecting junction during the parsing.

Example:

val arr = Array(
  Array('.', '.', '.', '.', '.', '.', '.', '.', '.', '.'),
  Array('.', '.', '*', '*', '*', '*', '*', '*', '*', '*'),
  Array('.', '.', '.', '*', '.', '.', '.', '.', '.', '*'),
  Array('.', '*', '*', '*', '*', '*', '*', '.', '.', '*'),
  Array('.', '.', '.', '*', '.', '.', '*', '.', '.', '*'),
  Array('*', '*', '*', '*', '.', '.', '*', '.', '.', '*'),
  Array('.', '.', '.', '.', '.', '.', '*', '.', '*', '.'),
  Array('.', '.', '.', '.', '.', '.', '*', '.', '*', '.'),
  Array('.', '*', '*', '*', '*', '*', '*', '*', '*', '.'),
  Array('.', '.', '.', '.', '.', '.', '*', '.', '*', '.')
)

val board = Board.initBoardLayout(arr)
/*
Board(10, '.', '*', HashSet(
  Slot((6, 8), false, 4, Set(2), ""),
  Slot((3, 1), true, 6, Set(2, 5), ""),
  Slot((3, 6), false, 7, Set(0, 5), ""),
  Slot((1, 9), false, 5, Set(0), ""),
  Slot((1, 3), false, 5, Set(0, 2, 4), ""),
  Slot((8, 1), true, 8, Set(5, 7), ""),
  Slot((1, 2), true, 8, Set(1, 7), ""),
  Slot((5, 0), true, 4, Set(3), "")
))
*/

board.printArr()
/*
. . . . . . . . . . 
. . * * * * * * * * 
. . . * . . . . . * 
. * * * * * * . . * 
. . . * . . * . . * 
* * * * . . * . . * 
. . . . . . * . * . 
. . . . . . * . * . 
. * * * * * * * * . 
. . . . . . * . * . 
*/

Solving the crossword puzzle

The core crossword solving logic is handled by method fillSlotsWithWords() placed within the body of case class Board.

case class Board private(sz: Int, bgCh: Char = '.', spCh: Char = '*', slots: Set[Slot] = Set()) {
  private val arr: Array[Array[Char]] = Array.ofDim(sz, sz)

  ...

  // Fill slots with words of matching lengths & junction characters
  def fillSlotsWithWords(words: Array[String]): Board = {
    val wordMap: Map[Int, Array[String]] = words.groupMap(_.length)(identity)
    val wLenProd: Int = wordMap.map{ case (_, ws) => ws.size }.product
    val trials: Int = wLenProd * wLenProd
    // Prioritize slots with `len` of the smallest by-len group and maximal number of `jctIdxs`
    val orderedSlots = slots.groupMap(_.len)(identity).toList.
      flatMap{ case (_, ss) => ss.map((ss.size, _)) }.
      sortBy{ case (k, slot) => (k, -slot.jctIdxs.size) }.
      map{ case (_, slot) => slot }
    val jctMap: Map[(Int, Int), Char] = slots.
      map(slot => slot.jctIdxs.map(Board.idxToCoords(slot.start, slot.horiz, _))).
      reduce(_ union _).map(_->' ').toMap
    def loop(slotList: List[Slot],
             slotSet: Set[Slot],
             wMap: Map[Int, Array[String]],
             jMap: Map[(Int, Int), Char],
             runs: Int): Set[Slot] = {
      if (runs == 0) {  // Done trying!
        logError(s"FAILURE: Tried $trials times ...", slotList, wMap, jMap)
        slotSet
      }
      else {
        slotList match {
          case Nil =>
            slotSet  // Success!
          case slot :: others =>
            val wordsWithLen = wMap.get(slot.len)
            wordsWithLen match {
              case None =>
                logError(s"FAILURE: Missing words of length ${slot.len}!", slotList, wMap, jMap)
                slotSet
              case Some(words) =>
                words.find{ word =>
                  slot.jctIdxs.forall{ idx =>
                    val jCoords = Board.idxToCoords(slot.start, slot.horiz, idx)
                    jMap(jCoords) == ' ' || word(idx) == jMap(jCoords)
                  }
                }
                match {
                  case Some(w) =>
                    val kvs = slot.jctIdxs.map { idx =>
                      Board.idxToCoords(slot.start, slot.horiz, idx) -> w(idx)
                    }
                    loop(others, slotSet - slot + slot.copy(word = w), wMap, jMap ++ kvs, runs-1)
                  case None =>
                    val newWMap = wMap + (slot.len -> (words.tail :+ words.head))
                    // Restart the loop with altered wordMap
                    loop(orderedSlots, slots, newWMap, jctMap, runs-1)
                }
            }
        }
      }
    }
    val newBoard = copy(slots = loop(orderedSlots, Set(), wordMap, jctMap, wLenProd * wLenProd))
    (0 until sz).foreach{ i => newBoard.arr(i) = arr(i) }
    newBoard.updateArrayFromSlots()
  }

  ...
}

Method fillSlotsWithWords() takes an array of words as the parameter. Those words are supposed to fit the slots of a given initialized Board. The method creates an optimally ordered List of the slots and a Map of words grouped by the length of the words with each key associated with a list of words of the same length. In addition, it also assembles a Map of slot junctions as a helper dataset for matching intersecting characters by XY-coordinates.

The method then uses a recursive loop() to fill slotList and shuffle the wordMap as needed. Let me elaborate a little bit:

  • Optimally ordered slots – Slots are pre-ordered so that those with the most unique slot-length and the most slot junctions will be processed first. The idea is to fill upfront the most slots with certainty (e.g. those with unique length) and lock down the most slot junction characters as subsequent matching criteria for the intersecting slots.
  • Order shuffling – During the recursive processing, when a slot of a given length can no longer be filled with the remaining list of slots, the list of words of that length will be shuffled and the loop() will be reset to run with the altered wordMap.

Finally, since it’s possible that the given crossword puzzle slot layout and words might not have a solution, a limit in the number of trials of running the recursive loop() is provided as a safety measure to avoid an infinite loop.

Example:

val words = Array("mandarin", "apple", "nance", "papaya", "avocado", "date", "kiwi", "honeydew")

val filledBoard = board.fillSlotsWithWords(words)
/*
Board(10, '.', '*', HashSet(
  Slot((1, 9), false, 5, Set(0), "nance"),
  Slot((3, 6), false, 7, Set(0, 5), "avocado"),
  Slot((5, 0), true, 4, Set(3), "date"),
  Slot((8, 1), true, 8, Set(5, 7), "honeydew"),
  Slot((6, 8), false, 4, Set(2), "kiwi"),
  Slot((3, 1), true, 6, Set(2, 5), "papaya"),
  Slot((1, 3), false, 5, Set(0, 2, 4), "apple"),
  Slot((1, 2), true, 8, Set(1, 7), "mandarin")
))
*/

filledBoard.printArr()
/*
. . . . . . . . . . 
. . m a n d a r i n 
. . . p . . . . . a 
. p a p a y a . . n 
. . . l . . v . . c 
d a t e . . o . . e 
. . . . . . c . k . 
. . . . . . a . i . 
. h o n e y d e w . 
. . . . . . o . i . 
*/

Final thoughts

Appended is the complete source code of the classes for the crossword puzzle.

Obviously there are many different ways to formulate and solve a puzzle game like this. What’s being illustrated here is a brute-force approach, as the order shuffling routine upon hitting a wall within the slot-filling recursive loop has to reset the recursion process. The good news is that, having tested it with a dozen of random examples (admittedly a small sample), the prioritization strategy (by optimally picking slots to be evaluated) does prove to help a great deal in efficiently solving the sample games.

case class Slot(start: (Int, Int), horiz: Boolean, len: Int, jctIdxs: Set[Int], word: String = "")

object Board {
  // Initialize a board's array from provided background char, slot space char & slots
  def apply(sz: Int, bgCh: Char = '.', spCh: Char = '*', slots: Set[Slot] = Set()): Board = {
    val board = new Board(sz, bgCh, spCh, slots)
    val slotCoords = slots.toList.flatMap{ slot =>
      val (i, j) = idxToCoords(slot.start, slot.horiz, slot.len - 1)
      List(i, j)
    }
    require(slots.isEmpty || slots.nonEmpty && slotCoords.max < sz, s"ERROR: $slots cannot be contained in ${board.arr}!")
    for (i <- 0 until sz; j <- 0 until sz) {
      board.arr(i)(j) = bgCh
    }
    slots.foreach{ slot =>
      val (i, j) = (slot.start._1, slot.start._2)
      (0 until slot.len).foreach{ k =>
        val (i, j) = idxToCoords(slot.start, slot.horiz, k)
        board.arr(i)(j) = if (slot.word.isEmpty) spCh else slot.word(k)
      }
    }
    board
  }

  // Convert an index of a slot into coordinates
  def idxToCoords(start: (Int, Int), horiz: Boolean, idx: Int): (Int, Int) = {
    if (horiz) (start._1, start._2 + idx) else (start._1 + idx, start._2)
  }

  // Initialize a board and create slots from board array with ONLY layout
  def initBoardLayout(layout: Array[Array[Char]], bg: Char = '.', sp: Char = '*'): Board = {
    val sz = layout.length
    def findSlot(i: Int, j: Int): Option[Slot] = {
      if (j < sz-1 && layout(i)(j+1) == sp) {  // Horizontal
        val ln = Iterator.from(j).takeWhile(k => k < sz && layout(i)(k) == sp).size
        val js = (0 until ln).collect{
          case k if (i>=0+1 && layout(i-1)(j+k)!=bg) || (i<sz-1 && layout(i+1)(j+k)!=bg) => k
        }.toSet
        Option.when(ln > 1)(Slot((i, j), true, ln, js))
      }
      else {  // Vertical
        val ln = Iterator.from(i).takeWhile(k => k < sz && layout(k)(j) == sp).size
        val js = (0 until ln).collect{
          case k if (j>=0+1 && layout(i+k)(j-1)!=bg) || (j<sz-1 && layout(i+k)(j+1)!=bg) => k
        }.toSet
        Option.when(ln > 1)(Slot((i, j), false, ln, js))
      }
    }
    def createSlots(i: Int, j: Int, slots: Set[Slot], mkCh: Char): Set[Slot] = {
      if (i == sz) slots
      else {
        if (j == sz)
          createSlots(i+1, 0, slots, mkCh)
        else {
          findSlot(i, j) match {
            case Some(slot) =>
              val jctCoords = slot.jctIdxs.map{ idx =>
                Board.idxToCoords(slot.start, slot.horiz, idx)
              }
              (0 until slot.len).foreach { k =>
                val (i, j) = Board.idxToCoords(slot.start, slot.horiz, k)
                if (!jctCoords.contains((i, j)))
                  layout(i)(j) = mkCh
              }
              createSlots(i, j+1, slots + slot, mkCh)
            case None =>
              createSlots(i, j+1, slots, mkCh)
          }
        }
      }
    }
    val mkCh = '\u0000'
    val newBoard = Board(sz, bg, sp).copy(slots = createSlots(0, 0, Set(), mkCh))
    (0 until sz).foreach{ i =>
      newBoard.arr(i) = layout(i).map{ ch => if (ch == mkCh) sp else ch }
    }
    newBoard
  }
}

case class Board private(sz: Int, bgCh: Char = '.', spCh: Char = '*', slots: Set[Slot] = Set()) {
  private val arr: Array[Array[Char]] = Array.ofDim(sz, sz)

  // Print content of a provided array
  def printArr(a: Array[Array[Char]] = arr): Unit =
    for (i <- 0 until sz) {
      for (j <- 0 until sz) {
        print(s"${a(i)(j)} ")
        if (a(i)(j) == '\u0000') print(" ")  // Print a filler space for null char
      }
      println()
    }

  // Report error messages
  def logError(msg: String, sList: List[Slot], wMap: Map[Int, Array[String]], jMap: Map[(Int, Int), Char]): Unit = {
    println(msg)
    println(s"Remaining slots: $sList")
    println(s"Latest wordMap: $wMap")
    println(s"Latest jctMap: $jMap")
  }

  // Fill slots with words of matching lengths & junction characters
  def fillSlotsWithWords(words: Array[String]): Board = {
    val wordMap: Map[Int, Array[String]] = words.groupMap(_.length)(identity)
    val wLenProd: Int = wordMap.map{ case (_, ws) => ws.size }.product
    val trials: Int = wLenProd * wLenProd
    // Prioritize slots with `len` of the smallest by-len group and maximal number of `jctIdxs`
    val orderedSlots = slots.groupMap(_.len)(identity).toList.
      flatMap{ case (_, ss) => ss.map((ss.size, _)) }.
      sortBy{ case (k, slot) => (k, -slot.jctIdxs.size) }.
      map{ case (_, slot) => slot }
    val jctMap: Map[(Int, Int), Char] = slots.
      map(slot => slot.jctIdxs.map(Board.idxToCoords(slot.start, slot.horiz, _))).
      reduce(_ union _).map(_->' ').toMap
    def loop(slotList: List[Slot],
             slotSet: Set[Slot],
             wMap: Map[Int, Array[String]],
             jMap: Map[(Int, Int), Char],
             runs: Int): Set[Slot] = {
      if (runs == 0) {  // Done trying!
        logError(s"FAILURE: Tried $trials times ...", slotList, wMap, jMap)
        slotSet
      }
      else {
        slotList match {
          case Nil =>
            slotSet  // Success!
          case slot :: others =>
            val wordsWithLen = wMap.get(slot.len)
            wordsWithLen match {
              case None =>
                logError(s"FAILURE: Missing words of length ${slot.len}!", slotList, wMap, jMap)
                slotSet
              case Some(words) =>
                words.find{ word =>
                  slot.jctIdxs.forall{ idx =>
                    val jCoords = Board.idxToCoords(slot.start, slot.horiz, idx)
                    jMap(jCoords) == ' ' || word(idx) == jMap(jCoords)
                  }
                }
                match {
                  case Some(w) =>
                    val kvs = slot.jctIdxs.map { idx =>
                      Board.idxToCoords(slot.start, slot.horiz, idx) -> w(idx)
                    }
                    loop(others, slotSet - slot + slot.copy(word = w), wMap, jMap ++ kvs, runs-1)
                  case None =>
                    val newWMap = wMap + (slot.len -> (words.tail :+ words.head))
                    // Restart the loop with altered wordMap
                    loop(orderedSlots, slots, newWMap, jctMap, runs-1)
                }
            }
        }
      }
    }
    val newBoard = copy(slots = loop(orderedSlots, Set(), wordMap, jctMap, wLenProd * wLenProd))
    (0 until sz).foreach{ i => newBoard.arr(i) = arr(i) }
    newBoard.updateArrayFromSlots()
  }

  // Update board array from slots
  def updateArrayFromSlots(): Board = {
    slots.foreach{ slot =>
      (0 until slot.len).foreach{ k =>
        val (i, j) = Board.idxToCoords(slot.start, slot.horiz, k)
        arr(i)(j) = if (slot.word.isEmpty) spCh else slot.word(k)
      }
    }
    this
  }
}

Solving The Sweet Spots Board Game

Leave a reply

Creating the Android board game, Sweet Spots, was a fun programming exercise, although developing an algorithmic program to solve the board game is in fact more fun.

A good portion of developing a board game is about validating the game state based on the game rules, creating game control logics, and visual look-and-feel. Much of the above is just mechanical programming exercise. On the other hand, solving the game is a vastly different exercise, requiring some algorithmic programming effort.

Sweet Spots under the hood

The game solving application was written in Java, with Ant the build tool. There are only two simple Java classes that constitute the hierarchical structure of the board game: Spot and Board. Another Java class, SweetSpots, consists of the core mechanism for game solving. Source code is available at GitHub.

Spot defines the (x,y)-coordinate position of each of the NxN spots (i.e. cells) on the board of size N. It also has an integer value that represents:

  • empty (i.e. undecided spot)
  • filler (i.e. spot not chosen for treasure chest)
  • target (i.e. spot chosen for a treasure chest)

In addition, it consists of an integer zone-id (0, 1, .., N-1) that represents the N individual zones.

Board defines the board size (N). The existing board game was developed with either 1 or 2 targets (i.e. number of treasure chests) per row/column/zone for a given game. For generality, the Board class consists of separate targets-per-row, targets-per-column and targets-per-zone, although they would all be the same (i.e. 1 or 2) when applying to the existing game version. It was initially generalized to allow rectangular board dimension (i.e. MxN instead of NxN), but was later simplified to square board.

Board also consists of a variable, spots, of type Spot[][] that maintains the game state during a game, and a number of methods for game rule validation. Besides the standard constructor that takes board size and target count parameters, it also has a constructor for cloning itself to keep a snapshot of the board state.

Class SweetSpots is the class embedded with game solving logic. It takes a board-zone file along with target counts that defines a game as input and consists of necessary methods to solve the game. The board-zone file is a text file which contains the zone information of a given game in the form of a matrix with coordinates (0,0) representing the top left-most entry. For instance, a 4×4 board-zone file might have the following content:

0 1 1 2
0 0 1 2
2 2 2 2
2 3 3 2

The matrix of integers represent 4 zones, each represented by an integer (0-3):

zone 0: (0,0), (0,1), (1,1)
zone 1: (1,0), (2,0), (2,1)
zone 2: (3,0), (3,1), (0,2), (1,2), (2,2), (3,2), (0,3), (3,3)
zone 3: (1,3), (2,3)

Class SweetSpots consists of a variable boardStack which is a stack of type LinkedList. The stack maintains a dynamic list of Board instance snapshots saved at various stages of the trial-and-error routine. The trial-and-error process is performed using two key methods, boardwalk() and rollback(). Method boardwalk() walks through each of the NxN spots on the board (hence “board walk”) in accordance with the game rules. Upon failing any of the game rule validation, rollback() handles rolling back to the previous game-solving state recorded in boardStack.

Below are pseudo-code logic for methods boardwalk() and rollback().

boardwalk(game, coordX, coordY): return int
    while not every spot on the entire board has been walked
        if current spot is empty
            if every targetCount per row/col/zone < targetCount per row/col/zone
                if no targets adjacent to current spot
                    create a snapshot of the board
                    push the snapshot to boardStack
                    put a target in current spot and fillers in adjacent spots
                else
                    put a filler in current spot
        if any row/col/zone has fewer empty spots to satisfy fulfilling targetCount
            return failure
        else // current cell is not empty
            return success
        go to next spot on the board
rollback(): return Board
    if boardStack is empty
        return null
    else
        pop the last saved board from boardStack
        locate the first empty spot
        if every spot on the board has been walked
            return null
        else
            put a filler in current spot
            return board

Solving a game

Class SolveGame is a simple executable module that uses the SweetSpots class to solve a game with defined zone data.

The main flow logic boils down to the following:

static boolean traceOn;
Board game = new Board(boardSize, targetsPerRow, targetsPerCol, targetsPerZone);
SweetSpots ss = new SweetSpots(traceOn);
...
while (ss.boardwalk(game, 0, 0) != 1) {
    game = ss.rollback();
    if (game == null) {
        break;
    }
}

To solve a game with defined zones, simply navigate to the main subdirectory of the java app and run the following command:

java -cp  com.genuine.game.sweetspots.SolveGame <trace?1:0> <boardZoneFile> <boardSize> <targetsPerRow> <targetsPerCol> <targetsPerZone>

For instance, to solve a game defined in ./gamefiles/game-4-1.txt, simply navigate to the main subdirectory of the java app and run the following command from /path/to/sweetspot/java/:

java -cp build/sweetspots-r1.0.0.jar com.genuine.game.sweetspots.SolveGame 0 ./gamefiles/game-4-1.txt 4 1 1 1

Creating a game

Class CreateGame is an executable module that creates a game by generating random zone data and guaranteeing a solution via repetitive method trials in class SweetSpots.

Creating a game for a given board size (i.e. N) and target count involves:

  • generating N random contiguous zones that patition the board, and,
  • ensuring there is a solution for the generated zones

Getting slightly more granular, it involves the following steps:

  1. Assign individual zones random sizes to fill the entire board: To reduce frequency of having extreme zone size, a simplistic weighted random probability distribution, triangularProbDist(), is used for determining the size for individual zones.
  2. For each zone, assign random contiguous spots of the assigned size on the board: Within class CreateGame is a method, zoneWalk(), which essentially “walks” row-wise or column-wise randomly till the assigned zone size is reached. Failure at any point of time to proceed further to cover the entire board with the zones will promptly force a return to step #1.
  3. Transpose the board to further randomize the zone-walk result.
  4. Repeat the above steps till the zones of assigned sizes successfully fill the entire board.
  5. Ensure that there is a solution for the created zones: This is achieved by essentially employing the same game solving logic used in SolveGame.

To create a game that consists of a solution, navigate to the main subdirectory of the java app and execute the following command:

java -cp  com.genuine.game.sweetspots.CreateGame <trace?1:0> <boardZoneFile> <boardSize> <targetsPerRow> <targetsPerCol> <targetsPerZone>

To create a game with 4×4 board size, go to /path/to/sweetspot/java/ and run the following command to generate the game zones in ./gamefiles/:

java -cp build/sweetspots-r1.0.0.jar com.genuine.game.sweetspots.CreateGame 0 ./gamefiles/game-4-1.txt 4 1 1 1

The generated game-zone file should look something like the following:

0 1 1 2
0 0 1 2
2 2 2 2
2 3 3 2

The above Java applications were developed back in Summer of 2013. Though some refactoring effort has been made, there is certainly room for improvement in different areas. In particular, the zone creation piece can be designed to be more robust, ideally enforcing a unique solution for the game. That would be something for a different time perhaps in the near future. Meanwhile, enjoy the board game, which can be downloaded from Google Play.