Created
December 9, 2020 00:41
-
-
Save spellgen/eaef9cd5eb7cb4ed82a783cb59c1cf62 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment