PHP football fixture generator

php_football_fixture_generator.php

<?php

declare(strict_types=1);

/**
 * FixtureGenerator
 *
 * Generates a full home-and-away football fixture schedule for a list of teams
 * across a provided list of dates.
 *
 * Design decisions:
 * - Deterministic: the same team order always produces the same output. Shuffle
 *   the teams array (or pass a seed via FixtureGeneratorOptions) to get a
 *   different schedule.
 * - POPO: no framework dependencies, no static state, trivially portable.
 * - Round-robin base: uses the standard "circle" round-robin algorithm to
 *   guarantee every pair meets exactly once in the first half. The second half
 *   swaps home/away for every fixture in the first half.
 * - Home/away balance: after building both halves the algorithm assigns home
 *   and away such that each team's running home/away imbalance is kept as small
 *   as possible (≤ 1 in most cases).
 * - Separation: the second half is scheduled so that the gap between a team's
 *   two meetings is maximised (mirrors the round from the first half as far
 *   apart as possible in the second half).
 */
final class FixtureGenerator
{
    /**
     * Generate a fixture list.
     *
     * @param  list<string>  $teams  Team names (or IDs). Order determines the
     *                               base schedule; shuffle beforehand for
     *                               randomness.
     * @param  list<string>  $dates  ISO-8601 date strings, one per matchday.
     *                               Count must equal (count($teams) - 1) * 2.
     * @param  FixtureGeneratorOptions|null  $options
     *
     * @return array<string, list<array{0: string, 1: string}>>
     *         Associative array keyed by date. Each value is a list of
     *         [homeTeam, awayTeam] pairs.
     *
     * @throws \InvalidArgumentException
     */
    public function generate(
        array $teams,
        array $dates,
        ?FixtureGeneratorOptions $options = null,
    ): array {
        $options ??= new FixtureGeneratorOptions();

        $this->validate($teams, $dates);

        $teams = $this->applySeeding($teams, $options);

        $teamCount  = count($teams);
        $roundCount = $teamCount - 1; // rounds per half

        // --- 1. Build first-half rounds via circle round-robin ---------------
        //
        // Standard algorithm: pin team[0], rotate the rest counter-clockwise
        // each round. Produces $roundCount rounds, each with $teamCount/2
        // pairings, every pair appearing exactly once.

        $firstHalfRounds = $this->buildRoundRobin($teams);

        // --- 2. Assign home/away for the first half --------------------------
        //
        // For each round we decide which team in each pairing is home. We
        // greedily choose the assignment that minimises each team's running
        // home/away imbalance (home = +1, away = -1). Ties are broken by
        // preferring the pairing order that matches the circle algorithm's
        // natural slot (team in the "upper" slot is home in odd rounds,
        // "lower" slot in even rounds) so the output is still deterministic.

        /** @var array<string, int> $balance  Running imbalance per team (+ve = more homes). */
        $balance = array_fill_keys($teams, 0);

        /** @var list<list<array{0: string, 1: string}>> $firstHalf */
        $firstHalf = [];

        foreach ($firstHalfRounds as $roundIndex => $pairings) {
            $round = [];
            foreach ($pairings as [$a, $b]) {
                // Prefer whichever team has a lower (more negative) balance
                // as the home side — they "need" a home game more.
                // Tie-break: even round index → $a is home; odd → $b is home.
                $aIsHome = match (true) {
                    $balance[$a] < $balance[$b] => true,
                    $balance[$a] > $balance[$b] => false,
                    default                     => ($roundIndex % 2 === 0),
                };

                [$home, $away] = $aIsHome ? [$a, $b] : [$b, $a];
                $round[]        = [$home, $away];
                $balance[$home]++;
                $balance[$away]--;
            }
            $firstHalf[] = $round;
        }

        // --- 3. Build second half (reverse fixtures) -------------------------
        //
        // Every fixture from the first half is reversed (home ↔ away).
        // To maximise separation we mirror the round ordering: a fixture in
        // first-half round $r is placed in second-half round
        // ($roundCount - 1 - $r), i.e. the furthest-away slot.
        // This guarantees a team cannot meet the same opponent back-to-back
        // across the half boundary, and maximises the gap in all cases.

        /** @var list<list<array{0: string, 1: string}>> $secondHalf */
        $secondHalf = array_fill(0, $roundCount, []);

        foreach ($firstHalf as $roundIndex => $fixtures) {
            $mirrorIndex = $roundCount - 1 - $roundIndex;
            foreach ($fixtures as [$home, $away]) {
                $secondHalf[$mirrorIndex][] = [$away, $home]; // swap
            }
        }

        // --- 4. Further separate any close repeat fixtures -------------------
        //
        // Even with mirroring, teams near the boundary (first-half round 0 ↔
        // second-half round ($roundCount-1)) are as far apart as possible, so
        // mirroring is already optimal. However, we run a local-search pass to
        // swap second-half round positions for individual fixtures to improve
        // the minimum separation across *all* team pairs, without introducing
        // any new violations.

        $secondHalf = $this->improveSecondHalfSeparation($firstHalf, $secondHalf, $teamCount);

        // --- 5. Zip rounds onto dates ----------------------------------------

        $allRounds = [...$firstHalf, ...$secondHalf];
        $dates     = array_values($dates);
        $result    = [];

        foreach ($allRounds as $i => $fixtures) {
            $result[$dates[$i]] = $fixtures;
        }

        return $result;
    }

