Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Auto Sweeper
#include<iostream>
#include<functional>
#include<algorithm>
#include<array>
#include<optional>
#include<random>
#include<sstream>
#include<queue>
constexpr int width = 9;
constexpr int height = 9;
constexpr int count = std::min(width*height - 9, 10);
template<class T, std::size_t Dim1, std::size_t Dim2>using dual_array = std::array<std::array<T, Dim2>, Dim1>;
typedef dual_array<std::optional<int>, width, height> field_t;
typedef dual_array<bool, width, height> mines_t;
template<class Engine>mines_t make_field(std::size_t sx, std::size_t sy, Engine&& engine)
{
std::uniform_int_distribution<int> xr(0, width - 1);
std::uniform_int_distribution<int> yr(0, height - 1);
mines_t field{};
for (int i = 0; i < count; ++i)
{
while (true)
{
auto x = xr(engine);
auto y = yr(engine);
if (sx - 1 <= x&&x <= sx + 1 && sy - 1 <= y&&y <= sy + 1)
{
continue;
}
if (field[x][y])
{
continue;
}
field[x][y] = true;
break;
}
}
return field;
}
struct receive_data_t
{
int number;
std::size_t x;
std::size_t y;
};
constexpr std::pair<int, int> rotate[] = { {-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1},{-1,0} };
constexpr bool range_check(std::size_t x, std::size_t y)
{
return 0 <= x&&x < width && 0 <= y&&y < height;
}
template<class Solver>struct test_engine
{
Solver solver;
bool run(std::size_t xs, std::size_t ys)
{
int rest = width*height - count;
auto mines = make_field(xs, ys, solver.random);
field_t numbers{};
open(mines, numbers, xs, ys, rest);
std::string dummy;
while (rest != 0)
{
print(numbers);
std::getline(std::cin, dummy);
auto p = solver.send();
if (open(mines, numbers, p.first, p.second, rest))
{
std::cout << "ゲームオーバー" << std::endl;
print(numbers);
std::getline(std::cin, dummy);
return false;
}
}
std::cout << "ゲームクリア" << std::endl;
print(numbers);
std::getline(std::cin, dummy);
return true;
}
void print(field_t const& numbers)
{
for (int y = 0; y < height; ++y)
{
for (int x = 0; x < width; ++x)
{
if (!numbers[x][y])
{
std::cout << "[ ]";
}
else if (*numbers[x][y] == 0)
{
std::cout << " ";
}
else
{
std::cout << " " << *numbers[x][y] << " ";
}
}
std::cout << std::endl;
}
}
bool open(mines_t& mines, field_t& numbers, std::size_t x, std::size_t y, int& rest)
{
if (numbers[x][y])
{
return false;
}
if (mines[x][y])
{
return true;
}
int c = 0;
for (auto const& p : rotate)
{
if (range_check(x + p.first, y + p.second) &&
mines[x + p.first][y + p.second])
{
++c;
}
}
numbers[x][y] = c;
solver.receive(receive_data_t{ c,x,y });
--rest;
if (c == 0)
{
for (auto const& p : rotate)
{
if (range_check(x + p.first, y + p.second))
{
open(mines, numbers, x + p.first, y + p.second, rest);
}
}
}
return false;
}
};
template<class Solver>struct checker_engine
{
Solver solver;
bool run(std::size_t xs, std::size_t ys)
{
int rest = width*height - count;
auto mines = make_field(xs, ys, solver.random);
field_t numbers{};
open(mines, numbers, xs, ys, rest);
while (rest != 0)
{
auto p = solver.send();
if (open(mines, numbers, p.first, p.second, rest))
{
return false;
}
}
return true;
}
bool open(mines_t& mines, field_t& numbers, std::size_t x, std::size_t y, int& rest)
{
if (numbers[x][y])
{
return false;
}
if (mines[x][y])
{
return true;
}
int c = 0;
for (auto const& p : rotate)
{
if (range_check(x + p.first, y + p.second) &&
mines[x + p.first][y + p.second])
{
++c;
}
}
numbers[x][y] = c;
solver.receive(receive_data_t{ c,x,y });
--rest;
if (c == 0)
{
for (auto const& p : rotate)
{
if (range_check(x + p.first, y + p.second))
{
open(mines, numbers, x + p.first, y + p.second, rest);
}
}
}
return false;
}
};
struct beginner_solver
{
dual_array<std::optional<int>, width, height> flags;
std::mt19937 random;
std::pair<std::size_t, std::size_t> send()
{
start:;
for (int x = 0; x < width; ++x)
{
for (int y = 0; y < height; ++y)
{
if (!flags[x][y] || *flags[x][y] == -1)
{
continue;
}
auto n = *flags[x][y];
auto r = 8 - n;
for (auto p : rotate)
{
if (x + p.first < 0 || width <= x + p.first)
{
--r;
}
else if (y + p.second < 0 || height <= y + p.second)
{
--r;
}
else if (!flags[x + p.first][y + p.second])
{
}
else if (*flags[x + p.first][y + p.second] == -1)
{
--n;
}
else
{
--r;
}
}
if (n == 0)
{
for (auto p : rotate)
{
if (x + p.first < 0 || width <= x + p.first)
{
continue;
}
else if (y + p.second < 0 || height <= y + p.second)
{
continue;
}
else if (!flags[x + p.first][y + p.second])
{
return { x + p.first,y + p.second };
}
}
}
if (r == 0)
{
bool f = false;
for (auto const& p : rotate)
{
if (x + p.first < 0 || width <= x + p.first)
{
continue;
}
else if (y + p.second < 0 || height <= y + p.second)
{
continue;
}
else if (!flags[x + p.first][y + p.second])
{
f = true;
flags[x + p.first][y + p.second] = -1;
}
}
if (f)
{
goto start;
}
}
}
}
std::uniform_int_distribution<int> xr(0, width - 1);
std::uniform_int_distribution<int> yr(0, height - 1);
while (true)
{
auto x = xr(random);
auto y = yr(random);
if (!flags[x][y])
{
return { x,y };
}
}
}
void receive(receive_data_t const& data)
{
flags[data.x][data.y] = data.number;
}
void reset()
{
flags = dual_array<std::optional<int>, width, height>{};
}
};
int main()
{
std::priority_queue<std::pair<int, std::pair<int, int>>> ranking;
checker_engine<beginner_solver> engine{ beginner_solver{{},std::mt19937{std::random_device()()}} };
for (int x = 0; x < 5; ++x)
{
for (int y = x; y < 5; ++y)
{
int w = 0;
for (int i = 0; i < 10000000; ++i)
{
engine.solver.reset();
if (engine.run(x, y))
{
++w;
}
}
ranking.emplace(std::make_pair(w, std::make_pair(x, y)));
std::cout << "(" << x << "," << y << ")終了" << std::endl;
}
}
for (int i = 0; i < 5; ++i)
{
auto top = ranking.top();
ranking.pop();
auto w = top.first;
auto x = top.second.first;
auto y = top.second.second;
std::cout << i + 1 << ":(" << x << "," << y << ")-" << w << std::endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment