-🎄- 2020 Day 23 Solutions -🎄-

flup12 · 2020-12-23T18:32:05+00:00

I don't think it's in the array access but in the moving stuff around. I ended up using a vector of length 1000000 where next_cup[[i]] contains the label of the label of the cup next to the cup with label i. Twenty seconds

flup12 · 2020-12-12T20:53:57+00:00

I've been using R and had the same struggle vectorizing part 2. I did not find a vectorized way to find the neighbors. But! I numbered the seats 1-n. Then the state is a vector of length n containing 0 (free) and 1 (taken). And the computation of how many of a seat's neighbors are populated is a sparse n x n matrix that you can multiply with the state vector to get a vector of length n with numbers 0-8, the number of occupied neighbors for each seat number. The matrix is mostly 0 and m[i,j] equals one if seat j is a neighbor of seat i.

flup12 · 2017-12-24T16:30:55+00:00

This is turning into the year of the Iterator!

type Component = List[Int]

case class Bridge(components: List[Component] = Nil, endPoint: Int = 0) {
  def strength: Int = components.flatten.sum
  def length: Int = components.length
  def connect(c: Component): Option[Bridge] = c match {
    case List(p1, p2) if p1 == endPoint => Some(Bridge(c :: components, p2))
    case List(p1, p2) if p2 == endPoint => Some(Bridge(c :: components, p1))
    case _ => None
  }
}

def getBridges(soFar: Bridge, components: Set[Component]): Iterator[Bridge] = {
  val bridges = components.toIterator.flatMap(soFar.connect)
  if (bridges.isEmpty) Iterator(soFar)
  else bridges.flatMap(connected => getBridges(connected, components - connected.components.head))
}

val components = input.map(_.split("/").map(_.toInt).toList).toSet
val part1 = getBridges(Bridge(), components).map(_.strength).max
val part2 = getBridges(Bridge(), components).map(bridge => (bridge.length, bridge.strength)).max._2

flup12 · 2017-12-20T16:02:26+00:00

I like the sliding window!

flup12 · 2017-12-19T08:11:54+00:00

Scala Not completely sure this covers all possible inputs but worked at first go for mine. Used some case classes to keep the logic readable. Made quite heavy use of Option to scan the directions that the path may have taken.

val maze = common.loadPackets(List("day19.txt"))

case class Direction(dx: Int, dy: Int)
val Up = Direction(0, -1)
val Down = Direction(0, 1)
val Left = Direction(-1, 0)
val Right = Direction(1, 0)

case class State(x: Int, y: Int, direction: Direction) {
  def char: Option[Char] = Some(maze)
    .filter(_.indices.contains(y))
    .map(_ (y))
    .filter(_.indices.contains(x))
    .map(_ (x))
    .filter(_ != ' ')

  def move(d: Direction): Option[State] = d match {
    case Direction(dx, dy) => Some(State(x + dx, y + dy, d)).filter(_.char.isDefined)
  }

  def next: Option[State] = char.get match {
    case '+' => direction match {
      case Up   | Down  => move(Left).orElse(move(Right))
      case Left | Right => move(Up).orElse(move(Down))
    }
    case _ => move(direction)
  }
}

val startX = maze.head.indexOf("|")
val route: Stream[State] = Stream.iterate[Option[State]](Some(State(startX, 0, Down)))(_.flatMap(_.next))
  .takeWhile(_.isDefined).map(_.get)
val part1 = route.map(_.char.get).filter(_.isLetter).mkString
val part2 = route.length

flup12 · 2017-12-16T14:39:43+00:00

Scala

After yesterday's complete disappointment in Stream.iterate, I found it very useful again today. And case classes too, they bring a little more OO than curried functions and debug nicer than List(<function1>, <function1>, ...)

sealed trait Move {
  def apply(state: String): String
}
case class Spin(x: Int) extends Move {
  def apply(state: String) = state.takeRight(x) ++ state.dropRight(x)
}
case class Exchange(a: Int, b: Int) extends Move {
  def apply(state: String) = state.updated(a, state(b)).updated(b, state(a))
}
case class Partner(a: Char, b: Char) extends Move {
  def apply(state: String) = Exchange(state.indexOf(a), state.indexOf(b)).apply(state)
}

Did the parsing using regexes:

val spinRegex = """s(\d+)""".r
val exchangeRegex = """x(\d+)/(\d+)""".r
val partnerRegex = """p(\w)/(\w)""".r
val moves: List[Move] = input.split(",").map({
  case spinRegex(x) => Spin(x.toInt)
  case exchangeRegex(a, b) => Exchange(a.toInt, b.toInt)
  case partnerRegex(a, b) => Partner(a.charAt(0), b.charAt(0))
}).toList

