Advent of Code 2023 - Day 21 - Part 2

/**
 * Lagrange's Interpolation formula for ax^2 + bx + c with x=[0,1,2] and y=[y0,y1,y2] we have
 *   f(x) = (x^2-3x+2) * y0/2 - (x^2-2x)*y1 + (x^2-x) * y2/2
 * so the coefficients are:
 * a = y0/2 - y1 + y2/2
 * b = -3*y0/2 + 2*y1 - y2/2
 * c = y0
 */
const simplifiedLagrange = (values) => {
  return {
    a: values[0] / 2 - values[1] + values[2] / 2,
    b: -3 * (values[0] / 2) + 2 * values[1] - values[2] / 2,
    c: values[0],
  };
};
const solvePart2 = (input) => {
  const values = [solvePart1(input, 65), solvePart1(input, 65 + 131), solvePart1(input, 65 + 131 * 2)];
  const poly = simplifiedLagrange(values);
  const target = (26_501_365 - 65) / 131;
  return poly.a * target * target + poly.b * target + poly.c;
};