Skip to content

Instantly share code, notes, and snippets.

@Fokko
Last active December 6, 2017 18:30
Show Gist options
  • Save Fokko/2cb4da1d39f14854bacb427600ab8bcb to your computer and use it in GitHub Desktop.
Save Fokko/2cb4da1d39f14854bacb427600ab8bcb to your computer and use it in GitHub Desktop.
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
*/
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment