GTA 5 MAX INT Billionaire

main.py

import heapq
from collections import defaultdict
from dataclasses import dataclass, field
from enum import Enum, auto


class Step(Enum):
    A = auto()
    B = auto()
    C = auto()


@dataclass
class Billionaire:
    stop_condition: int
    time: int = 0
    money: int = 0
    glitch_gain: int = 0
    steps: list[Step] = field(default_factory=list)

    @property
    def is_stop_condition_met(self) -> bool:
        return self.money >= self.stop_condition

    def repr_without_steps(self) -> str:
        return (
            f"Billionaire(time={self.time}, money={self.money}"
            f", glitch_gain={self.glitch_gain})"
        )

    def repr_with_steps(self) -> str:
        # Steps use keys from the Step enum
        steps_str = ", ".join([step.name for step in self.steps])
        return (
            f"Billionaire(time={self.time}, money={self.money}"
            f", glitch_gain={self.glitch_gain}, steps={steps_str})"
        )

    def perform_a(self) -> "Billionaire":
        return Billionaire(
            stop_condition=self.stop_condition,
            time=self.time + 51,
            money=self.money + 25_000,
            glitch_gain=self.glitch_gain,
            steps=[*self.steps, Step.A],
        )

    def perform_b(self) -> "Billionaire":
        return Billionaire(
            stop_condition=self.stop_condition,
            time=self.time + 120,
            money=self.money,
            glitch_gain=self.money,
            steps=[*self.steps, Step.B],
        )

    def perform_c(self) -> "Billionaire":
        return Billionaire(
            stop_condition=self.stop_condition,
            time=self.time + 18,
            money=self.money + self.glitch_gain,
            glitch_gain=self.glitch_gain,
            steps=[*self.steps, Step.C],
        )

    def __lt__(self, other: "Billionaire") -> bool:
        return self.time < other.time


def calculate(target: int) -> list[Billionaire]:
    initial_state = Billionaire(stop_condition=target)
    priority_queue: list[Billionaire] = [initial_state]
    dp: dict[int, Billionaire | None] = defaultdict(lambda: None)
    max_time: int = 0
    heapq.heapify(priority_queue)
    heapq.heappush(priority_queue, initial_state)
    best_billionaires: list[Billionaire] = [
        Billionaire(stop_condition=target, money=target, time=2**63)
    ]

    while len(priority_queue) > 0:
        current_state = heapq.heappop(priority_queue)
        if current_state.is_stop_condition_met:
            if current_state.time < best_billionaires[0].time:
                best_billionaires = [current_state]
            elif current_state.time == best_billionaires[0].time:
                best_billionaires.append(current_state)
            continue
        if current_state.time > best_billionaires[0].time:
            continue
        a = current_state.perform_a()
        b = current_state.perform_b()
        c = current_state.perform_c() if current_state.glitch_gain > 0 else None
        for new_billionaire in (a, b, c):
            if new_billionaire is None:
                continue
            best_at_time = dp[new_billionaire.time]
            if (
                best_at_time is not None
                and best_at_time.money > new_billionaire.money
                and best_at_time.glitch_gain > new_billionaire.glitch_gain
            ):
                continue

            max_time = max(max_time, new_billionaire.time)
            for i in range(new_billionaire.time, max_time + 1):
                older_billionaire = dp[i]
                if older_billionaire is not None and (
                    older_billionaire.glitch_gain > new_billionaire.glitch_gain
                    or older_billionaire.money > new_billionaire.money
                ):
                    break
                dp[i] = new_billionaire

            heapq.heappush(priority_queue, new_billionaire)
    return best_billionaires


if __name__ == "__main__":
    TARGET_MONEY = 2**31 - 1
    billionaires = calculate(TARGET_MONEY)
    print(f"Number of billionaires: {len(billionaires)}")
    for billionaire in billionaires:
        print(billionaire.repr_with_steps())