Advent-of-code-day3.scala

package com.godatadriven

object Day3 extends App {

  import scala.annotation.tailrec

  case class Pos(x: Int, y: Int) {
    def +(other: Pos): Pos = Pos(x + other.x, y + other.y)
  }

  val RightDirection = Pos(1, 0)
  val LeftDirection  = Pos(-1, 0)
  val UpDirection    = Pos(0, 1)
  val DownDirection  = Pos(0, -1)

  @tailrec
  def traverseSpiral(
    until: Int,
    cur: Int = 1,
    pos: Pos = Pos(0, 0),
    dir: Pos = Pos(1, 0),
    steps: Int = 2,
    stepsLeft: Int = 1
  ): Pos =
    if (cur == until) {
      // Found it!
      pos
    } else {
      // Continue to traverse, check if we have to change direction
      val updateStep = if (stepsLeft == 1) {
        dir match {
          case RightDirection => (UpDirection, steps, steps - 1)
          case UpDirection => (LeftDirection, steps + 1, steps)
          case DownDirection => (RightDirection, steps + 1, steps)
          case LeftDirection => (DownDirection, steps, steps - 1)
        }
      } else {
        (dir, steps, stepsLeft - 1)
      }
      traverseSpiral(
        until,
        cur + 1,
        pos + dir,
        updateStep._1,
        updateStep._2,
        updateStep._3
      )
    }


  assert(traverseSpiral(1) == Pos(0, 0))
  assert(traverseSpiral(2) == Pos(1, 0))
  assert(traverseSpiral(3) == Pos(1, 1))
  assert(traverseSpiral(4) == Pos(0, 1))
  assert(traverseSpiral(5) == Pos(-1, 1))
  assert(traverseSpiral(6) == Pos(-1, 0))
  assert(traverseSpiral(7) == Pos(-1, -1))
  assert(traverseSpiral(8) == Pos(0, -1))
  assert(traverseSpiral(9) == Pos(1, -1))
  assert(traverseSpiral(10) == Pos(2, -1))
  assert(traverseSpiral(11) == Pos(2, 0))
  assert(traverseSpiral(12) == Pos(2, 1))
  assert(traverseSpiral(13) == Pos(2, 2))
  assert(traverseSpiral(14) == Pos(1, 2))
  assert(traverseSpiral(15) == Pos(0, 2))
  assert(traverseSpiral(16) == Pos(-1, 2))
  assert(traverseSpiral(17) == Pos(-2, 2))
  assert(traverseSpiral(18) == Pos(-2, 1))
  assert(traverseSpiral(19) == Pos(-2, 0))
  assert(traverseSpiral(20) == Pos(-2, -1))
  assert(traverseSpiral(21) == Pos(-2, -2))

  @tailrec
  def traverseSpiralDiag(
    target: Int,
    pos: Pos = Pos(0, 0),
    dir: Pos = Pos(1, 0),
    steps: Int = 2,
    stepsLeft: Int = 1,
    history: Map[Pos, Int] = Map(Pos(0, 0) -> 1)
  ): Int = if (history(pos) > target) {
    // Found it!
    history(pos)
  } else {
    // Continue to traverse, check if we have to change direction
    val updateStep = if (stepsLeft == 1) {
      dir match {
        case RightDirection => (UpDirection, steps, steps - 1)
        case UpDirection => (LeftDirection, steps + 1, steps)
        case DownDirection => (RightDirection, steps + 1, steps)
        case LeftDirection => (DownDirection, steps, steps - 1)
      }
    } else {
      (dir, steps, stepsLeft - 1)
    }

    val newPos = pos + dir
    val neighborTiles = for {
      xOffset <- -1 to 1
      yOffset <- -1 to 1
      neighbor <- history.get(Pos(newPos.x + xOffset, newPos.y + yOffset))
    } yield {
      neighbor
    }

    val newScore = neighborTiles.sum

    traverseSpiralDiag(
      target,
      newPos,
      updateStep._1,
      updateStep._2,
      updateStep._3,
      history + (newPos -> newScore)
    )
  }


  assert(traverseSpiralDiag(1) == 2)
  assert(traverseSpiralDiag(9) == 10)
  assert(traverseSpiralDiag(10) == 11)
  assert(traverseSpiralDiag(722) == 747)
  assert(traverseSpiralDiag(747) == 806)

  traverseSpiralDiag(277678)

