Skip to content

Instantly share code, notes, and snippets.

@adietrichs
Created August 22, 2022 00:57
Show Gist options
  • Save adietrichs/3668b877c38225f6ddeb436e65868481 to your computer and use it in GitHub Desktop.
Save adietrichs/3668b877c38225f6ddeb436e65868481 to your computer and use it in GitHub Desktop.
0xMonaco 3rd Place Implementation
// 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;
}
}
// 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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment