Balanced Paren Clusters

balanced_paren_cluster.worksheet.sc

import $scalac.`-Ypartial-unification`
import $dep.`org.typelevel::cats-core:2.3.0`

import scala.collection.immutable._

import cats.Foldable
import cats.implicits._

/**
  * Balanced Paren Clusters
  * 
  * Given a string of balanced parentheses, split it up into top-level “clusters”.
  * 
  * Examples
  * 
  * (clusters "") ;=> []
  * (clusters "()") ;=> ["()"]
  * (clusters "(())") ;=> ["(())"]
  * (clusters "()()()") ;=> ["()" "()" "()"]
  * (clusters "(()())()(())") ;=> ["(()())" "()" "(())"]
  * 
  * You can assume the strings will only contain \( and \) and will be fully balanced.
  * 
  * Bonuses
  * 1. Handle unbalanced parens with a nice error message showing the relevant positions.
  * 2. Handle other braces, such as {} and [].
  * 
  * -------------------------------------------------------------------------------------
  * 
  * Source: https://purelyfunctional.tv/issues/purelyfunctional-tv-newsletter-431-clojure-directness/
  */
object Clusters {

  final case class Context(
    helpStack: List[Char],
    output: List[String]
  )

  object Context {

    def empty = {
      Context(List.empty, List.empty)
    }
  }

  type Result[C] = Either[String, C]

  def errorMessage(char: Char, index: Int): String =
    s"String is not balanced. Found faulty '$char' @ $index"

  def folder(context: Context, pair: (Char, Int)): Result[Context] = {

    val Context(helpStack, output) = context
    val (char, index)            = pair

    def newOutput = output match {
      case Nil => s"$char" :: Nil
      case head :: tl => s"$head$char" :: tl
    }

    helpStack match {
      case Nil if char === ')' => errorMessage(char, index).asLeft[Context]

      case Nil =>
        val newTest = output match {
          case Nil => s"$char" :: Nil
          case ls  => s"$char" :: ls
        }
        Context(List(char), newTest).asRight

      case head :: tail if char === ')' => Context(tail, newOutput).asRight

      case stack => Context(char :: stack, newOutput).asRight
    }
  }

  def apply(chars: List[Char]): Either[String, Context] = {
    chars match {
      case _ :: Nil => "Invalid input. Input must have size >= 2.".asLeft
      case _        => Foldable[List].foldM[Result, (Char, Int), Context](chars.zipWithIndex.toList, Context.empty)(folder)
    }
  }

}

def proveSuccess(input: List[Char], expectedClusters: Int) =
  assert({
    val result = Clusters(input)

    result.isRight && {
      val context = result.right.get

      context.helpStack.isEmpty &&
      context.output.size === expectedClusters
    }
  })

def proveFailure(input: List[Char], faultyChar: Char, faultyCharIndex: Int) =
  assert({
    val result = Clusters(input)

    result.isLeft && {
      val err = result.left.get
      err === s"String is not balanced. Found faulty '$faultyChar' @ $faultyCharIndex"
    }
  })

proveSuccess(List.empty[Char], 0)
proveSuccess(List('(', ')'), 1)
proveSuccess(List('(', ')', '(', ')', '(', ')'), 3)

proveSuccess(List('(', '(', ')', '(', ')', ')', '(', ')', '(', '(', ')', ')'), 3)
proveSuccess(List('(', '(', ')', ')'), 1)

proveFailure(List('(', ')', ')'), ')', 2)

assert({
  val result = Clusters(List('('))
  result.isLeft && {
    val err = result.left.get
    err === "Invalid input. Input must have size >= 2."
  }
})
assert({
  val result = Clusters(List(')'))
  result.isLeft && {
    val err = result.left.get
    err === "Invalid input. Input must have size >= 2."
  }
})