Численная проверка решения головоломки про топ 3 из 25 лошадей

Задача следующая:

Есть 25 лошадей. На ипподроме 5 дорожек. Надо определить 3 самые быстрые лошади за минимальное число заездов. Время замерять нельзя. Мы только знаем, кто в каком порядке финиширует. Можно считать, что время за которое каждая лошадь пробегает дистанцию не меняется от заезда к заезду.

Решение

Это можно сделать за 7 забегов.
Разбиваем на 5 групп по пять лошадей. Проводим 5 забегов (по одному на группу).
Из победителей в каждой группе формируем шестой забег. Победитель шестого забега - топ 1.
Формируем седьмой забег из:
1) Второго и третьего места из шестого забега.
2) Второго и третьего места из группы (группа в числе изначальных 5 забегов), из которой победитель шестого забега.
3) Второго места из группы (группа в числе изначальных 5 забегов), из которой лошадь, занявшая второе место в шестом забеге.

Победитель седьмего забега - топ 2, второе место в седьмом забеге - топ 3.

Код проверки

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        boolean debugMode = false;
        int numberOfSimulations = 1000_000;

        for (int simulation = 0; simulation < numberOfSimulations; simulation++) {

            if (simulation % 100000 == 0) {
                System.out.println("Simulation number " + simulation);
            }

            simulate(debugMode);
        }
        System.out.println("No mismatches found, all " + numberOfSimulations + " passed!");
    }

    private static void simulate(boolean debugMode) {
        List<Horse> horses = Horses.init();
        if (debugMode) {
            System.out.println("Initial horses:" + horses);
        }
        List<HorseRace> horseRaces = Horses.splitIntoFiveGroups(horses);
        if (debugMode) {
            System.out.println("Five Groups: " + horseRaces);
        }
        horseRaces.forEach(HorseRace::race);
        if (debugMode) {
            System.out.println("Five Groups After Five Races: " + horseRaces);
        }
        HorseRace sixRace = Horses.getWinnersToFormSixRace(horseRaces);
        if (debugMode) {
            System.out.println("Six Race Before: " + sixRace);
        }
        sixRace.race();
        if (debugMode) {
            System.out.println("Six Race After: " + sixRace);
        }
        Map<Horse, HorseRace> horsesToInitialFiveRaces = Horses.indexHorsesToInitialFiveRaces(horseRaces);
        HorseRace sevenRace = new HorseRace();
        sevenRace.add(sixRace.getSecond());
        sevenRace.add(sixRace.getThird());
        HorseRace raceOfWinnerOfSixRace = horsesToInitialFiveRaces.get(sixRace.getWinner());
        sevenRace.add(raceOfWinnerOfSixRace.getSecond());
        sevenRace.add(raceOfWinnerOfSixRace.getThird());
        HorseRace raceOfSecondOfSixRace = horsesToInitialFiveRaces.get(sixRace.getSecond());
        sevenRace.add(raceOfSecondOfSixRace.getSecond());

        if (debugMode) {
            System.out.println("Seven Race Before: " + sevenRace);
        }
        sevenRace.race();
        if (debugMode) {
            System.out.println("Seven Race After: " + sevenRace);
        }

        List<Horse> identifiedTopThreeBySevenRaces = new ArrayList<>();
        identifiedTopThreeBySevenRaces.add(sixRace.getWinner());
        identifiedTopThreeBySevenRaces.add(sevenRace.getWinner());
        identifiedTopThreeBySevenRaces.add(sevenRace.getSecond());
        List<Horse> expectedTopThree = Horses.copySortAndGetTopThree(horses);
        if (debugMode) {
            System.out.println("Expected top three horses:" + expectedTopThree);
        }
        if (debugMode) {
            System.out.println("identifiedTopThreeBySevenRaces: " + identifiedTopThreeBySevenRaces);
        }

        if (!identifiedTopThreeBySevenRaces.equals(expectedTopThree)) {
            System.out.println("Mismatch found!");
            System.out.println("Expected top three horses:" + expectedTopThree);
            System.out.println("identifiedTopThreeBySevenRaces: " + identifiedTopThreeBySevenRaces);
            throw new RuntimeException("Mismatch found!");
        }
    }
}

class Horses {
    public static List<Horse> init() {
        List<Integer> raceTimes = new ArrayList<>(
                IntStream.range(0, 25)
                        .map(index -> index * 100)
                        .boxed()
                        .toList());
        Collections.shuffle(raceTimes);
        return IntStream.range(0, 25)
                .mapToObj(index -> new Horse(index, raceTimes.get(index)))
                .collect(Collectors.toList());
    }
    public static List<Horse> copySortAndGetTopThree(List<Horse> horses) {
        return horses.stream()
                .map(Horse::new)
                .sorted()
                .limit(3)
                .toList();
    }

