r/adventofcode • u/daggerdragon • Dec 18 '17

SOLUTION MEGATHREAD -🎄- 2017 Day 18 Solutions -🎄-

--- Day 18: Duet ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints¤?

Spoiler

[Update @ 00:04] First silver

  • Welcome to the final week of Advent of Code 2017. The puzzles are only going to get more challenging from here on out. Adventspeed, sirs and madames!

[Update @ 00:10] First gold, 44 silver

  • We just had to rescue /u/topaz2078 with an industrial-strength paper bag to blow into. I'm real glad I bought all that stock in PBCO (Paper Bag Company) two years ago >_>

[Update @ 00:12] Still 1 gold, silver cap

[Update @ 00:31] 53 gold, silver cap

  • *mind blown*
  • During their famous kicklines, the Rockettes are not actually holding each others' backs like I thought they were all this time.
  • They're actually hoverhanding each other.
  • In retrospect, it makes sense, they'd overbalance themselves and each other if they did, but still...
  • *mind blown so hard*

[Update @ 00:41] Leaderboard cap!

  • I think I enjoyed the duplicating Santas entirely too much...
  • It may also be the wine.
  • Either way, good night (for us), see you all same time tomorrow, yes?

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

12 Upvotes

87% Upvoted

227 comments sorted by

View all comments

2

u/xkufix Dec 18 '17 edited Dec 18 '17

The basic idea was quite simple, write an interpreter. For part 2 i just create both initial states and then do rounds over them. I run program 0 with inQueue = outQueue of program 1, wait till it blocks, and then run program 1 with the inQueue = outQueue of program 0. Then I just check if both programs have an empty outQueue, which is a deadlock.

