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

// 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 ];
}

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

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);

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()

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

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

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 -> " "
    }
}