2019_Day_22.ts

import loadInput from "@/utils";

const PATH = "2019/Days/22/Input.txt"; // Relative to project root
const raw = loadInput(PATH);

// -----------------------------------------
// --- Day 22: Slam Shuffle ---
// -----------------------------------------

export function Day22(raw: string, deckSize: number = 10007, card: number): number {
  const input = raw.trim().split("\n").map(line => line.split(" "));
  let pos = card;

  for (let line of input) {
    const operation = getOperation(line);
    const value = operation === "new stack" ? 0 : Number(line.at(-1));

    if (value === undefined) {
      throw new Error("value is undefined")
    } else if (operation === "cut") {
      pos = ((pos - value) % deckSize + deckSize) % deckSize;
    } else if (operation === "increment") {
      pos = (pos * value) % deckSize;
    } else if (operation === "new stack") {
      pos = deckSize - 1 - pos;
    }
  }

  return pos;
}

function modInverse(a: bigint, m: bigint): bigint {
  // For prime m, inverse of a is a^(m-2) mod m
  return modPow(a, m - 2n, m);
}

function modPow(base: bigint, exp: bigint, mod: bigint): bigint {
  let result = 1n;
  base = base % mod;

  while (exp > 0n) {
    if (exp % 2n === 1n) {
      result = (result * base) % mod;
    }
    exp = exp / 2n;
    base = (base * base) % mod;
  }

  return result;
} 

export function Day22Part2(raw: string, deckSize: bigint = 119315717514047n, card: number, numShuffles: bigint): bigint {
  const input = raw.trim().split("\n").map(line => line.split(" ")).reverse();
  let pos = card;
  let a = 1n;
  let b = 0n;

  for (let line of input) {
    const operation = getOperation(line);
    const value = operation === "new stack" ? BigInt(0) : BigInt(Number(line.at(-1)));

    if (value === undefined) {
      throw new Error("value is undefined")
    } else if (operation === "cut") {
      b = b + value;
    } else if (operation === "increment") {
      const inv = modInverse(value, deckSize);
      a = a * inv;
      b = b * inv;
    } else if (operation === "new stack") {
      a = -a;
      b = -b - 1n;
    }
    a = ((a % deckSize) + deckSize) % deckSize;
    b = ((b % deckSize) + deckSize) % deckSize;
  }

  let resultA = 1n;
  let resultB = 0n;

  let baseA = a;
  let baseB = b;

  while (numShuffles > 0n) {
    if (numShuffles % 2n === 1n) {
      let newResultA = (resultA * baseA) % deckSize;
      let newResultB = ((resultA * baseB) + resultB) % deckSize;
      resultA = newResultA;
      resultB = newResultB;
    }

    let newBaseA = (baseA * baseA) % deckSize;
    let newBaseB = ((baseA * baseB) + baseB) % deckSize;
    baseA = newBaseA;
    baseB = newBaseB;

    numShuffles = numShuffles / 2n;
  }

  // resultA = ((a % deckSize) + deckSize) % deckSize;
  // resultB = ((b % deckSize) + deckSize) % deckSize;
  console.log("Result: (", resultA, ", ", resultB, ")");

  return (resultA * BigInt(2020) + resultB) % deckSize;
}

function getOperation(line: string[]) {
  if (line !== undefined) {
    if (line[0] === "cut") {
      ``
      return "cut";
    } else if (line[1] === "with") {
      return "increment"
    } else {
      return "new stack"
    }
  }
}

console.log(Day22Part2(raw, 119315717514047n, 2020, 101741582076661n))