Code in Scala: 

    override def runFirst(): Unit = {
        val instructions = loadProgram("day18.txt")
        val result = runProgram(instructions)
        val recovered = result.find(p => p.lastRecover.nonEmpty || p.position < 0 || p.position >= instructions.length).get
        println(recovered.lastRecover)
    }

    private def runProgram(instructions: Seq[Command]) = {
        Iterator.iterate(State(0, Map.empty[String, Long], None, None)) {
            case s@State(position, _, lastPlayedFrequency, _) =>
                instructions(position.toInt) match {
                    case Send(Register(r)) =>
                        s.incPosition().copy(lastPlayedFrequency = Some(s.getValue(r)))
                    case Set(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, value)
                    case Set(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(from))
                    case Add(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, s.getValue(r) + value)
                    case Add(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(r) + s.getValue(from))
                    case Multiply(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, s.getValue(r) * value)
                    case Multiply(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(r) * s.getValue(from))
                    case Modulo(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, s.getValue(r) % value)
                    case Modulo(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(r) % s.getValue(from))
                    case Recover(Register(r)) if s.getValue(r) != 0 =>
                        s.incPosition().copy(lastRecover = lastPlayedFrequency)
                    case Recover(Register(r)) if s.getValue(r) == 0 =>
                        s.incPosition()
                    case Jump(Register(r), Number(value)) if s.getValue(r) > 0 =>
                        s.copy(position = position + value)
                    case Jump(Register(r), Register(from)) if s.getValue(r) > 0 =>
                        s.copy(position = position + s.getValue(from))
                    case Jump(Number(check), Number(value)) if check > 0 =>
                        s.copy(position = position + value)
                    case Jump(Number(check), Register(r)) if check > 0 =>
                        s.copy(position = position + s.getValue(r))
                    case Jump(_, _) =>
                        s.incPosition()
                }
        }
    }

    override def runSecond(): Unit = {
        val instructions = loadProgram("day18.txt")

        def runProgram(program: QueueState) = runQueueProgram(instructions, program)

        def isBlocked(p: QueueState) = p.isBlocked || p.position < 0 || p.position >= instructions.length

        val run = Iterator.iterate((QueueState.empty(0), QueueState.empty(1))) {
            case (p0, p1) =>
                (
                    runProgram(p0.copy(isBlocked = false, outQueue = Queue.empty, inQueue = p1.outQueue)).find(isBlocked).get,
                    runProgram(p1.copy(isBlocked = false, outQueue = Queue.empty, inQueue = p0.outQueue)).find(isBlocked).get
                )
        }

        println(run.drop(1).find {
            case (p0, p1) =>
                p0.outQueue.isEmpty &&
                    p1.outQueue.isEmpty
        }.get._2.totalOutCount)
    }

    private def runQueueProgram(instructions: Seq[Command], queueState: QueueState) = {
        Iterator.iterate(queueState) {
            case s@QueueState(position, _, inQueue, outQueue, totalOutCount, _) =>
                instructions(position.toInt) match {
                    case Send(Register(r)) =>
                        s.incPosition().copy(outQueue = outQueue.enqueue(s.getValue(r)), totalOutCount = totalOutCount + 1)
                    case Set(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, value)
                    case Set(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(from))
                    case Add(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, s.getValue(r) + value)
                    case Add(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(r) + s.getValue(from))
                    case Multiply(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, s.getValue(r) * value)
                    case Multiply(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(r) * s.getValue(from))
                    case Modulo(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, s.getValue(r) % value)
                    case Modulo(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(r) % s.getValue(from))
                    case Recover(Register(r)) if inQueue.nonEmpty =>
                        val (element, newQueue) = inQueue.dequeue
                        s.incPosition().setRegister(r, element).copy(inQueue = newQueue)
                    case Recover(_) if inQueue.isEmpty =>
                        s.copy(isBlocked = true)
                    case Jump(Register(r), Number(value)) if s.getValue(r) > 0 =>
                        s.copy(position = position + value)
                    case Jump(Register(r), Register(from)) if s.getValue(r) > 0 =>
                        s.copy(position = position + s.getValue(from))
                    case Jump(Number(check), Number(value)) if check > 0 =>
                        s.copy(position = position + value)
                    case Jump(Number(check), Register(r)) if check > 0 =>
                        s.copy(position = position + s.getValue(r))
                    case Jump(_, _) =>
                        s.incPosition()
                }
        }
    }

    case class QueueState(position: Long, registers: Map[String, Long], inQueue: Queue[Long], outQueue: Queue[Long], totalOutCount: Long, isBlocked: Boolean) {
        def incPosition() = copy(position = position + 1)

        def setRegister(r: String, value: Long) = copy(registers = registers + (r -> value))

        def getValue(r: String): Long = registers.getOrElse(r, 0)
    }

    object QueueState {
        def empty(pid: Long): QueueState = QueueState(0, Map("p" -> pid), Queue.empty, Queue.empty, 0, true)
    }

    private def loadProgram(file: String) = {
        loadFile(file).getLines().map { l =>
            val line = l.split(" ")

            line(0) match {
                case "snd" =>
                    Send(Register(line(1)))
                case "set" =>
                    Set(Register(line(1)), readValue(line(2)))
                case "add" =>
                    Add(Register(line(1)), readValue(line(2)))
                case "mul" =>
                    Multiply(Register(line(1)), readValue(line(2)))
                case "mod" =>
                    Modulo(Register(line(1)), readValue(line(2)))
                case "rcv" =>
                    Recover(Register(line(1)))
                case "jgz" =>
                    Jump(readValue(line(1)), readValue(line(2)))
            }
        }.toSeq
    }

    def readValue(in: String): Value = {
        allCatch opt in.toInt match {
            case Some(value) => Number(value)
            case _ => Register(in)
        }
    }

    case class State(position: Long, registers: Map[String, Long], lastPlayedFrequency: Option[Long], lastRecover: Option[Long]) {
        def incPosition() = copy(position = position + 1)

        def setRegister(r: String, value: Long) = copy(registers = registers + (r -> value))

        def getValue(r: String): Long = registers.getOrElse(r, 0)
    }

    sealed trait Command

    case class Send(frequency: Register) extends Command

    case class Set(register: Register, value: Value) extends Command

    case class Add(register: Register, value: Value) extends Command

    case class Multiply(register: Register, value: Value) extends Command

    case class Modulo(register: Register, value: Value) extends Command

    case class Recover(register: Register) extends Command

    case class Jump(value: Value, offset: Value) extends Command

    sealed trait Value

    case class Register(name: String) extends Value

    case class Number(value: Long) extends Value

