djnzx · djnzx · Nov 2, 2024 · Oct 28, 2024 · Oct 28, 2024 · Oct 29, 2024
diff --git a/algo/src/main/scala/djnz/hackerrank/fp/a3structures/P10StockPrediction.scala b/algo/src/main/scala/djnz/hackerrank/fp/a3structures/P10StockPrediction.scala
@@ -0,0 +1,92 @@
+package djnz.hackerrank.fp.a3structures
+
+/** https://www.hackerrank.com/challenges/stocks-prediction/problem */
+object P10StockPrediction {
+
+  def next() = scala.io.StdIn.readLine()
+
+  /** index from 0 */
+  case class Query(index: Int, d: Int, up: Int)
+
+  def solve(stocks: Seq[Int], queries: Seq[Query], n: Int) = {
+
+    // queries per price
+    val qpp: Map[Int, List[Int]] = stocks.zipWithIndex
+      .foldLeft(Map.empty[Int, List[Int]]) {
+        case (map, (price, idx)) =>
+          val x = price -> (idx :: map.getOrElse(price, Nil))
+          map + x
+      }
+
+    case class Item(price: Int, indexes: IndexedSeq[Int])
+
+    // queries per price sorted by price
+    val qppSorted: Seq[Item] = qpp
+      .map { case (price, indexes) => Item(price, indexes.toIndexedSeq) }
+      .toIndexedSeq
+      .sorted(Ordering.by((x: Item) => x.price))
+
+    import scala.collection.mutable
+    def update(map: mutable.TreeMap[Int, Int], idx: Int): Unit = {
+
+      def doUpdate(l: Int, r: Int): Unit =
+        if (l <= r) map += (l -> r)
+        else map -= l
+
+      val (left, right) = map.rangeTo(idx).last
+      doUpdate(left, idx - 1)
+      doUpdate(idx + 1, right)
+    }
+
+    case class Bound(l: Int, r: Int)
+    val minBounds = Array.ofDim[Bound](n)
+    val minBoundMap = mutable.TreeMap[Int, Int](0 -> (n - 1))
+
+    // TODO: make it more functional
+    /** update minBoundMap, minBounds */
+    qppSorted
+      .flatMap { x =>
+        val idxBound = x.indexes.map { i =>
+          val (l, r) = minBoundMap.rangeTo(i).last
+          i -> Bound(l, r)
+        }
+        idxBound.indices.foreach(i => update(minBoundMap, x.indexes(i)))
+        idxBound
+      }
+      .foreach { case (index, bound) => minBounds(index) = bound }
+
+    val maxBounds = Array.ofDim[Int](queries.length)
+    val maxBoundMap = mutable.TreeMap[Int, Int](0 -> (n - 1))
+
+    // TODO: make it more functional
+    /** update minBoundMap, minBounds */
+    var idx = qppSorted.length - 1
+    queries
+      .sortBy(_.up)(Ordering.Int.reverse)
+      .map { q =>
+        while (idx >= 0 && qppSorted(idx).price > q.up) {
+          qppSorted(idx).indexes.foreach(update(maxBoundMap, _))
+          idx -= 1
+        }
+        val (l, r) = maxBoundMap.rangeTo(q.d).last
+        val minBound = minBounds(q.d)
+        q.index -> (math.min(minBound.r, r) - math.max(minBound.l, l) + 1)
+
+      }
+      .foreach { case (index, answer) => maxBounds(index) = answer }
+
+    maxBounds
+  }
+
+  def main(args: Array[String]): Unit = {
+    val n = next().toInt
+    val stocks = next().split(" ").map(_.toInt).take(n)
+    val m = next().toInt
+    val queries = (1 to m).map { i =>
+      next().split(" ").map(_.toInt) match { case Array(d, m) => Query(i - 1, d, stocks(d) + m) }
+    }
+
+    solve(stocks, queries, n)
+      .foreach(println)
+  }
+}
diff --git a/algo/src/main/scala/djnz/hackerrank/fp/a3structures/P10StockPredictionNaive.scala b/algo/src/main/scala/djnz/hackerrank/fp/a3structures/P10StockPredictionNaive.scala
@@ -0,0 +1,57 @@
+package djnz.hackerrank.fp.a3structures
+
+/** https://www.hackerrank.com/challenges/stocks-prediction/problem */
+object P10StockPredictionNaive {
+  // 0 < l < d < r < n
+
+  def next() = scala.io.StdIn.readLine()
+  case class Query(index: Int, d: Int, m: Int, min: Int, max: Int)
+
+  // as - prices per day
+  // d  - index
+  // we need the longest subarray: all i: ad <= ai <= ad + m
+  def query(as: Array[Int], d: Int, m: Int): Int = {
+    val min = as(d)
+    val max = min + m
+    def fits(x: Int) = x >= min && x <= max
+
+    def findL(it: Iterator[Int], acc: Int): Int = it.hasNext match {
+      case false => acc
+      case _     =>
+        val i = it.next()
+        fits(as(i)) match {
+          case true  => findL(it, i)
+          case false => acc
+        }
+    }
+
+    def findR(it: Iterator[Int], acc: Int): Int = it.hasNext match {
+      case false => acc
+      case _     =>
+        val i = it.next()
+        fits(as(i)) match {
+          case true  => findR(it, i)
+          case false => acc
+        }
+    }
+
+    val l = findL((0 to d).reverseIterator, d)
+    val r = findR((d until as.length).iterator, d)
+    r - l + 1
+  }
+
+  def solve(as: Array[Int], qs: Seq[Query]): Seq[Int] =
+    qs.map(q => query(as, q.d, q.m))
+
+  def main(args: Array[String]): Unit = {
+    val n = next().toInt
+    val as = next().split(" ").map(_.toInt).take(n)
+    val nq = next().toInt
+    val qs = (1 to nq)
+      .map(i => next().split(" ").map(_.toInt) match { case Array(d, m) => Query(i, d, m, as(d), as(d) + m) })
+
+    solve(as, qs)
+      .foreach(println)
+  }
+
+}
diff --git a/algo/src/main/scala/djnz/hackerrank/fp/a3structures/P11ConstructionSiteDP.scala b/algo/src/main/scala/djnz/hackerrank/fp/a3structures/P11ConstructionSiteDP.scala
@@ -0,0 +1,77 @@
+package djnz.hackerrank.fp.a3structures
+
+/** https://www.hackerrank.com/challenges/mirko-at-construction-site/problem */
+object P11ConstructionSiteDP {
+
+  def next() = scala.io.StdIn.readLine()
+
+  def main(args: Array[String]): Unit = {
+    val (_, q) = next().split(" ").map(_.toInt) match { case Array(x, y) => x -> y }
+
+    val base = next().split(" ").map(_.toInt)
+    val increments = next().split(" ").map(_.toInt)
+
+    case class Query(idx: Int, time: Int)
+    val queries = (0 until q).map(i => Query(i, next().toInt)).sortBy(_.time)
+
+    case class Building(idx: Int, base: Long, inc: Long) extends Ordered[Building] {
+      override def compare(that: Building): Int =
+        if (this.inc < that.inc) -1
+        else if (this.inc > that.inc) 1
+        else if (this.base < that.base) -1
+        else if (this.base > that.base) 1
+        else this.idx.compareTo(that.idx)
+    }
+
+    val buildings: List[Building] = base.indices
+      .map(i => Building(i + 1, base(i), increments(i)))
+      .groupBy(_.inc)
+      .map { case (_, list) => list.maxBy(_.base) }
+      .toList
+      .sorted
+
+    def cross(b0: Building, b1: Building) = (b1.base.toDouble - b0.base) / (b0.inc.toDouble - b1.inc)
+
+    @scala.annotation.tailrec
+    def sort(buildings: List[Building], acc: List[Building]): List[Building] = (buildings, acc) match {
+      case (Nil, _)            => acc              // done
+      case (v :: Nil, _)       => v :: acc         // last one, done
+      case (h :: t, Nil)       => sort(t, List(h)) // start
+      case (b1 :: b2 :: bs, h :: _) if {
+            val is1 = cross(h, b1)
+            val is2 = cross(h, b2)
+            is1 < is2 || is1 == is2 && b1.idx > b2.idx
+          } => sort(b2 :: bs, b1 :: acc)
+      case (_ :: bs, _ :: Nil) => sort(bs, acc)
+      case (_ :: bs, h :: hs)  => sort(h :: bs, hs)
+    }
+
+    val buildingsReordered = sort(buildings, Nil).reverse
+
+    case class Pair(qIdx: Int, highestIdx: Int)
+    case class State(buildings: List[Building], highest: List[Pair])
+    val s0 = State(buildingsReordered, Nil)
+
+    queries
+      .foldLeft(s0) { (s, q) =>
+
+        @scala.annotation.tailrec
+        def highest(buildings: List[Building]): State = buildings match {
+          case b :: Nil => State(s.buildings, Pair(q.idx, b.idx) :: s.highest)
+          case b1 :: b2 :: _ if {
+                val is = cross(b1, b2)
+                is > q.time || is == q.time && b1.idx > b2.idx
+              } => State(buildings, Pair(q.idx, b1.idx) :: s.highest)
+          case _ :: bs  => highest(bs)
+          case Nil      => sys.error("impossible, but req for exhaustiveness")
+        }
+
+        highest(s.buildings)
+      }
+      .highest
+      .sortBy(_.qIdx)
+      .map(_.highestIdx)
+      .foreach(println)
+  }
+
+}
diff --git a/algo/src/main/scala/djnz/hackerrank/fp/a3structures/P12TreeManager.scala b/algo/src/main/scala/djnz/hackerrank/fp/a3structures/P12TreeManager.scala
@@ -0,0 +1,158 @@
+package djnz.hackerrank.fp.a3structures
+
+/** https://www.hackerrank.com/challenges/tree-manager/problem
+  * Immutable State,
+  * Immutable Tree
+  */
+object P12TreeManager {
+  sealed trait Command
+  sealed trait CmdModify extends Command
+  sealed trait CmdDisplay extends Command
+  object Command {
+    import scala.util.Try
+    final case object CmdPrint extends CmdDisplay             // print
+    final case class CmdChangeValue(x: Int) extends CmdModify // change current value
+    final case object CmdVisitLeft extends CmdModify          // navigate left
+    final case object CmdVisitRight extends CmdModify         // navigate right
+    final case object CmdVisitParent extends CmdModify        // navigate parent
+    final case class CmdVisitChild(n: Int) extends CmdModify  // navigate to child N (from 1)
+    final case class CmdInsertLeft(x: Int) extends CmdModify  // insert left rel to current
+    final case class CmdInsertRight(x: Int) extends CmdModify // insert right rel to current
+    final case class CmdInsertChild(x: Int) extends CmdModify // add a new child (to 0 pos)
+    final case object CmdDelete extends CmdModify
+    // command parser
+    def parse(s: String): Option[Command] = Try(s match {
+      case "print"            => CmdPrint
+      case s"change $x"       => CmdChangeValue(x.toInt)
+      case "visit left"       => CmdVisitLeft
+      case "visit right"      => CmdVisitRight
+      case "visit parent"     => CmdVisitParent
+      case s"visit child $n"  => CmdVisitChild(n.toInt)
+      case s"insert left $x"  => CmdInsertLeft(x.toInt)
+      case s"insert right $x" => CmdInsertRight(x.toInt)
+      case s"insert child $x" => CmdInsertChild(x.toInt)
+      case "delete"           => CmdDelete
+      case _                  => ???
+    }).toOption
+  }
+
+  // tree representation
+  final case class Node(value: Int, children: Vector[Node] = Vector.empty)
+  // path node representation
+  final case class PathNode(link: Node, pos: Int, parent: Option[Node])
+  // recursively update two immutable structures
+  def updated(chain: List[PathNode], newNode: Node): List[PathNode] = chain match {
+    case h :: Nil =>
+      val newPathNode = h.copy(link = newNode)
+      newPathNode :: Nil
+    case h :: t   =>
+      val parent = h.parent.get
+      val newChildren = parent.children.updated(h.pos - 1, newNode)
+      val newParent = h.parent.get.copy(children = newChildren)
+      val newPathNode = h.copy(link = newNode, parent = Some(newParent))
+      newPathNode :: updated(t, newParent)
+    case _        => ???
+  }
+  // path representation: List[PathNode]
+  case class Path(chain: List[PathNode]) {
+    private def curr = chain.head
+    private def currNode = curr.link
+    private def curSiblings = curr.parent.get.children
+    private def insertAt[A](v: Vector[A], pos: Int, x: A): Vector[A] =
+      (v.slice(0, pos), v.slice(pos, v.size)) match {
+        case (l, r) => l ++ Vector(x) ++ r
+      }
+    private def removeAt[A](v: Vector[A], pos: Int): Vector[A] = {
+      val left = v.slice(0, pos)
+      val right = v.slice(pos + 1, v.size)
+      left ++ right
+    }
+
+    def value: Int = currNode.value
+    def moveL = chain match {
+      case h :: t => Path(h.copy(pos = h.pos - 1, link = curSiblings(h.pos - 2)) :: t)
+      case _      => ???
+    }
+    def moveR = chain match {
+      case h :: t => Path(h.copy(pos = h.pos + 1, link = curSiblings(h.pos)) :: t)
+      case _      => ???
+    }
+    def moveUp = Path(chain.tail)
+    def moveDown(n: Int) = Path(PathNode(currNode.children(n - 1), n, Some(currNode)) :: chain)
+    def changeValue(x: Int) = {
+      val newNode = currNode.copy(value = x)
+      Path(updated(chain, newNode))
+    }
+    def insertLeft(x: Int) = {
+      val newParent = curr.parent.get.copy(children = insertAt(curSiblings, curr.pos - 1, Node(x)))
+      Path(chain match {
+        case h :: t => h.copy(parent = Some(newParent), pos = h.pos + 1) :: updated(t, newParent)
+        case _      => ???
+      })
+    }
+    def insertRight(x: Int) = {
+      val newParent = curr.parent.get.copy(children = insertAt(curSiblings, curr.pos, Node(x)))
+      Path(chain match {
+        case h :: t => h.copy(parent = Some(newParent)) :: updated(t, newParent)
+        case _      => ???
+      })
+    }
+    def insertChild(x: Int) = {
+      val newChildren = Node(x) +: currNode.children
+      val newNode = currNode.copy(children = newChildren)
+      Path(updated(chain, newNode))
+    }
+    def delete = {
+      val newParentChildren = removeAt(curSiblings, curr.pos - 1)
+      val newParent = curr.parent.get.copy(children = newParentChildren)
+      Path(chain match {
+        case _ :: t => updated(t, newParent)
+        case _      => ???
+      })
+    }
+  }
+  // run one command on the state
+  import Command._
+  def run(path: Path, cmd: Command): (Path, Option[Int]) = cmd match {
+    case CmdPrint       => (path, Some(path.value))
+    case cmd: CmdModify =>
+      val path2 = cmd match {
+        case CmdChangeValue(x) => path.changeValue(x)
+        case CmdVisitLeft      => path.moveL
+        case CmdVisitRight     => path.moveR
+        case CmdVisitParent    => path.moveUp
+        case CmdVisitChild(n)  => path.moveDown(n)
+        case CmdInsertLeft(x)  => path.insertLeft(x)
+        case CmdInsertRight(x) => path.insertRight(x)
+        case CmdInsertChild(x) => path.insertChild(x)
+        case CmdDelete         => path.delete
+      }
+      path2 -> None
+  }
+  // process all commands
+  def solve(data: Seq[String]) = {
+    // initial state - list from one node points to our list with 1 elem
+    val p0 = Path(List(PathNode(Node(0), 1, None)))
+    val (_, outcome) = data
+      .flatMap(parse)
+      .foldLeft(
+        (p0, List.empty[Int]),
+      ) { case ((p, acc), cmd) =>
+        run(p, cmd) match {
+          case (p2, Some(v)) => (p2, v :: acc)
+          case (p2, None)    => (p2, acc)
+        }
+      }
+    outcome.reverse.mkString("\n")
+  }
+
+  def next() = scala.io.StdIn.readLine()
+
+  def main(args: Array[String]): Unit = {
+    val N = next().toInt
+    val list = (1 to N).map(_ => next())
+    val r = solve(list)
+    println(r)
+  }
+
+}