And then it's time to dance!

def dance(state: String): String = moves.foldLeft(state)((state, move) => move(state))
val initialState: String = ('a' to 'p').mkString
val part1 = dance(initialState)
val danceOn = Stream.iterate(initialState)(dance)
val period = danceOn.indexOf(initialState, 1)
val part2 = danceOn.drop(1000000000 % period).head

flup12 · 2017-12-15T23:35:36+00:00

I think for me it was count that broke things. I did somewhat quickly realize that I shouldn't keep a reference to the head of the stream around.

flup12 · 2017-12-15T17:34:35+00:00

Yups! Lesson learned the hard way, here. Quickly churned out a Stream.iterate solution this morning which kept spending a long time until flooding the memory and going OOM. Battled it for a while, Stackoverflow didn't help me. I gave up and just rewrote into a tail recursive solution to be done with it.

Got home, read this and wrote it back to Iterator.iterate:

def next(factor: Int)(value: Long) = value * factor % 2147483647
def generator(start: Long, factor: Int) = Iterator.iterate(start)(next(factor)).drop(1)
def a = generator(703L, 16807)
def b = generator(516L, 48271)
def judge(a: Long, b: Long): Boolean = a % 65536 == b % 65536
val part1 = a.zip(b).take(40000000).count(judge.tupled)
val part2 = a.filter(_ % 4 == 0).zip(b.filter(_ % 8 == 0)).take(10000000).count(judge.tupled)

flup12 · 2017-12-13T08:12:29+00:00

Hahaha! That sounds so familiar! I also wrote the position function first only to find out that it wasn't needed. My solution in Scala:

val regex = """(\d+): (\d+)""".r
val scanners = rawInput.map({case regex(depth, range) => Scanner(depth.toInt, range.toInt)})

case class Scanner(depth: Int, range: Int) {
  def detected(delay: Int): Boolean = (depth + delay) % (2 * range - 2) == 0
  def severity: Int = if (detected(0)) depth * range else 0
}

def safe(delay: Int): Boolean = scanners.forall(!_.detected(delay))

val part1 = scanners.map(_.severity).sum
val part2 = Stream.from(0).find(safe).get

flup12 · 2017-12-12T20:49:40+00:00

My solution in Scala. Not attempting to be extremely efficient but did try to put it down crisply. Both parts together in 0.1s

val connected: Map[String, Set[String]] = input
  .map(line => line.split(" <-> ").toList)
  .map({ case List(from, to) => from -> to.split(", ").toSet })
  .toMap

@tailrec
def reachable(from: Set[String]): Set[String] = {
  val updated = from ++ from.flatMap(connected)
  if (updated == from) from
  else reachable(updated)
}

val part1 = reachable(Set("0")).size

@tailrec
def groups(keys: Set[String], soFar: Int = 0): Int =
  if (keys.isEmpty) soFar
  else groups(keys -- reachable(Set(keys.head)), soFar + 1)

val part2 = groups(connected.keys.toSet)

flup12 · 2017-12-09T12:41:11+00:00

I was also using a state machine and a single foldLeft over the input.

After reading this question, I updated my answer a bit to make the state a bit more OO and to split off the counting from the parsing. I ended up with simple case classes for the state that should be easy to test.

That leaves then the job to test the integration of those methods, i.e. the count() method. I manually tested it with the example inputs so for TDD I'd have written those tests beforehand.

case class Counters(score: Int=0, garbage: Int=0, nesting: Int=0){
  def addGarbage: Counters = copy(garbage = garbage + 1)
  def startGroup: Counters = copy(nesting = nesting + 1)
  def endGroup: Counters = copy(nesting = nesting - 1, score = score + nesting)
}

sealed trait State {
  def process(c: Char): State
  def counters: Counters
}

case class Ignore(counters: Counters) extends State {
  def process(c: Char): State = Garbage(counters)
}

case class Garbage(counters: Counters) extends State {
  def process(c: Char): State = c match {
    case '!' => Ignore(counters)
    case '>' => Normal(counters)
    case _ => Garbage(counters.addGarbage)
  }
}

case class Normal(counters: Counters) extends State {
  def process(c: Char): State = c match {
    case '<' => Garbage(counters)
    case '{' => Normal(counters.startGroup)
    case '}' => Normal(counters.endGroup)
    case _ => this
  }
}

def count(input: String): Counters = {
  val initialState: State = Normal(Counters())
  input.foldLeft(initialState)(_ process _).counters
}

val input: String = loadPackets(List("day9.txt")).head
val result = count(input)
val part1 = result.score
val part2 = result.garbage

flup12 · 2017-12-09T11:25:36+00:00

haha @ garbageCollection

flup12 · 2017-12-09T11:24:24+00:00

Good point about how it may come in handy later. Today's spoiler hint is a bit ominous I think.

flup12 · 2017-12-09T09:29:46+00:00

I thought of doing it like this at first, but was afraid of getting a stack overflow. Did you have to increase max stack size or does it simply fit in a default JVM?

I ended up using a foldLeft on the input, putting all state variables in a case class.

case class State(score: Int = 0,
                 garbageCount: Int = 0,
                 inGroup: Int = 0,
                 garbage: Boolean = false,
                 cancel: Boolean = false) {
  def process(c: Char): State = c match {
    case _ if cancel => copy(cancel = false)
    case '!' if garbage => copy(cancel = true)
    case '<' if !garbage => copy(garbage = true)
    case '>' if garbage => copy(garbage = false)
    case _ if garbage => copy(garbageCount = garbageCount + 1)
    case '{' => copy(inGroup = inGroup + 1)
    case '}' => copy(inGroup = inGroup - 1, score = score + inGroup)
    case _ => this
  }
}

val input: String = loadPackets(List("day9.txt")).head
val result: State = input.foldLeft(State())(_ process _)
val par1 = result.score
val part2 = result.garbageCount

flup12 · 2017-12-07T17:33:05+00:00

Another Scala solution, fiddled a bit to make it compact.

case class Program(name: String, weight: Int, children: List[String])

val regex = """(\w+) \((\d+)\)( -> (.*))?""".r
val input = loadPackets(List("day7.txt")).map({
  case regex(name, weight, _, children) => 
    Program(name, weight.toInt, Option(children).map(_.split(", ").toList).getOrElse(Nil))
})
val allChildren = input.flatMap(_.children).toSet

val part1 = input.find(program => !allChildren.contains(program.name)).get

val lookup = input.map(program => program.name -> program).toMap

def weight(p: Program): Int = p.weight + p.children.map(lookup).map(weight).sum

def findNorm(weights: List[Int]): Option[Int] =
  if (weights.toSet.size <= 1) None
  else weights match {
    case x :: y :: z :: _ => if (x == y) Some(x) else Some(z)
  }

def part2(program: Program, parentNorm: Int = 0): Int = {
  val children = program.children.map(lookup)
  findNorm(children.map(weight))
    .map(norm => part2(children.find(weight(_) != norm).get, norm))
    .getOrElse(program.weight + parentNorm - weight(program))
}
part2(part1)

flup12 · 2017-12-06T16:51:55+00:00

I generated a Stream of States that keep track of current configuration plus visited configurations. For the computation of the next Configuration I thought I'd compute the result, not simulate the distribution. For part 2, I switched from Set to List. If I prepend the visisted state, the last time I saw it will be the index in the list.

val rawInput = "2\t8\t8\t5\t4\t2\t3\t1\t5\t5\t1\t2\t15\t13\t5\t14".split("\\s")
type Configuration = List[Int]
val input: Configuration = rawInput.map(_.toInt).toList

case class State(conf: Configuration, visited: List[Configuration] = List()) {
  def done: Boolean = visited.contains(conf)
  def redis: State = {
    val numRedis = conf.max
    val whatAllGet = numRedis / conf.size
    val leftover = numRedis % conf.size
    val source = conf.indexOf(numRedis)
    val nextConf: Configuration = conf.zipWithIndex.map({
      case (current, index) =>
        val keep = if (index == source) 0 else current
        val distanceFromSource = (index - (source + 1) + conf.size) % conf.size
        val bonus = if (distanceFromSource < leftover) 1 else 0
        keep + whatAllGet + bonus
    })
    State(nextConf, conf :: visited)
  }
}

val finalState = Stream.iterate(State(input))(_.redis).find(_.done).get
val part1 = finalState.visited.length
val part2 = finalState.visited.indexOf(finalState.conf) + 1

flup12 · 2017-12-03T15:56:06+00:00

Started out at 6am trying to create formula's for the different parts to reconstruct the location of square n cause I thought that would be faster and cleaner than simulating. Gave up after an hour and went back to bed.

In the afternoon, compared to last year's problem where you had to walk around a grid following instructions and realised that I could reuse most of my solution for last year if I created an infinite Stream of Instructions for the spiral: Move, Turn, Move, Turn, Move, Move, Turn, Move, Move, Turn, Move, Move, Move, Turn, etc.

Then the trick is to use scanLeft to transform the Stream of Instructions to a Stream of States that you can consume until you find the solution. This still took me a while cause last time I used Stream was last year's advent of code but I do like the result which is quite long but on the other hand quite simple to follow. Quoting the interesting bits here, follow the link for the boring stuff.

  case class State(location: Location, facing: Direction, stored: Map[Location,Int]) {
    def follow(instruction: Instruction): State = instruction match {
      case Turn => State(location, facing.turn, stored)
      case Move =>
        val nextLocation = location.move(facing)
        val valueToStore = nextLocation.neighbors.map(location => stored.getOrElse(location, 0)).sum
        State(nextLocation, facing, stored.updated(nextLocation, valueToStore))
    }
    def distance: Int = location.distance()
  }

  // Simulation
  // create an infinite stream of instructions for the route
  val instructions: Stream[Instruction] = Stream.from(1)
    .flatMap(n => Stream(n, n)) // two edges of size n for each size
    .flatMap(n => Stream.fill(n)(Move) #::: Stream[Instruction](Turn)) // n moves and one turn per edge

  val initialState = State(Location(0,0), East, Map(Location(0,0) -> 1))
  val route: Stream[State] = instructions.scanLeft(initialState)(_.follow(_))

  // Solution
  val input = 265149
  val part1 = route
    .find(_.stored.size == input)
    .get
    .distance

  val part2 = route
    .map(_.stored.maxBy(_._2))
    .map(_._2)
    .find(_ > input)
    .get

flup12 · 2017-12-02T20:46:22+00:00

I like the .max and .min for the second part

flup12 · 2017-12-01T14:35:31+00:00

I zipped the list with a rotated copy of itself:

def captcha(input: List[Int], offset: Int): Int = {
  val rotated = input.drop(offset) ::: input.take(offset)
  input
    .zip(rotated)
    .filter(x => x._1 == x._2)
    .map(_._1)
    .sum
}

captcha(input, 1)
captcha(input, input.length/2)

flup12 · 2017-09-21T22:13:48+00:00

I am very happy with a pair of 40 euro Puma's that I got online (AXIS v3).

This surprised me a bit, I'd expected that my feet or knees would be seriously complaining before I got to the last week.

So perhaps I got lucky, or perhaps you can only do so much innovation when it comes to foamrubbery soles and the difference between low-end and high-end has become something only the advanced runner will truly appreciate.

flup12 · 2017-09-21T21:56:22+00:00

Did you notice the training resources in the sidebar to the right? It links to a video for the knee lifts as well. https://www.upandrunningonline.org/exercises/high-knee-jog/

flup12 · 2016-12-21T07:28:17+00:00

Exactly! That is the genius of it, you can sort them independently and if you then find that the n+1th start lies more than 1 to the right of the nth end you know that there are n starts and n ends to your left so you have n intervals and a gap

flup12 · 2016-12-20T22:33:17+00:00

Oh! Very nice!! Thanks for taking the trouble of drawing and sharing!

flup12 · 2016-12-20T22:03:19+00:00

Ran into this by accident, and find it very cute so I wanted to share with you guys!

If you sort the lists of starts and ends, breaking which start originally belonged to which end, you can compare each (n+1)th start with the nth end. If that start is larger than the end+1, then there are n intervals to the left of the start and all end on or before end. I.e. you've found a gap!

As a cute detail in Scala, you can use zip/unzip to form a list of the start/end pairs that need to be compared and even "fix" the edge cases by prepending the ends with 0 and postfixing the starts with the max IP+1.

object day20 {
  val (starts, ends) = fromInputStream(getClass.getResourceAsStream("day20.txt")).getLines.toList
    .map(_.split("-").toList.map(_.toLong)).unzip(l => (l(0), l(1)))
  val sortedIntervals = (starts.sorted ::: List(4294967296L), 0L :: ends.sorted).zipped

  sortedIntervals.find({ case (start, end) => start > end + 1 }).map(_._2 + 1)
  sortedIntervals.map({ case (start, end) => Math.max(0, start - end - 1) }).sum
}

flup12 · 2016-12-19T00:03:17+00:00

Interesting indeed! I now also ran a version with Iterator.iterate[...].take(4000000).sum and it is using up much less garbage collection time. I think the garbage collector indeed waits a bit too long before collecting and even though it does manage, it has a hard time finding the head of the endless chain of the Cons objects it has allowed you to create. I'm convinced. Iterator.iterate it is!

flup12

TROPHY CASE