Category Archives: All About Software Technology

Scala Binary Search Tree

1 Reply

When I wrote about Scala linked list implementation a couple of years ago, I also did some quick ground work for implementing binary search trees (BST). Occupied by other R&D projects at the time, it was put aside and has since been patiently awaiting its turn to see the light of day. As much of the code is already there, I’m going to put it up in this blog post along with some narrative remarks.

First, we come up with an ADT (algebraic data type). Let’s call it BSTree, starting out with a base trait with generic type A for the data element to be stored inside the tree structure, to be extended by a case class BSBranch as tree branches and a case object BSLeaf as “null” tree nodes. The ADT’s overall structure resembles that of the one used in the linked list implementation described in the old post.

ADT BSTree

A few notes:

  • Data elements (of generic type A) are stored only in branches and data of the same value will go to the same branch and be represented with a proper count value.
  • BSTree is covariant, or else BSLeaf can’t even be defined as a sub-type of BSTree[Nothing].
  • A toString method is created for simplified string output of a tree instance.

Populating a BSTree

One of the first things we need is a method to insert tree nodes into an existing BSTree. We start expanding the base trait with method insert(). That’s all great for adding a node one at a time, but we also need a way to create a BSTree and populate it from a readily available collection of data elements. It makes sense to delegate such a factory method to the companion object BSTree as its method apply().

Note that type parameter B for insert() needs to be a supertype of A because Function1 is contravariant over its parameter type. In addition, the context bound “B : Ordering” constrains type B to be capable of being ordered (i.e. compared) which is necessary for traversing a binary search tree.

Testing BSTree.apply():

Tree traversal and finding tree nodes

Next, we need methods for tree traversal and search. For brevity, we only include in-order traversal.

Using the tree created above:

Removing tree nodes

To be able to remove tree nodes that consist of a specific or range of element values, we include also the following few methods in the base trait.

Note that delete() may involve a little shuffling of the tree nodes. Once the tree node to be removed is located, that node may need to be filled with the node having the next-bigger element & count values from its right node (or equivalently, the node having the next-smaller element from its left node).

Method trim() removes tree nodes with element values below or above the provided range. Meanwhile, method cutOut() does the opposite by cutting out tree nodes with values within the given range. It involves slightly more work than trim(), requiring the use of delete() for individual tree nodes.

Example:

Rebuilding a binary search tree

A highly unbalanced binary search tree beats the purpose of using such a data structure. One of the most straight forward ways to rebuild a binary search tree is to “unpack” the individual tree nodes of the existing tree by traversing in-order into a list (e.g. a Vector or List) of elements, followed by reconstructing a new tree with nodes being assigned elements from recursively half-ing the in-order node list.

Example:

Thoughts on the ADT

An alternative to how the ADT is designed is to have the class fields and methods declared in the BSTree base trait with specific implementations reside within subclasses BSBranch and BSLeaf, thus eliminating the need of the boiler-plate pattern matching for the subclasses. There is also the benefit of making class fields like left & right referenceable from the base trait, though they would need to be wrapped in Options with value None for BSLeaf.

As can be seen with the existing ADT, an advantage is having all the binary tree functions defined within the base trait once and for all. If there is the need for having left and right referenceable from the BSTree base trait, one can define something like below within the trait.

Example:

Then there is also non-idiomatic approach of using mutable class fields in a single tree class commonly seen in Java implementation, like below:

Addendum: Complete source code of the BSTree ADT

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
  }
}

Algorand NFTs With IPFS Assets

1 Reply

As of this writing, the overall cryptocurrency sector is undergoing a major downturn in which about two-third of the average blockchain’s market cap has evaporated since early April. This might not be the best time to try make anyone excited about launching NFTs on any blockchain. Nevertheless, volatility of cryptocurrencies has always been a known phenomenon. From a technological perspective, it’s much less of a concern than how well-designed the underlying blockchain is in terms of security, decentralization and scalability.

Many popular blockchain platforms out there are offering their own open-standard crypto tokens, but so far the most prominent crypto tokens, fungible or non-fungible, are Ethereum-based. For instance, the NFTs we minted on Avalanche‘s Fuji testnet in a previous blog post are Ethereum-based and ERC-721 compliant.

Given Ethereum’s large market share, dApp developers generally prefer having their NFTs transacting on Ethereum main chain or Ethereum-compatible chains like Polygon and Avalanche’s C-Chain, yet many others opt to pick incompatible chains as their NFT development/trading platforms.

Choosing a blockchain for NFT development

Use cases of NFT are mostly about provenance of authenticity. To ensure that the NFT related transactions to be verifiable at any point of time, the perpetual availability of the blockchain in which the transaction history reside is critical. Though not often, hard forks do happen, consequently rendering historical transactions forking off the main chain. That’s highly undesirable. Some blockchains such as Algorand and Polkadot tout that their chains are by-design “forkless”, which does provide an edge over competitors.

Another factor critical for transacting NFTs on a blockchain is low latency in consensually finalizing transactions. That latency is generally referred to as finality. Given that auctions are commonly time-sensitive events for trading of NFTs, a long delay is obviously ill-suited. Chains like Avalanche and Algorand are able to keep the finality under 5 seconds which is much shorter compared to 10+ minutes required on other blockchains like Cardano or Ethereum.

Algorand and IPFS

Launched 3 years ago in June 2019, Algorand is a layer-1 blockchain with a focus on being highly decentralized, scalable and secured with low transaction cost. Its low latency (i.e. finality) along with a design emphasis in running the blockchain with a forkless operational model makes it an appealing chain for transacting and securing NFTs.

In this blog post, we’re going to create a simple dApp in JavaScript to mint a NFT on the Algorand Testnet for a digital asset pinned to IPFS. IPFS, short for InterPlanetary File System, is a decentralized peer-to-peer network aimed to serve as a single resilient global network for storing and sharing files.

