semi related, for those who want to see an O(N) so...

# advent-of-code

[Nir]

semi related, for those who want to see an O(N) solution for part b), see thread

[Nir]

enum class InstructionType {
    JMP,
    NOP,
    ACC
}

data class Instruction(val type: InstructionType, val arg: Int)

fun getData() = (aocDataDir / "day8.txt").useLines { lines ->
    lines.map{ line ->
        val (typeStr, argStr) = line.split(" ")
        val type = when (typeStr) {
            "jmp" -> InstructionType.JMP
            "nop" -> InstructionType.NOP
            "acc" -> InstructionType.ACC
            else -> throw Exception("Bad data!")
        }
        Instruction(type, argStr.toInt())
    }.toList()
}

data class State(val accumulator: Int, val index: Int)

fun execute(program: List<Instruction>, state: State): State {
    val instr = program[state.index]
    return when (instr.type) {
        InstructionType.JMP -> state.copy(index = state.index + instr.arg)
        InstructionType.NOP -> state.copy(index = state.index + 1)
        InstructionType.ACC -> state.copy(index = state.index + 1, accumulator = state.accumulator + instr.arg)
    }
}

fun part2Fast(): Int {
    val program = getData()
    var flipState: State? = null
    var currentState = State(0, 0)
    val visited = mutableSetOf<Int>()
    while (true) {
        visited += currentState.index
        if (flipState != null) {
            currentState = execute(program, currentState)
            if (currentState.index == program.size) {
                return currentState.accumulator
            }
            if (currentState.index in visited) {
                currentState = execute(program, flipState)
                flipState = null
            }
            continue
        }
        val instr = program[currentState.index]
        if (instr.type != InstructionType.ACC) {
            flipState = currentState
        }
        currentState = when (instr.type) {
            InstructionType.ACC -> currentState.copy(accumulator = currentState.accumulator + instr.arg, index = currentState.index + 1)
            InstructionType.JMP -> currentState.copy(index = currentState.index + 1)
            InstructionType.NOP -> currentState.copy(index = currentState.index + instr.arg)
        }
    }
}

[bjonnh]

Nice that's exactly what I was going to code

[Nir]

Well, good on you 🙂 I adapated someone else's C++ solution

[Nir]

Took me a long while to understand how it works

[Nir]

Made me realizing how rarely I use backtracking and how weak I am at it

[Nir]

Alright, I managed to rewrite it in a way that makes a little more sense to me without introducing bugs, so I'm accepting this as having achieved some basic understanding of the problem 🙂

[bjonnh]

that's easy to do because there is no conditional branching

[bjonnh]

nor dynamic programming (changing code or using code as data interchangeably)

[Nir]

what do you mean exactly?

[Nir]

DP I'm good with

[Nir]

but this problem does not lend itself to DP

[bjonnh]

no I mean the language they propose doesn't do that

[bjonnh]

so it is easy to do those kind of optimized approaches

[Nir]

oh

[Nir]

yes, if there was some kind of more interesting branching, then you'd see more "realistic" backtracking

[Nir]

even if you could change up to 3 instructions, that would already make the code a lot more representative of real backtracking (and then, I'd be very bad at it)