AdventOfCode2023/UPolynomial.pas

{
  Solutions to the Advent Of Code.
  Copyright (C) 2024  Stefan Müller

  This program is free software: you can redistribute it and/or modify it under
  the terms of the GNU General Public License as published by the Free Software
  Foundation, either version 3 of the License, or (at your option) any later
  version.

  This program is distributed in the hope that it will be useful, but WITHOUT
  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.

  You should have received a copy of the GNU General Public License along with
  this program.  If not, see <http://www.gnu.org/licenses/>.
}

unit UPolynomial;

{$mode ObjFPC}{$H+}

interface

uses
  Classes, SysUtils, UBigInt;

type
  TInt64Array = array of Int64;

  { TBigIntPolynomial }

  TBigIntPolynomial = object
  private
    FCoefficients: array of TBigInt;
    function GetDegree: Integer;
    function GetCoefficient(const AIndex: Integer): TBigInt;
  public
    property Degree: Integer read GetDegree;
    property Coefficient[const AIndex: Integer]: TBigInt read GetCoefficient;
    function CalcValueAt(const AX: Int64): TBigInt;
    function CalcSignVariations: Integer;

    // Returns 2^n * f(x), given a polynomial f(x) and exponent n.
    function ScaleByPowerOfTwo(const AExponent: Cardinal): TBigIntPolynomial;

    // Returns f(s * x), given a polynomial f(x) and scale factor s.
    function ScaleVariable(const AScaleFactor: TBigInt): TBigIntPolynomial;

    // Returns f(2^n * x), given a polynomial f(x) and an exponent n.
    function ScaleVariableByPowerOfTwo(const AExponent: Cardinal): TBigIntPolynomial;

    // Returns f(x / 2), given a polynomial f(x).
    function ScaleVariableByHalf: TBigIntPolynomial;

    // Returns f(x + 1), given a polynomial f(x).
    function TranslateVariableByOne: TBigIntPolynomial;

    // Returns a polynomial with the reverse order of coefficients, i.e. the polynomial
    //   a_0 * x^n + a_1 * x^(n - 1) + ... + a_(n - 1) * x + a_n,
    // given a polynomial
    //   a_n * x^n + a_(n - 1) * x^(n - 1) + ... + a_1 * x + a_0.
    function RevertOrderOfCoefficients: TBigIntPolynomial;

    // Returns a polynomial with all coefficents shifted down one position, and the constant term removed. This should
    // only be used when the constant term is zero and is then equivalent to a division of polynomial f(x) by x.
    function DivideByVariable: TBigIntPolynomial;
    function IsEqualTo(const AOther: TBigIntPolynomial): Boolean;
    function ToString: string;
    class function Create(const ACoefficients: array of TBigInt): TBigIntPolynomial; static;
  end;

  { Operators }

  operator = (const A, B: TBigIntPolynomial): Boolean;
  operator <> (const A, B: TBigIntPolynomial): Boolean;

implementation

{ TBigIntPolynomial }

function TBigIntPolynomial.GetDegree: Integer;
begin
  Result := Length(FCoefficients) - 1;
end;

function TBigIntPolynomial.GetCoefficient(const AIndex: Integer): TBigInt;
begin
  Result := FCoefficients[AIndex];
end;

function TBigIntPolynomial.CalcValueAt(const AX: Int64): TBigInt;
var
  i: Integer;
begin
  Result := TBigInt.Zero;
  for i := High(FCoefficients) downto 0 do
    Result := Result * AX + FCoefficients[i];
end;

function TBigIntPolynomial.CalcSignVariations: Integer;
var
  current, last, i: Integer;
begin
  Result := 0;
  last := 0;
  for i := 0 to Length(FCoefficients) - 1 do
  begin
    current := FCoefficients[i].Sign;
    if (current <> 0) and (last <> current) then
    begin
      if last <> 0 then
        Inc(Result);
      last := current
    end;
  end;
end;

function TBigIntPolynomial.ScaleByPowerOfTwo(const AExponent: Cardinal): TBigIntPolynomial;
var
  len, i: Integer;
begin
  len := Length(FCoefficients);
  SetLength(Result.FCoefficients, len);
  for i := 0 to len - 1 do
    Result.FCoefficients[i] := FCoefficients[i] << AExponent;
end;

function TBigIntPolynomial.ScaleVariable(const AScaleFactor: TBigInt): TBigIntPolynomial;
var
  len, i: Integer;
  factor: TBigInt;
begin
  if AScaleFactor <> TBigInt.Zero then
  begin
    len := Length(FCoefficients);
    SetLength(Result.FCoefficients, len);
    Result.FCoefficients[0] := FCoefficients[0];
    factor := AScaleFactor;
    for i := 1 to len - 1 do begin
      Result.FCoefficients[i] := FCoefficients[i] * factor;
      factor := factor * AScaleFactor;
    end;
  end
  else begin
    SetLength(Result.FCoefficients, 1);
    Result.FCoefficients[0] := TBigInt.Zero;
  end;
end;

function TBigIntPolynomial.ScaleVariableByPowerOfTwo(const AExponent: Cardinal): TBigIntPolynomial;
var
  len, i: Integer;
  shift: Cardinal;
begin
  len := Length(FCoefficients);
  SetLength(Result.FCoefficients, len);
  Result.FCoefficients[0] := FCoefficients[0];
  shift := AExponent;
  for i := 1 to len - 1 do begin
    Result.FCoefficients[i] := FCoefficients[i] << shift;
    Inc(shift, AExponent);
  end;
end;

function TBigIntPolynomial.ScaleVariableByHalf: TBigIntPolynomial;
var
  len, i: Integer;
begin
    len := Length(FCoefficients);
    SetLength(Result.FCoefficients, len);
    Result.FCoefficients[0] := FCoefficients[0];
    for i := 1 to len - 1 do
      Result.FCoefficients[i] := FCoefficients[i] >> i;
end;

function TBigIntPolynomial.TranslateVariableByOne: TBigIntPolynomial;
var
  len, i, j: Integer;
  factors: array of Cardinal;
begin
  len := Length(FCoefficients);
  SetLength(Result.FCoefficients, len);
  SetLength(factors, len);
  for i := 0 to len - 1 do
  begin
    Result.FCoefficients[i] := TBigInt.Zero;
    factors[i] := 1;
  end;

  // Calculates new coefficients.
  for i := 0 to len - 1 do
  begin
    for j := 0 to len - i - 1 do
    begin
      if (i <> 0) and (j <> 0) then
        factors[j] := factors[j] + factors[j - 1];
      Result.FCoefficients[i] := Result.FCoefficients[i] + factors[j] * FCoefficients[j + i];
    end;
  end;
end;

function TBigIntPolynomial.RevertOrderOfCoefficients: TBigIntPolynomial;
var
  len, skip, i: Integer;
begin
  // Counts the trailing zeros to skip.
  len := Length(FCoefficients);
  skip := 0;
  while (skip < len) and (FCoefficients[skip] = 0) do
    Inc(skip);

  // Copies the other coefficients in reverse order.
  SetLength(Result.FCoefficients, len - skip);
  for i := skip to len - 1 do
    Result.FCoefficients[len - i - 1] := FCoefficients[i];
end;

function TBigIntPolynomial.DivideByVariable: TBigIntPolynomial;
var
  len: Integer;
begin
  len := Length(FCoefficients);
  if len > 1 then
    Result.FCoefficients := Copy(FCoefficients, 1, len - 1)
  else begin
    SetLength(Result.FCoefficients, 1);
    Result.FCoefficients[0] := TBigInt.Zero;
  end;
end;

function TBigIntPolynomial.IsEqualTo(const AOther: TBigIntPolynomial): Boolean;
var
  i: Integer;
begin
  if Length(FCoefficients) = Length(AOther.FCoefficients) then
  begin
    Result := True;
    for i := 0 to Length(FCoefficients) - 1 do
      if FCoefficients[i] <> AOther.FCoefficients[i] then
      begin
        Result := False;
        Break;
      end;
  end
  else
    Result := False;
end;

function TBigIntPolynomial.ToString: string;
var
  i: Integer;
begin
  Result := FCoefficients[0].ToString;
  for i := 1 to Length(FCoefficients) - 1 do
    if i > 1 then
      Result := Result + ' + ' + FCoefficients[i].ToString + ' * x^' + IntToStr(i)
    else
      Result := Result + ' + ' + FCoefficients[i].ToString + ' * x';
end;

class function TBigIntPolynomial.Create(const ACoefficients: array of TBigInt): TBigIntPolynomial;
var
  high, i: integer;
begin
  high := -1;
  for i := Length(ACoefficients) - 1 downto 0 do
    if ACoefficients[i] <> 0 then
    begin
      high := i;
      Break;
    end;
  if high >= 0 then
  begin
    SetLength(Result.FCoefficients, high + 1);
    for i := 0 to high do
      Result.FCoefficients[i] := ACoefficients[i];
  end
  else begin
    SetLength(Result.FCoefficients, 1);
    Result.FCoefficients[0] := TBigInt.Zero;
  end;
end;

{ Operators }

operator = (const A, B: TBigIntPolynomial): Boolean;
begin
  Result := A.IsEqualTo(B);
end;

operator <> (const A, B: TBigIntPolynomial): Boolean;
begin
  Result := not A.IsEqualTo(B);
end;

end.