Skip to content

Instantly share code, notes, and snippets.

@mizuhara
Created October 5, 2014 10:32
Show Gist options
  • Save mizuhara/439b2f594fd690597bc6 to your computer and use it in GitHub Desktop.
Save mizuhara/439b2f594fd690597bc6 to your computer and use it in GitHub Desktop.
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <sstream>
using namespace std;
enum color { Red = 0, Green, Blue, };
enum direction { Left = 0, Right, Up, Down, };
struct Position
{
int row;
int col;
Position(int r, int c) : row(r), col(c) {}
};
const vector<vector<string>> triangle = {
{ "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-" },
{ "-", "-", "-", "-", "-", "a", "-", "-", "-", "-", "-" },
{ "-", "-", "-", "-", "b", "c", "d", "-", "-", "-", "-" },
{ "-", "-", "-", "e", "f", "g", "h", "i", "-", "-", "-" },
{ "-", "-", "j", "k", "l", "m", "n", "o", "p", "-", "-" },
{ "-", "q", "r", "s", "t", "u", "v", "w", "x", "y", "-" },
{ "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-" },
};
template <typename Iterator>
string join(Iterator first, Iterator last, const string &separator)
{
stringstream ss;
while(first != last) {
ss << *first;
if(first + 1 != last) {
ss << separator;
}
++first;
}
return ss.str();
}
Position get_position_of(const char c)
{
for(size_t i = 0; i < triangle.size(); ++i) {
const string s = join(triangle[i].begin(), triangle[i].end(), "");
const size_t j = s.find(c);
if(j != string::npos) {
Position p(i, j);
return p;
}
}
assert("!invalid path");
}
string get_row(size_t index)
{
string s;
const vector<string> v = triangle[index];
for(const auto &e : v) {
if(e != "-") {
s += e;
}
}
return s;
}
string get_col(size_t index)
{
string s;
for(const auto &e : triangle) {
const string tmp = e[index];
if(tmp != "-") {
s += tmp;
}
}
return s;
}
pair<color, int> solve_core(const string &src, const char ch, const Position &pos, direction dir)
{
const vector<Position> ps = {
Position(pos.row, pos.col - 1), // 左
Position(pos.row, pos.col + 1), // 右
Position(pos.row - 1, pos.col), // 上
Position(pos.row + 1, pos.col), // 下
};
const Position p = ps[dir];
const int add_num = src.find(triangle[p.row][p.col]) == string::npos ? 1 : 0;
const size_t i = get_row(p.row).find(ch);
if(dir == Left) {
const color c = i % 2 == 0 ? Green : Red;
return { c, add_num };
}
if(dir == Right) {
const color c = i % 2 == 0 ? Red : Green;
return { c, add_num };
}
return { Blue, add_num };
}
string solve(const string &src)
{
vector<int> colors = { 0, 0, 0 };
for(const auto &e : src) {
Position p = get_position_of(e);
for(const auto i : { 0, 1, 2 }) {
const direction d = [&]() {
switch(i) {
case 0:
case 1:
return static_cast<direction>(i);
case 2:
const size_t pos = get_col(p.col).find(e);
return pos % 2 == 0 ? Down : Up;
}
}();
pair<color, int> pair = solve_core(src, e, p, d);
colors[pair.first] += pair.second;
}
}
return join(colors.begin(), colors.end(), ",");
}
void test(const string &src, const string &expected)
{
const string actual = solve(src);
if(actual == expected) {
cout << "[OK]" << endl;
} else {
cout << "[NG] -> [act] " << actual << ", [exp] " << expected << endl;
}
}
void test_all()
{
/*0*/ test("bdelmnouy", "5,7,9");
/*1*/ test("a", "1,1,1");
/*2*/ test("q", "1,1,1");
/*3*/ test("t", "1,1,1");
/*4*/ test("i", "1,1,1");
/*5*/ test("fg", "2,0,2");
/*6*/ test("gh", "0,2,2");
/*7*/ test("gm", "2,2,0");
/*8*/ test("fgh", "1,1,3");
/*9*/ test("fghm", "2,2,2");
/*10*/ test("fhm", "3,3,3");
/*11*/ test("bdfhjprx", "8,8,0");
/*12*/ test("abcdfghm", "4,4,0");
/*13*/ test("jklmqrst", "0,4,4");
/*14*/ test("klmntuvw", "4,0,4");
/*15*/ test("abcdefghijklmnopqrstuvwxy", "5,5,5");
/*16*/ test("abcdefghijklmnoqrtvwxy", "6,8,4");
/*17*/ test("abdefhijklnoprstvwxy", "10,8,4");
/*18*/ test("acegikmoqsuwy", "13,13,5");
/*19*/ test("bdfhjlnprtvxy", "13,11,1");
/*20*/ test("abdegijlnpqsuwy", "15,15,15");
/*21*/ test("aefghiqrstuvwxy", "3,3,15");
/*22*/ test("cfhkmoqrstuvwxy", "7,7,15");
/*23*/ test("cfhkmortvx", "10,10,10");
/*24*/ test("no", "0,2,2");
/*25*/ test("pwy", "3,3,3");
/*26*/ test("iqwy", "4,4,4");
/*27*/ test("lopuv", "3,3,5");
/*28*/ test("abdjtw", "6,6,6");
/*29*/ test("fgpstux", "5,3,5");
/*30*/ test("dijlnotv", "6,8,2");
/*31*/ test("bdefkmpwx", "5,9,3");
/*32*/ test("bfghjlmuwx", "4,8,6");
/*33*/ test("befghlopqrw", "5,7,9");
/*34*/ test("bfgjklmnqsux", "8,6,8");
/*35*/ test("fijklnpqstvwy", "9,9,9");
/*36*/ test("abcdfgilmnrsuv", "8,6,6");
/*37*/ test("abcdegijklnpruw", "11,11,9");
/*38*/ test("efgijkmnopqrtvwx", "6,8,4");
/*39*/ test("abcdefghilopqrtwy", "9,9,7");
/*40*/ test("abfghklmopqrsuvwxy", "8,6,12");
/*41*/ test("abcdeghklmoprstuwxy", "9,7,7");
/*42*/ test("abcdehijklmnopqrtwxy", "8,8,6");
/*43*/ test("acdefghimnopqrstuvwxy", "7,3,9");
/*44*/ test("abcfghijklmnopqrtuvwxy", "6,6,6");
/*45*/ test("abcdefghijklmnoqrstuwxy", "5,7,7");
/*46*/ test("abcdeghijklmnopqrstuvwxy", "6,6,6");
}
int main()
{
test_all();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment