Skip to content

Latest commit

 

History

History
40 lines (32 loc) · 2.15 KB

8.md

File metadata and controls

40 lines (32 loc) · 2.15 KB
Raw

8a

This seems akin to some assembly instructions to me.

nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6

Thoughts

This program states to be an infinite loop and we should return before the program is ran a second time. Ie. Every action can only be done once. While I've never written anythin of the sorts, I see a couple of approaches. All of them start with parsing the list of instructions to some (Action Instruction) type.

  • We could find a way to sort the instructions so they become sequential, then use a stack or just fold them (would immediatly remove our need for the infinte state).
  • We could just recursively go through the list (map with an index) keeping an index of the next instruction to go to. Solving infinity by:
    • Keeping a list of instructions, it seems we can just keep the first one given the example
    • Giving the function a new list, updating that current action to (Done) and maching on that.

After some thinking I think that recursion should work;

  • Parse the list of instructions to a Map Index (Action, Instruction)
  • Recursively go through the map, updating the map itself with a Done action when we're done. When we hit one of those, we've made it round.

The fist one was found quite quickly, and I think with a nice algorithm, running the instructions, ticking them off as it went along

8b

For this I could make use of the index running out of bounds. I'm using a map, if an item doesn't exist in the map, and it's within 0 - length of map + 1, we're not trying to execute a superweird instruction, but just going to the i + 1, meaning we've ran out of instructions and as such, successfully ran the program. For this, I just recursively go through all possible applications, swapping the jmp to a nop at a certain index. If I get a return of Loop, we recurse, if not, we've parsed the application.

This worked quite nicely.

Concluding

Writing parsers feels easier-and-easier. Supernice. Today, I took the time to write out an approach and as such created a mental model of the problem. I just dove in yesterday. Yesterday went a lot worse than today, so I need to keep on writing out the approach before code.