    // -------------------------------------------------------------------------
    // Private helpers
    // -------------------------------------------------------------------------

    /**
     * @param  list<string>  $teams
     * @param  list<string>  $dates
     */
    private function validate(array $teams, array $dates): void
    {
        $teamCount = count($teams);

        if ($teamCount < 2) {
            throw new \InvalidArgumentException(
                'At least two teams are required.'
            );
        }

        if ($teamCount % 2 !== 0) {
            throw new \InvalidArgumentException(
                sprintf(
                    'An even number of teams is required (got %d). Add a bye team if necessary.',
                    $teamCount,
                )
            );
        }

        $expectedDates = ($teamCount - 1) * 2;
        $actualDates   = count($dates);

        if ($actualDates !== $expectedDates) {
            throw new \InvalidArgumentException(
                sprintf(
                    'Expected %d dates for %d teams ((%d - 1) × 2), got %d.',
                    $expectedDates,
                    $teamCount,
                    $teamCount,
                    $actualDates,
                )
            );
        }

        if (count(array_unique($teams)) !== $teamCount) {
            throw new \InvalidArgumentException('Duplicate team names are not allowed.');
        }

        if (count(array_unique($dates)) !== $actualDates) {
            throw new \InvalidArgumentException('Duplicate dates are not allowed.');
        }
    }

    /**
     * Optionally seed and/or shuffle the teams array.
     *
     * @param  list<string>  $teams
     * @return list<string>
     */
    private function applySeeding(array $teams, FixtureGeneratorOptions $options): array
    {
        if (!$options->shuffle) {
            return $teams;
        }

        if ($options->seed !== null) {
            mt_srand($options->seed);
        }

        shuffle($teams);

        return $teams;
    }

    /**
     * Standard "circle" round-robin.
     *
     * Team at index 0 is pinned; the remaining teams rotate. Returns a list of
     * rounds, each round being a list of [teamA, teamB] pairings (no home/away
     * assignment yet).
     *
     * @param  list<string>  $teams  Must be even-length.
     * @return list<list<array{0: string, 1: string}>>
     */
    private function buildRoundRobin(array $teams): array
    {
        $n      = count($teams);
        $half   = $n / 2;
        $pinned = $teams[0];
        // Rotating pool: teams[1..n-1]
        $pool   = array_slice($teams, 1);

        $rounds = [];

        for ($round = 0; $round < $n - 1; $round++) {
            $pairings = [];

            // Pinned team always plays the first team in the pool.
            $pairings[] = [$pinned, $pool[0]];

            // Remaining pairs: pool[1] vs pool[n-2], pool[2] vs pool[n-3], …
            for ($i = 1; $i < $half; $i++) {
                $pairings[] = [$pool[$i], $pool[$n - 1 - $i]];
            }

            $rounds[] = $pairings;

            // Rotate pool one step clockwise (last element moves to front).
            array_unshift($pool, array_pop($pool));
        }

        return $rounds;
    }

    /**
     * Local-search pass to improve the minimum separation of reverse fixtures.
     *
     * For each pair of teams, their two meetings are currently separated by
     * mirroring ($roundCount - 1 gaps where $roundCount = $teamCount - 1).
     * This is already the maximum theoretical separation, so this pass focuses
     * on cases where, due to the mirroring calculation, some pairs end up with
     * a smaller gap because two fixtures in the same second-half round compete
     * for the same slot — it attempts round-level swaps within the second half
     * to smooth out any remaining issues.
     *
     * @param  list<list<array{0: string, 1: string}>>  $firstHalf
     * @param  list<list<array{0: string, 1: string}>>  $secondHalf
     * @return list<list<array{0: string, 1: string}>>
     */
    private function improveSecondHalfSeparation(
        array $firstHalf,
        array $secondHalf,
        int $teamCount,
    ): array {
        $roundCount = $teamCount - 1;

        // Build a map: pairKey => first-half round index.
        // pairKey is alphabetically sorted to be direction-agnostic.
        $firstHalfRound = [];
        foreach ($firstHalf as $roundIndex => $fixtures) {
            foreach ($fixtures as [$home, $away]) {
                $key = $this->pairKey($home, $away);
                $firstHalfRound[$key] = $roundIndex;
            }
        }

        // Calculate the current separation for each pair.
        $separation = $this->calcSeparations($firstHalfRound, $secondHalf, $roundCount);

        // Attempt round swaps in the second half to improve the minimum
        // separation. We iterate until no improving swap is found.
        $improved = true;

        while ($improved) {
            $improved = false;

            for ($i = 0; $i < $roundCount - 1; $i++) {
                for ($j = $i + 1; $j < $roundCount; $j++) {
                    // Would swapping second-half rounds $i and $j improve things?
                    $currentMin = min($separation);

                    // Temporarily swap.
                    [$secondHalf[$i], $secondHalf[$j]] = [$secondHalf[$j], $secondHalf[$i]];
                    $newSeparation = $this->calcSeparations($firstHalfRound, $secondHalf, $roundCount);
                    $newMin        = min($newSeparation);

                    if ($newMin > $currentMin) {
                        // Keep the swap and recalculate.
                        $separation = $newSeparation;
                        $improved   = true;
                    } else {
                        // Revert.
                        [$secondHalf[$i], $secondHalf[$j]] = [$secondHalf[$j], $secondHalf[$i]];
                    }
                }
            }
        }

        return $secondHalf;
    }

    /**
     * Calculate the separation (number of rounds between first and second
     * meeting) for every pair of teams, given the current second-half ordering.
     *
     * @param  array<string, int>                        $firstHalfRound
     * @param  list<list<array{0: string, 1: string}>>   $secondHalf
     * @return array<string, int>
     */
    private function calcSeparations(
        array $firstHalfRound,
        array $secondHalf,
        int $roundCount,
    ): array {
        $separations = [];

        foreach ($secondHalf as $secondRoundIndex => $fixtures) {
            foreach ($fixtures as [$home, $away]) {
                $key              = $this->pairKey($home, $away);
                $firstRound       = $firstHalfRound[$key];
                // Total rounds between the two meetings (exclusive).
                // First meeting is in overall round $firstRound (0-indexed).
                // Second meeting is in overall round $roundCount + $secondRoundIndex.
                $sep              = ($roundCount + $secondRoundIndex) - $firstRound - 1;
                $separations[$key] = $sep;
            }
        }

        return $separations;
    }

    /**
     * Canonical (direction-agnostic) key for a pair of teams.
     */
    private function pairKey(string $a, string $b): string
    {
        return $a < $b ? "{$a}|{$b}" : "{$b}|{$a}";
    }
}

// =============================================================================

/**
 * Options bag for FixtureGenerator::generate().
 */
final class FixtureGeneratorOptions
{
    public function __construct(
        /**
         * When true the teams array is shuffled before scheduling, producing a
         * different (but still deterministic-per-shuffle) fixture list.
         * Default: false (deterministic from the supplied team order).
         */
        public readonly bool $shuffle = false,

        /**
         * Optional seed for mt_srand() used when $shuffle is true. Pass an
         * integer to make a shuffled run reproducible (useful for re-generating
         * a schedule after the fact). Ignored when $shuffle is false.
         */
        public readonly ?int $seed = null,
    ) {}
}

// ---------------------------------------------------------------------------
// Teams – 2025-26 National League North (alphabetical)
// ---------------------------------------------------------------------------

$teams = [
    'AFC Fylde',
    'AFC Telford United',
    'Alfreton Town',
    'Bedford Town',
    'Buxton',
    'Chester',
    'Chorley',
    'Curzon Ashton',
    'Darlington',
    'Hereford',
    'Kidderminster Harriers',
    "King's Lynn Town",
    'Leamington',
    'Macclesfield',
    'Marine',
    'Merthyr Town',
    'Oxford City',
    'Peterborough Sports',
    'Radcliffe',
    'Scarborough Athletic',
    'South Shields',
    'Southport',
    'Spennymoor Town',
    'Worksop Town',
];

// ---------------------------------------------------------------------------
// Dates – 46 matchdays (24 teams → (24-1) × 2 = 46)
// ---------------------------------------------------------------------------

$dates = [];
$start = new DateTimeImmutable('2025-08-09');

for ($i = 0; $i < 46; $i++) {
    $dates[] = $start->modify("+{$i} weeks")->format('Y-m-d');
}

// ---------------------------------------------------------------------------
// Generate – deterministic (no shuffle, teams passed alphabetically)
// ---------------------------------------------------------------------------

$generator = new FixtureGenerator();

echo "=== DETERMINISTIC (alphabetical team order) ===\n\n";
$fixtures = $generator->generate($teams, $dates);
printFixtures($fixtures);
validateFixtures($fixtures, $teams);

// ---------------------------------------------------------------------------
// Generate – shuffled with a fixed seed (reproducible random)
// ---------------------------------------------------------------------------

echo "\n\n=== SHUFFLED (seed=42) ===\n\n";
$options  = new FixtureGeneratorOptions(shuffle: true, seed: 42);
$fixtures = $generator->generate($teams, $dates, $options);
printFixtures($fixtures);
validateFixtures($fixtures, $teams);

// ---------------------------------------------------------------------------
// Helper functions
// ---------------------------------------------------------------------------

function printFixtures(array $fixtures): void
{
    foreach ($fixtures as $date => $matches) {
        echo "── {$date} (" . count($matches) . " fixtures) ─────────────────────────\n";
        foreach ($matches as [$home, $away]) {
            echo "   {$home} vs {$away}\n";
        }
    }
}

/**
 * Validate the generated fixture list and print a stats summary.
 */
