word

word.scala

package word
import cats.implicits._

trait Scenario
object Scenario {

  case class Unsolvable(reason: String) extends Scenario

  case class NoA(length: Int) extends Scenario

  case class ContainsA(positions: List[Int]) extends Scenario

  def fromString(s: String): Scenario = {
    val length = s.length
    if (length < 3) {
      Unsolvable("string too short")
    } else {
      val positions = findPositionA(s)
      positions match {
        case Nil => NoA(length)
        case _ if positions.length % 3 != 0 => Unsolvable("odd number a")
        case _ => ContainsA(positions)
      }
    }
  }

  /* change to an arrayBuffer w/ whileLoop for speed and return Array[Int] */
  def findPositionA(s: String): List[Int] = {
    s.toCharArray.zipWithIndex.foldRight(List.empty[Int]) {
      case ((char, pos), acc) =>
        if (char == 'a') pos +: acc else acc
    }
  }
}

object Solvers {

  import Scenario._

  def solve(scenario: Scenario): Either[String, Int] = scenario match {
    case Unsolvable(reason) => reason.asLeft[Int]
    case NoA(length) => solveJustB(length).asRight[String]
    case ContainsA(pos) => solveA(pos.toArray).asRight[String]
  }

  /** there is a closed form solution but this is ok / near constant time
   * you iterate over 2 lists of 3, regardless of the size of i */
  def solveJustB(i: Int): Int = {
    def solveConfig(anchors: List[Int]): Int = {
      anchors.zip(anchors.drop(1)).foldLeft(1) {
        case (acc, (elem, next)) => (next - elem) * acc
      }
    }
    if(i == 3) {
      1
    } else {
      val leftConfig = List(0, 1, i)
      val rightConfig = List(0, i - 1, i)
      solveConfig(leftConfig) + solveConfig(rightConfig) - 2 // because we have two duplicates
    }
  }
  /*
  babaa should return 2: ba | ba | a, and |bab| a| |a|
  ababa should return 4: a | ba | ba, a |bab|a, ab| a| ba, ab |ab| a
   */
  def solveA(positions: Array[Int]): Int = {
    def go(newPos: Option[Array[(Int, Int)]], multiplier: Int, permutations: Int): Int = {
      newPos.fold(permutations)(pos => {
        val count = permutationsFromAnchors(pos, positions)
        go(shrink(positions, multiplier / 3), multiplier / 3, count + permutations)
      }
      )
    }
    go(shrink(positions, positions.length / 3), positions.length / 3, 0)
  }

  /* shrink to 3 anchor points each time, returning new array w/ original positions
  *  this can be optimized to constant time to avoid the whole traversal each time but I'm lazy */
  def shrink(positions: Array[Int], multiplier: Int): Option[Array[(Int, Int)]] = {
    if (multiplier == 0) {
      None
    } else {
      val expanded = positions.zipWithIndex.collect {
        case (e, i) if ((i + 1) % multiplier) == 0 => (e, i)
      }
      if (expanded.length == 3) Some(expanded) else None
    }
  }

  /** pos is always an array of length 3
   * if they are adjacent, the length between them is 1
   * otherwise you can only go as far as the _next_ a, not all the
   * way to the next anchor (which is only a possible max bound) */
  def permutationsFromAnchors(pos: Array[(Int, Int)], allPositions: Array[Int]): Int =
    pos.zip(pos.drop(1)).foldLeft(1) {
      case (acc, (left, right)) =>
        val (elem, elemOrig) = left
        val (next, _) = right
        val count = if (next - elem == 1) 1 else findPosBetweenAnchors(elem, elemOrig, allPositions)
        count * acc
    }

  def findPosBetweenAnchors(elem: Int, elemOrig: Int, original: Array[Int]): Int = {
    val nextPos = original(elemOrig + 1)
    nextPos - elem
  }
}