Programming

Advent of Code Day 1 and 2 in Scala

Advent of Code 2019

This is my catch-up post for Advent of Code 2019 day 1 and day 2. Both days involved tail recursive functions, which is a whole lot of fun to write! The first day required recursive fuel calculation logic. When adding fuel to a rocket, we need to ensure that we add fuel when a significant amount of fuel is added. Because fuel itself has weight, and has to be propelled.

Day 1: parts 1 and 2

class Puzzle1 {
  def calculateFuel(input: Int): Int = {
    val first = Math.floor(input.toFloat / 3).toInt
    first - 2
  }

  //recursive fuel calculation function!
  @tailrec final def recursiveFuel(acc: Int = 0, input: Int): Int = {
    val change = Math.floor(input.toFloat / 3).toInt
    if (change <= 2) {
      acc
    } else {
      //do the calculation and add it to accumulator, and recurse
      val addFuel = change - 2;
      recursiveFuel(acc + addFuel, addFuel)
    }
  }
}

Part 1 of Advent of Code Day 1 was very simple, just do the math. Part 2 requires a recursive function to accumulate the amount of fuel required, and track the additional fuel added. If that amount of fuel added is significant enough, you have to add fuel to hoist the mass added! Fun!

Day 2: parts 1 and 2

The second day is even more fun. An IntCode Computer!

An Intcode program is a list of integers separated by commas (like 1,0,0,3,99). To run one, start by looking at the first integer (called position 0). Here, you will find an opcode – either 1, 2, or 99. The opcode indicates what to do; for example, 99 means that the program is finished and should immediately halt. Encountering an unknown opcode means something went wrong.

https://adventofcode.com/2019/day/2

Now, we have to implement an algorithm that can process IntCode Ops and mutate it’s memory state. But I really hate mutating state, because that’s bad. Therefore, another tail-recursive function!

package is.kow.adventofcode._2019

import scala.annotation.tailrec

class IntCode(ops: List[Int]) {
  private final val ADD = 1
  private final val MULT = 2
  private final val END = 99

  def execute(): List[Int] = {

    @tailrec def process(acc: List[Int], opCount: Int): List[Int] = {
      acc.drop(opCount * 4) match {
        case ADD :: in1 :: in2 :: dest :: xs =>
          val result = acc(in1) + acc(in2)
          process(acc.updated(dest, result), opCount + 1)
        case MULT :: in1 :: in2 :: dest :: xs =>
          val result = acc(in1) * acc(in2)
          process(acc.updated(dest, result), opCount + 1)
        case END :: xs =>
          acc
        case _ => throw new Exception("Unknown opcode")
      }
    }

    process(ops, 0)
  }
}

I remembered my pattern matching logic from scala! Pattern Matching allowed me to select out the Operation, and then the Parameters to that operation, trivially.

Opcodes (like 1, 2, or 99) mark the beginning of an instruction. The values used immediately after an opcode, if any, are called the instruction’s parameters. For example, in the instruction 1,2,3,4, 1 is the opcode; 2, 3, and 4 are the parameters. The instruction 99 contains only an opcode and has no parameters.

https://adventofcode.com/2019/day/2 – part 2

Using the list builtin method .updated I can create a new list, changing out that location in the list. Perfect for the IntCode operations. I just have to keep track of how many operations I have done, so I can move along the list and execute the next operation in order.

This proved to be an excellent solution to both part 1 and part 2 of the Advent of Code Day 2 puzzle. For part 2, I pretty much just did the dumbest thing possible, and used tons of CPU power to brute force out the solution. I didn’t even exit the loop early, so I wasted all the CPU cycles.

  println("PART TWO:")

  (0 to 99).inclusive.foreach( noun => {
    (0 to 99).inclusive.foreach(verb => {
      val attempt = app.updated(1, noun).updated(2, verb)
      val result = new IntCode(attempt).execute()
      if(result.head == 19690720) {
        println(s"Noun = $noun verb = $verb")
        println(s"ANSWER: ${100 * noun + verb}")
      }
    })
  })

Further Reading

0 0 vote
Article Rating

Related posts

Advent of Code 2019 in Scala Day 7

David Kowis

Advent of Code 2019 Day 3 in Scala

David Kowis

Advent of Code 2019 Day 5 in Scala

David Kowis
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
Adventures in Software Development, Home Labbing, and DevOps
0
Would love your thoughts, please comment.x
()
x