Skip to content

Instantly share code, notes, and snippets.

@mizuhara

mizuhara/yhpg.cpp

Last active December 4, 2017 12:37
Show Gist options
  • Save mizuhara/f3c3f27553de87f7e0cd071f8cc573a5 to your computer and use it in GitHub Desktop.
Save mizuhara/f3c3f27553de87f7e0cd071f8cc573a5 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
yhpg.cpp
#include <cctype>
#include <string>
#include <vector>
#include <sstream>
#include <iterator>
#include <iostream>
#include <algorithm>
const char unoccupied_char = '-';
const std::vector<std::size_t> index_to_chair_number = {
1, 3, 5, 7, 9, 8, 6, 4, 2,
};
template <typename Container> std::string join(const Container & c, const std::string & delim)
{
std::stringstream ss;
for(auto && e : c) {
ss << e;
ss << delim;
}
return ss.str();
}
template <typename Pred> std::vector<std::size_t> find_most_comfortable_chairs(const std::vector<char> & chairs, const Pred & pred)
{
std::vector<std::size_t> ret;
for(std::size_t i = 0, sz = chairs.size(); i < sz; ++i) {
const auto left = (i + 1) % sz;
const auto right = (i + sz - 1) % sz;
if(pred(chairs, left, i, right)) {
ret.push_back(index_to_chair_number[i]);
}
}
std::sort(std::begin(ret), std::end(ret));
return ret;
}
bool is_occupied(const std::vector<char> & chairs, std::size_t i)
{
return chairs[i] != unoccupied_char;
}
bool is_most_comfortable_chair(const std::vector<char> & chairs, std::size_t left, std::size_t middle, std::size_t right)
{
return !is_occupied(chairs, middle) && !is_occupied(chairs, left) && !is_occupied(chairs, right);
}
bool is_2nd_most_comfortable_chair(const std::vector<char> & chairs, std::size_t left, std::size_t middle, std::size_t right)
{
const bool left_is_unoccupied = !is_occupied(chairs, left) && is_occupied(chairs, right);
const bool right_is_unoccupied = is_occupied(chairs, left) && !is_occupied(chairs, right);
return !is_occupied(chairs, middle) && (left_is_unoccupied || right_is_unoccupied);
}
bool is_3rd_most_comfortable_chair(const std::vector<char> & chairs, std::size_t left, std::size_t middle, std::size_t right)
{
return !is_occupied(chairs, middle);
}
bool prefer_smallest_number(char c)
{
return ('A' <= c) && (c <= 'M');
}
bool may_leave(char passenger)
{
return ('a' <= passenger) && (passenger <= 'z');
}
std::string solve(const std::string & src)
{
using rule_t =
bool (*)(const std::vector<char> &, std::size_t, std::size_t, std::size_t);
const rule_t rules[] = {
is_most_comfortable_chair, is_2nd_most_comfortable_chair, is_3rd_most_comfortable_chair,
};
std::vector<char> chairs(9, unoccupied_char);
for(auto && passanger : src) {
if(may_leave(passanger)) {
auto pos = std::find(std::begin(chairs), std::end(chairs), std::toupper(passanger));
*pos = unoccupied_char;
continue;
}
for(auto && rule : rules) {
const auto most_comfortable_chairs = find_most_comfortable_chairs(chairs, rule);
if(!most_comfortable_chairs.empty()) {
const auto pos = prefer_smallest_number(passanger) ? *most_comfortable_chairs.begin() : *(most_comfortable_chairs.end() - 1);
const auto it = std::find(std::begin(index_to_chair_number), std::end(index_to_chair_number), pos);
const auto i = std::distance(std::begin(index_to_chair_number), it);
chairs[i] = passanger;
break;
}
}
}
return join(chairs, "");
}
void test(const std::string & src, const std::string & expected)
{
const auto actual = solve(src);
if(actual == expected) {
std::cout << "ok" << std::endl;
} else {
std::cout << "[act] [exp]: [" << actual << "] [" << expected << "]" << std::endl;
}
}
void test_all()
{
/*0*/ test("NABETanI", "I-E--T-B-");
/*1*/ test("A", "A--------");
/*2*/ test("Aa", "---------");
/*3*/ test("Z", "----Z----");
/*4*/ test("Zz", "---------");
/*5*/ test("AaB", "B--------");
/*6*/ test("ABa", "-------B-");
/*7*/ test("ABCDEFGHI", "AGCEIDHBF");
/*8*/ test("OPQRSTUVW", "WSQUOTPVR");
/*9*/ test("F", "F--------");
/*10*/ test("L", "L--------");
/*11*/ test("Mm", "---------");
/*12*/ test("JQ", "J---Q----");
/*13*/ test("ACP", "A---P--C-");
/*14*/ test("GgS", "----S----");
/*15*/ test("USLE", "L-E-U-S--");
/*16*/ test("XJZY", "J-Y-X-Z--");
/*17*/ test("NnJXx", "J--------");
/*18*/ test("AJjQa", "----Q----");
/*19*/ test("HGThgQ", "----T-Q--");
/*20*/ test("NJRErI", "J-E-N--I-");
/*21*/ test("ZzWwDYG", "D---Y--G-");
/*22*/ test("ZGgKQHM", "K-H-Z-Q-M");
/*23*/ test("OZYSAsHP", "A-Y-OPZ-H");
/*24*/ test("VNnEISAW", "E-S-VWAI-");
/*25*/ test("HhYAKkCOE", "A-O-Y-EC-");
/*26*/ test("KAkHJTSWV", "H-JWTSVA-");
/*27*/ test("WNTYKHZhMQ", "KMTQWZN-Y");
/*28*/ test("YyJHFGfgTh", "J---T----");
/*29*/ test("NRWPLBZAOpC", "LBWONZRAC");
/*30*/ test("IORiTMXHUCF", "MCTFOURXH");
/*31*/ test("AEeHGBEJUNZn", "AZGEUB-HJ");
/*32*/ test("GgKGSOsZTLYS", "K-OYZTSGL");
/*33*/ test("VZvPOpWPMzHGF", "MGO-W-HFP");
/*34*/ test("CMmcUuLTWADFQ", "LFA-TQW-D");
/*35*/ test("HUGZMLzlNgTLDd", "H-N-U-MTL");
/*36*/ test("CFKEkHeJShUDTf", "C-UTSJ--D");
/*37*/ test("QJjGPMAICHKqWcY", "GIMHWKPYA");
/*38*/ test("HhIiQCIBiUMZcVv", "--B-QZU-M");
/*39*/ test("VMvEmFOPANIBUiVb", "F-PUONAEV");
/*40*/ test("EDCJUINdLPVnFpGe", "-VCFUJGLI");
/*41*/ test("FGQINTEnLMAlBbPpV", "FMITQAVGE");
/*42*/ test("WSVCORUMXsvNBuTtT", "CXBTWRNOM");
/*43*/ test("HJTjRVIQAXqDGxCtUh", "-AVCUGRDI");
/*44*/ test("ZzHXIEKQYUuBTxLlCq", "HTEYC-KIB");
/*45*/ test("RGDCAEBVrgFbTJUePjc", "-T-FUVADP");
/*46*/ test("WBIRSALCVvsbwalYBJP", "B-R-YPCIJ");
/*47*/ test("HKFZGEPAIphLRarAOaHo", "LHFIZ-GKE");
/*48*/ test("WFNwBfbSAXCZzMDJUcKx", "AM-JSUNDK");
}
int main()
{
test_all();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment