Data Structures & Algorithms

@main def run(): Unit =
  val data = Vector.range(0, 1_000_000)
  val target = 999_999

  var linearSteps = 0
  val it = data.iterator
  var found = false
  while !found && it.hasNext do
    linearSteps += 1
    if it.next() == target then found = true

  var binarySteps = 0
  var lo = 0
  var hi = data.length - 1
  var done = false
  while !done && lo <= hi do
    binarySteps += 1
    val mid = lo + (hi - lo) / 2
    if data(mid) == target then done = true
    else if data(mid) < target then lo = mid + 1
    else hi = mid - 1

  println(s"Linear search: $linearSteps steps")
  println(s"Binary search: $binarySteps steps")

import scala.collection.mutable

@main def run(): Unit =
  val xs = List(2, 3)
  val ys = 1 :: xs            // new head cell, xs shared
  println(ys)
  println(ys.tail eq xs)      // the very same object

  val v = Vector(1, 2, 3)
  val v2 = v :+ 4             // cheap append
  println(v2(3))
  println(v.updated(0, 99))   // new Vector, v unchanged
  println(v)

  val buf = mutable.ArrayBuffer.empty[Int]
  for i <- 1 to 5 do buf += i * i
  buf.remove(0)
  println(buf)

@main def run(): Unit =
  val text = "the cat and the hat and the bat"
  val counts = text.split(" ").foldLeft(Map.empty[String, Int]) { (m, w) =>
    m.updated(w, m.getOrElse(w, 0) + 1)
  }
  counts.toList.sortBy((w, n) => (-n, w)).foreach((w, n) => println(s"$w: $n"))

  println(counts.get("cat"))
  println(counts.get("dog"))
  println(text.split(" ").groupMapReduce(identity)(_ => 1)(_ + _) == counts)

  val backend = Set("scala", "sql", "docker", "aws")
  val data = Set("python", "sql", "spark", "aws")
  println((backend intersect data).toList.sorted)
  println((backend diff data).toList.sorted)
  println((backend union data).size)

final case class TwoListQueue[A](front: List[A], back: List[A]):
  def enqueue(a: A): TwoListQueue[A] = copy(back = a :: back)

  def dequeue: Option[(A, TwoListQueue[A])] = front match
    case head :: rest => Some((head, copy(front = rest)))
    case Nil if back.nonEmpty => TwoListQueue(back.reverse, Nil).dequeue
    case Nil => None

object TwoListQueue:
  def empty[A]: TwoListQueue[A] = TwoListQueue(Nil, Nil)

def balanced(s: String): Boolean =
  val pairs = Map(')' -> '(', ']' -> '[', '}' -> '{')
  val stack = s.foldLeft(Option(List.empty[Char])) {
    case (None, _) => None
    case (Some(st), c) if pairs.values.exists(_ == c) => Some(c :: st)
    case (Some(top :: rest), c) if pairs.get(c).contains(top) => Some(rest)
    case (Some(_), c) if pairs.contains(c) => None
    case (acc, _) => acc
  }
  stack.contains(Nil)

@main def run(): Unit =
  val q = TwoListQueue.empty[String].enqueue("a").enqueue("b").enqueue("c")
  val Some((first, q2)) = q.dequeue: @unchecked
  val Some((second, _)) = q2.enqueue("d").dequeue: @unchecked
  println(s"$first $second")

  for s <- List("{[()]}", "([)]", "((", "f(x[0])") do
    println(f"$s%-8s ${if balanced(s) then "yes" else "no"}")

import scala.annotation.tailrec

enum MyList[+A]:
  case Empty
  case Cell(head: A, tail: MyList[A])

  def prepend[B >: A](b: B): MyList[B] = Cell(b, this)

  def reverse: MyList[A] =
    @tailrec def loop(rest: MyList[A], acc: MyList[A]): MyList[A] = rest match
      case Empty => acc
      case Cell(h, t) => loop(t, Cell(h, acc))
    loop(this, Empty)

  def map[B](f: A => B): MyList[B] = this match
    case Empty => Empty
    case Cell(h, t) => Cell(f(h), t.map(f))

  def mkString: String =
    @tailrec def loop(rest: MyList[A], acc: Vector[String]): String = rest match
      case Empty => acc.mkString(" -> ")
      case Cell(h, t) => loop(t, acc :+ h.toString)
    loop(this, Vector.empty)

@main def run(): Unit =
  val xs = MyList.Empty.prepend(3).prepend(2).prepend(1)
  println(xs.mkString)
  println(xs.reverse.mkString)
  println(xs.map(_ * 10).mkString)

import scala.annotation.tailrec
import scala.collection.mutable

@tailrec
def sumDigits(n: Long, acc: Long = 0): Long =
  if n == 0 then acc else sumDigits(n / 10, acc + n % 10)

val memo = mutable.Map.empty[Int, BigInt]
def fib(n: Int): BigInt =
  if n <= 1 then BigInt(n)
  else memo.get(n) match
    case Some(v) => v
    case None =>
      val v = fib(n - 1) + fib(n - 2)
      memo(n) = v
      v

def flatten(xs: List[Any]): List[Any] = xs.flatMap {
  case inner: List[?] => flatten(inner)
  case x => List(x)
}

@main def run(): Unit =
  println(sumDigits(98765))
  println(fib(10))
  println(fib(100))
  println(flatten(List(1, List(2, List(3, List(4)), 5), Nil, 6)))

enum Tree:
  case Leaf
  case Node(left: Tree, value: Int, right: Tree)

  def insert(v: Int): Tree = this match
    case Leaf => Node(Leaf, v, Leaf)
    case n @ Node(l, x, r) =>
      if v < x then Node(l.insert(v), x, r)
      else if v > x then Node(l, x, r.insert(v))
      else n

  def contains(v: Int): Boolean = this match
    case Leaf => false
    case Node(l, x, r) => if v == x then true else if v < x then l.contains(v) else r.contains(v)

  def inOrder: List[Int] = this match
    case Leaf => Nil
    case Node(l, x, r) => l.inOrder ++ (x :: r.inOrder)

  def height: Int = this match
    case Leaf => 0
    case Node(l, _, r) => 1 + math.max(l.height, r.height)

@main def run(): Unit =
  val tree = List(50, 30, 70, 20, 40, 60, 80).foldLeft(Tree.Leaf)(_.insert(_))
  println(tree.inOrder.mkString(" "))
  println(s"${tree.contains(60)} ${tree.contains(65)}")
  println(s"height: ${tree.height}")

  val chain = (1 to 7).foldLeft(Tree.Leaf)(_.insert(_))
  println(s"height after sorted inserts: ${chain.height}")

  val ts = collection.immutable.TreeSet(1 to 7*)
  println(s"TreeSet stays balanced: ${ts.rangeFrom(5).toList}")

import scala.collection.mutable

case class Task(name: String, priority: Int)

def topK(xs: Iterable[Int], k: Int): List[Int] =
  val heap = mutable.PriorityQueue.empty[Int](using Ordering[Int].reverse) // min-heap
  for x <- xs do
    if heap.size < k then heap.enqueue(x)
    else if x > heap.head then
      heap.dequeue()
      heap.enqueue(x)
  heap.dequeueAll.reverse.toList

@main def run(): Unit =
  val minHeap = mutable.PriorityQueue(42, 7, 19, 3, 25)(using Ordering[Int].reverse)
  println(s"smallest: ${minHeap.head}")
  println(minHeap.dequeueAll.mkString(" "))

  val tasks = mutable.PriorityQueue.empty[Task](using Ordering.by(_.priority))
  tasks ++= List(Task("write tests", 2), Task("fix production bug", 10), Task("update README", 1), Task("review pull request", 5))
  while tasks.nonEmpty do println(tasks.dequeue().name)

  println(topK(List(5, 91, 17, 64, 3, 88, 42, 70), 3))

import scala.annotation.tailrec
import scala.collection.immutable.Queue

