unit vs2solve;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils;

type
  TGamePlayerVS = record
    Player1: Integer;
    Player2: Integer;
  end;
  TGame2VSInverseVSMap = array of TGamePlayerVS;
  TGame2VSConstraintCnt = array of Integer;

  TGame2VSConstraints = class;

  { TGameSingleCoded }

  TGameSingleCoded = class
    private
      // Constraints Reference
      FGameConstr: TGame2VSConstraints;
      // Anzahl der Gegenübertreffen um
      // (schnell) zu validieren das jeder 2 spiele spielt,
      // ohne neu zu berechnen.
      // ist nach berechnung leer um speicher zu spaaren
      FGameCnt: TGame2VSConstraintCnt;
      // Bitfeld, welches die die Spieler gegenüberstellung codiert
      // (untere Dreiecksmatrix)
      FGameMapping: TBits;
      function getMatchCnt: Integer;
      function getMatchActive( i: Integer ): Boolean;
      function getMatchPlayer1( i: Integer ): Integer;
      function getMatchPlayer2( i: Integer ): Integer;
    public
      // Anzahl (moegliche) Matches im Spiel
      property MatchCount: Integer read getMatchCnt;
      // Teste ob Match i aktiviert ist
      property Match[ i: Integer ]: Boolean read getMatchActive;
      // gibt spieler 1 von Match i zurueck
      property MatchPlayer1[ i: Integer ]: Integer read getMatchPlayer1;
      // gibt spieler 2 von Match i zurueck
      property MatchPlayer2[ i: Integer ]: Integer read getMatchPlayer2; 
    
      constructor Create( ARefGameConstr: TGame2VSConstraints );
      destructor Destroy; override;
      // erzeugen einer Kopie (für branching)
      function Copy: TGameSingleCoded;
      // fixieren, markiere diese Belegung als endgültig
      // -> gibt true zurück wenn das spiel korrekt ist (alle spielen 2 mal)
      // andernfalls false
      function Complete: Boolean;
      // prüfe ob ein Match 2er Spieler möglich ist, ohne die Constraints zu
      // verletzen
      function CanPlay( AMatchNr: Integer ): Boolean;
      // prüfe ob spieler noch spielen kann
      function PlayerCanPlay( APlayerNr: Integer ): Boolean;
      // setze ein Match
      procedure SetMatch( AMatchNr: Integer );
  end;

  { TGame2VSConstraints }

  TGame2VSConstraints = class
    private
      // Anzahl Spieler
      FNrPlayers: Integer;
      // Anzahl VS. Kombinationen in unterer Dreiecksmatrix (= Anzahl Matches)
      FLTMatrixFields: Integer;
      // Inverse Funktion um aus FLTMatrixFields position i zu bestimmen,
      // welche Spieler in einem Match gegnübertreffen
      FLTMatrixMapping: TGame2VSInverseVSMap;
      // Liste berechneter Spiele
      FList: TFPList;
      // Rekursion zum testen/erzeugen aller Matches (Player,X) im
      // aktuell behandelten "partiel korrektem" spiel RefGame
      function getGame( i: Integer ): TGameSingleCoded;
      function getGameCnt: Integer;
      procedure RecursiveSelect( MatchOfs: Integer; AFixPlayer: Integer; var RefGame: TGameSingleCoded );
    public
      property GameCount: Integer read getGameCnt;
      property Game[ i: Integer ]: TGameSingleCoded read getGame;
      constructor Create( ANrPlayers: Integer );
      destructor Destroy; override;
      // Enumeriere alle Möglichen (und unter den Beschränkungen korrekte) Spiele
      procedure SolveGames;
  end;

implementation

{ TGameSingleCoded }

constructor TGameSingleCoded.Create(ARefGameConstr: TGame2VSConstraints);
var i: Integer;
begin
  FGameConstr := ARefGameConstr;
  // erzeuge Feld mit Anzahl Matches per Spieler -> alles 0
  SetLength(FGameCnt, FGameConstr.FNrPlayers);
  for i := 0 to FGameConstr.FNrPlayers-1 do
    FGameCnt[i] := 0;
  // Match Bit-feld
  FGameMapping := TBits.Create(FGameConstr.FLTMatrixFields);
  FGameMapping.Clearall;
end;

destructor TGameSingleCoded.Destroy;
begin
  SetLength(FGameCnt,0);
  FGameMapping.Free;
  inherited Destroy;
end;

function TGameSingleCoded.Copy: TGameSingleCoded;
var i: Integer;
begin
  // erzeuge neues/sauberes objekt
  Result := TGameSingleCoded.Create(FGameConstr);
  // kopiere matchzahl
  for i := 0 to FGameConstr.FNrPlayers-1 do
    Result.FGameCnt[i] := FGameCnt[i];
  // "kopiere" Matchvektor -> newgame := 0000...00 or oldgame.bits
  Result.FGameMapping.OrBits(FGameMapping);
end;

function TGameSingleCoded.Complete: Boolean;
var i: Integer;
begin
  Result := true;
  // pruefe ob jeder 2 matches hat
  for i := 0 to Length(FGameCnt)-1 do
    if FGameCnt[i] <> 2 then
      begin
        Result := false;
        Break;
      end;
  // loesche matchfeld -> markiert validiert
  if Result then
    SetLength(FGameCnt,0);
end;

function TGameSingleCoded.CanPlay(AMatchNr: Integer): Boolean;
begin
  // Match nicht spielbar, wenn es bereits markiert wurde
  if FGameMapping.Bits[AMatchNr-1] then
    Exit(False);
  // Match ist spielbar wenn sowohl Player 1, als auch Player 2 ihre maximale
  // matchzahl nicht überschritten haben
  Result := (FGameCnt[FGameConstr.FLTMatrixMapping[AMatchNr-1].Player1-1] < 2) and
            (FGameCnt[FGameConstr.FLTMatrixMapping[AMatchNr-1].Player2-1] < 2);
end;

function TGameSingleCoded.PlayerCanPlay( APlayerNr: Integer ): Boolean;
begin
  // prüfe ob spieler noch 1 spiel spielen kann
  Result := FGameCnt[APlayerNr-1] < 2;
end;

function TGameSingleCoded.getMatchCnt: Integer;
begin
  Result := FGameConstr.FLTMatrixFields;
end;

function TGameSingleCoded.getMatchActive( i: Integer ): Boolean;
begin
  Result := FGameMapping.Bits[i];
end;

function TGameSingleCoded.getMatchPlayer1( i: Integer ): Integer;
begin
  Result := FGameConstr.FLTMatrixMapping[i].Player1;
end;

function TGameSingleCoded.getMatchPlayer2( i: Integer ): Integer;
begin
  Result := FGameConstr.FLTMatrixMapping[i].Player2;
end;

procedure TGameSingleCoded.SetMatch(AMatchNr: Integer);
begin
  // Match nicht spielbar, wenn es bereits markiert wurde
  ASSERT( not FGameMapping.Bits[AMatchNr-1] );
  // erhöhe den Matchzähler für Spieler1/2 und setze das Match als gespielt
  FGameMapping.Bits[AMatchNr-1] := true;
  Inc(FGameCnt[FGameConstr.FLTMatrixMapping[AMatchNr-1].Player1-1],1);
  Inc(FGameCnt[FGameConstr.FLTMatrixMapping[AMatchNr-1].Player2-1],1);
end;

{ TGame2VSConstraints }

procedure TGame2VSConstraints.RecursiveSelect(MatchOfs: Integer;
  AFixPlayer: Integer; var RefGame: TGameSingleCoded);
var i: Integer;
    newgame: TGameSingleCoded;
begin
  // Untere Dreiecksmatrix erlaubt nur Matches mit (AFixPlayer,x) so dass
  // x > AFixPlayer -> das sind genau (NrPlayers-AFixPlayer)
  // -> Prüfe Matches MatchOfs+1..(MatchOfs+(NrPlayers-AFixPlayer))
  // -> Abbruch der Rekursion bei letztem spieler (NrPlayers-AFixPlayer = 0)
  //   -> prüfen der korrektheit des spiels -> alle spielen 2 mal

  // Prüfe ob wir am ende der Rekursion sind
  if FNrPlayers > AFixPlayer then
    begin
      // harte Optimierung - pruefe die ob Spieler 1..(AFixPlayer-1) bereits
      // 2 spiele haben, andernfalls ist das spiel inkorrekt
      for i := 1 to AFixPlayer-1 do
        if RefGame.PlayerCanPlay(i) then
          begin
            RefGame.Free;
            RefGame := nil;
            Exit;
          end;
    
      // noch nicht am ende, prüfe Optimierung --
      // An allen Matches dieser Rekursionsebene ist AFixPlayer beteiligt
      // -> wird können das durchtesten spaaren wenn AFixPlayer bereits
      // das maximum seiner Matches erreicht hat

      if RefGame.PlayerCanPlay(AFixPlayer) then
        begin
          // noch nicht fertig -> prüfe alle Matches für AFixPlayer
          for i := MatchOfs+1 to MatchOfs+(FNrPlayers-AFixPlayer) do
            begin
              if RefGame.CanPlay(i) then
                begin
                  newgame := RefGame.Copy;
                  newgame.SetMatch(i);
                  RecursiveSelect(MatchOfs+(FNrPlayers-AFixPlayer),AFixPlayer+1,newgame);
                end;
            end;

          // Ab hier ist RefGame müll. Da AFixPlayer spielen kann, alle tieferen
          // rekursionen aber nurnoch Matches (y,x) mit x > y > AFixPlayer
          // prüft, wird AFixPlayer in diesem spiel nie 2 matches bestreiten
          // -> mülltonne
          RefGame.Free;
          RefGame := nil;
        end
      else
        begin
          // AFixPlayer hat seine Matches - prüfe weiter mit AFixPlayer+1
          RecursiveSelect(MatchOfs+(FNrPlayers-AFixPlayer),AFixPlayer+1,RefGame);
        end;
    end
  else
    begin
      // validierung/hinzufügen oder löschen
      if RefGame.Complete then
        FList.Add(RefGame)
      else
        RefGame.Free;
      RefGame := nil;
    end;
end;

function TGame2VSConstraints.getGame( i: Integer ): TGameSingleCoded;
begin
  Result := TGameSingleCoded(FList[i]);
end;

function TGame2VSConstraints.getGameCnt: Integer;
begin
  Result := FList.Count;
end;

constructor TGame2VSConstraints.Create(ANrPlayers: Integer);
var i,j,k: Integer;
begin
  // min. 2 spieler
  if ANrPlayers <= 1 then
    ANrPlayers := 2;
  // setze spieler zahl
  FNrPlayers := ANrPlayers;
  // berechne größe der unteren dreiecksmatrix
  FLTMatrixFields := 0;
  //for i := 1 to ANrPlayers-1 do
  // Inc(FLTMatrixFields,ANrPlayers-i);
  FLTMatrixFields := ANrPlayers*ANrPlayers - ((ANrPlayers*(ANrPlayers+1)) div 2); // <- vereinfachte summe
  // berechne inverse mapping
  SetLength(FLTMatrixMapping,FLTMatrixFields);
  k := 0;
  for i := 1 to FNrPlayers-1 do
    for j := i+1 to FNrPlayers do
      begin
        FLTMatrixMapping[k].Player1 := i;
        FLTMatrixMapping[k].Player2 := j;
        Inc(k,1);
        //Writeln('Matchmake: ',k,' - ',i,' vs ',j);
      end;
  ASSERT(k=FLTMatrixFields);
  // erzeuge Liste für berechnete spiele
  FList := TFPList.Create;
end;

destructor TGame2VSConstraints.Destroy;
var i: Integer;
begin
  for i := 0 to FList.Count-1 do
    TGameSingleCoded(FList[i]).Free;
  FList.Free;
  SetLength(FLTMatrixMapping,0);
  inherited Destroy;
end;

procedure TGame2VSConstraints.SolveGames;
var i,j: Integer;
    newgame: TGameSingleCoded;
begin
  if FList.Count > 0 then
    Exit; // bereits berechnet

  // erste selektion, Spieler 1 hat immer 2 spiele wenn NrPlayer > 2
  if FNrPlayers > 2 then
    begin
      // spieler 1 spielt 2 mal
      for i := 1 to FNrPlayers-2 do
        for j := i+1 to FNrPlayers-1 do
        begin
          newgame := TGameSingleCoded.Create(self);
          newgame.SetMatch(i);
          newgame.SetMatch(j);
          RecursiveSelect(0,1,newgame);
        end;
    end
  else
    begin
      // trivial -> 1 lösung, spieler 1 spielt 1 mal oder gar nicht
      newgame := TGameSingleCoded.Create(self);
      newgame.SetMatch(1);
      FList.Add(newgame);
    end;
end;

end.