function validateFixtures(array $fixtures, array $teams): void
{
    echo "\n── VALIDATION ────────────────────────────────────────────────────────\n";

    $teamCount  = count($teams);
    $roundCount = ($teamCount - 1) * 2;
    $dateList   = array_keys($fixtures);

    // ------------------------------------------------------------------
    // 1. Total fixture count
    // ------------------------------------------------------------------
    $totalFixtures = array_sum(array_map('count', $fixtures));
    $expected      = $teamCount * ($teamCount - 1); // each ordered pair once
    echo "Total fixtures   : {$totalFixtures} (expected {$expected}) "
        . ($totalFixtures === $expected ? "✓" : "✗ MISMATCH") . "\n";

    // ------------------------------------------------------------------
    // 2. Every team plays exactly once per matchday
    // ------------------------------------------------------------------
    $matchdayViolations = 0;
    foreach ($fixtures as $date => $matches) {
        $seen = [];
        foreach ($matches as [$home, $away]) {
            foreach ([$home, $away] as $team) {
                if (isset($seen[$team])) {
                    $matchdayViolations++;
                    echo "  ✗ {$team} appears twice on {$date}\n";
                }
                $seen[$team] = true;
            }
        }
    }
    echo "Single-game days : " . ($matchdayViolations === 0 ? "✓ (no team plays twice on a date)" : "✗ {$matchdayViolations} violations") . "\n";

    // ------------------------------------------------------------------
    // 3. Every pair meets exactly once at home and once away
    // ------------------------------------------------------------------
    $pairings = [];
    foreach ($fixtures as $matches) {
        foreach ($matches as [$home, $away]) {
            $pairings["{$home}→{$away}"] = ($pairings["{$home}→{$away}"] ?? 0) + 1;
        }
    }

    $pairingErrors = 0;
    foreach ($teams as $a) {
        foreach ($teams as $b) {
            if ($a === $b) {
                continue;
            }
            $count = $pairings["{$a}→{$b}"] ?? 0;
            if ($count !== 1) {
                $pairingErrors++;
                echo "  ✗ {$a} hosts {$b} {$count} times (expected 1)\n";
            }
        }
    }
    echo "Pair coverage    : " . ($pairingErrors === 0 ? "✓ (every ordered pair appears exactly once)" : "✗ {$pairingErrors} pair errors") . "\n";

    // ------------------------------------------------------------------
    // 4. Home/away balance per team
    // ------------------------------------------------------------------
    $homeCount = array_fill_keys($teams, 0);
    $awayCount = array_fill_keys($teams, 0);

    foreach ($fixtures as $matches) {
        foreach ($matches as [$home, $away]) {
            $homeCount[$home]++;
            $awayCount[$away]++;
        }
    }

    $gamesPerTeam    = $teamCount - 1; // e.g. 23 for 24 teams
    $balanceViolations = 0;

    foreach ($teams as $team) {
        if ($homeCount[$team] !== $gamesPerTeam || $awayCount[$team] !== $gamesPerTeam) {
            $balanceViolations++;
            echo "  ✗ {$team}: {$homeCount[$team]}H / {$awayCount[$team]}A (expected {$gamesPerTeam}/{$gamesPerTeam})\n";
        }
    }
    echo "H/A balance      : " . ($balanceViolations === 0 ? "✓ (every team plays {$gamesPerTeam}H / {$gamesPerTeam}A)" : "✗ {$balanceViolations} team(s) unbalanced") . "\n";

    // ------------------------------------------------------------------
    // 5. Home/away alternation quality
    // ------------------------------------------------------------------
    // Count how many consecutive same-venue pairs (H-H or A-A) each team has.
    $teamSchedules = array_fill_keys($teams, []);

    foreach ($dateList as $date) {
        foreach ($fixtures[$date] as [$home, $away]) {
            $teamSchedules[$home][] = 'H';
            $teamSchedules[$away][] = 'A';
        }
    }

    $totalConsecutive = 0;
    foreach ($teamSchedules as $team => $schedule) {
        for ($i = 0; $i < count($schedule) - 1; $i++) {
            if ($schedule[$i] === $schedule[$i + 1]) {
                $totalConsecutive++;
            }
        }
    }

    $totalTransitions = $teamCount * ($roundCount - 1);
    $alternationPct   = round((1 - $totalConsecutive / $totalTransitions) * 100, 1);
    echo "H/A alternation  : {$alternationPct}% perfect "
        . "({$totalConsecutive} consecutive same-venue pairs across all teams)\n";

    // ------------------------------------------------------------------
    // 6. Minimum separation between a team's two meetings with each opponent
    // ------------------------------------------------------------------
    $pairingRound = [];
    foreach ($dateList as $roundIndex => $date) {
        foreach ($fixtures[$date] as [$home, $away]) {
            $key = $home < $away ? "{$home}|{$away}" : "{$away}|{$home}";
            $pairingRound[$key][] = $roundIndex;
        }
    }

    $separations = [];
    foreach ($pairingRound as $key => $rounds) {
        if (count($rounds) === 2) {
            $separations[$key] = abs($rounds[1] - $rounds[0]) - 1;
        }
    }

    if (!empty($separations)) {
        $minSep  = min($separations);
        $maxSep  = max($separations);
        $avgSep  = round(array_sum($separations) / count($separations), 1);
        $backToBack = count(array_filter($separations, fn($s) => $s === 0));

        echo "Pair separation  : min={$minSep} avg={$avgSep} max={$maxSep} rounds between meetings\n";
        echo "Back-to-back     : " . ($backToBack === 0 ? "✓ none" : "✗ {$backToBack} pair(s)") . "\n";
    }

    echo "──────────────────────────────────────────────────────────────────────\n";
}