day08.test.ts

/* === TYPES === */
type Command = {
  name: "acc" | "jmp" | "nop";
  arg: number;
};
/* === PREPARE INPUT === */
const re = /^(acc|jmp|nop) \+?(-?\d+)/;
const parseLine = (line: string): Command => {
  const [, name, arg] = line.match(re) ?? [];

  return {
    name,
    arg: Number.parseInt(arg, 10),
  } as Command;
};
export const prepareInput = ([input]: TemplateStringsArray) =>
  input.split("\n").map(parseLine);

/* === UTILS === */

/* === IMPLEMENTATION === */

type RunUntilLoop = (
  commands: Command[],
  value: number,
  lineNo?: number,
  run?: Set<number>
) => number;
const runUntilLoop: RunUntilLoop = (
  commands,
  value,
  lineNo = 0,
  run = new Set()
) => {
  // Loops
  if (run.has(lineNo)) return value;
  run.add(lineNo);

  const { name, arg } = commands[lineNo];
  switch (name) {
    case "nop":
      return runUntilLoop(commands, value, lineNo + 1, run);
    case "jmp":
      return runUntilLoop(commands, value, lineNo + arg, run);
    case "acc":
      return runUntilLoop(commands, value + arg, lineNo + 1, run);
  }
};

type RunAndFix = (
  commands: Command[],
  value: number,
  lineNo?: number,
  run?: Set<number>,
  fixLine?: number
) => number;
const runAndFix: RunAndFix = (
  commands,
  value,
  lineNo = 0,
  run = new Set(),
  fixLine
) => {
  // Program ends
  if (lineNo >= commands.length) return value;

  // Loops
  if (run.has(lineNo)) return 0;
  run.add(lineNo);

  const { name, arg } = commands[lineNo];

  // No previous branching
  if (!fixLine) {
    if (name === "nop") {
      return (
        runAndFix(commands, value, lineNo + 1, run, fixLine) +
        runAndFix(commands, value, lineNo + arg, new Set(run), lineNo)
      );
    }

    if (name === "jmp") {
      return (
        runAndFix(commands, value, lineNo + arg, run, fixLine) +
        runAndFix(commands, value, lineNo + 1, new Set(run), lineNo)
      );
    }
  }

  switch (name) {
    case "nop":
      return runAndFix(commands, value, lineNo + 1, run, fixLine);
    case "jmp":
      return runAndFix(commands, value, lineNo + arg, run, fixLine);
    case "acc":
      return runAndFix(commands, value + arg, lineNo + 1, run, fixLine);
  }
};

/* === TESTS === */

test("Day 8a - test", () => {
  const result = runUntilLoop(testInput, 0);

  expect(result).toBe(5);
});

test("Day 8a - prod", () => {
  const result = runUntilLoop(prodInput, 0);

  expect(result).toBe(1654);
});

test("Day 8b - test", () => {
  const result = runAndFix(testInput, 0);

  expect(result).toBe(8);
});

test("Day 8b - prod", () => {
  const result = runAndFix(prodInput, 0);

  expect(result).toBe(833);
});

/* === INPUTS === */

const testInput = prepareInput`nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6`;

