Fraudio

FraudioSpec.scala

import org.scalatest.{FlatSpec, Matchers}

import scala.annotation.tailrec

class FraudioSpec extends FlatSpec with Matchers {

  def maxTickets(tickets: Array[Int]): Int = {
    @tailrec def select(current: Int, max: Int, tickets: Array[Int]): Int = tickets match {
      case Array() => max
      case Array(head, tail@_*) =>
        tail.headOption match {
          case Some(i) if i == head || i == head + 1 =>
            val c = current + 1
            select(c, Math.max(c, max), tail.toArray)
          case Some(i) if i > head =>
            select(current = 1, max, tail.toArray)
          case None =>
            max
        }
    }

    select(current = 1, max = 0, tickets.sorted)
  }

  it should "find max tickets" in {
    maxTickets(Array(4, 4, 13, 2, 3)) shouldBe 4
  }

  def traverse(x1: Int, y1: Int, x2: Int, y2: Int): Boolean = x1 + y1 match {
    case _ if x1 == x2 && y1 == y2 => true
    case next if next <= x2 =>
      // (x,y) -> (x+y,y)
      traverse(next, y1, x2, y2)
    case next if next <= y2 =>
      // (x,y) -> (x,x+y)
      traverse(x1, next, x2, y2)
    case _ => false
  }

  def canReach(x1: Int, y1: Int, x2: Int, y2: Int): String = {
    if (traverse(x1, y1, x2, y2)) "Yes" else "No"
  }

  it should "check if is reachable" in {
    canReach(1, 4, 5, 9) shouldBe "Yes"
    canReach(1, 4, 5, 10) shouldBe "No"
  }

  def traverse(graph: Map[String, Set[String]]): Seq[Set[String]] = {

    @tailrec def combine(keys: Set[String],
                combined: Map[String, Set[String]] = Map.empty): Seq[Set[String]] = {
      keys.headOption match {
        case None =>
          combined.values.toSeq
        case Some(head) =>
          val children = accumulate(head)
          val connected = head -> children
          combine(keys - head, combined -- children + connected)
      }
    }

    def accumulate(key: String,
                   accumulated: Set[String] = Set.empty,
                   visited: Set[String] = Set.empty): Set[String] = {
      val children = graph.getOrElse(key, Set.empty) -- visited
      if (children.isEmpty) Set(key)
      else children.flatMap(n => accumulate(n, accumulated, visited + n)) + key
    }

    combine(graph.keySet)
  }

  def connectedSum(n: Int, edges: Array[String]): Int = {
    val nodes: Map[String, Set[String]] = edges.foldLeft(Map.empty[String, Set[String]]) { case (graph, string) =>
      string.split(' ') match {
        case Array(a) =>
          graph + (a -> graph.getOrElse(a, Set.empty))
        case Array(a, b) =>
          val values = graph.getOrElse(a, Set.empty) + b
          graph + (a -> values)
        case _ => graph
      }
    }

    traverse(nodes).foldLeft(0) { case (sum, set) =>
      sum + Math.ceil(Math.sqrt(set.size)).toInt
    }
  }

  it should "calculate the weighted sum" in {
    connectedSum(4, Array("4", "3", "2", "1 2", "1 4")) shouldBe 3
    connectedSum(4, Array("4", "3", "2", "1 2", "1 4", "2 3")) shouldBe 2
  }
}

sbt.sh

sbt:challenges4s> testOnly FraudioSpec
[info] Compiling 1 Scala source to /Users/hilios/Workspace/challenges4s/target/scala-2.12/classes ...
[info] Done compiling.
[info] Compiling 12 Scala sources to /Users/hilios/Workspace/challenges4s/target/scala-2.12/test-classes ...
[info] Done compiling.
[info] FraudioSpec:
[info] - should find max tickets
[info] - should check if is reachable
[info] - should calculate the weighted sum
[info] Run completed in 2 seconds, 88 milliseconds.
[info] Total number of tests run: 3
[info] Suites: completed 1, aborted 0
[info] Tests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0
[info] All tests passed.
[success] Total time: 10 s, completed 6 Dec 2019, 13:58:48