backwards.go

package main

import (
	"aoc/vm"
	"fmt"
)

type jump struct {
	pos int
	op  string
	arg int
}

type state struct {
	vm           *vm.VM
	wasFlipped   bool
	flipLocation int
	code         []*vm.Instruction
	jumpTable    map[int][]jump // possible jumps to a given location
}

func backwards(vm *vm.VM) (int, error) {
	code := vm.Code()
	s := &state{
		vm:        vm,
		code:      code,
		jumpTable: make(map[int][]jump),
	}
	for k, c := range code {
		if c.Op == "nop" || c.Op == "jmp" {
			// make a note of where this (potential) jump could take us
			if c.Arg == 0 {
				continue
			}
			target := k + c.Arg
			jt := s.jumpTable[target]
			if len(jt) == 0 {
				jt = make([]jump, 0)
			}
			jt = append(jt, jump{pos: k, op: c.Op, arg: c.Arg})
			s.jumpTable[target] = jt
		}
	}

	if s.run(len(code)) {
		return s.flipLocation, nil
	}

	return 0, fmt.Errorf("didn't find a way to backtrack this")
}

func (s *state) run(pos int) bool {

	if pos == -1 {
		return true
	}
	var k int
	// see how far back we can go without jumps

loop:
	for k = pos - 1; k >= 0; k-- {
		c := s.code[k]
		switch c.Op {
		case "acc", "nop":
			continue
		default:
			if s.code[k].Arg == 1 {
				continue
			}
			break loop
		}
	}

	if k == -1 {
		return true
	}
	// option 1 - can we find a jump to the previous position?
	for _, j := range s.jumpTable[k+1] {
		if s.wasFlipped {
			return false
		}
		if s.run(j.pos) {
			return true
		}
	}
	// we can continue if this jmp is a nop (and we didn't already flip one)
	if s.wasFlipped {
		return false
	}
	s.wasFlipped = true
	s.flipLocation = k
	return s.run(k)
}