const prodInput = prepareInput`nop +346
acc +44
acc +15
jmp +473
acc +29
acc -13
jmp +525
acc +22
acc +13
nop +265
jmp +397
jmp +39
acc +39
nop -1
acc +36
acc +25
jmp +153
nop +374
jmp +27
jmp +282
jmp +1
jmp +1
jmp +15
acc +33
acc -3
jmp +533
acc +25
acc -14
acc -16
jmp +245
nop +567
acc +7
jmp +147
acc +26
acc +40
acc -9
jmp +295
acc +14
nop +388
acc -1
jmp -21
nop +524
nop +166
nop +515
jmp +18
jmp +214
acc +42
nop -35
acc +7
jmp +492
acc +14
acc +48
jmp +326
acc +48
acc -18
acc -5
jmp +343
jmp +81
acc +18
acc +16
acc +21
jmp +355
acc +48
nop +358
acc +49
acc -2
jmp +89
acc +4
jmp +171
acc +6
jmp +299
acc -8
jmp +150
acc +41
acc -9
acc +48
jmp +73
jmp +523
nop +471
jmp +493
acc -16
nop +440
acc +2
acc +33
jmp +117
acc +3
acc +34
jmp +310
acc +8
jmp +197
acc +26
acc +47
jmp +194
nop +115
jmp +259
nop +456
jmp +420
nop +398
jmp +235
acc +44
acc +47
jmp +218
jmp +1
jmp +275
acc +12
jmp +434
acc +50
acc +10
nop +361
jmp +367
acc -16
acc +44
jmp +96
acc +9
acc +38
acc -15
nop -31
jmp -55
nop +421
acc +50
acc +12
jmp -64
acc +33
acc +25
jmp +382
acc +7
jmp -22
jmp +95
acc +44
acc +32
acc +23
jmp +1
jmp +456
acc +49
jmp +15
jmp +312
acc +6
jmp +216
acc +7
jmp +458
jmp +465
nop +372
acc +35
acc +32
acc +13
jmp -35
acc +50
nop +32
jmp +143
jmp +327
acc +0
nop -82
nop -62
acc +41
jmp -81
acc -10
nop -106
jmp +82
acc +1
acc +11
jmp +124
acc +25
acc +17
jmp -73
nop +8
acc +29
acc +33
acc +10
jmp +123
jmp +236
acc +41
jmp +370
acc +17
acc -13
acc +35
jmp -47
nop +287
acc +22
jmp +38
jmp +1
nop -52
nop -9
acc +22
jmp +253
acc +12
acc -18
acc +21
nop -69
jmp +28
acc +16
jmp +392
jmp +325
jmp -74
acc +34
acc +47
acc +41
jmp +201
nop +361
acc +50
jmp +30
jmp -127
nop -171
jmp +349
acc +11
nop +156
acc +1
acc -18
jmp +393
acc -8
jmp +1
acc -17
nop +188
jmp +134
acc -9
acc -14
jmp +206
jmp -209
jmp +1
acc +49
nop +112
acc -4
jmp -20
acc +41
jmp -145
acc +8
jmp +276
acc +48
jmp -5
jmp -143
acc +0
jmp -161
jmp +238
acc +8
jmp -134
acc +34
acc +10
jmp +1
nop +109
jmp -100
acc +41
acc -4
jmp -12
acc +42
acc +46
acc -7
acc +28
jmp +85
jmp +216
jmp +364
acc +0
acc -6
nop +331
acc +33
jmp +163
acc +37
acc +20
acc +33
acc +45
jmp -159
acc +34
acc +10
acc +48
acc +10
jmp +358
acc -9
jmp +276
acc +27
acc +45
nop +129
acc +32
jmp +243
acc +0
acc -5
jmp -24
acc +44
nop +307
acc -18
acc +13
jmp +37
acc +5
nop -125
nop -126
acc -18
jmp +186
jmp -87
jmp -262
nop -20
jmp -108
acc +26
acc +20
jmp +193
nop +185
jmp +129
acc +26
jmp +122
acc -8
nop +143
nop +166
jmp -236
acc +33
jmp -139
acc +38
jmp +1
acc +21
acc +31
jmp -79
acc -13
jmp -78
acc +29
jmp +160
acc +48
acc -8
acc +28
acc +15
jmp -284
jmp +25
acc +24
jmp +1
jmp -92
acc +22
jmp +169
acc -15
acc +16
acc +4
jmp -85
acc -18
acc -19
acc -2
jmp -278
acc +48
jmp -195
jmp -40
jmp -110
acc +47
jmp -26
acc +26
nop -187
acc +40
acc +42
jmp +167
acc +50
acc +36
acc -14
jmp -313
nop -203
jmp +227
acc -15
acc +22
jmp -23
acc +6
acc +30
acc +12
jmp +69
nop -212
nop -105
acc +12
jmp -155
nop +69
acc -16
jmp -68
acc -18
acc +35
acc +34
acc +6
jmp -80
acc +7
acc +19
acc -8
jmp -94
acc +12
nop -148
acc +33
nop -41
jmp -107
acc +25
acc +9
nop +107
jmp -44
jmp +1
jmp -254
acc +10
acc +0
acc +37
acc +33
jmp +137
nop +136
jmp -225
acc -4
acc -17
acc +39
jmp -286
jmp +150
nop -380
acc +34
acc +16
nop +146
jmp +105
jmp +119
jmp -190
acc +0
nop +205
nop -302
jmp -17
acc -4
jmp -7
jmp -14
jmp -394
acc +34
acc -1
acc +37
acc -17
jmp -312
nop -180
nop -139
acc +21
jmp -378
acc +24
acc +38
jmp +129
acc +26
jmp +19
acc +31
jmp -190
acc +29
acc -5
jmp +14
nop +186
acc +12
acc +9
acc -16
jmp +9
acc +2
nop -382
nop -284
nop -377
jmp -169
jmp +129
acc +49
jmp -297
acc +48
acc +18
acc +8
jmp +170
acc +12
acc -4
acc +28
jmp -20
acc -11
jmp -363
jmp +1
acc +9
acc +31
jmp +31
acc +36
acc +42
acc +2
nop -131
jmp -322
acc +35
acc +44
acc +11
acc +14
jmp -213
acc -16
acc -15
acc -5
jmp -277
acc -17
jmp -252
acc -19
acc +31
acc -16
acc -5
jmp +48
jmp +1
jmp -97
acc +5
jmp -382
acc +26
acc +41
acc +31
acc -2
jmp -392
acc +41
jmp -124
acc +45
acc +24
acc +10
jmp -339
acc +29
acc -10
acc -10
acc +3
jmp -456
jmp -25
acc +37
acc +39
acc -11
acc -1
jmp +106
jmp -328
jmp -489
nop -111
nop -458
acc +31
jmp -100
acc -18
jmp -258
acc -17
nop -46
acc +43
acc +45
jmp -127
jmp +34
acc +33
jmp -200
nop -90
acc +20
jmp -271
acc +41
jmp -189
acc -16
nop -321
acc +25
acc -12
jmp -62
acc -1
jmp +1
acc +35
acc +39
jmp -184
jmp -236
nop -331
acc +12
jmp +78
acc +15
jmp -30
acc -11
jmp -117
jmp -8
jmp +9
acc +2
jmp -497
acc +10
acc +0
acc -6
jmp -155
jmp -148
jmp -95
jmp -96
jmp -249
nop -277
nop -411
acc -13
acc -2
jmp -383
acc -13
jmp -110
acc +13
acc +16
acc +5
acc -2
jmp -67
acc +37
jmp -491
acc +35
acc +34
acc +32
acc -2
jmp -546
acc -19
jmp -322
acc +48
acc +18
acc +35
acc +8
jmp -448
acc +41
acc -15
acc +34
acc +46
jmp -50
acc +12
nop -184
acc +14
acc +38
jmp -370
jmp +10
acc -14
acc -16
nop -259
nop -300
jmp -400
acc +38
acc +29
acc +27
jmp -175
jmp -456
acc +30
jmp -308
jmp -538
jmp +1
acc -16
nop -127
jmp -407
acc +5
jmp -57
acc +21
acc +3
acc +42
acc +43
jmp -521
acc -9
acc +20
nop -217
jmp -15
acc +37
acc -12
acc -18
jmp +1
jmp -465
acc +37
nop -577
acc +8
acc +43
jmp +1`;