  /*
scala> Fokkos-MacBook-Pro:~ fokkodriesprong$ scala
Welcome to Scala 2.11.11 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_92).
Type in expressions for evaluation. Or try :help.

scala>   import scala.annotation.tailrec
import scala.annotation.tailrec

scala>   case class Pos(x: Int, y: Int) {
     |     def +(other: Pos): Pos = Pos(x + other.x, y + other.y)
     |   }
defined class Pos

scala>   val RightDirection = Pos(1, 0)
RightDirection: Pos = Pos(1,0)

scala>   val LeftDirection  = Pos(-1, 0)
LeftDirection: Pos = Pos(-1,0)

scala>   val UpDirection    = Pos(0, 1)
UpDirection: Pos = Pos(0,1)

scala>   val DownDirection  = Pos(0, -1)
DownDirection: Pos = Pos(0,-1)

scala>   @tailrec
     |   def traverseSpiral(
     |     until: Int,
     |     cur: Int = 1,
     |     pos: Pos = Pos(0, 0),
     |     dir: Pos = Pos(1, 0),
     |     steps: Int = 2,
     |     stepsLeft: Int = 1
     |   ): Pos =
     |     if (cur == until) {
     |       // Found it!
     |       pos
     |     } else {
     |       // Continue to traverse, check if we have to change direction
     |       val updateStep = if (stepsLeft == 1) {
     |         dir match {
     |           case RightDirection => (UpDirection, steps, steps - 1)
     |           case UpDirection => (LeftDirection, steps + 1, steps)
     |           case DownDirection => (RightDirection, steps + 1, steps)
     |           case LeftDirection => (DownDirection, steps, steps - 1)
     |         }
     |       } else {
     |         (dir, steps, stepsLeft - 1)
     |       }
     |       traverseSpiral(
     |         until,
     |         cur + 1,
     |         pos + dir,
     |         updateStep._1,
     |         updateStep._2,
     |         updateStep._3
     |       )
     |     }
traverseSpiral: (until: Int, cur: Int, pos: Pos, dir: Pos, steps: Int, stepsLeft: Int)Pos

scala>   assert(traverseSpiral(1) == Pos(0, 0))

scala>   assert(traverseSpiral(2) == Pos(1, 0))

scala>   assert(traverseSpiral(3) == Pos(1, 1))

scala>   assert(traverseSpiral(4) == Pos(0, 1))

scala>   assert(traverseSpiral(5) == Pos(-1, 1))

scala>   assert(traverseSpiral(6) == Pos(-1, 0))

scala>   assert(traverseSpiral(7) == Pos(-1, -1))

scala>   assert(traverseSpiral(8) == Pos(0, -1))

scala>   assert(traverseSpiral(9) == Pos(1, -1))

scala>   assert(traverseSpiral(10) == Pos(2, -1))

scala>   assert(traverseSpiral(11) == Pos(2, 0))

scala>   assert(traverseSpiral(12) == Pos(2, 1))

scala>   assert(traverseSpiral(13) == Pos(2, 2))

scala>   assert(traverseSpiral(14) == Pos(1, 2))

scala>   assert(traverseSpiral(15) == Pos(0, 2))

scala>   assert(traverseSpiral(16) == Pos(-1, 2))

scala>   assert(traverseSpiral(17) == Pos(-2, 2))

scala>   assert(traverseSpiral(18) == Pos(-2, 1))

scala>   assert(traverseSpiral(19) == Pos(-2, 0))

scala>   assert(traverseSpiral(20) == Pos(-2, -1))

scala>   assert(traverseSpiral(21) == Pos(-2, -2))

scala>   @tailrec
     |   def traverseSpiralDiag(
     |     target: Int,
     |     pos: Pos = Pos(0, 0),
     |     dir: Pos = Pos(1, 0),
     |     steps: Int = 2,
     |     stepsLeft: Int = 1,
     |     history: Map[Pos, Int] = Map(Pos(0, 0) -> 1)
     |   ): Int = if (history(pos) > target) {
     |     // Found it!
     |     history(pos)
     |   } else {
     |     // Continue to traverse, check if we have to change direction
     |     val updateStep = if (stepsLeft == 1) {
     |       dir match {
     |         case RightDirection => (UpDirection, steps, steps - 1)
     |         case UpDirection => (LeftDirection, steps + 1, steps)
     |         case DownDirection => (RightDirection, steps + 1, steps)
     |         case LeftDirection => (DownDirection, steps, steps - 1)
     |       }
     |     } else {
     |       (dir, steps, stepsLeft - 1)
     |     }
     |
     |     val newPos = pos + dir
     |     val neighborTiles = for {
     |       xOffset <- -1 to 1
     |       yOffset <- -1 to 1
     |       neighbor <- history.get(Pos(newPos.x + xOffset, newPos.y + yOffset))
     |     } yield {
     |       neighbor
     |     }
     |
     |     val newScore = neighborTiles.sum
     |
     |     traverseSpiralDiag(
     |       target,
     |       newPos,
     |       updateStep._1,
     |       updateStep._2,
     |       updateStep._3,
     |       history + (newPos -> newScore)
     |     )
     |   }
traverseSpiralDiag: (target: Int, pos: Pos, dir: Pos, steps: Int, stepsLeft: Int, history: Map[Pos,Int])Int

scala>   assert(traverseSpiralDiag(1) == 2)

scala>   assert(traverseSpiralDiag(9) == 10)

scala>   assert(traverseSpiralDiag(10) == 11)

scala>   assert(traverseSpiralDiag(722) == 747)

scala>   assert(traverseSpiralDiag(747) == 806)

scala>   traverseSpiralDiag(277678)
res28: Int = 279138

   */
}