Advent of Code 2019 Solution Megathread - Day 15: Oxygen System

We're running out of air, but don't worry: our old pal the IntCode Robot is back to help us out.

Day 15 - The Problem

More bad news! We're running out of air, and we have no idea about the shape of our ship. Luckily, our care package contains an IntCode program that can run an Oxygen System Repair Robot.

We need to find an efficient path to the Oxygen System location in Part 1. Fire up those IntCodes and get searching our mazelike module.

Part 2 needs us to see how long we have to wait until the area is safe to go into again. We may need a better map...

Ongoing Meta

Dev.to List of Leaderboards

• 120635-5c140b9a - provided by Linda Thompson

If you were part of Ryan Palo's leaderboard last year, you're still a member of that!

If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)

I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.

There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.

Neat Statistics

I'm planning on adding some statistics, but other than "what languages did we see yesterday" does anyone have any ideas?

Languages Seen On Day 13

Under construction

Comments

[Massimo Artizzu]

IntCodes on odd days as usual. Will we have to use them on Christmas too? 🤔

At first was considering getting the map out of the input itself, but it's hidden well enough so I thought it was easier to give it a try anyway.

So, the approach. Instead of the suggested way of backtracking with the drone, I decided to keep a "frontier" of tiles next to unexplored ones, and expand it at every iteration until the leak is reached (for part one) or the frontier is empty (for part two).

Therefor "frontier" consists in an object mapping coordinates with the "state" of the machine (which has to be copied). The only optimization I made here to my IntCode machine was using a Uint16Array instead of a normal array, but it wasn't really necessary.

To the code (in JavaScript):

// Initial part like usual, only using typed arrays. See my repo
function moveRobot(column, row, direction) {
  switch (direction) {
    case 1: return [ column, row - 1 ];
    case 2: return [ column, row + 1 ];
    case 3: return [ column - 1, row ];
    case 4: return [ column + 1, row ];
  }
}

function evolveFrontier(initialMap, initialState, condition) {
  const map = { ...initialMap };
  let frontier = { [Object.keys(map)[0]]: initialState };
  let counter = 0;
  while (!(condition(map, frontier))) {
    counter++;
    const newFrontier = {};
    for (const [ coords, state ] of Object.entries(frontier)) {
      const [ column, row ] = coords.split(',').map(Number);
      for (let direction = 1; direction <= 4; direction++) {
        const [ newColumn, newRow ] = moveRobot(column, row, direction);
        const positionKey = `${newColumn},${newRow}`;
        if (positionKey in map) {
          continue;
        }
        const newState = state.slice();
        const drone = createProgramInstance(newState, direction);
        const { value } = drone.next();
        map[positionKey] = value;
        if (value !== 0) {
          newFrontier[positionKey] = newState;
        }
        drone.return(); // Closes the generator to avoid memory leaks
      }
    }
    frontier = newFrontier;
  }
  return [ map, frontier, counter ];
}

The evolveFrontier function takes three arguments:

• the initial map (an object mapping coordinates with their type of tile): it's needed to keep track of the explored tiles;
• the initial state: a copy of the IntCode program;
• a condition callback: so the look knows when to stop. It return the map at the moment the condition becomes true; the frontier at the same istant; and the number of iterations.

The first part is now rather easy:

const [ tankMap, tankFrontier, movements ] = evolveFrontier(
  { '0,0': 1 },
  codes,
  map => [ ...Object.values(map) ].includes(2)
);
console.log('Part 1:', movements);

The values tankMap and tankFrontier will be needed for the second part:

const leakCoords = Object.keys(tankMap).find(coords => tankMap[coords] === 2);
const leakState = tankFrontier[leakCoords];

const [ ,, fillUpAfter ] = evolveFrontier(
  { [leakCoords]: 2 },
  leakState,
  (_, frontier) => Object.keys(frontier).length === 0
);
// -1 because the last round has always hit a wall
console.log('Part 2:', fillUpAfter - 1);

Find today's text, my input the my complete solution at my repo.

[Rizwan]

let to the party. Swift here --->

enum Direction: Int, CaseIterable {
    case north  = 1
    case south  = 2
    case west = 3
    case east = 4

    func next() -> Self {
        switch self {
        case .north:
            return .south
        case .south :
            return .west
        case .west:
            return .east
        case .east:
            return .north
        }
    }
}

enum Status: Int, CustomStringConvertible {
    var description: String {
        get {
            desc()
        }
    }

    func desc() -> String {
        switch self {
        case .wall:
            return "Wall"
        case .moved:
            return "Moved"
        case .oxygen:
            return "Oxygen System"
        }
    }

    case wall = 0
    case moved = 1
    case oxygen = 2
}

struct Point: CustomStringConvertible, Equatable, Hashable {
    var x: Int
    var y: Int

    var description: String {
        get {
            return "X: \(self.x) Y: \(self.y)"
        }
    }

    func move(_ direction: Direction) -> Point {
        switch direction {
        case .north:
            return Point.init(x: x, y: y + 1)
        case .south:
            return Point.init(x: x, y: y - 1)
        case .west:
            return Point.init(x: x - 1, y: y)
        case .east:
            return Point.init(x: x + 1, y: y)
        }
    }

    func distance() -> Int {
        return abs(x) + abs(y)
    }
}

class Driod {
    var grid: [Point: Status] = [:]
    var memory: [Int]
    let computer: Opcode

    init(_ memory: [Int]) {
        self.memory = memory
        self.computer = Opcode.init(memory, 0)
    }

    func search() {
        var queue: [Point] = [Point]()
        queue.insert(Point.init(x: 0, y: 0), at: 0)
        var seen:[Point:Opcode] = [Point.init(x: 0, y: 0): Opcode.init(memory)]

        while !queue.isEmpty {
            let currentP = queue.removeLast()
            Direction.allCases.forEach { (direction) in
                let pos = currentP.move(direction)
                guard seen[pos] == nil else { return }
                let computer = seen[currentP]!.clone()
                computer.inputIds.removeAll()
                computer.inputIds.append(direction.rawValue)
                let status = Status.init(rawValue: computer.run())
                seen[pos] = computer
                grid[pos] = status
                if status != .wall {
                    queue.insert(pos, at: 0)
                }
            }
        }
    }

    func stepsToO2() -> Int {
        var queue: Array<(steps:Int,point:Point)> = Array<(steps:Int,point:Point)>()
        queue.insert((steps:0,point:Point.init(x: 0, y: 0)), at: 0)
        var seen: Set<Point> = Set<Point>()
        var stepsToO2 = -1
        while !queue.isEmpty && stepsToO2 == -1 {
            let tuple = queue.removeLast()
            let steps = tuple.steps
            let point = tuple.point
            seen.insert(point)

            Direction.allCases.forEach { (direction) in
                let pos = point.move(direction)
                if !seen.contains(pos) {
                    let status = grid[pos, default: .wall]
                    if status != .wall {
                        queue.insert((steps:steps+1,point:pos), at:0)
                    }
                    if status == .oxygen {
                        stepsToO2 = steps + 1
                    }
                }
            }
        }
        return stepsToO2
    }

    func minToFillO2() -> Int {
        let o2Point = grid.first(where: { $0.value == .oxygen })!.key
        var queue: [Point] = [Point]()
        queue.insert(o2Point, at: 0)
        var seen: Set<Point> = Set<Point>()
        var min = -1

        while !queue.isEmpty {
            var queueNext: [Point] = []
            while !queue.isEmpty {
                let currentP = queue.removeLast()
                seen.insert(currentP)

                Direction.allCases.forEach { (direction) in
                    let pos = currentP.move(direction)

                    guard !seen.contains(pos),
                        grid[pos, default: .wall] == .moved else {
                        return
                    }
                    queueNext.append(pos)
                }
            }
            queue = queueNext
            min += 1
        }

        return min
    }
}

func partOne() {
    let driod = Driod(input)
    driod.search()
    print("Part 1 answer is :\(driod.stepsToO2())")
}

func partTwo() {
    let driod = Driod(input)
    driod.search()
    print("Part 2 answer is :\(driod.minToFillO2())")
}

partOne()
partTwo()

[Neil Gall]

Since it was Sunday I took the remote control metaphor to heart, added a server socket, modified my C IntCode machine so the socket performed the input and output, then went off to write the exploring code in another language to run in a separate process. I literally have to open two shells to run the solution.

Part 1 was an obvious depth-first search so I thought I'll do the search code in Haskell. Time was a bit broken up today but I got a bit bogged down in backtracking behaviour that wasn't quite tracking the correct position of the repair droid. Got there in the end however, and using depth-first meant the shortest route to the oxygen system fell out of the recorded path used for backtracking.

Part 2 is a classic "flood fill" algorithm. My space was encoded as a map of positions to contents, so an efficient implementation wasn't going to fall out naturally. Thankfully the space was small enough that it runs quickly:

$ time runhaskell day15.hs
Part 1 .. 296
Part 2 .. 302

real    0m3.919s
user    0m3.586s
sys 0m0.217s

[Jon Bristow]

Really ugly kotlin solution.

I did this without state, and this caused me some wacky problems. I'll reply with a cleaner version later.

import arrow.core.Either
import arrow.core.None
import arrow.core.Option
import arrow.core.Some
import arrow.core.left
import arrow.core.right
import arrow.core.some
import intcode.CurrentState
import intcode.handleCodePoint
import intcode.toIntCodeProgram
import java.util.LinkedList

sealed class ShipTile {
    object Empty : ShipTile()
    object Oxygen : ShipTile()
    object Wall : ShipTile()
}

data class RepairRobot(
    val code: MutableMap<Long, Long>,
    val position: PointL = PointL(0, 0),
    val map: MutableMap<PointL, ShipTile> = mutableMapOf(PointL(0, 0) to ShipTile.Empty),
    val lastInstruction: Option<Direction> = Option.empty(),
    val state: Either<String, CurrentState> = CurrentState().right(),
    val instructions: LinkedList<Direction> = LinkedList()
)

object Day15 {

    private const val FILENAME = "src/main/resources/day15.txt"
    private val fileData = FILENAME.toIntCodeProgram()
    private tailrec fun RepairRobot.move(): RepairRobot {
        return when {
            instructions.size > 2500 -> this.copy(state = "reached mapping limit".left())
            state is Either.Left<String> -> this
            state is Either.Right<CurrentState> -> when (state.b.pointer) {
                is None -> this
                is Some<Long> -> {
                    val nRobot = this.processReturn().sendDirection(instructions)
                    nRobot.copy(state = handleCodePoint(code, nRobot.state))
                        .move()
                }
                else -> this
            }
            else -> this
        }
    }

    fun part1() {
        val r = RepairRobot(
            code = fileData.toMutableMap(), instructions = LinkedList(allDirections())
        )
            .move()
        println(r.state)
        val path = r.map.path(r.position, listOf(PointL(0, 0) to 0))
        println(path)
        println(r.map.size)
        r.printScreen()
        println(
            fillWithOxygen(
                r.map.filter { it.key != r.position && it.value == ShipTile.Empty }.map { it.key }.toSet(),
                setOf(r.position)
            )
        )
    }

    private tailrec fun fillWithOxygen(
        map: Set<PointL>,
        position: Set<PointL>,
        minutes: Int = 0,
        filled: Int = 0
    ): Int {
        println("map:${map.size}")
        println("position:${position.size}")
        println("minutes:$minutes")
        println("filled:$filled")
        println()
        return when {
            map.isEmpty() -> minutes
            else -> {
                val filling = position.flatMap { p ->
                    allDirections().map(p::inDirection).filter { it in map }
                }.toSet()
                val unfilled = map - filling
                fillWithOxygen(unfilled, filling, minutes + 1, filled + filling.size)
            }
        }
    }
}

private tailrec fun MutableMap<PointL, ShipTile>.path(
    end: PointL,
    queue: List<Pair<PointL, Int>>,
    seen: Set<PointL> = emptySet()
): Int {
    return when {
        queue.isEmpty() -> throw Error("not found")
        queue.first().first == end -> queue.first().second
        else -> {
            val (p, dist) = queue.first()
            val candidates = listOf(
                p.inDirection(Direction.Up()),
                p.inDirection(Direction.Left()),
                p.inDirection(Direction.Down()),
                p.inDirection(Direction.Right())
            ).filter { it !in seen && this[it] != null && this[it] != ShipTile.Wall }
                .map { it to dist + 1 }
            path(
                end, queue.drop(1) + candidates, seen + queue.first().first
            )
        }
    }
}

fun main() {
    Day15.part1()
}

private fun RepairRobot.sendDirection(
    instructions: LinkedList<Direction>
): RepairRobot {

    return when {
        state is Either.Right<CurrentState> && state.b.waitingForInput
                && instructions.isNotEmpty() -> {
            val nInstr = instructions.pop()
            state.b.inputs.add(nInstr.toLong())
            copy(state = state, lastInstruction = nInstr.some())
        }
        state is Either.Right<CurrentState> && state.b.waitingForInput -> copy(state = "No more instructions".left())
        else -> this
    }
}

fun PointL.inDirection(direction: Direction): PointL =
    when (direction) {
        is Direction.Up -> PointL.y.set(this, this.y - 1)
        is Direction.Down -> PointL.y.set(this, this.y + 1)
        is Direction.Left -> PointL.x.set(this, this.x - 1)
        is Direction.Right -> PointL.x.set(this, this.x + 1)
    }

private tailrec fun RepairRobot.processReturn(): RepairRobot {
    return when (state) {
        is Either.Left<String> -> this
        is Either.Right<CurrentState> -> {
            if (state.b.output.isNotEmpty()) {
                val rNext = when (state.b.output.pop()) {
                    0L -> {
                        lastInstruction.map { dir ->
                            map[position.inDirection(dir)] = ShipTile.Wall
                        }
                        this.copy(
                            lastInstruction = Option.empty(),
                            position = position
                        )
                    }
                    1L -> {
                        lastInstruction.map { dir ->
                            map[position.inDirection(dir)] = ShipTile.Empty
                            instructions.push(dir.reverse().turnLeft())
                            instructions.push(dir)
                            instructions.push(dir.turnLeft())
                        }
                        this.copy(
                            lastInstruction = Option.empty(),
                            position = lastInstruction.fold({ position }, { position.inDirection(it) })
                        )
                    }
                    2L -> {
                        lastInstruction.map { dir ->
                            map[position.inDirection(dir)] = ShipTile.Oxygen
                            instructions.push(dir.reverse().turnLeft())
                            instructions.push(dir)
                            instructions.push(dir.turnLeft())
                        }
                        this.copy(
                            lastInstruction = Option.empty(),
                            position = lastInstruction.fold({ position }, { position.inDirection(it) })
//                            state = "Found Oxygen ${lastInstruction.fold( { position }, { position.inDirection(it) })}".left()
                        )
                    }
                    else -> this
                }

                rNext.processReturn()
            } else {
                this
            }
        }
    }
}

fun allDirections(): Collection<Direction> {
    return listOf(
        Direction.Left(),
        Direction.Up(),
        Direction.Right(),
        Direction.Down()
    )
}

private fun Direction.reverse(): Direction {
    return this.turnLeft().turnLeft()
}

fun RepairRobot.printScreen() {
    println(instructions.size)
    val toConsider = map + (position to ShipTile.Empty)
    val topLeft = PointL(
        toConsider.keys.map(PointL::x).min() ?: 0L,
        toConsider.keys.map(PointL::y).min() ?: 0L
    )
    val bottomRight = PointL(
        toConsider.keys.map(PointL::x).max() ?: 0L,
        toConsider.keys.map(PointL::y).max() ?: 0L
    )
    println(
        (topLeft.y..bottomRight.y).joinToString("\n") { y ->
            (topLeft.x..bottomRight.x).joinToString("") { x ->
                when (val p = PointL(x, y)) {
                    position -> lastInstruction.fold({ "B" }, { it.glyph })
                    else -> map[p].toGlyph()
                }
            }
        }
    )
    println("---")
}

private fun ShipTile?.toGlyph(): String {
    return when (this) {
        is ShipTile.Empty -> "."
        is ShipTile.Oxygen -> "O"
        is ShipTile.Wall -> "#"
        null -> " "
    }
}