val graph: Map[String, List[String]] = Map(
  "home"    -> List("blog", "tools"),
  "blog"    -> List("post-a", "post-b"),
  "tools"   -> List("ats"),
  "post-a"  -> List("ats"),
  "post-b"  -> Nil,
  "ats"     -> List("pricing"),
  "pricing" -> Nil,
)

def shortestPath(from: String, to: String): Option[List[String]] =
  @tailrec
  def loop(queue: Queue[String], cameFrom: Map[String, String]): Option[List[String]] =
    queue.dequeueOption match
      case None => None
      case Some((node, _)) if node == to =>
        Some(List.unfold(Option(to))(_.map(n => (n, cameFrom.get(n)))).reverse)
      case Some((node, rest)) =>
        val fresh = graph(node).filterNot(n => n == from || cameFrom.contains(n))
        loop(rest.enqueueAll(fresh), cameFrom ++ fresh.map(_ -> node))
  loop(Queue(from), Map.empty)

def dfs(node: String, seen: Vector[String] = Vector.empty): Vector[String] =
  graph(node).foldLeft(seen :+ node) { (acc, next) =>
    if acc.contains(next) then acc else dfs(next, acc)
  }

@main def run(): Unit =
  println(shortestPath("home", "pricing").map(_.mkString(" -> ")))
  println(dfs("home").mkString(", "))
  println(shortestPath("pricing", "home"))

import scala.collection.Searching.{Found, InsertionPoint}

def mergeSort(xs: List[Int]): List[Int] =
  def merge(a: List[Int], b: List[Int], acc: List[Int]): List[Int] = (a, b) match
    case (Nil, _) => acc.reverse ++ b
    case (_, Nil) => acc.reverse ++ a
    case (x :: xt, y :: yt) =>
      if x <= y then merge(xt, b, x :: acc) else merge(a, yt, y :: acc)
  if xs.lengthCompare(1) <= 0 then xs
  else
    val (left, right) = xs.splitAt(xs.length / 2)
    merge(mergeSort(left), mergeSort(right), Nil)

@main def run(): Unit =
  val prices = Vector(5, 9, 9, 14, 20, 31)
  for t <- List(9, 10, 1, 40) do
    prices.search(t) match
      case Found(i) => println(s"$t found at $i")
      case InsertionPoint(i) => println(s"$t not found, would go at $i")

  println(mergeSort(List(38, 27, 43, 3, 9, 82, 10)))

case class Person(name: String, dept: String, salary: Int)

@main def run(): Unit =
  val people = List(
    Person("Ravi", "data", 90), Person("Ana", "web", 75),
    Person("Chen", "data", 120), Person("Bola", "web", 75),
  )

  // dept ascending, then salary descending
  val sorted = people.sortBy(p => (p.dept, -p.salary))
  sorted.foreach(p => println(f"${p.name}%-5s ${p.dept}%-4s ${p.salary}"))

  val bySalary = Ordering.by[Person, Int](_.salary).reverse.orElseBy(_.name)
  println(people.sorted(using bySalary).map(_.name))

// dp(a) = fewest coins that make amount a
def minCoins(coins: List[Int], amount: Int): Int =
  val inf = Int.MaxValue
  val dp = Array.fill(amount + 1)(inf)
  dp(0) = 0
  for a <- 1 to amount; c <- coins if c <= a && dp(a - c) != inf do
    dp(a) = math.min(dp(a), dp(a - c) + 1)
  if dp(amount) == inf then -1 else dp(amount)

// longest common subsequence, one row at a time
def lcs(a: String, b: String): Int =
  val last = a.foldLeft(Vector.fill(b.length + 1)(0)) { (prev, ca) =>
    b.indices.foldLeft(Vector(0)) { (row, j) =>
      row :+ (if ca == b(j) then prev(j) + 1 else math.max(prev(j + 1), row(j)))
    }
  }
  last.last

@main def run(): Unit =
  println(minCoins(List(1, 5, 10, 25), 63))
  println(minCoins(List(1, 3, 4), 6))
  println(minCoins(List(5, 10), 3))
  println(lcs("ABCBDAB", "BDCABA"))
  println(lcs("kitten", "sitting"))