Challenge2024>ProblemDay 17>Input

type InputData = {
  a: number,
  b: number,
  c: number,
  instructions: Array<number>,
};

enum OpCode {
  ADV = 0b000,
  BXL = 0b001,
  BST = 0b010,
  JNZ = 0b011,
  BXC = 0b100,
  OUT = 0b101,
  BDV = 0b110,
  CDV = 0b111,
};

enum Operand {
  Operand0 = 0b000,
  Operand1 = 0b001,
  Operand2 = 0b010,
  Operand3 = 0b011,
  Operand4 = 0b100,
  Operand5 = 0b101,
  Operand6 = 0b110,
  Operand7 = 0b111,
};

type State = {
  a: number,
  b: number,
  c: number,
  pointer: number,
  output: Array<number>,
};

const solution: Fn = async ({ a, b, c, instructions }) => {
  const promise = new Promise<string>((resolve) => {
    setTimeout(() => {
      const state: State = {
        a, b, c,
        pointer: 0,
        output: [],
      };

      run(instructions, state);
      const output = state.output.join(',');
      resolve(output);
    });
  });

  return promise;
};

const run: RunFn = (instructions, state) => {
  // instructions are always in pairs of opcode and operand
  // opcode is always the first value in the instruction
  // operand is always the next value after the opcode
  const opCodeOffset = 2;
  const operandOffset = 1;

  while (state.pointer >= 0 && state.pointer < instructions.length) {
    if (state.pointer + operandOffset >= instructions.length) { break; }

    const opcode = instructions[state.pointer] as OpCode;
    const operand = instructions[state.pointer + operandOffset] as Operand;

    switch (opcode) {
      case OpCode.ADV:
        runADV(operand, state);
        break;
      case OpCode.BXL:
        runBXL(operand, state);
        break;
      case OpCode.BST:
        runBST(operand, state);
        break;
      case OpCode.JNZ:
        // JNZ does not increment the pointer, it jumps to a new location
        // JNZ jumps only if register A is not zero
        if (state.a === 0) { break; }

        runJNZ(operand, state);
        continue;
      case OpCode.BXC:
        runBXC(operand, state);
        break;
      case OpCode.OUT:
        runOUT(operand, state);
        break;
      case OpCode.BDV:
        runBDV(operand, state);
        break;
      case OpCode.CDV:
        runCDV(operand, state);
        break;
    }

    state.pointer += opCodeOffset;
  }
};

const runADV: RunInstructionFn = (operand, state) => {
  const power = getComboOperandValue(operand, state);
  if (power === null) { return; }

  const numerator = state.a;
  const denominator = Math.pow(2, power);
  const result = Math.floor(numerator / denominator);
  state.a = result;
};

const runBXL: RunInstructionFn = (operand, state) => {
  const result = BigInt(state.b) ^ BigInt(operand);
  state.b = Number(result);
};

const runBST: RunInstructionFn = (operand, state) => {
  const value = getComboOperandValue(operand, state);
  if (value === null) { return; }

  const result = value % 8;
  state.b = result;
};

const runJNZ: RunInstructionFn = (operand, state) => {
  const newPointer = Number(operand);
  state.pointer = newPointer;
};

const runBXC: RunInstructionFn = (_, state) => {
  const result = BigInt(state.b) ^ BigInt(state.c);
  state.b = Number(result);
};

const runOUT: RunInstructionFn = (operand, state) => {
  const value = getComboOperandValue(operand, state);
  if (value === null) { return; }

  const output = value % 8;
  state.output.push(output);
};

const runBDV: RunInstructionFn = (operand, state) => {
  const power = getComboOperandValue(operand, state);
  if (power === null) { return; }

  const numerator = state.a;
  const denominator = Math.pow(2, power);
  const result = Math.floor(numerator / denominator);
  state.b = result;
};

const runCDV: RunInstructionFn = (operand, state) => {
  const power = getComboOperandValue(operand, state);
  if (power === null) { return; }

  const numerator = state.a;
  const denominator = Math.pow(2, power);
  const result = Math.floor(numerator / denominator);
  state.c = result;
};

const getComboOperandValue: GetOperandValueFn = (operand, state) => {
  switch (operand) {
    case Operand.Operand0:
    case Operand.Operand1:
    case Operand.Operand2:
    case Operand.Operand3:
      return operand;
    case Operand.Operand4: return state.a;
    case Operand.Operand5: return state.b;
    case Operand.Operand6: return state.c;
    default: return null;
  }
}

const solution: Fn = async ({ a, b, c, instructions }) => {
  const promise = new Promise<number>((resolve) => {
    setTimeout(() => {
      const output = findSelfReplicatingValue({ a, b, c, instructions });
      resolve(output ?? 0);
    });
  });

  return promise;
};

// initial brute force of register A values
//   suggests that the values at the start of the output
//   don't change as much as the ones at the end
// this suggests that the higher bits in the register A value
//   correspond to the earlier values in the output
//   and the lower bits to the later ones
// further analysis also reveals that each output corresponds to 3 bits of register A
// so the solution must be to find the corresponding bits to match a certain output
//   and combining them to form the final value for register A
const findSelfReplicatingValue: FindFn = ({ b, c, instructions }) => {
  const input: InputData = {
    a: 0, b, c, instructions,
  };

  const value = findMatchingRegisterAValue(input, instructions.length - 1);
  return value;
};


// a pattern soon became apparent and an answer was found (but higher than expected)
// also, further pattern analysis on the bits has some unexplained behaviour
//   but switching to octal instead of binary made the behaviour consistent
//   (octal because the max value of the output is 7)
// so the final solution is to find the octal that corresponds to the last instruction
//   then finding the next octal that when combined with the previous octal
//   will result in an output that matches the last 2 values of the instructions
//   then repeating this process until the output fully matches the instructions
// there are cases where the output cannot be matched mid way through
//   so there needs to be a way for the solution to back track to the previous octal
//   and start looking for another possible value starting from that octal
const findMatchingRegisterAValue: FindMatch = (
  { a, b, c, instructions },
  targetInstructionIndex
) => {
  if (targetInstructionIndex < 0 || targetInstructionIndex > instructions.length) {
    return null;
  }

  const maxValue = 7; // max value in the output is 7
  const target = instructions[targetInstructionIndex];
  const outputIndexOffset = instructions.length - targetInstructionIndex;
  const baseValue = a.toString(8);

  for (let i = 0n; i <= maxValue; i++) {
    const value = BigInt(`0o${baseValue}${i}`);
    const input: InputData = {
      a: Number(value), b, c, instructions,
    };
    const result = getFinalState(input);
    const outputIndex = result.output.length - outputIndexOffset;
    const actual = result.output[outputIndex];

    if (actual === target) {
      // this function is recursively called when a match is found
      //   which ensures that previous instructions always match the corresponding output
      // so when a match is found for the current instruction
      //   and the output is as long as the instructions,
      //   then the output matches the instructions exactly and the answer is found
      if (result.output.length === instructions.length) {
        return input.a;
      }

      // move to the previous instruction
      //   and try to find a value for register A that results in an output
      //   that matches the corresponding values in the instructions
      const next = findMatchingRegisterAValue(input, targetInstructionIndex - 1);
      if (next !== null) { return next; }

      // if no match is found, continue searching for a different value
    }
  }

  return null;
};

const getFinalState: GetStateFn = ({ a, b, c, instructions }) => {
  const state: State = {
    a,
    b,
    c,
    pointer: 0,
    output: [],
  };

  // check part 1 for run definition
  run(instructions, state);
  return state;
};