Advent of Code - Day 8: Handheld Halting

Tricky one, resembling more like a medium LC problem. Here it is: Day 8 - Advent of Code 2020

Especially the second part of the problem:

--- Part Two ---

After some careful analysis, you believe that exactly one instruction is corrupted.

Somewhere in the program, either a jmp is supposed to be a nop, or a nop is supposed to be a jmp. (No acc instructions were harmed in the corruption of this boot code.)

The program is supposed to terminate by attempting to execute an instruction immediately after the last instruction in the file. By changing exactly one jmp or nop, you can repair the boot code and make it terminate correctly.

For example, consider the same program from above:

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

If you change the first instruction from nop +0 to jmp +0, it would create a single-instruction infinite loop, never leaving that instruction. If you change almost any of the jmp instructions, the program will still eventually find another jmp instruction and loop forever.

However, if you change the second-to-last instruction (from jmp -4 to nop -4), the program terminates! The instructions are visited in this order:

nop +0  | 1
acc +1  | 2
jmp +4  | 3
acc +3  |
jmp -3  |
acc -99 |
acc +1  | 4
nop -4  | 5
acc +6  | 6

After the last instruction (acc +6), the program terminates by attempting to run the instruction below the last instruction in the file. With this change, after the program terminates, the accumulator contains the value 8 (acc +1, acc +1, acc +6).

Fix the program so that it terminates normally by changing exactly one jmp (to nop) or nop (to jmp). What is the value of the accumulator after the program terminates?

Your puzzle answer was .

I have a list of instructions and a simple recursive method to analyze it (part 1). For part 2, the idea is to have an extra parameter with the number of changes made. If the number of changes is one, you can't change it anymore, hence you're forced to keep going. If the number of changes is zero, you have one try for the nop or jump. The key is to retract after the recursive call and reset the number of changes, and the accumulator. Also force a quick return if the solution has been reached. Code is down below, cheers, ACC.

class Code
{
    public string instruction = "";
    public bool visited = false;

    public Code(string instruction)
    {
        this.instruction = instruction;
        visited = false;
    }
}

static void Main(string[] args)
{
    FileInfo fi = new FileInfo("input.txt");
    StreamReader sr = fi.OpenText();
    List code = new List();
    while (!sr.EndOfStream)
    {
        string str = sr.ReadLine().Trim();
        if (!String.IsNullOrEmpty(str))
        {
            Code c = new Code(str);
            code.Add(c);
        }
    }
    int acc = 0;
    int numberOfChanges = 0;
    ProcessInstruction(code, 0, ref acc, ref numberOfChanges);
    Console.WriteLine(acc);
    sr.Close();
}

public static bool ProcessInstruction(List code,
                                        int index,
                                        ref int acc,
                                        ref int numberOfChanges)
{
    if (index == code.Count && code[index - 1].visited) return true;
    if (index < 0 || index >= code.Count || code[index].visited) return false;

    code[index].visited = true;

    string[] parts = code[index].instruction.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
    int n = Int32.Parse(parts[1]);

    if (numberOfChanges >= 1) //Can't change anymore
    {
        if (code[index].instruction.StartsWith("nop")) return ProcessInstruction(code, index + 1, ref acc, ref numberOfChanges);
        if (code[index].instruction.StartsWith("jmp")) return ProcessInstruction(code, index + n, ref acc, ref numberOfChanges);
    }
    else
    {
        if (code[index].instruction.StartsWith("nop"))
        {
            //Keep
            if (ProcessInstruction(code, index + 1, ref acc, ref numberOfChanges)) return true;
            //Change
            numberOfChanges++;
            if (ProcessInstruction(code, index + n, ref acc, ref numberOfChanges)) return true;
            numberOfChanges--;
        }
        if (code[index].instruction.StartsWith("jmp"))
        {
            //Keep
            if (ProcessInstruction(code, index + n, ref acc, ref numberOfChanges)) return true;
            //Change
            numberOfChanges++;
            if (ProcessInstruction(code, index + 1, ref acc, ref numberOfChanges)) return true;
            numberOfChanges--;
        }
    }
    if (code[index].instruction.StartsWith("acc"))
    {
        acc += n;
        if (ProcessInstruction(code, index + 1, ref acc, ref numberOfChanges)) return true;
        acc -= n;
    }
    return false;
}