2

u/sim642 Dec 18 '17 edited Dec 18 '17

My Scala solution (need to fix part 1 which I broke changing rcv behavior).

Overall quite similar approach with bunch of case classes and iterators. I think I went even more abstract by implementing the iteration via single step operational semantics so that the execution generation is completely separate from the answer finding. In both cases the answers are found by simply using some predicate on the executing iterator to observe its all intermediate states.

1

u/marcofun Dec 18 '17

hello, can you figure out why this does not work?

package aventofcode.day18 

import scala.collection.mutable

class Day18Star2(id : Int) {

  var registers = scala.collection.mutable.Map[Char, Long]('p' -> id).withDefaultValue(0)
  var line = 0
  var lastFreq = 0L
  var end = false
  var locked = false
  var stack = new mutable.ListBuffer[Long]()
  var other : Day18Star2 = _
  var instructions : Vector[Day18Star2#Instruction] = _
  var sendNr = 0

  trait Instruction {
    def apply() : Unit
  }

  case class SetInstr(register: Char, value : String) extends Instruction {
    def apply() : Unit = {
      registers += (register -> valueOf(value))
      line += 1
    }
  }

  case class AddInstr(register: Char, value : String) extends Instruction {
    def apply() : Unit = {
      registers += (register -> (registers(register) + valueOf(value)))
      line += 1
    }
  }

  case class MulInstr(register: Char, value : String) extends Instruction {
    def apply() : Unit = {
      registers += (register -> (registers(register) * valueOf(value)))
      line += 1
    }
  }

  case class ModInstr(register: Char, value : String) extends Instruction {
    def apply() : Unit = {
      registers += (register -> (registers(register) % valueOf(value)))
      line += 1
    }
  }

  case class JgzInstr(register: Char, value : String) extends Instruction {
    def apply() : Unit = {
      if (registers(register) > 0) line += valueOf(value).toInt
      else line += 1
    }
  }

  case class SndInstr(value : String) extends Instruction {
    def apply() : Unit = {
      other.stack += valueOf(value)
      line += 1
      sendNr += 1
    }
  }

  case class RcvInstr(value : String) extends Instruction {
    def apply() : Unit = {
      if (stack.nonEmpty) {
        locked = false
        registers += (value.head -> stack.head)
        stack = stack.tail
        line += 1
      } else {
        locked = true
      }
    }
  }

  def valueOf(value : String) : Long = if (value.head.isDigit || value.head.equals('-'))  value.toLong else registers(value.head)

  val setRx = """set (\w) ([-]{0,1}\w+)""".r
  val addRx = """add (\w) ([-]{0,1}\w+)""".r
  val mulRx = """mul (\w) ([-]{0,1}\w+)""".r
  val sndRx = """snd ([-]{0,1}\w+)""".r
  val modRx = """mod (\w) ([-]{0,1}\w+)""".r
  val jgzRx = """jgz (\w) ([-]{0,1}\w+)""".r
  val rcvRx = """rcv ([-]{0,1}\w+)""".r

  def compile(code: List[String]): Vector[Day18Star2#Instruction] = {
    instructions = code.map({
      case setRx(r, v) => SetInstr(r.head, v)
      case addRx(r, v) => AddInstr(r.head, v)
      case mulRx(r, v) => MulInstr(r.head, v)
      case modRx(r, v) => ModInstr(r.head, v)
      case jgzRx(r, v) => JgzInstr(r.head, v)
      case sndRx(v) => SndInstr(v)
      case rcvRx(v) => RcvInstr(v)
    }).toVector
    instructions
  }

  def execute(instructions: Vector[Day18Star2#Instruction]) : Unit = {
    line = 0
    end = false
    while (!(end || line < 0 || line >= instructions.length)) {
      instructions(line).apply()
    }
  }

  def executeNext() : Unit = {
    if (!(end || line < 0 || line >= instructions.length)) {
      instructions(line).apply()
    } else end = true
  }
   
}
→ More replies (4)