code. compile. run. debug. share.
#include <bits/stdc++.h>
#include "useful.h"
using namespace std;
// ------- Constants -------------------------------------------------------
const int maxTime = 26;
enum Actor {ME, ELEPHANT};
// ------ Classes ----------------------------------------------------------
class StateActor
{
public:
string node = "";
int minutes = 0;
StateActor();
StateActor(string, int);
void print();
};
class State
{
public:
StateActor me;
StateActor elephant;
list<string> isOpen;
int releasedPressure = 0;
State();
State(StateActor, StateActor);
State(StateActor, StateActor, list<string>, int);
void print();
void move(StateActor, Actor);
void setVisited();
bool isVisited();
bool imposible();
};
// ----- Globals ----------------------------------------------------------
bool trace = true;
bool test;
map<string, pair<int, list<string>>> nodes;
priority_queue<State> myQ;
list<tuple<string, string, int>> visited;
int noValves = 0;
map<int, string> valves;
map<string, int> valveNo;
map<string, int> releases;
int dist[15][15];
int maxFlow = 0;
// ------------------------------------------------------------------------
StateActor::StateActor(string str, int i)
{
node = str;
minutes = i;
}
StateActor::StateActor()
{
}
void StateActor::print()
{
cout << "Node: " << node << " minutes: " << minutes << endl;
}
// ------------------------------------------------------------------------
State::State()
{
}
State::State(StateActor actor1, StateActor actor2, list<string> inList, int num1)
{
me = actor1;
elephant = actor2;
releasedPressure = num1;
isOpen = inList;
}
State::State(StateActor actor1, StateActor actor2)
{
me = actor1;
elephant = actor2;
}
bool State::isVisited()
{
for (auto x: visited)
{
string visitedMe = get<0>(x);
if (visitedMe == me.node)
{
string visitedElephant = get<1>(x);
if (visitedElephant == elephant.node)
{
int visitedReleased = get<2>(x);
if (visitedReleased == releasedPressure)
{
return true;
}
}
}
}
return false;
}
void State::setVisited()
{
tuple<string, string, int> temp = {me.node, elephant.node, releasedPressure};
visited.push_back(temp);
}
void State::print()
{
cout << "Me: "; me.print();
cout << "Elephant: "; elephant.print();
cout << "releasedPressure: " << releasedPressure << endl;
cout << "Is open: ";
for (auto x: isOpen)
{
cout << x << " ";
}
cout << endl;
}
bool operator<(const State& p1, const State& p2)
{
return p1.releasedPressure < p2.releasedPressure;
}
int getDistance(string first, string second)
{
int firstNode = valveNo[first];
int secondNode = valveNo[second];
int distance = dist[firstNode][secondNode];
return distance;
}
bool member(list<string> strList, string str)
{
for (auto x: strList)
{
if (x == str)
{
return true;
}
}
return false;
}
bool State::imposible()
{
map<int, int> marginal;
for (int i = 0; i <= 26; i++)
{
if (i == 0)
{
marginal[i] = 0;
}
else if (i == 1)
{
marginal[i] = 9;
}
else
{
marginal[i] = i * 9 + marginal[i - 1];
}
}
if ((releasedPressure + marginal[26 - me.minutes]) < maxFlow)
{
return true;
}
if ((releasedPressure + marginal[26 - elephant.minutes]) < maxFlow)
{
return true;
}
return false;
}
void State::move(StateActor currActor, Actor actor)
{
string currNode = currActor.node;
for (auto x: valves)
{
string nextNode = x.second;
if ((currNode != nextNode) && (nextNode != "AA"))
{
if (!member(isOpen, nextNode))
{
int distance = getDistance(currNode, nextNode);
int nextMinute = currActor.minutes + distance + 1;
if (nextMinute <= maxTime)
{
StateActor newStateActor = {nextNode, nextMinute};
list<string> newOpen = isOpen;
newOpen.push_back(nextNode);
int newReleasedPressure = releasedPressure + ((maxTime - nextMinute) * releases[nextNode]);
State currState;
if (actor == ME)
{
currState = State(newStateActor, elephant, newOpen, newReleasedPressure);
}
else
{
currState = State(me, newStateActor, newOpen, newReleasedPressure);
}
if (newReleasedPressure > maxFlow)
{
maxFlow = newReleasedPressure;
cout << "Max flow: " << maxFlow << endl;
currState.print();
}
if (!currState.imposible())
{
currState.setVisited();
myQ.push(currState);
}
}
}
}
}
}
// ------------------------------------------------------------------------
void releasePressure()
{
StateActor me = StateActor("AA", 0);
StateActor elephant = StateActor("AA", 0);
State state = State(me, elephant);
myQ.push(state);
state.setVisited();
while (!myQ.empty())
{
State currState = myQ.top();
myQ.pop();
State tempState = currState;
tempState.move(tempState.me, ME);
tempState = currState;
tempState.move(tempState.elephant, ELEPHANT);
}
}
int main ()
{
test = false;
trace = false;
cout << "Starting " << endl;
prepare();
releasePressure();
cout << "Finished " << endl;
return 0;
}
Valve XG has flow rate=0; tunnels lead to valves CR, OH
Valve ZF has flow rate=7; tunnels lead to valves SC, BY, PM, LW, CJ
Valve RD has flow rate=13; tunnels lead to valves JS, VM
Valve XJ has flow rate=0; tunnels lead to valves JO, YO
Valve CJ has flow rate=0; tunnels lead to valves UA, ZF
Valve UA has flow rate=0; tunnels lead to valves ZP, CJ
Valve EQ has flow rate=0; tunnels lead to valves ZP, RP
Valve IU has flow rate=0; tunnels lead to valves EV, CN
Valve QM has flow rate=0; tunnels lead to valves XA, CN
Valve WC has flow rate=0; tunnels lead to valves JS, OH
Valve MU has flow rate=0; tunnels lead to valves AA, ZP
Valve MW has flow rate=11; tunnels lead to valves BM, AG, RG, NL
Valve XA has flow rate=0; tunnels lead to valves JO, QM
Valve OH has flow rate=12; tunnels lead to valves WC, YS, XG, KO
Valve QD has flow rate=20; tunnels lead to valves BY, KY, CR, RP
Valve OE has flow rate=0; tunnels lead to valves FB, BU
Valve CB has flow rate=0; tunnels lead to valves AA, FX
Valve TB has flow rate=23; tunnel leads to valve VM
Valve PM has flow rate=0; tunnels lead to valves ZF, AA
Valve YS has flow rate=0; tunnels lead to valves OH, RG
Valve KO has flow rate=0; tunnels lead to valves OH, VT
Valve AA has flow rate=0; tunnels lead to valves PM, MU, BM, AW, CB
Valve RG has flow rate=0; tunnels lead to valves YS, MW
Valve BU has flow rate=0; tunnels lead to valves OE, EV
Valve RK has flow rate=0; tunnels lead to valves KY, FX
Valve JO has flow rate=18; tunnels lead to valves NL, SX, XA, XJ
Valve AG has flow rate=0; tunnels lead to valves IS, MW
Valve AW has flow rate=0; tunnels lead to valves BS, AA
Valve ZP has flow rate=9; tunnels lead to valves UA, NG, DU, MU, EQ
Valve KY has flow rate=0; tunnels lead to valves QD, RK
Valve EV has flow rate=19; tunnels lead to valves VT, BU, IU, SX
Valve FB has flow rate=24; tunnel leads to valve OE
Valve DU has flow rate=0; tunnels lead to valves IS, ZP
Valve NG has flow rate=0; tunnels lead to valves FX, ZP
Valve HC has flow rate=0; tunnels lead to valves CN, HB
Valve SC has flow rate=0; tunnels lead to valves IS, ZF
Valve HB has flow rate=22; tunnel leads to valve HC
Valve VM has flow rate=0; tunnels lead to valves RD, TB
Valve LW has flow rate=0; tunnels lead to valves ZF, FX
Valve SX has flow rate=0; tunnels lead to valves EV, JO
Valve FX has flow rate=6; tunnels lead to valves FA, NG, RK, LW, CB
Valve JS has flow rate=0; tunnels lead to valves WC, RD
Valve BM has flow rate=0; tunnels lead to valves MW, AA
Valve FA has flow rate=0; tunnels lead to valves IS, FX
Valve RP has flow rate=0; tunnels lead to valves QD, EQ
Valve NL has flow rate=0; tunnels lead to valves MW, JO
Valve CN has flow rate=15; tunnels lead to valves HC, QM, IU
Valve BS has flow rate=0; tunnels lead to valves IS, AW
Valve KP has flow rate=25; tunnel leads to valve YO
Valve YO has flow rate=0; tunnels lead to valves XJ, KP
Valve CR has flow rate=0; tunnels lead to valves XG, QD
Valve BY has flow rate=0; tunnels lead to valves QD, ZF
Valve IS has flow rate=5; tunnels lead to valves DU, SC, AG, FA, BS
Valve VT has flow rate=0; tunnels lead to valves KO, EV
Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
Valve BB has flow rate=13; tunnels lead to valves CC, AA
Valve CC has flow rate=2; tunnels lead to valves DD, BB
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
Valve EE has flow rate=3; tunnels lead to valves FF, DD
Valve FF has flow rate=0; tunnels lead to valves EE, GG
Valve GG has flow rate=0; tunnels lead to valves FF, HH
Valve HH has flow rate=22; tunnel leads to valve GG
Valve II has flow rate=0; tunnels lead to valves AA, JJ
Valve JJ has flow rate=21; tunnel leads to valve II
#ifndef USEFUL_H
#define USEFUL_H
#include <bits/stdc++.h>
using namespace std;
extern bool test;
extern map<string, pair<int, list<string>>> nodes;
extern int noValves;
extern map<int, string> valves;
extern map<string, int> valveNo;
extern map<string, int> releases;
extern int dist[15][15];
void error(string str1, string str2, int num);
void error(string str1, string str2, string str3);
void paus();
void readInput();
void init();
void readInput();
void buildGraph();
void printGraph();
void countNoValves();
void print(map<string, bool>);
void buildCompactGrah();
void prepare();
#endif
#include "useful.h"
string inFileName;
map<int, string> code;
void readRow(int rowNo, string row)
{
char chr; int num; string str;
stringstream ss = stringstream(row);
code[rowNo] = row;
}
void printInput()
{
cout << "Read input: " << endl;
for (auto x: code)
{
cout << x.first << ": " << x.second << endl;
}
}
void init()
{
if (test)
{
inFileName = "Test.txt";
}
else
{
inFileName = "Input.txt";
}
}
void printGraph()
{
for (auto x: nodes)
{
cout << "Valve " << x.first << " has flow rate " << x.second.first << ", tunnels lead to valves ";
for (auto tunnel: x.second.second)
{
cout << tunnel << ", ";
}
cout << endl;
}
cout << endl;
}
string buildNode(string str)
{
stringstream ss(str);
string str1;
char chr;
int num;
ss >> str1 >> str1;
string name = str1;
ss >> str1 >> str1 >> chr >> chr >> chr >> chr >> chr >> num;
int flow = num;
ss >> chr >> str1 >> str1 >> str1 >> str1;
list<string> adj;
char chr1, chr2;
while (ss >> chr1 >> chr2)
{
string nodeName = "";
nodeName = nodeName + chr1 + chr2;
adj.push_back(nodeName);
ss >> chr;
}
pair<int, list<string>> nodeContents = {flow, adj};
nodes[name] = nodeContents;
return name;
}
void buildGraph()
{
for (auto x: code)
{
buildNode(x.second);
}
}
void error(string str1, string str2, int num)
{
cout << "Error in " << str1 << ": " << str2 << ": " << num << endl;
exit(1);
}
void error(string str1, string str2, string str3)
{
cout << "Error in " << str1 << ": " << str2 << ": " << str3 << endl;
exit(1);
}
void paus()
{
cout << "Press return to continue" << endl;
cin.get();
}
void readRow(int, string);
void readInput()
{
string rowString;
int rowNo = 0;
ifstream inFile(inFileName);
if (inFile)
{
while (getline(inFile, rowString))
{
readRow(rowNo, rowString);
rowNo++;
}
}
else
{
error("readInput", "file not found", inFileName);
}
inFile.close();
}
void countNoValves()
{
for (auto x: nodes)
{
if (x.second.first)
{
releases[x.first] = x.second.first;
noValves++;
}
}
}
void print(map<string, bool> list)
{
for (auto x: list)
{
cout << x.first << " ";
}
cout << endl;
}
bool isVisited(pair<string, int> node, map<pair<string, int>, bool> visited)
{
for (auto x: visited)
{
if (x.first == node)
{
return x.second;
}
}
return false;
}
void setVisited(pair<string, int> node, map<pair<string, int>, bool> &visited)
{
visited[node] = true;
}
int countDistance(string first, string end)
{
queue<pair<string, int>> Q = {};
map<pair<string, int>, bool> visited;
pair<string, int> node = {first, 0};
Q.push(node);
setVisited(node, visited);
while (!Q.empty())
{
node = Q.front();
Q.pop();
if (node.first == end)
{
return node.second;
}
else
{
int minute = node.second + 1;
for (auto x: nodes[node.first].second)
{
pair<string, int> temp = {x, minute};
if (!isVisited(temp, visited))
{
setVisited(temp, visited);
Q.push(temp);
}
}
}
}
error("countDistance", "should not happen", "");
return -1;
}
void buildCompactGrah()
{
int count = 0;
valves[count] = "AA";
for (auto x: nodes)
{
if (x.second.first)
{
count++;
valves[count] = x.first;
valveNo[x.first] = count;
}
}
for (auto x: valves)
{
cout << x.second << ", ";
}
cout << endl;
int noOfValves = valves.size();
cout << "number of valves: " << noOfValves << endl;
for (int i = 0; i < noOfValves; i++)
{
for (int j = i + 1; j < noOfValves; j++)
{
dist[i][j] = countDistance(valves[i], valves[j]);
dist[j][i] = dist[i][j];
}
}
}
void prepare()
{
init();
readInput();
buildGraph();
buildCompactGrah();
countNoValves();
}
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|