0xMonaco 3rd Place Implementation

Car3.sol

// SPDX-License-Identifier: MIT
pragma solidity 0.8.13;

import "./Truck.sol";

contract Car3 is Truck {
    // constants from Monaco
    uint internal constant FINISH_DISTANCE = 1000;

    constructor(Monaco _monaco) Truck(_monaco) {}

    function takeYourTurn(Monaco.CarData[] calldata allCars, uint256 ourCarIndex) external override onlyMonaco {
        if (handleFirstTurn(allCars, ourCarIndex)) return;
        if (handleFinish(allCars, ourCarIndex)) return;
        // if (handleAdvanced(allCars, ourCarIndex)) return;
        uint budget = calcBudget(allCars, ourCarIndex);
        budget -= shellIfEconomical(allCars, ourCarIndex, budget);
        accelerate(budget);
    }

    function handleFirstTurn(Monaco.CarData[] calldata allCars, uint256 ourCarIndex) internal returns (bool) {
        if (allCars[ourCarIndex].speed > 0) return false;
        monaco.buyAcceleration(1);
        return true;
    }

    function handleFinish(Monaco.CarData[] calldata allCars, uint256 ourCarIndex) internal returns (bool) {
        if (allCars[0].y < 900) return false;

        // uint maxAcceleration = getMaxAcceleration(allCars[ourCarIndex].balance);


        State memory s = createState(allCars);
        // uint turnsUntilNextMove = calcTurnsUntilNextMove(s, allCars, ourCarIndex);
        // shellIfEmergency(allCars, ourCarIndex, turnsUntilNextMove);

        uint[3] memory turnsToWin = simulateFuture(s, allCars, ourCarIndex);

        uint myTurnsToWin = turnsToWin[ourCarIndex];
        bool canFinishImmediately = myTurnsToWin == 1 || (myTurnsToWin == 2 && calcTurnsUntilNextMove(s, allCars, ourCarIndex) == 1);

        bool goAllIn = canFinishImmediately;

        uint budget = allCars[ourCarIndex].balance;
        if (ourCarIndex > 0 && turnsToWin[ourCarIndex - 1] != 0) {
            goAllIn = true;
            if (!canFinishImmediately || myTurnsToWin >= turnsToWin[ourCarIndex - 1]) {
                try monaco.buyShell(1) returns (uint256 cost) { budget -= cost; } catch {}
            }
        }
        if (turnsToWin[(ourCarIndex + 1) % 3] != 0 || turnsToWin[(ourCarIndex + 2) % 3] != 0) goAllIn = true;

        if (goAllIn) {
            accelerate(budget);
            return true;
        }
        return false;
    }

    function handleAdvanced(Monaco.CarData[] calldata allCars, uint256 ourCarIndex) internal returns (bool) {
        if (allCars[0].y < 700 || ourCarIndex != 2) return false;

        uint[2] memory turnsToFinish;
        for (uint i = 0; i < 2; i++) {
            turnsToFinish[i] = (1000 - allCars[i].y) / allCars[i].speed;
        }
        uint minTurnsToFinish = turnsToFinish[0] < turnsToFinish[1] ? turnsToFinish[0] : turnsToFinish[1];

        uint budget = 3 * allCars[2].balance / minTurnsToFinish;
        if (budget > allCars[2].balance) budget = allCars[2].balance;
        uint alternativeBudget = calcBudget(allCars, ourCarIndex);
        if (alternativeBudget > budget) budget = alternativeBudget;

        if (allCars[1].speed > 1 && monaco.getShellCost(1) <= budget) budget -= monaco.buyShell(1);
        accelerate(budget);
    }

    function simulateFuture(State memory s, Monaco.CarData[] calldata allCars, uint256 ourCarIndex) internal returns (uint[3] memory turnsToWin) {
        uint[3] memory maxSpeeds = [uint(allCars[0].speed), uint(allCars[1].speed), uint(allCars[2].speed)];
        uint[3] memory maxYs = [uint(allCars[0].y), uint(allCars[1].y), uint(allCars[2].y)];
        uint[3] memory invertedOrder = invertOrder(s.batchOrder);
        uint[3] memory nextInvertedOrder = invertOrder(s.nextBatchOrder);
        bool[3] memory didAccelerate;
        uint turnCount = 0;
        for (uint turn = invertedOrder[ourCarIndex]; turn < 3 + nextInvertedOrder[ourCarIndex]; turn++) {
            turnCount++;
            uint i = turn < 3 ? s.batchOrder[turn] : s.nextBatchOrder[turn - 3];
            if (!didAccelerate[i]) {
                didAccelerate[i] = true;
                maxSpeeds[i] += getMaxAcceleration(allCars[i].balance);
            }
            if (i != ourCarIndex) {
                uint iOther = 3 - ourCarIndex - i;
                if (maxYs[ourCarIndex] > maxYs[i] && (maxYs[iOther] > maxYs[ourCarIndex] || maxYs[iOther] <= maxYs[i])) maxSpeeds[ourCarIndex] = 1;
            }
            for (uint j = 0; j < 3; j++) {
                if (maxYs[j] >= 1000) continue;
                maxYs[j] += maxSpeeds[j];
                if (maxYs[j] >= 1000) turnsToWin[j] = turnCount;
            }
        }
    }

    function invertOrder(uint[3] memory order) internal returns (uint[3] memory invertedOrder) {
        for (uint i = 0; i < 3; i++) {
            invertedOrder[order[i]] = i;
        }
    }

    function calcTurnsUntilNextMove(State memory s, Monaco.CarData[] calldata allCars, uint256 ourCarIndex) internal pure returns (uint) {
        uint turnsRemaining = s.batchOrder[0] == ourCarIndex ? 3 : (s.batchOrder[1] == ourCarIndex ? 2 : 1);
        turnsRemaining += s.nextBatchOrder[0] == ourCarIndex ? 0 : (s.batchOrder[1] == ourCarIndex ? 1 : 2);
        return turnsRemaining;
    }

    function createState(Monaco.CarData[] calldata allCars) internal returns (State memory s) {
        s.turns = monaco.turns() - 1;
        // require(!irregularTurns(s));
        setBatchOrder(s, [allCars[0].car, allCars[1].car]);
        setNextBatchOrder(s);
    }

    function calcBudget(Monaco.CarData[] calldata allCars, uint256 ourCarIndex) internal pure returns (uint budget) {
        (uint b1, uint b2) = (allCars[(ourCarIndex + 1) % 3].balance, allCars[(ourCarIndex + 2) % 3].balance);
        uint maxEnemyBalance = b1 >= b2 ? b1 : b2;
        uint myBalance = allCars[ourCarIndex].balance;
        if (myBalance > maxEnemyBalance) budget = myBalance - maxEnemyBalance;
    }

    function shellIfEconomical(Monaco.CarData[] calldata allCars, uint256 ourCarIndex, uint budget) internal returns (uint spent) {
        if (ourCarIndex == 0) return 0;
        uint targetSpeed = allCars[ourCarIndex - 1].speed;
        if (targetSpeed <= 1) return 0;
        uint shellCost = monaco.getShellCost(1);
        if (shellCost > budget) return 0;
        uint costInflicted = monaco.getAccelerateCost(targetSpeed - 1);
        if (costInflicted < shellCost * 2) return 0;
        return monaco.buyShell(1);
    }

    function accelerate(uint budget) internal {
        uint amount = getMaxAcceleration(budget);
        if (amount == 0) return;
        monaco.buyAcceleration(amount);
    }

    function getMaxAcceleration(uint budget) internal returns (uint) {
        uint amount = 0;
        while (monaco.getAccelerateCost(amount + 1) <= budget) amount++;
        return amount;
    }
}

Truck.sol

// SPDX-License-Identifier: MIT
pragma solidity 0.8.13;

import "./Car.sol";

abstract contract Truck is Car {
    struct State {
        uint turns;
        uint[3] batchOrder;
        uint[3] nextBatchOrder;
    }

    uint8 myTurns = 0;

    constructor(Monaco _monaco) Car(_monaco) {}

    modifier onlyMonaco() {
        require(msg.sender == address(monaco));
        _;
    }

    function setBatchOrder(State memory s, Car[2] memory sortedCars) internal view {
        Car[2] memory orderedCars = [monaco.cars(1), monaco.cars(2)];
        uint ioLeft = 3;
        for (uint i = 0; i < 2; i++) {
            uint io = 0;
            for (; io < 2; io++) {
                if (orderedCars[io] == sortedCars[i]) break;
            }
            s.batchOrder[io] = i;
            ioLeft -= io;
        }
        s.batchOrder[ioLeft] = 2;
    }

    function setNextBatchOrder(State memory s) internal view {
        s.nextBatchOrder = [s.batchOrder[2], s.batchOrder[0], s.batchOrder[1]];
        uint72 entropy = monaco.entropy();
        for (uint io = 0; io < 3; ++io) {
            entropy = uint72(uint(keccak256(abi.encode(entropy))));
            uint io2 = io + (entropy % (3 - io));
            uint temp = s.nextBatchOrder[io];
            s.nextBatchOrder[io] = s.nextBatchOrder[io2];
            s.nextBatchOrder[io2] = temp;
        }
        s.nextBatchOrder = [s.nextBatchOrder[1], s.nextBatchOrder[2], s.nextBatchOrder[0]];
    }

    function irregularTurns(State memory s) internal returns (bool) {
        return s.turns / 3 == (myTurns += 1);
    }
}