Skip to content

Instantly share code, notes, and snippets.

@mizuhara
Created January 18, 2017 12:09
Show Gist options
  • Save mizuhara/e2ad99f5dc800c1d56ed91e7348942ec to your computer and use it in GitHub Desktop.
Save mizuhara/e2ad99f5dc800c1d56ed91e7348942ec to your computer and use it in GitHub Desktop.
#include <queue>
#include <regex>
#include <string>
#include <bitset>
#include <sstream>
#include <iostream>
#include <algorithm>
const int width = 8;
const int height = 8;
const std::string black = "1";
const std::string white = "0";
const std::string dummy_string = "-";
struct Pos
{
int x;
int y;
};
std::vector<std::string> split(const std::string & src, const std::string & sep)
{
std::vector<std::string> ret;
const auto reg = sep.empty() ? std::regex("(.{1})") : std::regex(sep);
const auto flag = sep.empty() ? 1 : -1;
std::copy(std::sregex_token_iterator(src.begin(), src.end(), reg, flag), std::sregex_token_iterator(), std::back_inserter(ret));
return ret;
}
std::string hex_to_bin(const std::string & hex)
{
unsigned long ul;
std::stringstream ss(hex);
ss >> std::hex >> ul;
return std::bitset<8>(ul).to_string();
}
std::vector<std::string> make_mass(const std::string & src)
{
std::vector<std::string> mass;
const auto s = split(src, "/");
for(auto && chr : s) {
const auto bin = hex_to_bin(chr);
mass.push_back(bin);
}
return mass;
}
std::vector<Pos> next_pos(const Pos & p)
{
const std::vector<Pos> np = {
{ p.x + 1, p.y },
{ p.x - 1, p.y },
{ p.x, p.y + 1 },
{ p.x, p.y - 1 },
};
return np;
}
bool is_pos_valid(const Pos & p)
{
return (0 <= p.x && p.x < width) && (0 <= p.y && p.y < height);
}
int count_of(const std::vector<std::string> & mass, const std::string & s)
{
int count { 0 };
auto m = mass;
for(int h = 0; h < height; ++h) {
for(int w = 0; w < width; ++w) {
int tmp { 1 };
std::queue<Pos> q;
if(m[h].substr(w, 1) != s) {
continue;
}
q.push({ h, w });
while(!q.empty()) {
const auto cp = q.front(); q.pop();
m[cp.x].replace(cp.y, 1, dummy_string);
const auto nps = next_pos(cp);
for(auto np : nps) {
if(!is_pos_valid(np)) {
continue;
}
if(m[np.x].substr(np.y, 1) != s) {
continue;
}
m[cp.x].replace(cp.y, 1, dummy_string);
q.push(np);
++tmp;
}
}
if(tmp == 2) {
++count;
}
}
}
return count;
}
std::string solve(const std::string & src)
{
const auto mass = make_mass(src);
const auto white_count = count_of(mass, white);
const auto black_count = count_of(mass, black);
return std::to_string(white_count) + "," + std::to_string(black_count);
}
void test(const std::string & src, const std::string & expected)
{
const auto actual = solve(src);
std::cout << (actual == expected ? "OK" : "***NG***") << std::endl;
}
int main()
{
/*0*/ test( "dc/bc/a7/59/03/d5/d4/ea", "2,3" );
/*1*/ test( "ff/ff/ff/ff/ff/ff/ff/ff", "0,0" );
/*2*/ test( "00/00/00/00/00/00/00/00", "0,0" );
/*3*/ test( "cc/33/cc/33/cc/33/cc/33", "16,16" );
/*4*/ test( "aa/aa/55/55/aa/aa/55/55", "16,16" );
/*5*/ test( "ac/a3/5c/53/ca/3a/c5/35", "8,8" );
/*6*/ test( "db/00/db/00/db/00/aa/aa", "0,13" );
/*7*/ test( "24/24/db/24/24/db/24/24", "0,12" );
/*8*/ test( "d7/d7/e9/f1/f7/de/60/56", "3,2" );
/*9*/ test( "17/7d/64/9b/a5/39/53/a6", "2,2" );
/*10*/ test( "bb/8f/18/fb/89/c2/c7/35", "1,2" );
/*11*/ test( "6d/63/20/08/54/cd/32/4f", "2,2" );
/*12*/ test( "a9/ca/cd/46/99/e6/f0/30", "2,2" );
/*13*/ test( "5b/70/fd/45/e2/a1/ab/9a", "1,2" );
/*14*/ test( "24/e4/a8/12/e1/a6/3f/f3", "2,1" );
/*15*/ test( "79/32/2e/07/d5/10/e7/9d", "2,2" );
/*16*/ test( "60/bc/ab/ec/1f/eb/63/2c", "4,2" );
/*17*/ test( "a5/dd/92/4e/67/c6/dc/34", "6,1" );
/*18*/ test( "aa/96/6d/67/d2/a8/ac/90", "3,2" );
/*19*/ test( "95/72/7d/5c/47/dc/ef/99", "4,0" );
/*20*/ test( "17/d6/6a/27/1f/25/26/b8", "2,1" );
/*21*/ test( "f0/f3/76/c5/31/ca/6b/ae", "1,2" );
/*22*/ test( "01/59/26/fa/8c/70/12/cd", "1,4" );
/*23*/ test( "1a/c3/1f/0b/83/b6/81/0d", "0,5" );
/*24*/ test( "4c/49/05/cf/54/bb/1f/da", "1,2" );
/*25*/ test( "eb/7c/d5/09/2a/c2/14/6b", "0,7" );
/*26*/ test( "b4/d3/4c/c4/ed/19/e8/63", "1,3" );
/*27*/ test( "bd/bc/6d/60/9b/00/9a/32", "2,4" );
/*28*/ test( "94/97/3f/e3/c7/06/15/c0", "2,2" );
/*29*/ test( "5f/1d/67/16/b8/f7/0a/2a", "2,2" );
/*30*/ test( "df/e6/f9/4f/59/e9/1f/ee", "3,0" );
/*31*/ test( "5a/53/9a/9a/73/b4/37/07", "3,2" );
/*32*/ test( "bd/87/7c/e7/c0/37/82/da", "2,3" );
/*33*/ test( "3d/c0/13/ac/57/3d/15/78", "2,2" );
/*34*/ test( "63/64/54/3a/40/28/4e/4e", "0,3" );
/*35*/ test( "f6/81/c9/15/00/4c/a0/a8", "1,4" );
/*36*/ test( "19/41/df/f8/e3/74/6b/9b", "4,2" );
/*37*/ test( "d5/0b/dd/35/3b/d2/0b/6b", "1,5" );
/*38*/ test( "08/b7/91/f3/6e/3c/74/a0", "0,0" );
/*39*/ test( "b8/a8/b4/a6/93/2c/94/3f", "0,0" );
/*40*/ test( "88/22/21/ee/dc/19/43/01", "0,0" );
/*41*/ test( "e1/ee/35/bc/fc/00/8e/fe", "0,0" );
/*42*/ test( "3c/42/63/5f/27/47/07/90", "0,0" );
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment