Please I need help converting the following C++ code to java code. #include <ios
ID: 3751020 • Letter: P
Question
Please I need help converting the following C++ code to java code.#include <iostream> #include <sstream> #include <set> #include <queue> #include <stack>
using namespace std;
#include "State.h" #include "Stat.h"
const int DISPLAYED = 15;
// Depth-First Search bool DFS(const State& init, const State& goal, Stat& stat) { stat.reset(); stat.start();
int displayed = 0;
stack<State> frontier; set<State> explored;
frontier.push(init); explored.insert(init);
while (!frontier.empty()) { stat.concurency++;
State state = frontier.top(); frontier.pop(); explored.insert(state);
if (displayed++ < DISPLAYED) cout << state << endl;
if (state == goal) // solved { stat.stop(); stat.steps = state.step; return true; }
for (auto& nb: state.neighbors()) { if (!explored.count(nb) ) { nb.step = state.step + 1; frontier.push(nb); } } }
stat.stop(); return false; // not solutions }
// Breadth-First Search bool BFS(const State& init, const State& goal, Stat& stat) { stat.reset(); stat.start();
int displayed = 0;
queue<State> frontier; set<State> explored;
frontier.push(init); explored.insert(init);
while (!frontier.empty()) { stat.concurency++;
State state = frontier.front(); frontier.pop(); explored.insert(state);
if (displayed++ < DISPLAYED) cout << state << endl;
if (state == goal) // solved { stat.stop(); stat.steps = state.step; return true; }
for (auto& nb : state.neighbors()) {
if (!explored.count(nb)) { nb.step = state.step + 1; frontier.push(nb); } } }
stat.stop(); return false; // not solutions }
// A* Search bool AStar(const State& init, const State& goal, Stat& stat) { stat.reset(); stat.start();
int displayed = 0;
std::priority_queue<State, vector<State>, Comparator> frontier{ Comparator(goal) };
set<State> explored;
frontier.push(init); explored.insert(init);
while (!frontier.empty()) { stat.concurency++;
State state = frontier.top(); frontier.pop(); explored.insert(state);
if (displayed++ < DISPLAYED) cout << state << endl;
if (state == goal) // solved { stat.stop(); stat.steps = state.step; return true; }
for (auto& nb : state.neighbors()) { if (!explored.count(nb)) { nb.step = state.step + 1; frontier.push(nb); } } }
stat.stop(); return false; // not solutions }
int main() { //string initStr = "7 2 4 5 0 6 8 3 2"; //string goalStr = "2 2 3 4 5 6 7 8 0";
State init, goal;
cin >> init; cin >> goal;
Stat stat;
DFS(init, goal, stat); cout << "DFS..." << endl; cout << stat << endl;
BFS(init, goal, stat); cout << "BFS..." << endl; cout << stat << endl;
AStar(init, goal, stat); cout << "A*..." << endl; cout << stat << endl;
return 0; }
#ifndef STAT_H #define STAT_H
#include <iostream> #include <ctime>
using namespace std;
/* Structure to collect algorithm statistics */ struct Stat { int steps; int concurency;
clock_t startClock; clock_t stopClock;
Stat() { reset(); }
void reset() { steps = 0; concurency = 0; startClock = 0; stopClock = 0;
}
void start() { startClock = clock(); } void stop() { stopClock = clock(); }
double getTime() const { return (double)(stopClock - startClock) / CLOCKS_PER_SEC; }
friend ostream & operator<<(ostream & out, const Stat & stat) { out << "Total number of steps: " << stat.steps << endl; out << "Elapsed time: " << stat.getTime() << " s" << endl; out << "Maximum number of concurent states: " << stat.concurency << endl;
return out; } };
#endif
#ifndef STATE_H #define STATE_H
#include <iostream> #include <sstream> #include <string> #include <vector> #include <utility> #include <functional>
using namespace std;
const int DIM = 3;
/* Structure representing game state */ struct State { int arr[DIM][DIM]; int emptyX, emptyY; int step;
State() : step(0) {}
// Returns neighbor list for fourth directions vector<State> neighbors() { vector<State> states; for (int i = 0; i < 4; i += 1) { int dx = (i % 2) * (2 * (i / 2) - 1); int dy = ((i + 1) % 2) * (2 * (i / 2) - 1);
if (emptyX + dx >= 0 && emptyX + dx < DIM && emptyY + dy >= 0 && emptyY + dy < DIM) { State st = *this; st.emptyX = emptyX + dx; st.emptyY = emptyY + dy;
swap(st.arr[emptyY][emptyX], st.arr[st.emptyY][st.emptyX]);
states.push_back(st); } } return states; }
// friend bool operator==(const State& lhs, const State& rhs) { for (int i = 0; i < DIM; ++i) for (int j = 0; j < DIM; ++j) if (lhs.arr[i][j] != rhs.arr[i][j]) return false; return true; }
// Uses in set<State> friend bool operator<(const State& lhs, const State& rhs) { for (int i = 0; i < DIM; ++i) for (int j = 0; j < DIM; ++j) if (lhs.arr[i][j] < rhs.arr[i][j]) return true; else if (lhs.arr[i][j] > rhs.arr[i][j]) return false; return false; }
// Input friend istream& operator>>(istream& in, State& state) {
for (int i = 0; i < DIM; ++i) { for (int j = 0; j < DIM; ++j) { in >> state.arr[i][j]; if (state.arr[i][j] == 0) { state.emptyX = j; state.emptyY = i; } } } return in; }
// Output friend ostream& operator<<(ostream& out, const State& state) { out << "+-----+" << endl;
for (int i = 0; i < DIM; ++i) { out << "|" << state.arr[i][0];;
for (int j = 1; j < DIM; ++j) out << " " << state.arr[i][j];
out << "|" << endl; }
out << "+-----+" << endl; return out; }
// Hamming priority function static int distance(const State& curr, const State& goal) { int dist = 0; for (int i = 0; i < DIM; ++i) for (int j = 0; j < DIM; ++j) if (curr.arr[i][j] == goal.arr[i][j]) ++dist; return dist + curr.step; } };
// Compares two State by Hamming distance class Comparator { State goal; public: Comparator(const State& goal) : goal(goal) {}
bool operator()(const State& lhs, const State& rhs) const { return State::distance(lhs, goal) < State::distance(rhs, goal); } };
#endif // STATE_H
Please I need help converting the following C++ code to java code.
#include <iostream> #include <sstream> #include <set> #include <queue> #include <stack>
using namespace std;
#include "State.h" #include "Stat.h"
const int DISPLAYED = 15;
// Depth-First Search bool DFS(const State& init, const State& goal, Stat& stat) { stat.reset(); stat.start();
int displayed = 0;
stack<State> frontier; set<State> explored;
frontier.push(init); explored.insert(init);
while (!frontier.empty()) { stat.concurency++;
State state = frontier.top(); frontier.pop(); explored.insert(state);
if (displayed++ < DISPLAYED) cout << state << endl;
if (state == goal) // solved { stat.stop(); stat.steps = state.step; return true; }
for (auto& nb: state.neighbors()) { if (!explored.count(nb) ) { nb.step = state.step + 1; frontier.push(nb); } } }
stat.stop(); return false; // not solutions }
// Breadth-First Search bool BFS(const State& init, const State& goal, Stat& stat) { stat.reset(); stat.start();
int displayed = 0;
queue<State> frontier; set<State> explored;
frontier.push(init); explored.insert(init);
while (!frontier.empty()) { stat.concurency++;
State state = frontier.front(); frontier.pop(); explored.insert(state);
if (displayed++ < DISPLAYED) cout << state << endl;
if (state == goal) // solved { stat.stop(); stat.steps = state.step; return true; }
for (auto& nb : state.neighbors()) {
if (!explored.count(nb)) { nb.step = state.step + 1; frontier.push(nb); } } }
stat.stop(); return false; // not solutions }
// A* Search bool AStar(const State& init, const State& goal, Stat& stat) { stat.reset(); stat.start();
int displayed = 0;
std::priority_queue<State, vector<State>, Comparator> frontier{ Comparator(goal) };
set<State> explored;
frontier.push(init); explored.insert(init);
while (!frontier.empty()) { stat.concurency++;
State state = frontier.top(); frontier.pop(); explored.insert(state);
if (displayed++ < DISPLAYED) cout << state << endl;
if (state == goal) // solved { stat.stop(); stat.steps = state.step; return true; }
for (auto& nb : state.neighbors()) { if (!explored.count(nb)) { nb.step = state.step + 1; frontier.push(nb); } } }
stat.stop(); return false; // not solutions }
int main() { //string initStr = "7 2 4 5 0 6 8 3 2"; //string goalStr = "2 2 3 4 5 6 7 8 0";
State init, goal;
cin >> init; cin >> goal;
Stat stat;
DFS(init, goal, stat); cout << "DFS..." << endl; cout << stat << endl;
BFS(init, goal, stat); cout << "BFS..." << endl; cout << stat << endl;
AStar(init, goal, stat); cout << "A*..." << endl; cout << stat << endl;
return 0; }
#ifndef STAT_H #define STAT_H
#include <iostream> #include <ctime>
using namespace std;
/* Structure to collect algorithm statistics */ struct Stat { int steps; int concurency;
clock_t startClock; clock_t stopClock;
Stat() { reset(); }
void reset() { steps = 0; concurency = 0; startClock = 0; stopClock = 0;
}
void start() { startClock = clock(); } void stop() { stopClock = clock(); }
double getTime() const { return (double)(stopClock - startClock) / CLOCKS_PER_SEC; }
friend ostream & operator<<(ostream & out, const Stat & stat) { out << "Total number of steps: " << stat.steps << endl; out << "Elapsed time: " << stat.getTime() << " s" << endl; out << "Maximum number of concurent states: " << stat.concurency << endl;
return out; } };
#endif
#ifndef STATE_H #define STATE_H
#include <iostream> #include <sstream> #include <string> #include <vector> #include <utility> #include <functional>
using namespace std;
const int DIM = 3;
/* Structure representing game state */ struct State { int arr[DIM][DIM]; int emptyX, emptyY; int step;
State() : step(0) {}
// Returns neighbor list for fourth directions vector<State> neighbors() { vector<State> states; for (int i = 0; i < 4; i += 1) { int dx = (i % 2) * (2 * (i / 2) - 1); int dy = ((i + 1) % 2) * (2 * (i / 2) - 1);
if (emptyX + dx >= 0 && emptyX + dx < DIM && emptyY + dy >= 0 && emptyY + dy < DIM) { State st = *this; st.emptyX = emptyX + dx; st.emptyY = emptyY + dy;
swap(st.arr[emptyY][emptyX], st.arr[st.emptyY][st.emptyX]);
states.push_back(st); } } return states; }
// friend bool operator==(const State& lhs, const State& rhs) { for (int i = 0; i < DIM; ++i) for (int j = 0; j < DIM; ++j) if (lhs.arr[i][j] != rhs.arr[i][j]) return false; return true; }
// Uses in set<State> friend bool operator<(const State& lhs, const State& rhs) { for (int i = 0; i < DIM; ++i) for (int j = 0; j < DIM; ++j) if (lhs.arr[i][j] < rhs.arr[i][j]) return true; else if (lhs.arr[i][j] > rhs.arr[i][j]) return false; return false; }
// Input friend istream& operator>>(istream& in, State& state) {
for (int i = 0; i < DIM; ++i) { for (int j = 0; j < DIM; ++j) { in >> state.arr[i][j]; if (state.arr[i][j] == 0) { state.emptyX = j; state.emptyY = i; } } } return in; }
// Output friend ostream& operator<<(ostream& out, const State& state) { out << "+-----+" << endl;
for (int i = 0; i < DIM; ++i) { out << "|" << state.arr[i][0];;
for (int j = 1; j < DIM; ++j) out << " " << state.arr[i][j];
out << "|" << endl; }
out << "+-----+" << endl; return out; }
// Hamming priority function static int distance(const State& curr, const State& goal) { int dist = 0; for (int i = 0; i < DIM; ++i) for (int j = 0; j < DIM; ++j) if (curr.arr[i][j] == goal.arr[i][j]) ++dist; return dist + curr.step; } };
// Compares two State by Hamming distance class Comparator { State goal; public: Comparator(const State& goal) : goal(goal) {}
bool operator()(const State& lhs, const State& rhs) const { return State::distance(lhs, goal) < State::distance(rhs, goal); } };
#endif // STATE_H
#include <iostream> #include <sstream> #include <set> #include <queue> #include <stack>
using namespace std;
#include "State.h" #include "Stat.h"
const int DISPLAYED = 15;
// Depth-First Search bool DFS(const State& init, const State& goal, Stat& stat) { stat.reset(); stat.start();
int displayed = 0;
stack<State> frontier; set<State> explored;
frontier.push(init); explored.insert(init);
while (!frontier.empty()) { stat.concurency++;
State state = frontier.top(); frontier.pop(); explored.insert(state);
if (displayed++ < DISPLAYED) cout << state << endl;
if (state == goal) // solved { stat.stop(); stat.steps = state.step; return true; }
for (auto& nb: state.neighbors()) { if (!explored.count(nb) ) { nb.step = state.step + 1; frontier.push(nb); } } }
stat.stop(); return false; // not solutions }
// Breadth-First Search bool BFS(const State& init, const State& goal, Stat& stat) { stat.reset(); stat.start();
int displayed = 0;
queue<State> frontier; set<State> explored;
frontier.push(init); explored.insert(init);
while (!frontier.empty()) { stat.concurency++;
State state = frontier.front(); frontier.pop(); explored.insert(state);
if (displayed++ < DISPLAYED) cout << state << endl;
if (state == goal) // solved { stat.stop(); stat.steps = state.step; return true; }
for (auto& nb : state.neighbors()) {
if (!explored.count(nb)) { nb.step = state.step + 1; frontier.push(nb); } } }
stat.stop(); return false; // not solutions }
// A* Search bool AStar(const State& init, const State& goal, Stat& stat) { stat.reset(); stat.start();
int displayed = 0;
std::priority_queue<State, vector<State>, Comparator> frontier{ Comparator(goal) };
set<State> explored;
frontier.push(init); explored.insert(init);
while (!frontier.empty()) { stat.concurency++;
State state = frontier.top(); frontier.pop(); explored.insert(state);
if (displayed++ < DISPLAYED) cout << state << endl;
if (state == goal) // solved { stat.stop(); stat.steps = state.step; return true; }
for (auto& nb : state.neighbors()) { if (!explored.count(nb)) { nb.step = state.step + 1; frontier.push(nb); } } }
stat.stop(); return false; // not solutions }
int main() { //string initStr = "7 2 4 5 0 6 8 3 2"; //string goalStr = "2 2 3 4 5 6 7 8 0";
State init, goal;
cin >> init; cin >> goal;
Stat stat;
DFS(init, goal, stat); cout << "DFS..." << endl; cout << stat << endl;
BFS(init, goal, stat); cout << "BFS..." << endl; cout << stat << endl;
AStar(init, goal, stat); cout << "A*..." << endl; cout << stat << endl;
return 0; } #include <iostream> #include <sstream> #include <set> #include <queue> #include <stack>
using namespace std;
#include "State.h" #include "Stat.h"
const int DISPLAYED = 15;
// Depth-First Search bool DFS(const State& init, const State& goal, Stat& stat) { stat.reset(); stat.start();
int displayed = 0;
stack<State> frontier; set<State> explored;
frontier.push(init); explored.insert(init);
while (!frontier.empty()) { stat.concurency++;
State state = frontier.top(); frontier.pop(); explored.insert(state);
if (displayed++ < DISPLAYED) cout << state << endl;
if (state == goal) // solved { stat.stop(); stat.steps = state.step; return true; }
for (auto& nb: state.neighbors()) { if (!explored.count(nb) ) { nb.step = state.step + 1; frontier.push(nb); } } }
stat.stop(); return false; // not solutions }
// Breadth-First Search bool BFS(const State& init, const State& goal, Stat& stat) { stat.reset(); stat.start();
int displayed = 0;
queue<State> frontier; set<State> explored;
frontier.push(init); explored.insert(init);
while (!frontier.empty()) { stat.concurency++;
State state = frontier.front(); frontier.pop(); explored.insert(state);
if (displayed++ < DISPLAYED) cout << state << endl;
if (state == goal) // solved { stat.stop(); stat.steps = state.step; return true; }
for (auto& nb : state.neighbors()) {
if (!explored.count(nb)) { nb.step = state.step + 1; frontier.push(nb); } } }
stat.stop(); return false; // not solutions }
// A* Search bool AStar(const State& init, const State& goal, Stat& stat) { stat.reset(); stat.start();
int displayed = 0;
std::priority_queue<State, vector<State>, Comparator> frontier{ Comparator(goal) };
set<State> explored;
frontier.push(init); explored.insert(init);
while (!frontier.empty()) { stat.concurency++;
State state = frontier.top(); frontier.pop(); explored.insert(state);
if (displayed++ < DISPLAYED) cout << state << endl;
if (state == goal) // solved { stat.stop(); stat.steps = state.step; return true; }
for (auto& nb : state.neighbors()) { if (!explored.count(nb)) { nb.step = state.step + 1; frontier.push(nb); } } }
stat.stop(); return false; // not solutions }
int main() { //string initStr = "7 2 4 5 0 6 8 3 2"; //string goalStr = "2 2 3 4 5 6 7 8 0";
State init, goal;
cin >> init; cin >> goal;
Stat stat;
DFS(init, goal, stat); cout << "DFS..." << endl; cout << stat << endl;
BFS(init, goal, stat); cout << "BFS..." << endl; cout << stat << endl;
AStar(init, goal, stat); cout << "A*..." << endl; cout << stat << endl;
return 0; }
#ifndef STAT_H #define STAT_H
#include <iostream> #include <ctime>
using namespace std;
/* Structure to collect algorithm statistics */ struct Stat { int steps; int concurency;
clock_t startClock; clock_t stopClock;
Stat() { reset(); }
void reset() { steps = 0; concurency = 0; startClock = 0; stopClock = 0;
}
void start() { startClock = clock(); } void stop() { stopClock = clock(); }
double getTime() const { return (double)(stopClock - startClock) / CLOCKS_PER_SEC; }
friend ostream & operator<<(ostream & out, const Stat & stat) { out << "Total number of steps: " << stat.steps << endl; out << "Elapsed time: " << stat.getTime() << " s" << endl; out << "Maximum number of concurent states: " << stat.concurency << endl;
return out; } };
#endif #ifndef STAT_H #define STAT_H
#include <iostream> #include <ctime>
using namespace std;
/* Structure to collect algorithm statistics */ struct Stat { int steps; int concurency;
clock_t startClock; clock_t stopClock;
Stat() { reset(); }
void reset() { steps = 0; concurency = 0; startClock = 0; stopClock = 0;
}
void start() { startClock = clock(); } void stop() { stopClock = clock(); }
double getTime() const { return (double)(stopClock - startClock) / CLOCKS_PER_SEC; }
friend ostream & operator<<(ostream & out, const Stat & stat) { out << "Total number of steps: " << stat.steps << endl; out << "Elapsed time: " << stat.getTime() << " s" << endl; out << "Maximum number of concurent states: " << stat.concurency << endl;
return out; } };
#endif
#ifndef STATE_H #define STATE_H
#include <iostream> #include <sstream> #include <string> #include <vector> #include <utility> #include <functional>
using namespace std;
const int DIM = 3;
/* Structure representing game state */ struct State { int arr[DIM][DIM]; int emptyX, emptyY; int step;
State() : step(0) {}
// Returns neighbor list for fourth directions vector<State> neighbors() { vector<State> states; for (int i = 0; i < 4; i += 1) { int dx = (i % 2) * (2 * (i / 2) - 1); int dy = ((i + 1) % 2) * (2 * (i / 2) - 1);
if (emptyX + dx >= 0 && emptyX + dx < DIM && emptyY + dy >= 0 && emptyY + dy < DIM) { State st = *this; st.emptyX = emptyX + dx; st.emptyY = emptyY + dy;
swap(st.arr[emptyY][emptyX], st.arr[st.emptyY][st.emptyX]);
states.push_back(st); } } return states; }
// friend bool operator==(const State& lhs, const State& rhs) { for (int i = 0; i < DIM; ++i) for (int j = 0; j < DIM; ++j) if (lhs.arr[i][j] != rhs.arr[i][j]) return false; return true; }
// Uses in set<State> friend bool operator<(const State& lhs, const State& rhs) { for (int i = 0; i < DIM; ++i) for (int j = 0; j < DIM; ++j) if (lhs.arr[i][j] < rhs.arr[i][j]) return true; else if (lhs.arr[i][j] > rhs.arr[i][j]) return false; return false; }
// Input friend istream& operator>>(istream& in, State& state) {
for (int i = 0; i < DIM; ++i) { for (int j = 0; j < DIM; ++j) { in >> state.arr[i][j]; if (state.arr[i][j] == 0) { state.emptyX = j; state.emptyY = i; } } } return in; }
// Output friend ostream& operator<<(ostream& out, const State& state) { out << "+-----+" << endl;
for (int i = 0; i < DIM; ++i) { out << "|" << state.arr[i][0];;
for (int j = 1; j < DIM; ++j) out << " " << state.arr[i][j];
out << "|" << endl; }
out << "+-----+" << endl; return out; }
// Hamming priority function static int distance(const State& curr, const State& goal) { int dist = 0; for (int i = 0; i < DIM; ++i) for (int j = 0; j < DIM; ++j) if (curr.arr[i][j] == goal.arr[i][j]) ++dist; return dist + curr.step; } };
// Compares two State by Hamming distance class Comparator { State goal; public: Comparator(const State& goal) : goal(goal) {}
bool operator()(const State& lhs, const State& rhs) const { return State::distance(lhs, goal) < State::distance(rhs, goal); } };
#endif // STATE_H #ifndef STATE_H #define STATE_H
#include <iostream> #include <sstream> #include <string> #include <vector> #include <utility> #include <functional>
using namespace std;
const int DIM = 3;
/* Structure representing game state */ struct State { int arr[DIM][DIM]; int emptyX, emptyY; int step;
State() : step(0) {}
// Returns neighbor list for fourth directions vector<State> neighbors() { vector<State> states; for (int i = 0; i < 4; i += 1) { int dx = (i % 2) * (2 * (i / 2) - 1); int dy = ((i + 1) % 2) * (2 * (i / 2) - 1);
if (emptyX + dx >= 0 && emptyX + dx < DIM && emptyY + dy >= 0 && emptyY + dy < DIM) { State st = *this; st.emptyX = emptyX + dx; st.emptyY = emptyY + dy;
swap(st.arr[emptyY][emptyX], st.arr[st.emptyY][st.emptyX]);
states.push_back(st); } } return states; }
// friend bool operator==(const State& lhs, const State& rhs) { for (int i = 0; i < DIM; ++i) for (int j = 0; j < DIM; ++j) if (lhs.arr[i][j] != rhs.arr[i][j]) return false; return true; }
// Uses in set<State> friend bool operator<(const State& lhs, const State& rhs) { for (int i = 0; i < DIM; ++i) for (int j = 0; j < DIM; ++j) if (lhs.arr[i][j] < rhs.arr[i][j]) return true; else if (lhs.arr[i][j] > rhs.arr[i][j]) return false; return false; }
// Input friend istream& operator>>(istream& in, State& state) {
for (int i = 0; i < DIM; ++i) { for (int j = 0; j < DIM; ++j) { in >> state.arr[i][j]; if (state.arr[i][j] == 0) { state.emptyX = j; state.emptyY = i; } } } return in; }
// Output friend ostream& operator<<(ostream& out, const State& state) { out << "+-----+" << endl;
for (int i = 0; i < DIM; ++i) { out << "|" << state.arr[i][0];;
for (int j = 1; j < DIM; ++j) out << " " << state.arr[i][j];
out << "|" << endl; }
out << "+-----+" << endl; return out; }
// Hamming priority function static int distance(const State& curr, const State& goal) { int dist = 0; for (int i = 0; i < DIM; ++i) for (int j = 0; j < DIM; ++j) if (curr.arr[i][j] == goal.arr[i][j]) ++dist; return dist + curr.step; } };
// Compares two State by Hamming distance class Comparator { State goal; public: Comparator(const State& goal) : goal(goal) {}
bool operator()(const State& lhs, const State& rhs) const { return State::distance(lhs, goal) < State::distance(rhs, goal); } };
#endif // STATE_H
Explanation / Answer
public class GlobalMembers
{
public static final int DISPLAYED = 15;
// Depth-First Search
public static boolean DFS(State init, State goal, Stat stat)
{
stat.reset();
stat.start();
int displayed = 0;
stack<State> frontier = new stack<State>();
set<State> explored = new set<State>();
frontier.push(init);
explored.insert(init);
while (!frontier.empty())
{
stat.concurency++;
State state = frontier.top();
frontier.pop();
explored.insert(state);
if (displayed++ < DISPLAYED)
{
System.out.print(state);
System.out.print(" ");
}
if (state.equalsTo(goal)) // solved
{
stat.stop();
stat.steps = state.step;
return true;
}
//There is no equivalent to implicit typing in Java unless the Java 10 inferred typing option is selected:
for (auto nb : state.neighbors())
{
if (!explored.count(nb))
{
nb.step = state.step + 1;
frontier.push(nb);
}
}
}
stat.stop();
return false; // not solutions
}
// Breadth-First Search
public static boolean BFS(State init, State goal, Stat stat)
{
stat.reset();
stat.start();
int displayed = 0;
queue<State> frontier = new queue<State>();
set<State> explored = new set<State>();
frontier.push(init);
explored.insert(init);
while (!frontier.empty())
{
stat.concurency++;
State state = frontier.front();
frontier.pop();
explored.insert(state);
if (displayed++ < DISPLAYED)
{
System.out.print(state);
System.out.print(" ");
}
if (state.equalsTo(goal)) // solved
{
stat.stop();
stat.steps = state.step;
return true;
//There is no equivalent to implicit typing in Java unless the Java 10 inferred typing option is selected:
for (auto nb : state.neighbors())
{
if (!explored.count(nb))
{
nb.step = state.step + 1;
frontier.push(nb);
}
}
}
stat.stop();
return false; // not solutions
}
// A* Search
public static boolean AStar(State init, State goal, Stat stat)
{
stat.reset();
stat.start();
int displayed = 0;
std::priority_queue<State, vector<State>, Comparator> frontier = new std::priority_queue<State, vector<State>, Comparator>(new Comparator(goal));
set<State> explored = new set<State>();
frontier.push(init);
explored.insert(init);
while (!frontier.empty())
{
stat.concurency++;
State state = frontier.top();
frontier.pop();
explored.insert(state);
if (displayed++ < DISPLAYED)
{
System.out.print(state);
System.out.print(" ");
}
if (state.equalsTo(goal)) // solved
{
stat.stop();
stat.steps = state.step;
return true;
}
//C++ TO JAVA: There is no equivalent to implicit typing in Java unless the Java 10 inferred typing option is selected:
for (auto nb : state.neighbors())
{
if (!explored.count(nb))
{
nb.step = state.step + 1;
frontier.push(nb);
}
}
}
stat.stop();
return false; // not solutions
}
public static int Main()
{
//string initStr = "7 2 4 5 0 6 8 3 2";
//string goalStr = "2 2 3 4 5 6 7 8 0";
State init = new State();
State goal = new State();
init = ConsoleInput.readToWhiteSpace(true);
goal = ConsoleInput.readToWhiteSpace(true);
Stat stat = new Stat();
DFS(init, goal, stat);
System.out.print("DFS...");
System.out.print(" ");
System.out.print(stat);
System.out.print(" ");
BFS(init, goal, stat);
System.out.print("BFS...");
System.out.print(" ");
System.out.print(stat);
System.out.print(" ");
AStar(init, goal, stat);
System.out.print("A*...");
System.out.print(" ");
System.out.print(stat);
}
/*
Structure to collect algorithm statistics
*/
public class Stat
{
public int steps;
public int concurency;
public clock_t startClock = new clock_t();
public clock_t stopClock = new clock_t();
public Stat()
{
reset();
}
public final void reset()
{
steps = 0;
concurency = 0;
startClock = 0;
stopClock = 0;
}
public final void start()
{
startClock = clock();
}
public final void stop()
{
stopClock = clock();
}
// 'const' methods are not available in Java:
//ORIGINAL LINE: double getTime() const
public final double getTime()
{
return (double)(stopClock - startClock) / CLOCKS_PER_SEC;
}
}
/*
Structure representing game state
*/
public class State implements Comparable<State>
{
public final int compareTo(State otherInstance)
{
if (lessThan(otherInstance))
{
return -1;
}
else if (otherInstance.lessThan(this))
{
return 1;
}
return 0;
}
public int[][] arr = new int[DIM][DIM];
public int emptyX;
public int emptyY;
public int step;
public State()
{
this.step = 0;
}
// Returns neighbor list for fourth directions
public final vector<State> neighbors()
{
vector<State> states = new vector<State>();
for (int i = 0; i < 4; i += 1)
{
int dx = (i % 2) * (2 * (i / 2) - 1);
int dy = ((i + 1) % 2) * (2 * (i / 2) - 1);
if (emptyX + dx >= 0 && emptyX + dx < GlobalMembers.DIM && emptyY + dy >= 0 && emptyY + dy < GlobalMembers.DIM)
{
//C++ TO JAVA CONVERTER TODO TASK: The following line was determined to contain a copy constructor call - this should be verified and a copy constructor should be created:
//ORIGINAL LINE: State st = *this;
State st = new State(this);
st.emptyX = emptyX + dx;
st.emptyY = emptyY + dy;
swap(st.arr[emptyY][emptyX], st.arr[st.emptyY][st.emptyX]);
states.push_back(st);
}
}
return states;
}
//
// Java has no concept of a 'friend' function:
//ORIGINAL LINE: friend boolean operator ==(const State& lhs, const State& rhs)
public boolean equalsTo(State lhs, State rhs)
{
for (int i = 0; i < GlobalMembers.DIM; ++i)
{
for (int j = 0; j < GlobalMembers.DIM; ++j)
{
if (lhs.arr[i][j] != rhs.arr[i][j])
{
return false;
}
}
}
return true;
}
// Uses in set<State>
//Java has no concept of a 'friend' function:
//ORIGINAL LINE: friend boolean operator <(const State& lhs, const State& rhs)
public boolean lessThan(State lhs, State rhs)
{
for (int i = 0; i < GlobalMembers.DIM; ++i)
{
for (int j = 0; j < GlobalMembers.DIM; ++j)
{
if (lhs.arr[i][j] < rhs.arr[i][j])
{
return true;
}
else if (lhs.arr[i][j] > rhs.arr[i][j])
{
return false;
}
}
}
return false;
}
// Input
//: Java has no concept of a 'friend' function:
//ORIGINAL LINE: friend istream& operator >>(istream& in, State& state)
public istream rightShift(istream in, State state)
{
for (int i = 0; i < GlobalMembers.DIM; ++i)
{
for (int j = 0; j < GlobalMembers.DIM; ++j)
{
//The right shift operator was not replaced by Java's logical right shift operator since the left operand was not confirmed to be of an unsigned type, but you should review whether the logical right shift operator (>>>) is more appropriate:
in >> state.arr[i][j];
if (state.arr[i][j] == 0)
{
state.emptyX = j;
state.emptyY = i;
}
}
}
return in;
}
// Hamming priority function
public static int distance(State curr, State goal)
{
int dist = 0;
for (int i = 0; i < GlobalMembers.DIM; ++i)
{
for (int j = 0; j < GlobalMembers.DIM; ++j)
{
if (curr.arr[i][j] == goal.arr[i][j])
{
++dist;
}
}
}
return dist + curr.step;
}
}
// Compares two State by Hamming distance
public class Comparator
{
private State goal = new State();
public Comparator(State goal)
{
this.goal = new State(goal);
}
//'const' methods are not available in Java:
//ORIGINAL LINE: boolean operator ()(const State& lhs, const State& rhs) const
public final boolean functorMethod(State lhs, State rhs)
{
return State.distance(lhs, goal) < State.distance(rhs, goal);
}
}