Advertisement
dmkozyrev

Untitled

Apr 24th, 2018
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.41 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <string>
  3. #include <map>
  4. #include <queue>
  5. #include <cassert>
  6. #include <array>
  7.  
  8. struct State {
  9.     char ful, fur, fdl, fdr;
  10.     char lul, lur, ldl, ldr;
  11.     char bul, bur, bdl, bdr;
  12.     char rul, rur, rdl, rdr;
  13.     char uul, uur, udl, udr;
  14.     char dul, dur, ddl, ddr;
  15.    
  16.     State rotateFCW() const {
  17.         State res = *this;
  18.         res.fur = ful;
  19.         res.fdr = fur;
  20.         res.fdl = fdr;
  21.         res.ful = fdl;
  22.         res.rul = udl;
  23.         res.rdl = udr;
  24.         res.dul = rdl;
  25.         res.dur = rul;
  26.         res.lur = dul;
  27.         res.ldr = dur;
  28.         res.udl = ldr;
  29.         res.udr = lur;
  30.         return res;
  31.     }
  32.    
  33.     State rotateFCCW() const {
  34.         State res = *this;
  35.         res.ful = fur;
  36.         res.fur = fdr;
  37.         res.fdr = fdl;
  38.         res.fdl = ful;
  39.         res.udl = rul;
  40.         res.udr = rdl;
  41.         res.rdl = dul;
  42.         res.rul = dur;
  43.         res.dul = lur;
  44.         res.dur = ldr;
  45.         res.ldr = udl;
  46.         res.lur = udr;
  47.     //  assert(res.rotateFCW() == *this)
  48.         return res;
  49.     }
  50.    
  51.     State rotateLCW() const {
  52.         State res = *this;
  53.         res.lur = lul;
  54.         res.ldr = lur;
  55.         res.ldl = ldr;
  56.         res.lul = ldl;
  57.         res.ful = uul;
  58.         res.fdl = udl;
  59.         res.dul = ful;
  60.         res.ddl = fdl;
  61.         res.bdr = dul;
  62.         res.bur = ddl;
  63.         res.uul = bdr;
  64.         res.udl = bur;
  65.         //assert(res.rotateLCCW() == *this);
  66.         return res;
  67.     }
  68.    
  69.     State rotateLCCW() const {
  70.         State res = *this;
  71.         res.lul = lur;
  72.         res.lur = ldr;
  73.         res.ldr = ldl;
  74.         res.ldl = lul;
  75.         res.uul = ful;
  76.         res.udl = fdl;
  77.         res.ful = dul;
  78.         res.fdl = ddl;
  79.         res.dul = bdr;
  80.         res.ddl = bur;
  81.         res.bdr = uul;
  82.         res.bur = udl;
  83.     //  assert(res.rotateLCW() == *this);
  84.         return res;
  85.     }
  86.    
  87.     State rotateUCW() const {
  88.         State res = *this;
  89.         //assert(res.rotateUCCW() == *this);
  90.         res.uur = uul;
  91.         res.udr = uur;
  92.         res.udl = udr;
  93.         res.uul = udl;
  94.         res.ful = rul;
  95.         res.fur = rur;
  96.         res.lul = ful;
  97.         res.lur = fur;
  98.         res.bul = lul;
  99.         res.bur = lur;
  100.         res.rul = bul;
  101.         res.rur = bur;
  102.         return res;
  103.     }
  104.    
  105.     State rotateUCCW() const {
  106.         State res = *this;
  107.         res.uul = uur;
  108.         res.uur = udr;
  109.         res.udr = udl;
  110.         res.udl = uul;
  111.         res.rul = ful;
  112.         res.rur = fur;
  113.         res.ful = lul;
  114.         res.fur = lur;
  115.         res.lul = bul;
  116.         res.lur = bur;
  117.         res.bul = rul;
  118.         res.bur = rur;
  119.         //assert(res.rotateUCW() == *this);
  120.         return res;
  121.     }
  122.    
  123.     static State read() {
  124.         State p;
  125.         scanf(" %c%c %c%c %c%c %c%c %c%c %c%c", &p.ful, &p.fur, &p.lul, &p.lur, &p.bul, &p.bur, &p.rul, &p.rur, &p.uul, &p.uur, &p.dul, &p.dur);
  126.         scanf(" %c%c %c%c %c%c %c%c %c%c %c%c", &p.fdl, &p.fdr, &p.ldl, &p.ldr, &p.bdl, &p.bdr, &p.rdl, &p.rdr, &p.udl, &p.udr, &p.ddl, &p.ddr);
  127.         return p;
  128.     }
  129.    
  130.     std::string to_string() const {
  131.         char buf[25] = {};
  132.         sprintf(buf, "%c%c%c%c%c%c%c%c%c%c%c%c", ful, fur, lul, lur, bul, bur, rul, rur, uul, uur, dul, dur);
  133.         sprintf(buf+12, "%c%c%c%c%c%c%c%c%c%c%c%c", fdl, fdr, ldl, ldr, bdl, bdr, rdl, rdr, udl, udr, ddl, ddr);
  134.         return buf;
  135.     }
  136.    
  137.     bool isSolved() const {
  138.         return
  139.             ful == fur && ful == fdl && ful == fdr &&
  140.             lul == lur && lul == ldl && lul == ldr &&
  141.             bul == bur && bul == bdl && bul == bdr &&
  142.             rul == rur && rul == rdl && rul == rdr &&
  143.             uul == uur && uul == udl && uul == udr &&
  144.             dul == dur && dul == ddl && dul == ddr;
  145.     }
  146. };
  147.  
  148. bool operator<(const State& left, const State& right) {
  149.     if (left.ful < right.ful) return true;
  150.     if (left.ful > right.ful) return false;
  151.     if (left.fur < right.fur) return true;
  152.     if (left.fur > right.fur) return false;
  153.     if (left.fdl < right.fdl) return true;
  154.     if (left.fdl > right.fdl) return false;
  155.     if (left.fdr < right.fdr) return true;
  156.     if (left.fdr > right.fdr) return false;
  157.     if (left.lul < right.lul) return true;
  158.     if (left.lul > right.lul) return false;
  159.     if (left.lur < right.lur) return true;
  160.     if (left.lur > right.lur) return false;
  161.     if (left.ldl < right.ldl) return true;
  162.     if (left.ldl > right.ldl) return false;
  163.     if (left.ldr < right.ldr) return true;
  164.     if (left.ldr > right.ldr) return false;
  165.     if (left.bul < right.bul) return true;
  166.     if (left.bul > right.bul) return false;
  167.     if (left.bur < right.bur) return true;
  168.     if (left.bur > right.bur) return false;
  169.     if (left.bdl < right.bdl) return true;
  170.     if (left.bdl > right.bdl) return false;
  171.     if (left.bdr < right.bdr) return true;
  172.     if (left.bdr > right.bdr) return false;
  173.     if (left.rul < right.rul) return true;
  174.     if (left.rul > right.rul) return false;
  175.     if (left.rur < right.rur) return true;
  176.     if (left.rur > right.rur) return false;
  177.     if (left.rdl < right.rdl) return true;
  178.     if (left.rdl > right.rdl) return false;
  179.     if (left.rdr < right.rdr) return true;
  180.     if (left.rdr > right.rdr) return false;
  181.     if (left.uul < right.uul) return true;
  182.     if (left.uul > right.uul) return false;
  183.     if (left.uur < right.uur) return true;
  184.     if (left.uur > right.uur) return false;
  185.     if (left.udl < right.udl) return true;
  186.     if (left.udl > right.udl) return false;
  187.     if (left.udr < right.udr) return true;
  188.     if (left.udr > right.udr) return false;
  189.     if (left.dul < right.dul) return true;
  190.     if (left.dul > right.dul) return false;
  191.     if (left.dur < right.dur) return true;
  192.     if (left.dur > right.dur) return false;
  193.     if (left.ddl < right.ddl) return true;
  194.     if (left.ddl > right.ddl) return false;
  195.     if (left.ddr < right.ddr) return true;
  196.     if (left.ddr > right.ddr) return false;
  197.     return false;
  198. }
  199.  
  200. bool operator>(const State& a, const State& b) {
  201.     return b < a;
  202. }
  203.  
  204. bool operator==(const State& a, const State& b) {
  205.     return !(a < b || a > b);
  206. }
  207.  
  208. bool operator!=(const State& a, const State& b) {
  209.     return !(a == b);
  210. }
  211.  
  212. int main() {
  213.     //freopen("input.txt", "rt", stdin);
  214.     std::map<State, State> from;
  215.     State start = State::read();
  216.     from[start] = start;
  217.     std::queue<State> queue;
  218.     queue.push(start);
  219.     State t = start;
  220.     //int count = 0;
  221.     while (!queue.empty()) {
  222.         State curr = queue.front(); queue.pop();
  223.         if (++count % 10000 == 0) {
  224.             printf("runned: %d\n", count);
  225.         }
  226.         /*
  227.         if (curr.isSolved()) {
  228.             t = curr;
  229.             break;
  230.         } */
  231.         for (auto& next : {curr.rotateFCW(),
  232.             curr.rotateFCCW(),
  233.             curr.rotateUCW(),
  234.             curr.rotateUCCW(),
  235.             curr.rotateLCW(),
  236.             curr.rotateLCCW()})
  237.         {
  238.             if (from.find(next) == from.end()) {
  239.                 from[next] = curr;
  240.                 queue.push(next);
  241.             }
  242.         }
  243.     }
  244.    
  245.     printf("size = %d\n", (int)from.size());
  246.     return 0;
  247.    
  248.     std::string answer = "";
  249.     while (t != from[t]) {
  250.         auto p = from[t];
  251.         if (p.rotateFCW() == t) {
  252.             answer = "F" + answer;
  253.         } else if (p.rotateFCCW() == t) {
  254.             answer = "F'" + answer;
  255.         } else if (p.rotateUCW() == t) {
  256.             answer = "U" + answer;
  257.         } else if (p.rotateUCCW() == t) {
  258.             answer = "U'" + answer;
  259.         } else if (p.rotateLCW() == t) {
  260.             answer = "L" + answer;
  261.         } else if (p.rotateLCCW() == t) {
  262.             answer = "L'" + answer;
  263.         } else {
  264.             throw std::runtime_error("Can not find rotation!");
  265.         }
  266.         t = p;
  267.     }
  268.     printf("%s", answer == "" ? "Solved" : answer.c_str());
  269.     return 0;
  270. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement