ぷよぷよの解答
ぷよぷよ - How to disappear completelyがもう公開しても大丈夫なので。
#include <fstream> #include <iostream> #include <vector> #include <string> #include <boost/assert.hpp> #include <boost/typeof/typeof.hpp> #include <pstade/oven/algorithm.hpp> #include <pstade/oven/begin_end.hpp> #include <pstade/oven/counting.hpp> #include <pstade/oven/dropped.hpp> #include <pstade/oven/foreach.hpp> #include <pstade/oven/identities.hpp> #include <pstade/oven/io.hpp> #include <pstade/oven/pack.hpp> #include <pstade/oven/popped.hpp> #include <pstade/oven/reversed.hpp> #include <pstade/oven/zipped.hpp> struct Puyo { char type_; bool searched_; bool erased_; }; std::ostream& operator << (std::ostream &os, Puyo const &p) { return os << "Type : " << p.type_; } class Field { public: std::vector<std::vector<Puyo>> data_; }; std::ostream &operator << (std::ostream &os, Field &f) { using namespace pstade::oven; PSTADE_OVEN_FOREACH(_1, f.data_|dropped(1)|popped) { PSTADE_OVEN_FOREACH(_1_1, _1|dropped(1)|popped) { os << (_1_1.erased_ ? '*' : _1_1.type_); } os << "\n"; } return os; } std::auto_ptr<Field> read_data(std::string const & filename) { std::ifstream ifs(filename.c_str()); if(!ifs) { throw std::runtime_error("failed to open file"); } std::string s; std::vector<std::string> lines; while(std::getline(ifs, s)) { lines.push_back(s); } struct different_pred { bool operator()(std::string const &lhs, std::string const &rhs) const { return lhs.length() != rhs.length(); } }; std::auto_ptr<Field> pf(new Field); if(lines.empty()) { pf->data_.resize(0); } else { using namespace pstade::oven; BOOST_ASSERT(adjacent_find(lines, different_pred()) == (lines|end)); size_t const ylen = lines.size() + 2; size_t const xlen = lines[0].length() + 2; Puyo const bp = { '$', false, false }; pf->data_.resize(ylen); PSTADE_OVEN_FOREACH(_1, pack(lines, pf->data_|dropped(1)|popped)|zipped) { boost::get<1>(_1).resize(xlen); for(size_t i = 0; i < xlen-2; ++i) { char const c = boost::get<0>(_1)[i]; Puyo const p = { ((c==' '||c=='0')?' ':c), false, false }; boost::get<1>(_1)[i+1] = p; } boost::get<1>(_1)[0] = boost::get<1>(_1)[xlen-1] = bp; std::cout << (boost::get<1>(_1)|identities) << std::endl; } pf->data_[0].resize(xlen); PSTADE_OVEN_FOREACH(_1, pf->data_[0]) { _1 = bp; } pf->data_[ylen-1] = pf->data_[0]; } return pf; } int search(Field &f, size_t x, size_t y, Puyo const &p, int count) { size_t const xs[] = { x-1, x, x+1, x }; //left, top, right, bottom size_t const ys[] = { y, y-1, y, y+1 }; //left, top, right, bottom for(size_t i = 0; i < 4; ++i) { Puyo &adjacent_p = f.data_[ys[i]][xs[i]]; if(adjacent_p.type_ != p.type_) { continue; } if(!adjacent_p.searched_) { adjacent_p.searched_ = true; count++; if(count >= 4) { return count; } count = search(f, xs[i], ys[i], adjacent_p, count); if(count >= 4) { return count; } } } return count; } void walk(Field &f, size_t x, size_t y, Puyo const &p) { size_t const xs[] = { x-1, x, x+1, x }; //left, top, right, bottom size_t const ys[] = { y, y-1, y, y+1 }; //left, top, right, bottom for(size_t i = 0; i < 4; ++i) { Puyo &adjacent_p = f.data_[ys[i]][xs[i]]; if(adjacent_p.type_ != p.type_) { continue; } if(!adjacent_p.erased_) { adjacent_p.erased_ = true; walk(f, xs[i], ys[i], adjacent_p); } } } bool prepare(Field &f) { using namespace pstade::oven; BOOST_AUTO(&data, f.data_); size_t const xlen = f.data_[0].size(); size_t const ylen = f.data_.size(); bool changed = false; PSTADE_OVEN_FOREACH(y, counting(1, ylen-1)) { PSTADE_OVEN_FOREACH(x, counting(1, xlen-1)) { Puyo &p = data[y][x]; if(p.searched_) { continue; } p.searched_ = true; if(p.type_ == ' ' || p.type_ == '$') { continue; } if(::search(f, x, y, p, 1) >= 4) { changed = true; p.erased_ = true; walk(f, x, y, p); } } } return changed; } void step(Field &f) { using namespace pstade::oven; BOOST_AUTO(&data, f.data_); size_t const xlen = f.data_[0].size(); size_t const ylen = f.data_.size(); //erase; PSTADE_OVEN_FOREACH(y, counting(0, ylen-2)) { PSTADE_OVEN_FOREACH(x, counting(1, xlen-1)) { while(data[ylen-2 - y][x].erased_) { for(size_t yshift = ylen-2 - y; yshift > 1; --yshift) { data[yshift][x] = data[yshift-1][x]; } Puyo const sp = { ' ', false, false }; data[1][x] = sp; } } } //reset PSTADE_OVEN_FOREACH(_1, data) { PSTADE_OVEN_FOREACH(_1_1, _1) { _1_1.searched_ = false; if(_1_1.erased_) { _1_1.type_ = ' '; _1_1.erased_ = false; } } } } int main(int argc, char **argv) { ::setlocale(LC_ALL, ""); if(argc != 2) { std::cerr << "no inputs" << std::endl; return 0; } try { std::auto_ptr<Field> f = read_data(argv[1]); std::ofstream ofs((std::string(argv[1]) + ".result").c_str()); int i = 0; while(true) { ofs << "[" << i << "]\n"; ofs << *f << std::endl; if(prepare(*f)) { ofs << "[" << i << ".5]\n"; ofs << *f << std::endl; step(*f); } else { break; } ++i; } } catch(std::exception &e) { std::cerr << "error has occured [ " << e.what() << " ]" << std::endl; return 0; } }
時間がかかってしまったので僕のレベルでは入社は難しいようです。
引数からファイル名受け取って
GYRR RYYGYG GYGYRR RYGYRG YGYRYG GYRYRG YGYRYR YGYRYR YRRGRG RYGYGG GRYGYR GRYGYR GRYGYR
こんな感じに出力します
[0] GYRR RYYGYG GYGYRR RYGYRG YGYRYG GYRYRG YGYRYR YGYRYR YRRGRG RYGYGG GRYGYR GRYGYR GRYGYR [0.5] GYRR R**GYG G*GYRR R*GYRG YGYRYG GYRYRG YGYRYR YGYRYR YRRGRG RYGYGG GRYGYR GRYGYR GRYGYR [1] YRR R GGYG G GYRR R GYRG YGYRYG GYRYRG YGYRYR YGYRYR YRRGRG RYGYGG GRYGYR GRYGYR GRYGYR
http://jbbs.livedoor.jp/bbs/read.cgi/game/45949/1237508784/28の108連鎖は動きます。
7745564556755676 5574456445677677 5574566456675566 4456745674567457 7557755775577556 4466446644664466 7456745674567457 7567456745674576 7466446644664477 4557755775577556 4567456745674576 7756745674567456 4557755775577557 7766446644664477 4756745674567456 4567456745674567 4766446644664466 7557755775577557 7567456745674567 4456745674567457 7557755775577556 4466446644664466 7456745674567457 7567456745674567 7466446644664466 4557755775577557 4567456745674567
出来上がったものをエディタの高さ合わせてPageUp/Downで見てると楽しいｗ
