Skip to content

Instantly share code, notes, and snippets.

@mizuhara
Created June 5, 2016 06:27
Show Gist options
  • Save mizuhara/15d06134f02311bc85db173cc110ccfe to your computer and use it in GitHub Desktop.
Save mizuhara/15d06134f02311bc85db173cc110ccfe to your computer and use it in GitHub Desktop.
#include <vector>
#include <string>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <unordered_map>
std::string nextRoot(const std::string & root, int sideway)
{
static const std::unordered_map<std::string, std::string> um = {
{ "A", "_B______H" },
{ "B", "_AC______" },
{ "C", "__BD_____" },
{ "D", "___CE____" },
{ "E", "____DF___" },
{ "F", "_____EG__" },
{ "G", "______FH_" },
{ "H", "_______GA" },
};
return um.at(root).substr(sideway, 1);
}
std::vector<std::pair<int, bool>> createHazardMap(
const std::string & sideway,
const std::string & stone)
{
auto curStone = stone;
std::vector<std::pair<int, bool>> hazardMap;
for(size_t i = 0; i < sideway.length(); ++i)
{
const auto curSideway = atoi(sideway.substr(i, 1).c_str());
const auto r = nextRoot(curStone, curSideway);
const auto isHazard = r != "_";
if(isHazard)
{
curStone = nextRoot(curStone, curSideway);
}
hazardMap.push_back(std::make_pair(curSideway, isHazard));
}
std::reverse(std::begin(hazardMap), std::end(hazardMap));
return hazardMap;
}
bool isAdjacentSidewayExist(const std::string & root, const std::pair<int, bool> & hazardMap)
{
return nextRoot(root, hazardMap.first) != "_";
}
bool isSidewayHazard(const std::pair<int, bool> & hazardMap)
{
return hazardMap.second;
}
bool canClimbMountain(
const std::string & root,
const std::vector<std::pair<int, bool>> & hazardMap)
{
auto curRoot = root;
for(auto && hm : hazardMap)
{
if(isAdjacentSidewayExist(curRoot, hm))
{
if(isSidewayHazard(hm))
{
return false;
}
curRoot = nextRoot(curRoot, hm.first);
}
}
return true;
}
std::string solve(const std::string & sideway, const std::string & stone)
{
const std::string roots { "ABCDEFGH" };
const auto hazardMap = createHazardMap(sideway, stone);
std::string ans {};
for(auto && root : roots)
{
if(canClimbMountain(std::string {root}, hazardMap))
{
ans += root;
}
}
// #9のように全ての麓から登頂できることはない.
if(ans == roots)
{
ans.erase(roots.find(stone), 1);
}
return ans;
}
void test(const std::string & src, const std::string & expected)
{
const auto pos_to_split = src.find(":");
const auto routes = src.substr(0, pos_to_split);
const auto stone = src.substr(pos_to_split + 1, 1);
const auto actual = solve(routes, stone);
std::cout << (actual == expected ? "ok" : "***NG***" ) << std::endl;
}
void test_all()
{
/*0*/ test("2512:C", "DEFGH");
/*1*/ test("1:A", "CDEFGH");
/*2*/ test(":C", "ABDEFGH");
/*3*/ test("2345:B", "AGH");
/*4*/ test("1256:E", "ABCDH");
/*5*/ test("1228:A", "ADEFG");
/*6*/ test("5623:B", "AEFGH");
/*7*/ test("8157:C", "ABDEFGH");
/*8*/ test("74767:E", "ABCFGH");
/*9*/ test("88717:D", "ABCEFGH");
/*10*/ test("148647:A", "ACDEFH");
/*11*/ test("374258:H", "BCDEFH");
/*12*/ test("6647768:F", "ABCDEH");
/*13*/ test("4786317:E", "ABFGH");
/*14*/ test("3456781:C", "");
/*15*/ test("225721686547123:C", "CEF");
/*16*/ test("2765356148824666:F", "ABCDEH");
/*17*/ test("42318287535641783:F", "BDE");
/*18*/ test("584423584751745261:D", "FGH");
/*19*/ test("8811873415472513884:D", "CFG");
/*20*/ test("74817442725737422451:H", "BCDEF");
/*21*/ test("223188865746766511566:C", "ABGH");
/*22*/ test("2763666483242552567747:F", "ABCG");
/*23*/ test("76724442325377753577138:E", "EG");
/*24*/ test("327328486656448784712618:B", "");
/*25*/ test("4884637666662548114774288:D", "DGH");
/*26*/ test("84226765313786654637511248:H", "DEF");
/*27*/ test("486142154163288126476238756:A", "CDF");
/*28*/ test("1836275732415226326155464567:F", "BCD");
/*29*/ test("62544434452376661746517374245:G", "G");
/*30*/ test("381352782758218463842725673473:B", "A");
}
int main()
{
test_all();
return 0;
}
@mizuhara
Copy link
Author

mizuhara commented Jun 9, 2016

shiracamusさん

コメントありがとうございます。また、返事が遅くなってすみません。

rootは麓の意味で使っており、typoではないです。
ただ、山の麓の意味で使う場合はrootではなくてbaseが正しいみたいですね。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment