index.test.ts

import { IntCodeState, fromProgramString, compute, IntCodeTape, pushInput, popOutput, computeTillStop, computeTillOutput } from "./index";

const largeExample:string = '3,21,1008,21,8,20,1005,20,22,107,8,21,20,1006,20,31,1106,0,36,98,0,0,1002,21,125,20,4,20,1105,1,46,104,999,1105,1,46,1101,1000,1,20,4,20,1105,1,46,98,99'
const quine:string = '109,1,204,-1,1001,100,1,100,1008,100,16,101,1006,101,0,99';
const bigOutput:string = '104,1125899906842624,99';
const bigMult:string = '1102,34915192,34915192,7,4,7,99,0';
const ioHalt:string = '3,0,4,0,99'

describe('IntCode', ():void => {
  describe('fromInputString(input)', ():void => {
    it('takes input and returns an initial intCodeState', ():void => {
      let result:IntCodeState = fromProgramString(bigOutput);
      expect(result).toEqual({
        cursor: 0n,
        program:{
          '0': 104n,
          '1': 1125899906842624n,
          '2': 99n
        },
        relativeBase:0n,
        inputBuffer:[],
        outputBuffer:[],
        finished:false
      });
    });
    it('optionally takes an input buffer', ():void => {
      let result:IntCodeState = fromProgramString(bigOutput, [1n]);
      expect(result).toEqual({
        cursor: 0n,
        program:{
          '0': 104n,
          '1': 1125899906842624n,
          '2': 99n
        },
        relativeBase:0n,
        inputBuffer:[1n],
        outputBuffer:[],
        finished:false
      });

    });
  });
  describe('compute(state)', ():void => {
    it('returns no change if finished is true',():void => {
      const finished:IntCodeState = {
        ...fromProgramString(bigOutput),
        finished:true
      };
      const result:IntCodeState = compute(finished);
      expect(result).toEqual(finished);
    });
    describe('Add', ():void => {
      test('works in position mode', ():void => {
        const simpleAdd:IntCodeState = fromProgramString('1,5,6,7,99,37,48,0');
        const state:IntCodeState = compute(simpleAdd);
        const expected:IntCodeState = {
          ...simpleAdd,
          program: {
            ...simpleAdd.program,
            "7": 37n + 48n
          },
          cursor: 4n
        }
        expect(state).toEqual(expected);
      });
      it('works in immediate mode', ():void => {
        const immediateAdd:IntCodeState = fromProgramString('1101,5,6,7,99,37,48,0');
        const state:IntCodeState = compute(immediateAdd);
        const expected:IntCodeState = {
          ...immediateAdd,
          program: {
            ...immediateAdd.program,
            "7": 5n + 6n
          },
          cursor: 4n
        };
        expect(state).toEqual(expected)
      });
      it('works in relative mode', ():void => {
        const immediateAdd:IntCodeState = {
          ...fromProgramString('22201,3,4,5,99,37,48,0'),
          relativeBase: 2n
        }
        const state:IntCodeState = compute(immediateAdd);
        const expected:IntCodeState = {
          ...immediateAdd,
          program: {
            ...immediateAdd.program,
            "7": 37n + 48n
          },
          cursor: 4n
        };
        expect(state).toEqual(expected)

      });
    })
    describe('Multiply', ():void => {
      test('works in position mode', ():void => {
        const simpleAdd:IntCodeState = fromProgramString('2,5,6,7,99,37,48,0');
        const state:IntCodeState = compute(simpleAdd);
        const expected:IntCodeState = {
          ...simpleAdd,
          program: {
            ...simpleAdd.program,
            "7": 37n * 48n
          },
          cursor: 4n
        }
        expect(state).toEqual(expected);
      });
      it('works in immediate mode', ():void => {
        const immediateAdd:IntCodeState = fromProgramString('1102,5,6,7,99,37,48,0');
        const state:IntCodeState = compute(immediateAdd);
        const expected:IntCodeState = {
          ...immediateAdd,
          program: {
            ...immediateAdd.program,
            "7": 5n * 6n
          },
          cursor: 4n
        };
        expect(state).toEqual(expected)
      });
      it('works in relative mode', ():void => {
        const immediateAdd:IntCodeState = {
          ...fromProgramString('22202,3,4,5,99,37,48,0'),
          relativeBase: 2n
        }
        const state:IntCodeState = compute(immediateAdd);
        const expected:IntCodeState = {
          ...immediateAdd,
          program: {
            ...immediateAdd.program,
            "7": 37n * 48n
          },
          cursor: 4n
        };
        expect(state).toEqual(expected)

      });
    });
    describe('Read Input', ():void => {
      it('returns no change if input is empty and instruction is input', ():void => {
        const readNoInput:IntCodeState = fromProgramString('3,3,99,0', []);
        const result:IntCodeState = compute(readNoInput);
        expect(result).toEqual(readNoInput);
      });
      it('works in position mode', ():void => {
        const readInput:IntCodeState = fromProgramString('3,3,99,0', [29n, 31n]);
        const result:IntCodeState = compute(readInput);
        expect(result).toEqual({
          ...readInput, 
          cursor: 2n,
          inputBuffer: [31n],
          program: {
            ...readInput.program,
            "3":29n
          }
        });
      });
      it('works in relative mode', ():void => {
        const readInput:IntCodeState = {
          ...fromProgramString('203,5,99,0', [29n, 31n]),
          relativeBase: -2n
        }
        const result:IntCodeState = compute(readInput);
        expect(result).toEqual({
          ...readInput, 
          cursor: 2n,
          inputBuffer: [31n],
          program: {
            ...readInput.program,
            "3":29n
          }
        });
      });
    });
    describe('Write Output', ():void => {
      it('works in position mode', ():void => {
        const writeOutput:IntCodeState = fromProgramString('4,3,99,12');
        const result:IntCodeState = compute(writeOutput);
        expect(result).toEqual({
          ...writeOutput, 
          cursor: 2n,
          outputBuffer: [12n]
        });
      });
      it('works in immediate mode', ():void => {
        const writeOutput:IntCodeState = fromProgramString('104,3,99,12');
        const result:IntCodeState = compute(writeOutput);
        expect(result).toEqual({
          ...writeOutput, 
          cursor: 2n,
          outputBuffer: [3n]
        });
      });
      it('works in relative mode', ():void => {
        const writeOutput:IntCodeState = {
          ...fromProgramString('204,5,99,12'),
          relativeBase: -2n
        }
        const result:IntCodeState = compute(writeOutput);
        expect(result).toEqual({
          ...writeOutput, 
          cursor: 2n,
          outputBuffer: [12n]
        });
      });
    });
    describe('Jump If True', ():void => {
      it('works in position mode', ():void => {
        const jitOutput = fromProgramString('5,9,0,5,10,11,104,1,99,0,1,8');
        const result = compute(jitOutput);
        expect(result).toEqual({
          ...result,
          cursor: 3n
        });
        const secondResult = compute(result);
        expect(secondResult).toEqual({
          ...result,
          cursor: 8n
        });
      });
      it('works in immediate mode', ():void => {
        const jitOutput = fromProgramString('1105,0,0,1105,1,8,104,1,99,0,1,8');
        const result = compute(jitOutput);
        expect(result).toEqual({
          ...result,
          cursor: 3n
        });
        const secondResult = compute(result);
        expect(secondResult).toEqual({
          ...result,
          cursor: 8n
        });
      });
      it('works in relative mode', ():void => {
        const jitOutput = {
          ...fromProgramString('2205,4,-5,2205,5,6,104,1,99,0,1,8'),
          relativeBase: 5n
        }
        const result = compute(jitOutput);
        expect(result).toEqual({
          ...result,
          cursor: 3n
        });
        const secondResult = compute(result);
        expect(secondResult).toEqual({
          ...result,
          cursor: 8n
        });
      });
    });
    describe('Jump If False', ():void => {
      it('works in position mode', ():void => {
        const jitOutput = fromProgramString('6,10,0,6,9,11,104,1,99,0,1,8');
        const result = compute(jitOutput);
        expect(result).toEqual({
          ...result,
          cursor: 3n
        });
        const secondResult = compute(result);
        expect(secondResult).toEqual({
          ...result,
          cursor: 8n
        });
      });
      it('works in immediate mode', ():void => {
        const jitOutput = fromProgramString('1106,1,0,1106,0,8,104,1,99,0,1,8');
        const result = compute(jitOutput);
        expect(result).toEqual({
          ...result,
          cursor: 3n
        });
        const secondResult = compute(result);
        expect(secondResult).toEqual({
          ...result,
          cursor: 8n
        });
      });
      it('works in relative mode', ():void => {
        const jitOutput = {
          ...fromProgramString('2206,15,5,2206,14,16,104,1,99,0,1,8'),
          relativeBase: -5n
        }
        const result = compute(jitOutput);
        expect(result).toEqual({
          ...result,
          cursor: 3n
        });
        const secondResult = compute(result);
        expect(secondResult).toEqual({
          ...result,
          cursor: 8n
        });
      });
    });
    describe('Less Than', ():void => {
      it('works in position mode', ():void => {
        const ltProgram = fromProgramString('7,9,10,11,7,12,13,14,99,0,1,6,1,0,7');
        const result1 = compute(ltProgram);
        expect(result1).toEqual({
          ...ltProgram,
          cursor: 4n,
          program: {
            ...ltProgram.program,
            "11": 1n
          }
        });
        const result2 = compute(result1);
        expect(result2).toEqual({
          ...result1,
          cursor:8n,
          program: {
            ...result1.program,
            "14": 0n
          }
        });
      });
      it('works in immediate mode', ():void => {
        const ltProgram = fromProgramString('1107,0,1,11,1107,1,0,14,99,0,1,6,1,0,7');
        const result1 = compute(ltProgram);
        expect(result1).toEqual({
          ...ltProgram,
          cursor: 4n,
          program: {
            ...ltProgram.program,
            "11": 1n
          }
        });
        const result2 = compute(result1);
        expect(result2).toEqual({
          ...result1,
          cursor:8n,
          program: {
            ...result1.program,
            "14": 0n
          }
        });
      });
      it('works in position mode', ():void => {
        const ltProgram = {
          ...fromProgramString('22207,10,11,12,22207,13,14,15,99,0,1,6,1,0,7'),
          relativeBase: -1n
        }
        const result1 = compute(ltProgram);
        expect(result1).toEqual({
          ...ltProgram,
          cursor: 4n,
          program: {
            ...ltProgram.program,
            "11": 1n
          }
        });
        const result2 = compute(result1);
        expect(result2).toEqual({
          ...result1,
          cursor:8n,
          program: {
            ...result1.program,
            "14": 0n
          }
        });
      });
    });
    describe('Less Than', ():void => {
      it('works in position mode', ():void => {
        const ltProgram = fromProgramString('8,9,10,11,8,12,13,14,99,1,1,6,1,0,7');
        const result1 = compute(ltProgram);
        expect(result1).toEqual({
          ...ltProgram,
          cursor: 4n,
          program: {
            ...ltProgram.program,
            "11": 1n
          }
        });
        const result2 = compute(result1);
        expect(result2).toEqual({
          ...result1,
          cursor:8n,
          program: {
            ...result1.program,
            "14": 0n
          }
        });
      });
      it('works in immediate mode', ():void => {
        const ltProgram = fromProgramString('1108,1,1,11,1108,1,0,14,99,0,1,6,1,0,7');
        const result1 = compute(ltProgram);
        expect(result1).toEqual({
          ...ltProgram,
          cursor: 4n,
          program: {
            ...ltProgram.program,
            "11": 1n
          }
        });
        const result2 = compute(result1);
        expect(result2).toEqual({
          ...result1,
          cursor:8n,
          program: {
            ...result1.program,
            "14": 0n
          }
        });
      });
      it('works in position mode', ():void => {
        const ltProgram = {
          ...fromProgramString('22208,10,11,12,22208,13,14,15,99,1,1,6,1,0,7'),
          relativeBase: -1n
        }
        const result1 = compute(ltProgram);
        expect(result1).toEqual({
          ...ltProgram,
          cursor: 4n,
          program: {
            ...ltProgram.program,
            "11": 1n
          }
        });
        const result2 = compute(result1);
        expect(result2).toEqual({
          ...result1,
          cursor:8n,
          program: {
            ...result1.program,
            "14": 0n
          }
        });
      });
    });
    describe('Adjust Relative Base', ():void => {
      it('works in position mode', ():void => {
        const shiftedProgram:IntCodeState = fromProgramString('9,3,99,7,6');
        const result = compute(shiftedProgram);
        expect(result).toEqual({
          ...shiftedProgram,
          relativeBase: 7n,
          cursor: 2n
        });
      });
      it('works in immediate mode', ():void => {
        const shiftedProgram:IntCodeState = fromProgramString('109,3,99,7,6');
        const result = compute(shiftedProgram);
        expect(result).toEqual({
          ...shiftedProgram,
          relativeBase: 3n,
          cursor: 2n
        });
      });
      it('works in immediate mode', ():void => {
        const shiftedProgram:IntCodeState = {
          ...fromProgramString('209,4,99,7,6'),
          relativeBase: -1n
        }
        const result = compute(shiftedProgram);
        expect(result).toEqual({
          ...shiftedProgram,
          relativeBase: 6n,
          cursor: 2n
        });
      });
    });
    describe('Finish', ():void => {
      it('finishes the program', () => {
        const finishedProgram:IntCodeState = fromProgramString('99');
        const result = compute(finishedProgram);
        expect(result).toEqual({
          ...finishedProgram,
          finished: true
        });
      });
    });
  });
  describe('pushInput(state, input)', ():void => {
    it('adds an input', ():void => {
      const simplestProgram:IntCodeState = fromProgramString('99', [7n]);
      const result = pushInput(simplestProgram, 8n);
      expect(result).toEqual({
        ...simplestProgram,
        inputBuffer: [...simplestProgram.inputBuffer, 8n]
      });
    });
  });
  describe('popOutput(state)', ():void => {
    it('shifts the output and returns it', ():void => {
      const simplestProgram:IntCodeState = fromProgramString('104,7,104,5,99');
      const withOutput = compute(compute(simplestProgram));
      const [output, newProgram] = popOutput(withOutput);
      expect(output).toBe(7n);
      expect(newProgram).toEqual({
        ...withOutput,
        outputBuffer: [5n]
      });
    });
  });
  describe('computeTillStop', ():void => {
    it('runs until a program finishes', ():void => {
      const getToEnd = fromProgramString('3,5,4,5,99,0', [9n]);
      const done = computeTillStop(getToEnd);
      expect(done).toEqual({
        ...getToEnd,
        program: {
          ...getToEnd.program,
          '5': 9n
        },
        inputBuffer: [],
        outputBuffer: [9n],
        finished: true,
        cursor: 4n
      });
    });
    it('pauses on read if there is no input', ():void => {
      const getToEnd = fromProgramString('3,5,4,5,99,0');
      const done = computeTillStop(getToEnd);
      expect(done).toEqual(getToEnd);
    });
  });
  describe('computeTillOutput(program)', ():void => {
    it('computes a program until there is some output', ():void => {
      const addOnceThenOutput = fromProgramString('1101,2,3,7,4,7,99,0');
      const [firstOutput, resultProgram] = computeTillOutput(addOnceThenOutput);
      expect(firstOutput).toEqual(5n);
      expect(resultProgram).toEqual({
        ...addOnceThenOutput,
        cursor:6n,
        program: {
          ...addOnceThenOutput.program,
          '7': 5n
        }
      });
    });
    it('returns a program when it finishes',():void => {
      const addOnceThenFinish = fromProgramString('1101,2,3,5,99,0');
      const [firstOutput, resultProgram] = computeTillOutput(addOnceThenFinish);
      expect(firstOutput).toBeUndefined();
      expect(resultProgram).toEqual({
        ...addOnceThenFinish,
        finished:true,
        cursor:4n,
        program:{
          ...addOnceThenFinish.program,
          "5":5n
        }
      });
    })
  });
});

index.ts

import isEqual from 'lodash.isequal';

export type IntCodeTape = {[addr:string]:bigint}

export type IntCodeState = {
  cursor:bigint;
  program:IntCodeTape;
  relativeBase:bigint;
  inputBuffer:bigint[];
  outputBuffer:bigint[];
  finished:boolean;
}

const modesLength:number = 5;
export function fromProgramString(programString:string, inputBuffer:bigint[] = []):IntCodeState{
  const program:IntCodeTape = {};
  programString.split(',').forEach((line:string, i:number):void => {
    program[i] = BigInt(line);
  });
  return {
    cursor: 0n,
    program,
    relativeBase:0n,
    inputBuffer,
    outputBuffer:[],
    finished:false
  };
}

function getAddr(program: IntCodeTape, cursor:bigint, mode:string, relativeBase:bigint = 0n):string {
  const val: bigint = program[cursor.toString()]

  if(mode === '2') return (val + relativeBase).toString()
  return val.toString();
}

function getVal(program:IntCodeTape, cursor:bigint, mode: string, relativeBase:bigint): bigint {
  const val: bigint = program[cursor.toString()] || 0n
  if(mode === '1') return val;
  return program[mode === '2' ? (val + relativeBase).toString() : val.toString()] || 0n;
}

function add(program:IntCodeTape, cursor: bigint, mode:string, relativeBase:bigint):Partial<IntCodeState>{
  const a = getVal(program, cursor + 1n, mode[modesLength - 1], relativeBase);
  const b = getVal(program, cursor + 2n, mode[modesLength - 2], relativeBase);
  const c = getAddr(program, cursor + 3n, mode[modesLength - 3], relativeBase);

  return {
    cursor: cursor + 4n,
    program: {
      ...program,
      [c]: a + b
    }
  };
}

function mult(program:IntCodeTape, cursor: bigint, mode:string, relativeBase:bigint):Partial<IntCodeState>{
  const a = getVal(program, cursor + 1n, mode[modesLength - 1], relativeBase);
  const b = getVal(program, cursor + 2n, mode[modesLength - 2], relativeBase);
  const c = getAddr(program, cursor + 3n, mode[modesLength - 3], relativeBase);
  
  return {
    cursor: cursor + 4n,
    program: {
      ...program,
      [c]: a * b
    }
  };
}
function read(program:IntCodeTape, cursor:bigint, mode:string, bufferIn:bigint[], relativeBase:bigint):Partial<IntCodeState>{
  if(bufferIn.length === 0){
    return {};
  }
  const a = getAddr(program, cursor + 1n, mode[modesLength - 1], relativeBase)
  const [val, ...inputBuffer] = bufferIn;
  return {
    cursor: cursor + 2n,
    program: {
      ...program,
      [a]: val
    },
    inputBuffer
  }
}

function write(program:IntCodeTape, cursor:bigint, mode:string, outputBuffer:bigint[], relativeBase):Partial<IntCodeState>{
  const a = getVal(program, cursor + 1n, mode[modesLength - 1], relativeBase)
  return {
    cursor: cursor + 2n,
    outputBuffer: [...outputBuffer, a]
  };
}

function jit(program:IntCodeTape, cursor:bigint, mode:string, relativeBase:bigint):Partial<IntCodeState>{
  const a = getVal(program, cursor + 1n, mode[modesLength - 1], relativeBase);
  if(a === 0n) return { cursor: cursor + 3n};
  return { 
    cursor: getVal(program, cursor + 2n, mode[modesLength - 2], relativeBase)
  }
}

function jif(program:IntCodeTape, cursor:bigint, mode:string, relativeBase:bigint):Partial<IntCodeState>{
  const a = getVal(program, cursor + 1n, mode[modesLength - 1], relativeBase);
  if(a !== 0n) return { cursor: cursor + 3n};
  return { 
    cursor: getVal(program, cursor + 2n, mode[modesLength - 2], relativeBase)
  }
}

function lt(program:IntCodeTape,cursor:bigint,mode:string, relativeBase:bigint):Partial<IntCodeState>{
  const a = getVal(program, cursor + 1n, mode[modesLength - 1], relativeBase);
  const b = getVal(program, cursor + 2n, mode[modesLength - 2], relativeBase);
  const c = getAddr(program, cursor + 3n, mode[modesLength - 3], relativeBase);
  return {
    cursor: cursor + 4n,
    program: {
      ...program,
      [c]: a < b ? 1n : 0n
    }
  }
}

function eq(program:IntCodeTape,cursor:bigint,mode:string, relativeBase:bigint):Partial<IntCodeState>{
  const a = getVal(program, cursor + 1n, mode[modesLength - 1], relativeBase);
  const b = getVal(program, cursor + 2n, mode[modesLength - 2], relativeBase);
  const c = getAddr(program, cursor + 3n, mode[modesLength - 3], relativeBase);
  return {
    cursor: cursor + 4n,
    program: {
      ...program,
      [c]: a === b ? 1n : 0n
    }
  }
}

function arb(program:IntCodeTape,cursor:bigint,mode:string, relativeBase:bigint):Partial<IntCodeState>{
  const a:bigint = getVal(program, cursor + 1n, mode[modesLength - 1], relativeBase);

  return {
    relativeBase: relativeBase + a,
    cursor: cursor + 2n
  };
}

export function compute(input:IntCodeState):IntCodeState{
  if(input.finished) return input;  
  const {cursor, program, relativeBase, inputBuffer, outputBuffer} = input;
  const underCursor:bigint = program[cursor.toString()];
  const command = underCursor % 100n;
  const mode = (underCursor / 100n).toString().padStart(modesLength, '0');
  const changes:Partial<IntCodeState> = command === 1n ? add(program, cursor, mode, relativeBase)
    : command === 2n ? mult(program, cursor, mode, relativeBase)
    : command === 3n ? read(program, cursor, mode, inputBuffer, relativeBase)
    : command === 4n ? write(program, cursor, mode, outputBuffer, relativeBase)
    : command === 5n ? jit(program, cursor, mode, relativeBase)
    : command === 6n ? jif(program, cursor, mode, relativeBase)
    : command === 7n ? lt(program, cursor, mode, relativeBase)
    : command === 8n ? eq(program, cursor, mode, relativeBase)
    : command === 9n ? arb(program, cursor, mode, relativeBase)
    : command === 99n ? { finished: true}
    : {};

  return {
    ...input,
    ...changes
  };
};

export function pushInput(state:IntCodeState, input: bigint):IntCodeState{
  return {
    ...state,
    inputBuffer: [...state.inputBuffer, input]
  }
}

export function popOutput({outputBuffer: [output, ...outputBuffer], ...rest}:IntCodeState):[bigint|undefined, IntCodeState]{
  return [output, {...rest, outputBuffer }];
}

export function computeTillStop(program:IntCodeState):IntCodeState{
  let current = program;
  while(true){
    const next = compute(current);
    if(isEqual(current, next)){
      return current;
    }
    current = next;
  }
}

export function computeTillOutput(program:IntCodeState): [bigint|undefined, IntCodeState]{
  let current = program;
  while(true){
    if(current.outputBuffer.length){
      return popOutput(current);
    }
    const next = compute(current);
    if(next.finished || isEqual(next, current)){
      return popOutput(next);
    }
    current = next;
  }
}