    public static List<HorseRace> splitIntoFiveGroups(List<Horse> horses) {
        List<HorseRace> horseRaces = new ArrayList<>();
        for (int i = 0; i < horses.size(); i += 5) {
            HorseRace race = new HorseRace();
            for (int j = i; j < i + 5; j++) {
                race.add(horses.get(j));
            }
            horseRaces.add(race);
        }
        return horseRaces;
    }

    public static HorseRace getWinnersToFormSixRace(List<HorseRace> horseRaces) {
        return new HorseRace(
                horseRaces.stream()
                        .map(HorseRace::getWinner)
                        .collect(Collectors.toList()));
    }

    public static Map<Horse, HorseRace> indexHorsesToInitialFiveRaces(List<HorseRace> horseRaces) {
        Map<Horse, HorseRace> index = new HashMap<>();
        for (HorseRace horseRace : horseRaces) {
            for (Horse horse : horseRace.getHorses()) {
                index.put(horse, horseRace);
            }
        }
        return index;
    }
}

class Horse implements Comparable<Horse> {
    private final int index;
    private final int raceTime;

    public Horse(int index, int raceTime) {
        this.index = index;
        this.raceTime = raceTime;
    }

    public Horse(Horse horse) {
        this.index = horse.index;
        this.raceTime = horse.raceTime;
    }

    @Override
    public String toString() {
        return "Horse{" +
                "index=" + index +
                ", raceTime=" + raceTime +
                '}';
    }

    @Override
    public int compareTo(Horse horse) {
        return this.raceTime - horse.raceTime;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Horse horse = (Horse) o;
        return index == horse.index && raceTime == horse.raceTime;
    }

    @Override
    public int hashCode() {
        return Objects.hash(index, raceTime);
    }
}

class HorseRace {
    private final List<Horse> horses;

    public HorseRace() {
        this.horses = new ArrayList<>();
    }

    public HorseRace(List<Horse> horses) {
        this.horses = horses;
    }

    public void add(Horse horse) {
        if (this.horses.size() >= 5) {
            throw new IllegalArgumentException("Number of horses in a race is limited by 5");
        }
        this.horses.add(horse);
    }

    public List<Horse> getHorses() {
        return this.horses;
    }

    public void race() {
        Collections.sort(horses);
    }

    public Horse getWinner() {
        return horses.getFirst();
    }

    public Horse getSecond() {
        return horses.get(1);
    }

    public Horse getThird() {
        return horses.get(2);
    }

    @Override
    public String toString() {
        return "HorseRace{" +
                "horses=" + horses +
                '}';
    }
}

Второй, немного измененный, вариант, где время забега не целое уникальное число, а случайное вещественное число:

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        boolean debugMode = false;
        int numberOfSimulations = 1000_000;

        for (int simulation = 0; simulation < numberOfSimulations; simulation++) {

            if (simulation % 100000 == 0) {
                System.out.println("Simulation number " + simulation);
            }

            simulate(debugMode);
        }
        System.out.println("No mismatches found, all " + numberOfSimulations + " passed!");
    }

    private static void simulate(boolean debugMode) {
        List<Horse> horses = Horses.init();
        if (debugMode) {
            System.out.println("Initial horses:" + horses);
        }
        List<HorseRace> horseRaces = Horses.splitIntoFiveGroups(horses);
        if (debugMode) {
            System.out.println("Five Groups: " + horseRaces);
        }
        horseRaces.forEach(HorseRace::race);
        if (debugMode) {
            System.out.println("Five Groups After Five Races: " + horseRaces);
        }
        HorseRace sixRace = Horses.getWinnersToFormSixRace(horseRaces);
        if (debugMode) {
            System.out.println("Six Race Before: " + sixRace);
        }
        sixRace.race();
        if (debugMode) {
            System.out.println("Six Race After: " + sixRace);
        }
        Map<Horse, HorseRace> horsesToInitialFiveRaces = Horses.indexHorsesToInitialFiveRaces(horseRaces);
        HorseRace sevenRace = new HorseRace();
        sevenRace.add(sixRace.getSecond());
        sevenRace.add(sixRace.getThird());
        HorseRace raceOfWinnerOfSixRace = horsesToInitialFiveRaces.get(sixRace.getWinner());
        sevenRace.add(raceOfWinnerOfSixRace.getSecond());
        sevenRace.add(raceOfWinnerOfSixRace.getThird());
        HorseRace raceOfSecondOfSixRace = horsesToInitialFiveRaces.get(sixRace.getSecond());
        sevenRace.add(raceOfSecondOfSixRace.getSecond());

        if (debugMode) {
            System.out.println("Seven Race Before: " + sevenRace);
        }
        sevenRace.race();
        if (debugMode) {
            System.out.println("Seven Race After: " + sevenRace);
        }

        List<Horse> identifiedTopThreeBySevenRaces = new ArrayList<>();
        identifiedTopThreeBySevenRaces.add(sixRace.getWinner());
        identifiedTopThreeBySevenRaces.add(sevenRace.getWinner());
        identifiedTopThreeBySevenRaces.add(sevenRace.getSecond());
        List<Horse> expectedTopThree = Horses.copySortAndGetTopThree(horses);
        if (debugMode) {
            System.out.println("Expected top three horses:" + expectedTopThree);
        }
        if (debugMode) {
            System.out.println("identifiedTopThreeBySevenRaces: " + identifiedTopThreeBySevenRaces);
        }

        if (!identifiedTopThreeBySevenRaces.equals(expectedTopThree)) {
            System.out.println("Mismatch found!");
            System.out.println("Expected top three horses:" + expectedTopThree);
            System.out.println("identifiedTopThreeBySevenRaces: " + identifiedTopThreeBySevenRaces);
            throw new RuntimeException("Mismatch found!");
        }
    }
}

class Horses {
    public static List<Horse> init() {
        Random random = new Random();
        return IntStream.range(0, 25)
                .mapToObj(index -> new Horse(index, random.nextDouble()))
                .collect(Collectors.toList());
    }
    public static List<Horse> copySortAndGetTopThree(List<Horse> horses) {
        return horses.stream()
                .map(Horse::new)
                .sorted()
                .limit(3)
                .toList();
    }

    public static List<HorseRace> splitIntoFiveGroups(List<Horse> horses) {
        List<HorseRace> horseRaces = new ArrayList<>();
        for (int i = 0; i < horses.size(); i += 5) {
            HorseRace race = new HorseRace();
            for (int j = i; j < i + 5; j++) {
                race.add(horses.get(j));
            }
            horseRaces.add(race);
        }
        return horseRaces;
    }

    public static HorseRace getWinnersToFormSixRace(List<HorseRace> horseRaces) {
        return new HorseRace(
                horseRaces.stream()
                        .map(HorseRace::getWinner)
                        .collect(Collectors.toList()));
    }

    public static Map<Horse, HorseRace> indexHorsesToInitialFiveRaces(List<HorseRace> horseRaces) {
        Map<Horse, HorseRace> index = new HashMap<>();
        for (HorseRace horseRace : horseRaces) {
            for (Horse horse : horseRace.getHorses()) {
                index.put(horse, horseRace);
            }
        }
        return index;
    }
}

class Horse implements Comparable<Horse> {
    private final int index;
    private final double raceTime;

    public Horse(int index, double raceTime) {
        this.index = index;
        this.raceTime = raceTime;
    }

    public Horse(Horse horse) {
        this.index = horse.index;
        this.raceTime = horse.raceTime;
    }

    @Override
    public String toString() {
        return "Horse{" +
                "index=" + index +
                ", raceTime=" + raceTime +
                '}';
    }

    @Override
    public int compareTo(Horse horse) {
        return Double.compare(this.raceTime, horse.raceTime);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Horse horse = (Horse) o;
        return index == horse.index;
    }

    @Override
    public int hashCode() {
        return Objects.hash(index);
    }
}

class HorseRace {
    private final List<Horse> horses;

    public HorseRace() {
        this.horses = new ArrayList<>();
    }

    public HorseRace(List<Horse> horses) {
        this.horses = horses;
    }

    public void add(Horse horse) {
        if (this.horses.size() >= 5) {
            throw new IllegalArgumentException("Number of horses in a race is limited by 5");
        }
        this.horses.add(horse);
    }

    public List<Horse> getHorses() {
        return this.horses;
    }

    public void race() {
        Collections.sort(horses);
    }

    public Horse getWinner() {
        return horses.getFirst();
    }

    public Horse getSecond() {
        return horses.get(1);
    }

    public Horse getThird() {
        return horses.get(2);
    }

    @Override
    public String toString() {
        return "HorseRace{" +
                "horses=" + horses +
                '}';
    }
}