Algorand NFT

Algorand comes with its standard asset class, ASA (Algorand Standard Assets), which can be used for representing a variety of customizable digital assets. A typical NFT can be defined configuratively as an ASA by assigning asset parameters with values that conform to Algorand’s NFT specifications.

The two common Algorand specs for NFTs are ARC-3 and ARC-69. A main difference between the two specs is that ARC-69 asset data is kept on-chain whereas ARC-3’s isn’t. We’ll be minting an ARC-3 NFT with the digital asset stored on IPFS.

Contrary to the previous NFT development exercise on Avalanche that leverages a rich-UI stack (i.e. Scaffold-ETH), this is going to be a barebone proof-of-concept with core focus on how to programmatically create a NFT for a digital asset (an digital image) pinned to IPFS. No web frontend UI.

Algorand SDKs

Algorand offers SDKs for a few programming languages including JavaScript, Python, Go and Java. We’ll be using the JavaScript SDK. The official developer website provides tutorials for various dApp use cases and one of them is exactly about launching ARC-3 NFT for assets on IPFS. Unfortunately, even though the tutorial is only about 6 months old it no longer works due to some of its code already being obsolete.

It’s apparently a result of the rapidly evolving SDK code — a frustrating but common problem for developers to have to constantly play catch-up game with backward incompatible APIs evolving at a breakneck pace. For example, retrieval of user-level information is no longer supported by the latest Algorand SDK client (algod client), but no where could I find any tutorials doing it otherwise. Presumably for scalability, it turns out such queries are now delegated to an Algorand indexer which runs as an independent process backed by a PostgreSQL compatible database.

Given the doubt of the demo code on the Algorand website being out of date, I find it more straight forward (though a little tedious) to pick up the how-to’s by directly digging into the SDK source code js-algorand-sdk. For instance, one could quickly skim through the method signature and implementation logic of algod client method pendingTransactionInformation from the corresponding source or indexer method lookupAccountByID from indexer’s source for their exact tech specs.

Create a NPM project with dependencies

Minimal requirements for this Algorand NFT development exercise include the following:

  • Node.js installed with NPM
  • An account at Pinata, an IPFS pinning service
  • An Algorand compatible crypto wallet (Pera is preferred for the availability of a “developer” mode)

First, create a subdirectory as the project root. For example:

Next, create dependency file package.json with content like below:

Install the NPM package:

Create file “.env” for keeping private keys

Besides the SDKs for Pinata and Algorand, dotenv is also included in the package.json dependency file, allowing variables such as NFT recipient’s wallet mnemonic, algod client/indexer URLs (for Algorand Testnet) and Pinata API keys, to be kept in file .env in the filesystem.

Note that Algorand uses a 25-word mnemonic with the 25th word derived from the checksum out of selected words within the 24-word BIP39-compliant mnemonic. Many blockchains simply use 12-word BIP39 mnemonics.

ARC-3 NFT metadata

Next, we create file assetMetadata.js for storing algorand ARC-3 specific metadata:

Main application logic

The main function createNft does a few things:

  • Create an account object from the wallet mnemonic stored in file .env
  • Create an digital asset (an image) pinned to IPFS
  • Create an ARC-3 compliant NFT associated with the pinned asset

Account object creation

Function createAccount is self explanatory. It retrieves the wallet mnemonic from file .env, derives from it the secret key and wallet address (public key) and display a reminder to make sure the account is funded with Algorand Testnet tokens as fees for transactions.

Pinning a digital asset to IPFS

Function createAssetOnIpfs is responsible for creating and pinning a digital asset to IPFS. This is where the asset attributes including source file path, description, MIME type (e.g. image/png, video/mp4) will be provided. In this example a ninja smiley JPEG under the project root is being used as a placeholder. Simply substitute it with your favorite image, video, etc.

The actual pinning work is performed by function assetPinnedToIpfs which returns identifying IPFS URL for the digital asset’s metadata.

Creating an Alogrand ARC-3 NFT

Function createNft is just an interfacing wrapper of the createArc3Asset function that does the actual work of initiating and signing the transactions on the Algorand Testnet for creating the ARC-3 NFT associated with the pinned asset using algod client.

Note that element values total:1 and decimals:0 are for ensuring uniqueness of the NFT. Also worth noting is that Algorand SDK provides a waitForConfirmation() function for awaiting transaction confirmation for a specified number of rounds:

However, for some unknown reason, it doesn’t seem to work with a fixed waitRounds, thus a custom function seen in a demo app on Algorand’s website is being used instead. The custom code simply verifies returned value from algod client method pendingTransactionInformation(txId) in a loop.

Putting everything together

For simplicity, the above code logic is all put in a single JavaScript script algo-nft-ipfs.js under the project root.

Minting the Algorand NFT

To mint the ARC-3 compliant NFT:

Upon successful minting of the NFT, you’ll see messages similar to the following with a reminder for where to look up for details about the NFT and its associated transactions on the Algorand Testnet:

Verifying …

From the algoexplorer.io website, the URL of the IPFS metadata file for the NFT should look like below:

Value should match the hash value of the pinned asset metadata file under your Pinata account and should be viewable at:

There are a few Algorand compatible wallets with Pera being the one created by the Algorand’s development team. For developers, Pera has a convenient option for switching between the Algorand Mainnet and Testnet. To verify the receipt of the NFT, simply switch to Algorand Testnet (under Settings > Developer Settings > Node Settings).

Here’s what the received NFT in a Pera wallet would look like:

Pera - Ninja Smiley ARC3 NFT

From within Pera Explorer:

Pera Explorer - Ninja Smiley ARC3