AdventOfCode2023/solvers/ULavaductLagoon.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 ULavaductLagoon;

{$mode ObjFPC}{$H+}

interface

uses
  Classes, SysUtils, StrUtils, Generics.Collections, Math, USolver;

type

  { TDig }

  TDig = class
    Direction, Length: Integer;
  end;

  TDigs = specialize TObjectList<TDig>;

  { TDigSite }

  TDigSite = class
  private
    FDigs: TDigs;
    FArea, FTrench: Int64;
    function CheckMergeDigs(const ADigIndex: Integer): Cardinal;
  public
    procedure AddDig(constref ADig: TDig);
    procedure CollapseUTurns;
    function CalcFinalArea: Int64;
    constructor Create;
    destructor Destroy; override;
  end;

  { TLavaductLagoon }

  TLavaductLagoon = class(TSolver)
    FSite1, FSite2: TDigSite;
    procedure AddDig(const ALine: string);
  public
    constructor Create;
    destructor Destroy; override;
    procedure ProcessDataLine(const ALine: string); override;
    procedure Finish; override;
    function GetDataFileName: string; override;
    function GetPuzzleName: string; override;
  end;

implementation

{ TDigSite }

function TDigSite.CheckMergeDigs(const ADigIndex: Integer): Cardinal;
begin
  Result := 0;
  if (0 <= ADigIndex) and (ADigIndex < FDigs.Count - 1) then
  begin
    // Appends two consecutive digs, if they go in the same direction.
    if FDigs[ADigIndex].Direction = FDigs[ADigIndex + 1].Direction then
    begin
      FDigs[ADigIndex].Length := FDigs[ADigIndex].Length + FDigs[ADigIndex + 1].Length;
      FDigs.Delete(ADigIndex + 1);
      Inc(Result);
    end
    // Otherwise, checks if the directions are opposite.
    else if Abs(FDigs[ADigIndex].Direction - FDigs[ADigIndex + 1].Direction) = 2 then
    begin
      // Recurses, if the opposite digs cancel each other out.
      if FDigs[ADigIndex].Length = FDigs[ADigIndex + 1].Length then
      begin
        FDigs.DeleteRange(ADigIndex, 2);
        Inc(Result, 2);
        Inc(Result, CheckMergeDigs(ADigIndex - 1));
      end
      else begin
        // Otherwise, subtracts the opposite directions.
        if FDigs[ADigIndex].Length > FDigs[ADigIndex + 1].Length then
          FDigs[ADigIndex].Length := FDigs[ADigIndex].Length - FDigs[ADigIndex + 1].Length
        else begin
          FDigs[ADigIndex].Length := FDigs[ADigIndex + 1].Length - FDigs[ADigIndex].Length;
          FDigs[ADigIndex].Direction := FDigs[ADigIndex + 1].Direction;
        end;
        FDigs.Delete(ADigIndex + 1);
        Inc(Result);
      end;
    end;
  end;
end;

procedure TDigSite.AddDig(constref ADig: TDig);
begin
  FDigs.Add(ADig);
  Inc(FTrench, ADig.Length);

  // The new dig might have to be merged with the preceeding dig.
  CheckMergeDigs(FDigs.Count - 2);
end;

procedure TDigSite.CollapseUTurns;
var
  i, side, backtrack, shorter: Integer;
begin
  // If there is a U-turn, it must involve the last dig, otherwise we would have collapsed it in an earlier call
  // already. Therefore we check the last three digs first.
  i := FDigs.Count - 3;
  while (0 <= i) and (i + 2 < FDigs.Count) do
  begin
    // We check if three consecutive digs starting at i form a U-turn. It's enough to check whether the first and the
    // third have different directions because they must be parallel.
    if FDigs[i].Direction <> FDigs[i + 2].Direction then
    begin
      // Either right or left U-turns enclose an area inside the trench. We do not need to know which one is which and
      // just assume here that the right U-turns enclose an area outside and therefore negate it. If it's the other way
      // around, then we can simply negate the end result.
      side := FDigs[i + 1].Length;
      if (FDigs[i].Direction + 1 = FDigs[i + 1].Direction)
      or (FDigs[i + 1].Direction + 1 = FDigs[i + 2].Direction) then
        side := -side;

      // Updates the shortened dig and collapses the U-turn.
      backtrack := 0;
      shorter := Min(FDigs[i].Length, FDigs[i + 2].Length);
      Inc(FArea, side * shorter);
      if FDigs[i + 2].Length = shorter then
      begin
        FDigs.Delete(i + 2);
        Inc(backtrack);
        Inc(backtrack, CheckMergeDigs(i + 1));
      end
      else
        Dec(FDigs[i + 2].Length, shorter);

      if FDigs[i].Length = shorter then
      begin
        FDigs.Delete(i);
        Inc(backtrack);
        Inc(backtrack, CheckMergeDigs(i - 1));
      end
      else
        Dec(FDigs[i].Length, shorter);
      Dec(i, backtrack);
    end
    else
      Inc(i);
  end;
end;

function TDigSite.CalcFinalArea: Int64;
begin
  // If the area is negative, then outside and inside have to be "swapped", which Abs() achieves here.
  // When collapsing the U-turns, only the area up to the imaginary middle line of the dug trench is considered, so half
  // of the full length of the dug trench + 1 has to be added to include the whole trench in the area calculation.
  Result := Abs(FArea) + FTrench div 2 + 1;
end;

constructor TDigSite.Create;
begin
  FDigs := TDigs.Create;
end;

destructor TDigSite.Destroy;
begin
  FDigs.Free;
  inherited Destroy;
end;

{ TLavaductLagoon }

procedure TLavaductLagoon.AddDig(const ALine: string);
var
  split: TStringArray;
  dig: TDig;
begin
  dig := TDig.Create;
  split := ALine.Split([' ']);
  case split[0] of
    'R': dig.Direction := 0;
    'D': dig.Direction := 1;
    'L': dig.Direction := 2;
    'U': dig.Direction := 3;
  end;
  dig.Length := StrToInt(split[1]);
  FSite1.AddDig(dig);

  dig := TDig.Create;
  dig.Direction := StrToInt(split[2][8]);
  dig.Length := Hex2Dec(Copy(split[2], 3, 5));
  FSite2.AddDig(dig);
end;

constructor TLavaductLagoon.Create;
begin
  FSite1 := TDigSite.Create;
  FSite2 := TDigSite.Create;
end;

destructor TLavaductLagoon.Destroy;
begin
  FSite1.Free;
  FSite2.Free;
  inherited Destroy;
end;

procedure TLavaductLagoon.ProcessDataLine(const ALine: string);
begin
  AddDig(ALine);
  FSite1.CollapseUTurns;
  FSite2.CollapseUTurns;
end;

procedure TLavaductLagoon.Finish;
begin
  // If the area is negative, then outside and inside have to be "swapped", which Abs() achieves here.
  // When collapsing the U-turns, only the area up to the imaginary middle line of the dug trench is considered, so half
  // of the full length of the dug trench + 1 has to be added to include the whole trench in the area calculation.
  FPart1 := FSite1.CalcFinalArea;
  FPart2 := FSite2.CalcFinalArea;
end;

function TLavaductLagoon.GetDataFileName: string;
begin
  Result := 'lavaduct_lagoon.txt';
end;

function TLavaductLagoon.GetPuzzleName: string;
begin
  Result := 'Day 18: Lavaduct Lagoon';
end;

end.