139 lines
4.5 KiB
Plaintext
139 lines
4.5 KiB
Plaintext
{
|
|
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 UPolynomialRootsTestCases;
|
|
|
|
{$mode ObjFPC}{$H+}
|
|
|
|
interface
|
|
|
|
uses
|
|
Classes, SysUtils, fpcunit, testregistry, UPolynomial, UPolynomialRoots, UBigInt;
|
|
|
|
type
|
|
|
|
{ TPolynomialRootsTestCase }
|
|
|
|
TPolynomialRootsTestCase = class(TTestCase)
|
|
private
|
|
procedure AssertBisectIntervals(AIsolatingIntervals: TIsolatingIntervalArray; constref AExpectedRoots:
|
|
array of Cardinal);
|
|
procedure AssertBisectIntegers(ARoots: TBigIntArray; constref AExpectedRoots: array of Cardinal);
|
|
published
|
|
procedure TestBisectNoBound;
|
|
procedure TestBisectWithBound;
|
|
procedure TestBisectInteger;
|
|
end;
|
|
|
|
implementation
|
|
|
|
{ TPolynomialRootsTestCase }
|
|
|
|
procedure TPolynomialRootsTestCase.AssertBisectIntervals(AIsolatingIntervals: TIsolatingIntervalArray;
|
|
constref AExpectedRoots: array of Cardinal);
|
|
var
|
|
exp: Cardinal;
|
|
found: Boolean;
|
|
i, foundIndex: Integer;
|
|
begin
|
|
AssertEquals('Unexpected number of isolating intervals.', Length(AExpectedRoots), Length(AIsolatingIntervals));
|
|
for exp in AExpectedRoots do
|
|
begin
|
|
found := False;
|
|
for i := 0 to Length(AIsolatingIntervals) - 1 do
|
|
if (AIsolatingIntervals[i].A <= exp) and (exp <= AIsolatingIntervals[i].B) then
|
|
begin
|
|
found := True;
|
|
foundIndex := i;
|
|
Break;
|
|
end;
|
|
AssertTrue('No isolating interval for expected root ' + IntToStr(exp) + ' found.', found);
|
|
Delete(AIsolatingIntervals, foundIndex, 1);
|
|
end;
|
|
end;
|
|
|
|
procedure TPolynomialRootsTestCase.AssertBisectIntegers(ARoots: TBigIntArray; constref AExpectedRoots:
|
|
array of Cardinal);
|
|
var
|
|
exp: Cardinal;
|
|
found: Boolean;
|
|
i, foundIndex: Integer;
|
|
begin
|
|
AssertEquals('Unexpected number of integer roots.', Length(AExpectedRoots), Length(ARoots));
|
|
for exp in AExpectedRoots do
|
|
begin
|
|
found := False;
|
|
for i := 0 to Length(ARoots) - 1 do
|
|
if ARoots[i] = exp then
|
|
begin
|
|
found := True;
|
|
foundIndex := i;
|
|
Break;
|
|
end;
|
|
AssertTrue('Expected root ' + IntToStr(exp) + ' not found.', found);
|
|
Delete(ARoots, foundIndex, 1);
|
|
end;
|
|
end;
|
|
|
|
procedure TPolynomialRootsTestCase.TestBisectNoBound;
|
|
const
|
|
expRoots: array of Cardinal = (34000, 23017, 5);
|
|
var
|
|
a: TBigIntPolynomial;
|
|
r: TIsolatingIntervalArray;
|
|
begin
|
|
// y = 3 * (x - 34000) * (x - 23017) * (x - 5) * (x^2 - 19) * (x + 112)
|
|
// = 3 * x^6 - 170730 * x^5 + 2329429920 * x^4 + 251300082690 * x^3 - 1270471872603 * x^2 + 4774763204640 * x - 24979889760000
|
|
a := TBigIntPolynomial.Create([-24979889760000, 4774763204640, -1270471872603, 251300082690, 2329429920, -170730, 3]);
|
|
r := TPolynomialRoots.BisectIsolation(a);
|
|
AssertBisectIntervals(r, expRoots);
|
|
end;
|
|
|
|
procedure TPolynomialRootsTestCase.TestBisectWithBound;
|
|
const
|
|
expRoots: array of Cardinal = (23017, 5);
|
|
var
|
|
a: TBigIntPolynomial;
|
|
r: TIsolatingIntervalArray;
|
|
begin
|
|
// y = 3 * (x - 34000) * (x - 23017) * (x - 5) * (x^2 - 19) * (x + 112)
|
|
// = 3 * x^6 - 170730 * x^5 + 2329429920 * x^4 + 251300082690 * x^3 - 1270471872603 * x^2 + 4774763204640 * x - 24979889760000
|
|
a := TBigIntPolynomial.Create([-24979889760000, 4774763204640, -1270471872603, 251300082690, 2329429920, -170730, 3]);
|
|
r := TPolynomialRoots.BisectIsolation(a, 15);
|
|
AssertBisectIntervals(r, expRoots);
|
|
end;
|
|
|
|
procedure TPolynomialRootsTestCase.TestBisectInteger;
|
|
const
|
|
expRoots: array of Cardinal = (23017, 5);
|
|
var
|
|
a: TBigIntPolynomial;
|
|
r: TBigIntArray;
|
|
begin
|
|
// y = 3 * (x - 34000) * (x - 23017) * (x - 5) * (x^2 - 19) * (x + 112)
|
|
// = 3 * x^6 - 170730 * x^5 + 2329429920 * x^4 + 251300082690 * x^3 - 1270471872603 * x^2 + 4774763204640 * x - 24979889760000
|
|
a := TBigIntPolynomial.Create([-24979889760000, 4774763204640, -1270471872603, 251300082690, 2329429920, -170730, 3]);
|
|
r := TPolynomialRoots.BisectInteger(a, 15);
|
|
AssertBisectIntegers(r, expRoots);
|
|
end;
|
|
|
|
initialization
|
|
|
|
RegisterTest('Helper', TPolynomialRootsTestCase);
|
|
end.
|
|
|