Skip to content

Instantly share code, notes, and snippets.

@zhiyb

zhiyb/Makefile

Last active January 1, 2019 13:23
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save zhiyb/8a76fbb8a668f7b81f84855869d63dc1 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save zhiyb/8a76fbb8a668f7b81f84855869d63dc1 to your computer and use it in GitHub Desktop.
Download ZIP
A random Ingress question...
Raw
readme.txt
📝 做题
一个16级agent因为水群被流放到一个孤岛上，岛上只有一个白po。
给他2小时59分钟，只允许他占po，插脚，插mod，毒po，炸脚，画符。
不允许其他任何与游戏相关的操作。
假设那agent手机电池无限大，网络全程顺畅，物资无限，每次画符全对，且速度奖励永远为250ap。
问：2小时59分内最多能拿多少ap？
注：不考虑其他po和其它agent的因素。不考虑爆仓因素。不考虑充能，连link，插薯条，插信标，兑换passcode，上传照片，安利其他agent，注册账号，切换账号等其他所有游戏操作 。不考虑操作本身的时间，只考虑各种操作的cd时间。ap不考虑官方活动加乘系数。该agent全程没有被ban。
Raw
ap.cpp
#include <iostream>
#include <stdexcept>
using std::cout;
using std::endl;
#define MAX_ITERATIONS 128
#define HOUR HOURS
#define HOURS * 60 * 60
#define MINUTE MINUTES
#define MINUTES * 60
#define SECOND SECONDS
#define SECONDS
enum {TimerHack = 0, TimerUnmoddedHack, TimerBurnout, TimerFlip, TimerNum};
typedef enum {ActionDeploy, ActionModVRHS, ActionModVRMH,
ActionFlip, ActionDestroy, ActionHack, ActionNum} action_t;
typedef enum {FactionResistance, FactionEnlightened} faction_t;
typedef enum {ModNone = 0, ModVRHS, ModVRMH} mod_t;
struct portal_t
{
float timer[TimerNum];
int level;
int hack;
faction_t faction;
mod_t mod[2];
};
struct state_t
{
int ap = 0;
float time = 2 HOURS + 59 MINUTES;
faction_t faction = FactionResistance;
portal_t portal[1] = {0};
} init;
static int apMax = 0, timeMax = 0, levelMax = 0;
static action_t action[MAX_ITERATIONS];
const action_t actions[] = {
ActionDeploy, ActionModVRHS, ActionModVRMH,
ActionFlip, ActionDestroy, ActionHack
};
const char *toStr(const action_t action)
{
switch (action) {
case ActionDeploy:
return "Deploy";
case ActionModVRHS:
return "VRHS";
case ActionModVRMH:
return "VRMH";
case ActionFlip:
return "Flip";
case ActionDestroy:
return "Destroy";
case ActionHack:
return "Hack";
}
return "Unknown";
}
const char *toStr(const faction_t faction)
{
return faction == FactionResistance ? "Resistance" : "Enlightened";
}
const char *toStr(const mod_t mod)
{
return mod == ModVRHS ? "VRHS" : mod == ModVRMH ? "VRMH" : "Unknown";
}
void print(const state_t &state)
{
cout << "Status report for " << toStr(state.faction) << ": " << endl;
cout << "\tAP\t" << state.ap << endl;
cout << "\tTime\t" << state.time << endl;
for (auto &portal: state.portal) {
cout << "\tPortal report:" << endl;
cout << "\t\tHack\t" << portal.timer[TimerHack] << endl;
cout << "\t\tBurnout\t" << portal.timer[TimerBurnout] << endl;
cout << "\t\tFlip\t" << portal.timer[TimerFlip] << endl;
cout << "\t\tLevel\t" << portal.level << endl;
cout << "\t\tHackNum\t" << portal.hack << endl;
cout << "\t\tFaction\t" << toStr(portal.faction) << endl;
for (auto mod: portal.mod)
if (mod != ModNone)
cout << "\t\tMod\t" << toStr(mod) << endl;
}
cout << endl;
}
faction_t opposite(faction_t faction)
{
return faction == FactionResistance ? FactionEnlightened
: FactionResistance;
}
// Wait for timers
bool wait(state_t *state, portal_t *portal, float time)
{
if (time > state->time)
return false;
state->time -= time;
for (auto &timer: portal->timer)
if (timer)
timer = std::max(0.f, timer - time);
return true;
}
// Hack portal
bool hack(state_t *state, portal_t *portal)
{
// It's not efficient to hack an uncaptured portal
if (portal->level == 0)
return false;
// Calculate number of hacks before burnout and cool down time
int max = 4;
float cd = 5 MINUTES;
// Subsequent mods are only half effective
int modMH = 1;
float modHS = 1;
for (auto mod: portal->mod)
if (mod == ModVRMH) {
max += 12 / modMH;
modMH = 2;
} else if (mod == ModVRHS) {
cd = cd * (1.0 - 0.7 / modHS);
modHS = 2;
}
// Wait for cool down
if (portal->hack >= max) {
if (!wait(state, portal, portal->timer[TimerBurnout]))
return false;
portal->hack = 0;
}
if (!wait(state, portal, portal->timer[TimerHack]))
return false;
// Apply action and update AP
portal->hack++;
portal->timer[TimerHack] = cd;
portal->timer[TimerUnmoddedHack] = 5 MINUTES;
if (portal->timer[TimerBurnout] == 0)
portal->timer[TimerBurnout] = 4 HOURS;
state->ap += (portal->level == 5 ? 3 : 1) * 50 + 250 +
(portal->faction == state->faction ? 0 : 100);
return true;
}
// Apply action
bool apply(state_t *state, portal_t *portal, action_t action)
{
switch (action)
{
case ActionDeploy: // Capture portal and deploy all resonators
// Check portal faction
if (portal->level != 0)
return false;
// Apply action and update AP
portal->level = 5;
portal->faction = state->faction;
state->ap += 125 * 8 + 500 + 250;
return true;
case ActionModVRHS:
case ActionModVRMH:
// Check portal faction
if (portal->faction != state->faction || portal->level == 0)
return false;
// Find an available mod slot
for (auto &mod: portal->mod) {
if (mod != ModNone)
continue;
// Apply action, update timer and calculate AP
mod = action == ActionModVRHS ? ModVRHS : ModVRMH;
if (action == ActionModVRHS) {
// Heat sink resets hack statistics
portal->hack = 0;
portal->timer[TimerHack] = 0;
portal->timer[TimerBurnout] = 0;
}
state->ap += 125;
return true;
}
// No mod slot available
return false;
case ActionFlip:
// Check portal faction
if (portal->level == 0)
return false;
// Wait for cool down
if (!wait(state, portal, portal->timer[TimerFlip]))
return false;
// Set timer, apply action and calculate AP
portal->timer[TimerFlip] = 1 HOUR;
portal->faction = opposite(portal->faction);
return true;
case ActionDestroy: // Destroy all resonators
// Check portal faction
if (portal->faction == state->faction || portal->level == 0)
return false;
// Recalculate hack cooldown
portal->timer[TimerHack] = portal->timer[TimerUnmoddedHack];
// Apply action and calculate AP
portal->level = 0;
for (auto &mod: portal->mod)
mod = ModNone;
state->ap += 75 * 8;
return true;
case ActionHack:
return hack(state, portal);
};
return false;
}
// Additional constraints
bool constrains(const state_t *state, const portal_t *portal,
const action_t action, const int level)
{
// Filter out some inefficient actions at level 0
if (level == 0 && action != ActionDeploy)
return false;
// It's not efficient to deploy VRHS without Hack first
if (action == ActionModVRHS && portal->hack == 0)
return false;
// It's not efficient to destroy without hack first
if (action == ActionDestroy && portal->hack == 0)
return false;
// It's not efficient to hack before flip to the opposite faction
if (action == ActionFlip && state->faction == portal->faction &&
::action[level - 1] == ActionHack)
return false;
// It's not efficient to hack after flip to the same faction
if (action == ActionHack && state->faction == portal->faction &&
::action[level - 1] == ActionFlip)
return false;
// Always deploy VRMH before hack
if (action == ActionModVRMH && ::action[level - 1] == ActionHack)
return false;
// Always deploy VRMH before VRHS
if (action == ActionModVRMH && ::action[level - 1] == ActionModVRHS)
return false;
return true;
}
// Report all actions and status
void report(int level)
{
cout << "Recursion @ " << level << " / " << levelMax << endl;
state_t state = init;
action_t prev;
int repeat = 0;
float time = state.time;
for (unsigned int i = 0; i < level; i++) {
if (i != 0) {
if (action[i] != prev) {
if (repeat != 1)
cout << " x " << repeat;
if (state.time != time)
cout << " (" << (state.time - time) << ")";
cout << ", ";
time = state.time;
}
repeat++;
}
if (i == 0 || action[i] != prev) {
cout << toStr(action[i]);
repeat = 1;
}
prev = action[i];
// Apply action after time print
apply(&state, &state.portal[0], action[i]);
}
if (repeat)
cout << " x " << repeat;
if (state.time != time)
cout << " (" << (state.time - time) << ")";
cout << endl;
print(state);
}
// Recursively try different actions
void recursion(const state_t &state, const int level)
{
if (level >= MAX_ITERATIONS)
throw std::runtime_error("Insufficient recursion level");
else if (level > levelMax)
levelMax = level;
// Recursively try different actions
bool end = true;
for (auto action: actions) {
// Check for additional constraints
if (!constrains(&state, &state.portal[0], action, level))
continue;
// Try to apply the action
state_t tmp = state;
if (!apply(&tmp, &tmp.portal[0], action))
continue;
if (level < 0) {
// For debugging
cout << " Action: " << toStr(action) << endl;
print(tmp);
}
// Record the action then recurse to the next level
::action[level] = action;
recursion(tmp, level + 1);
end = false;
}
// Report status if no more action possible
if (!end)
return;
if (state.ap >= apMax) {
apMax = state.ap;
timeMax = state.time;
report(level);
}
}
int main()
{
cout << "Initial state:" << endl;
print(init);
recursion(init, 0);
cout << "Maximum AP: " << apMax << endl;
return 0;
}
Raw
Makefile
SHELL := /bin/bash
.PHONY: run
run: ap
time ./$<
ap: ap.o
$(CXX) -o $@ $^ -O3
%.o: %.cpp
$(CXX) -o $@ -c $^ -O3
clean:
rm ap ap.o
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment