fork(8) download
copy 
  1. // 2D to 1D Maze Checker.
  2. //
  3. // Instructions:
  4. //
  5. // The maze checker accepts as input a 2D traditional maze,
  6. // followed by a 1D maze.  An example input is:
  7. //
  8. // +-+-+-+-+-+-+
  9. // | |   |     |
  10. // + + + + +-+-+
  11. // |   | |     |
  12. // +-+-+ +-+-+ +
  13. // |           |
  14. // +-+-+-+ +-+ +
  15. // |         | |
  16. // + +-+-+-+ + +
  17. // | |       | |
  18. // +-+-+-+-+-+-+
  19. // |  D|  D E|G E F|  F  |  G  |
  20. //
  21. // If you compile this checker on your own system, the maze checker
  22. // will also accept as an argument the name of a file containing
  23. // both mazes.  If you have two arguments, the checker will use
  24. // the first as the filename for the 2D maze, and the second as
  25. // the filename for the 1D maze.
  26. //
  27. // If you compile this on your own system and run it in say bash,
  28. // you can link this up directly to your program for a maze.
  29. // To use it this way, use a piped redirect as your second argument,
  30. // like so:
  31. //
  32. //    ./a.exe mazefilename <(./runmyprogram)
  33. //
  34. // ...where mazefilename contains a 2D maze, and your program simply
  35. // outputs to stdout the 1D maze.
  36. //
  37. // This checker is intentionally non-golfy; if you can follow it
  38. // feel free to steal some algorithm hints.  However, it doesn't
  39. // actually do anything to make 1D mazes...
  40.  
  41. #include <string>
  42. #include <vector>
  43. #include <algorithm>
  44. #include <iostream>
  45. #include <iomanip>
  46. #include <fstream>
  47. #include <utility>
  48. #include <iterator>
  49. #include <unordered_set>
  50.  
  51. // XXX XXX XXX
  52. // Uncomment this for canonicalization diagnostics
  53. //#define DIAGNOSTICS
  54.  
  55. using namespace std;
  56. vector<string> tr;
  57. unordered_set<unsigned> visited;
  58.  
  59. // True iff c is a valid wall character
  60. bool wall(char c) {
  61.    switch (c) {
  62.    case '+':
  63.    case '-':
  64.    case '|':
  65.       return true;
  66.    }
  67.    return false;
  68. }
  69.  
  70. // True iff c is a valid space character
  71. bool space(char c) {
  72.    if (c==' ') return true;
  73.    return false;
  74. }
  75.  
  76. // Convert an ofset to a maze-character
  77. char ofs2mc(unsigned int o) {
  78.    if (o<26) return 'A'+o;
  79.    o-=26;
  80.    if (o<26) return 'a'+o;
  81.    return 0;
  82. }
  83.  
  84. // Convert a maze-character to an offset
  85. unsigned mc2ofs(char c) {
  86.    if (c>='A'&&c<='Z') return c-'A';
  87.    if (c>='a'&&c<='z') return 26+c-'a';
  88.    return 255;
  89. }
  90.  
  91. // True iff c is a valid warp character
  92. bool warpchar(char c) {
  93.    return mc2ofs(c)<255;
  94. }
  95.  
  96. // True iff r is a row consisting only of a wall
  97. bool solidrow(const string& r) { return r.find_first_not_of("+-|")==string::npos; }
  98. // True iff r has +'s for all lattice points.
  99. bool latticed(const string& r) {
  100.    for (unsigned i=0, e=r.size(); i<e; i+=2) if (!wall(r[i])) return false;
  101.    return true;
  102. }
  103. // True iff r has internal spaces as required for non-latticed rows
  104. bool spaced(const string& r) {
  105.    for (unsigned i=1, e=r.size(); i<e; i+=2) if (!space(r[i])) return false;
  106.    return true;
  107. }
  108. // Adds row if valid, returns true if valid, and sets finished to true
  109. // if valid, if this is not the first row, and if it's a wall.
  110. // If invalid, returns false.
  111. bool add(string& row, bool &finished) {
  112.    if (!row.empty()) {
  113.       if (row[row.size()-1]=='\r') row.resize(row.size()-1);
  114.    }
  115.    if (row.empty()) return false;
  116.    if (row.size()<4) return false;
  117.    if (0==row.size()%2) return false;
  118.    if (tr.empty()) {
  119.       if (!solidrow(row)) return false;
  120.       if (!latticed(row)) return false;
  121.       tr.emplace_back("");
  122.       tr.back().swap(row);
  123.       return true;
  124.    }
  125.    if (0==(tr.size()%2)) {
  126.       if (!latticed(row)) return false;
  127.       tr.push_back(row);
  128.       if (solidrow(row)) return finished=true;
  129.       return true;
  130.    }
  131.    if (row[0]!='|') return false;
  132.    if (row[row.size()-1]!='|') return false;
  133.    if (!spaced(row)) return false;
  134.    tr.push_back(row);
  135.    return true;
  136. }
  137.  
  138. // Generic graph structure
  139. struct Graph {
  140.    // Stores the edges in the graph.
  141.    // The n-th entry is node n.  Each char in the string
  142.    // represents an edge to n.
  143.    std::vector<string> edges;
  144.    unsigned makenode() {
  145.       if (edges.size()>=52) return 53;
  146.       unsigned rv = edges.size();
  147.       edges.push_back(string());
  148.       return rv;
  149.    }
  150.    void addEdge(unsigned e1, unsigned e2) {
  151.       edges[e1].push_back(ofs2mc(e2));
  152.       edges[e2].push_back(ofs2mc(e1));
  153.    }
  154.    void showGraph() {
  155.       for (unsigned i=0, e=edges.size(); i<e; ++i) {
  156.          const string& edgelist = edges[i];
  157.          for (unsigned int j=0, je=edgelist.size(); j<je; ++j) {
  158.             if (mc2ofs(edgelist[j])<i) continue;
  159.             cout << ofs2mc(i) << " - " << edgelist[j] << "\n";
  160.          }
  161.       }
  162.    }
  163. };
  164.  
  165. // Scan a maze searching for any dead end at all.
  166. // We don't need to path search here; we know an end when
  167. // we see one, and left to right/top to bottom search suffices.
  168. bool findanend(unsigned &x, unsigned& y) {
  169.    const unsigned width = tr[0].size();
  170.    const unsigned height = tr.size();
  171.    for (y=1; y<height; y+=2) {
  172.       for (x=1; x<width; x+=2) {
  173.          bool left  = (tr[y][x-1]==' ');
  174.          bool up    = (tr[y-1][x]==' ');
  175.          bool right = (tr[y][x+1]==' ');
  176.          bool down  = (tr[y+1][x]==' ');
  177.          if (left+up+right+down==1) return true;
  178.       }
  179.    }
  180.    return false;
  181. }
  182.  
  183. // Creates a graph out of the maze in (global) tr.
  184. //
  185. // Directions:
  186. //    1
  187. //  0 x 2
  188. //    3
  189. bool makegraph(Graph& g, unsigned x=1, unsigned y=1, int fromdir=-1, int fromnode=-1) {
  190.    unsigned edges=0;
  191.    if (fromdir<0) {
  192.       // This algorithm requires starting with a location that's a node
  193.       // in order to correctly hook the first found endpoints.
  194.       //
  195.       // Finding an end is the easiest way to prime the pump for this.
  196.       if (!findanend(x,y)) { cerr << "cannot find an end" << endl; return false; }
  197.    }
  198.    if (visited.count((x<<16)|y)) { cerr << "already visited " << x << "," << y << endl; return false; }
  199.    visited.insert((x<<16)|y);
  200.    bool left  = (fromdir-0) && (tr[y][x-1]==' ');
  201.    bool up    = (fromdir-1) && (tr[y-1][x]==' ');
  202.    bool right = (fromdir-2) && (tr[y][x+1]==' ');
  203.    bool down  = (fromdir-3) && (tr[y+1][x]==' ');
  204.    bool from  = (fromdir+1);
  205.    int nextnode = fromnode;
  206.    switch (edges = left+up+right+down+from) {
  207.    case 1:
  208.    case 3:
  209.    case 4:
  210.       nextnode = g.makenode();
  211.       tr[y][x]=ofs2mc(nextnode);
  212.       if (nextnode>52) { cerr << "node limit exceeded" << endl; return false; }
  213.       if (fromnode>=0) g.addEdge(fromnode, nextnode);
  214.    }
  215.    if (left ) if (!makegraph(g, x-2, y  , 2, nextnode)) return false;
  216.    if (up   ) if (!makegraph(g, x  , y-2, 3, nextnode)) return false;
  217.    if (right) if (!makegraph(g, x+2, y  , 0, nextnode)) return false;
  218.    if (down ) if (!makegraph(g, x  , y+2, 1, nextnode)) return false;
  219.    return true;
  220. }
  221.  
  222. bool testallvisited() {
  223.    const unsigned width = tr[0].size();
  224.    const unsigned height = tr.size();
  225.    for (unsigned y=1; y<height; y+=2) {
  226.       for (unsigned x=1; x<width; x+=2) {
  227.          if (!visited.count((x<<16)|y)) return false;
  228.       }
  229.    }
  230.    return true;
  231. }
  232.  
  233. // Join (concatenate) all strings from begin to end.
  234. template<typename I> string join(I begin, I end) {
  235.    string rv;
  236.    while (begin!=end) {rv.append(*begin); ++begin;}
  237.    return rv;
  238. }
  239.  
  240. // Canonicalize the graphs.  Note that this canonicalization algorithm
  241. // is tailored for the types of graphs we care about (namely, connected
  242. // graphs with no cycles; aka "unrooted trees").
  243. string canonicalize(const Graph& graph) {
  244.    // A replacement to perform
  245.    struct Replacement {
  246.       unsigned at;
  247.       char     var;
  248.       string   with;
  249. #ifdef DIAGNOSTICS
  250.       void prn() {
  251.          cerr << ":" << ofs2mc(at) << ":s/" << var << "/" << with << "/" << endl;
  252.       }
  253. #endif
  254.    };
  255.    // A "canon" represents a canonical form for a subset of the graph
  256.    // built onto a node.  Not until we connect the final edges does
  257.    // this canon actually represent the graph.
  258.    //
  259.    // There is a "Canon" per node; which we'll just call the canon
  260.    // for that node.
  261.    struct Canon {
  262.       // The "canon" for each edge of this node.
  263.       // Initially, this is just the name of the far node;
  264.       // with respect to the canon we consider this a "variable".
  265.       vector<string> eds;
  266. #ifdef DIAGNOSTICS
  267.       void prn() {
  268.          cerr << "{";
  269.          for (unsigned i=0,e=eds.size(); i<e; ++i)
  270.             cerr << " {" << eds[i] << "}";
  271.          cerr << " }" << endl;
  272.       }
  273. #endif
  274.       void add(const string& nodelist) {
  275.          eds.resize(nodelist.size());
  276.          for (unsigned i=0,e=eds.size(); i<e; ++i)
  277.             eds[i]=nodelist.substr(i,1);
  278.       }
  279.       unsigned size() const { return eds.size(); }
  280.       // Count the variables in this Canon
  281.       unsigned varct() const {
  282.          unsigned rv=0;
  283.          for (unsigned i=0,e=size(); i<e; ++i)
  284.             if (eds[i].size()==1) rv+=warpchar(eds[i][0]);
  285.          return rv;
  286.       }
  287.       // Returns a canonical substitution for a single variable.
  288.       string substitution() {
  289.          if (varct()!=1) throw 2;
  290.          sort(eds.begin(), eds.end());
  291.          return join(eds.begin()+1, eds.end());
  292.       }
  293.       // Returns a full canon.  This is used once we run out
  294.       // of variables to replace.  _Each_ full canon represents
  295.       // the entire graph; _one_ of them (lexically chosen)
  296.       // is the graph's canonical form.
  297.       string canon() {
  298.          if (varct()) throw 2;
  299.          sort(eds.begin(),eds.end());
  300.          return join(eds.begin(), eds.end());
  301.       }
  302.       // Apply a replacement to a node.
  303.       bool apply(const Replacement& r) {
  304.          for (unsigned i=0,e=size(); i<e; ++i)
  305.             if ((eds[i].size()==1)&&(eds[i][0]==r.var)) {
  306.                eds[i]=string("}")+r.with+string("{");
  307.                return true;
  308.             }
  309.          return false;
  310.       }
  311.    };
  312.    vector<Canon> es(graph.edges.size());
  313.    unsigned const gsize=graph.edges.size();
  314.    unsigned int maxedges=0;
  315.    for(unsigned i=0; i<gsize; ++i) {
  316.       const string& er = graph.edges[i];
  317.       if (er.size()>maxedges) maxedges=er.size();
  318.       if (maxedges>4) return "";
  319.       es[i].add(er);
  320.    }
  321.    string rv;
  322.    unordered_set<unsigned> cullset;
  323.    for (unsigned varNodesLeft=es.size();varNodesLeft;) {
  324.       varNodesLeft=0;
  325.       vector<Replacement> rlist;
  326. #ifdef DIAGNOSTICS
  327.       cerr << "------- loop" << endl;
  328.       cerr << gsize << "/" << cullset.size() << endl;
  329. #endif
  330.       // Cycle 1: Find all substitutables...
  331.       // these are nodes with only one edge left as a variable
  332.  
  333.       // Ignore nodes with no variables,
  334.       // form replacements for nodes with one variable,
  335.       // and count all other nodes
  336.       for (unsigned i=0; i<gsize; ++i) {
  337.          if (cullset.count(i)) continue;
  338.          Canon& node = es[i];
  339.          switch (node.varct()) {
  340.          case 0:
  341. #ifdef DIAGNOSTICS
  342.             cerr << ofs2mc(i) << ": 0 size :"; node.prn();
  343. #endif
  344.             continue;
  345.          case 1:
  346.             {
  347. #ifdef DIAGNOSTICS
  348.                cerr << ofs2mc(i) << ": 1 size :"; node.prn();
  349. #endif
  350.                cullset.insert(i);
  351.                string nodecanon = node.substitution();
  352.                rlist.emplace_back(
  353.                   Replacement{
  354.                   mc2ofs(node.eds[0][0]),
  355.                   ofs2mc(i),
  356.                   nodecanon
  357.                   });
  358. #ifdef DIAGNOSTICS
  359.                rlist.back().prn();
  360. #endif
  361.                continue;
  362.             }
  363.          default:
  364. #ifdef DIAGNOSTICS
  365.             cerr << ofs2mc(i) << ": 2* size :"; node.prn();
  366. #endif
  367.             ++varNodesLeft;
  368.          }
  369.       }
  370.       if (rlist.empty()) {
  371.          // cannot proceed; something's off
  372.          if (varNodesLeft) {
  373. #ifdef DIAGNOSTICS
  374.             cerr << "ABORT" << endl;
  375. #endif
  376.             return ""; 
  377.          }
  378. #ifdef DIAGNOSTICS
  379.          cerr << "END_OF_SUBS" << endl;
  380. #endif
  381.          break;
  382.       }
  383.       rv.clear();
  384.       for (unsigned i=0, e=rlist.size(); i<e; ++i) {
  385.          auto rentry=rlist[i];
  386.          auto & rnode=es[rentry.at];
  387.          rnode.apply(rentry);
  388. #ifdef DIAGNOSTICS
  389.          cerr << "[*" << ofs2mc(rentry.at) << "]: "; rnode.prn();
  390. #endif
  391.          //if (varNodesLeft) continue;
  392.          if (rnode.varct()) continue;
  393.          string thisc = rnode.canon();
  394. #ifdef DIAGNOSTICS
  395.          cerr << "considering " << thisc;
  396. #endif
  397.          if (thisc>rv) {
  398.             rv=thisc;
  399. #ifdef DIAGNOSTICS
  400.             cerr << "...preferred" << endl;
  401.          } else {
  402.             cerr << "...rejected for " << rv << endl;
  403. #endif
  404.          }
  405.       }
  406. #ifdef DIAGNOSTICS
  407.       cerr << "-- var nodes " << varNodesLeft << endl;
  408.       cerr << "rv candidate: " << rv << endl;
  409. #endif
  410.    }
  411.    for_each(rv.begin(),rv.end(),[](char&c){
  412.             c=(c-'{')?'(':')';
  413.             });
  414. #ifdef DIAGNOSTICS
  415.    cerr << "Canonical:" << rv << endl;
  416. #endif
  417.    return rv;
  418. }
  419.  
  420. int main(int argc, const char* argv[])
  421. {
  422.    string row;
  423.    bool finished=false;
  424.    unique_ptr<ifstream> pif;
  425.    istream* in = &cin;
  426.    if (argc>1) {
  427.       pif.reset(new ifstream(argv[1]));
  428.       in = pif.get();
  429.    }
  430.  
  431.    while (!finished
  432.           && getline(*in, row)
  433.           && add(row, finished))
  434.    {
  435.    }
  436.    if (!finished) {
  437.       cerr << "Not a valid maze" << endl;
  438.       cerr << tr.size() << " lines read" << endl;
  439.       return 1;
  440.    }
  441.    Graph tmg;
  442.    if (!makegraph(tmg)) {
  443.       cerr << "Not a compliant maze" << endl;
  444.       return 1;
  445.    }
  446.    if (!testallvisited()) {
  447.       cerr << "Not a compliant maze (not all visited)" << endl;
  448.       return 1;
  449.    }
  450.  
  451.    // XXX XXX XXX
  452.    // Uncomment if you want to see your maze with node labels
  453.    //    copy(tr.begin(), tr.end(), ostream_iterator<string>(cout,"\n"));
  454.  
  455.    // XXX XXX XXX
  456.    // Uncomment if you want to see your graph in edge form
  457.    //    tmg.showGraph();
  458.  
  459.    string canonicalTM = canonicalize(tmg);
  460.    row.clear();
  461.    if (argc>2) {
  462.       pif.reset(new ifstream(argv[2]));
  463.       in = pif.get();
  464.    }
  465.    while (getline(*in, row)) {
  466.       if (row.empty()) continue;
  467.       // Allow allows a "->" between the mazes
  468.       if (row.find_first_of(">")!=string::npos) continue;
  469.       // Allow blank lines with whitespace between mazes
  470.       if (row.find_first_not_of(" \t\r\n")==string::npos) continue;
  471.       break;
  472.    }
  473.    if (row.empty()) {
  474.       cerr << "1D Maze not found" << endl;
  475.       return 1;
  476.    }
  477.    if (row[row.size()-1]=='\r') row.resize(row.size()-1);
  478.    if (0==row.size()%2) {
  479.       cerr << "Not a valid 1D maze; width must be odd (mazes built on lattice points)" << endl;
  480.       return 1;
  481.    }
  482.    if ((row[0]!='|')||(row[row.size()-1]!='|')) {
  483.       cerr << "1D maze error: No outer walls" << endl;
  484.       return 1;
  485.    }
  486.    for (unsigned i=0, e=row.size(); i<e; i+=2) {
  487.       if ((row[i]!='|')&&(row[i]!=' ')) {
  488.          cerr
  489.             << row << "\n"
  490.             << setw(i+1) << "^" << "\n"
  491.             << "Lattice point must be wall or space" << endl;
  492.          return 1;
  493.       }
  494.    }
  495.    {
  496.       unsigned ct[52]={};
  497.       for (unsigned i=0, e=row.size(); i<e; ++i) {
  498.          switch (row[i]) {
  499.          case '|':
  500.          case ' ':
  501.             continue;
  502.          default:
  503.             break;
  504.          }
  505.          if (warpchar(row[i])) {
  506.             if (++ct[mc2ofs(row[i])]>2) {
  507.                cerr << "Warp point " << row[i] << " can only appear twice" << endl;
  508.                return 1;
  509.             }
  510.          }
  511.       }
  512.       for (unsigned i=0; i<52; ++i) {
  513.          if (ct[i]==2) continue;
  514.          if (ct[i]==0) continue;
  515.          cerr << "Warp point " << ofs2mc(i) << " must appear twice" << endl;
  516.          return 1;
  517.       }
  518.    }
  519.  
  520.    Graph w1dgraph;
  521.    unsigned warps[52]; fill(warps, warps+52, 52);
  522.    int from=-1;
  523.    for (unsigned i=0;;++i) {
  524.       unsigned ndx=i*2+1;
  525.       if (ndx>=row.size()) break;
  526.       unsigned gsize = w1dgraph.edges.size();
  527.       int to = 0;
  528.       char p=row[ndx];
  529.       if (warpchar(p)) {
  530.          if (warps[mc2ofs(p)]==52) {
  531.             to = w1dgraph.makenode();
  532.             warps[mc2ofs(p)] = to;
  533.          } else {
  534.             to = warps[mc2ofs(p)];
  535.          }
  536.       } else if (p==' ') {
  537.          to = w1dgraph.makenode();
  538.       } else throw 1;
  539.       if ((from>=0)&&(row[ndx-1]==' ')) {
  540.          w1dgraph.addEdge(from,to);
  541.       }
  542.       from=to;
  543.    }
  544.    // XXX XXX XXX
  545.    // Uncomment if you want to see your 1D maze's graph once relabeled
  546.    string canonical1D = canonicalize(w1dgraph);
  547.    if (canonicalTM != canonical1D) {
  548.       cerr
  549.          << "This doesn't look right...\n"
  550.          << "The traditional maze's graph has the canonical form:\n"
  551.          << "  " << canonicalTM << "\n"
  552.          << "But the 1D graph's canonical form is:\n"
  553.          << "  " << canonical1D << endl;
  554.       return 1;
  555.    }
  556.    cout
  557.       << "Success!  Both mazes match.\n"
  558.       << "The resulting canonical form graph is:\n"
  559.       << canonicalTM << endl;
  560. }
  561.  
Success #stdin #stdout 0s 3496KB
comments (?)
stdin
copy 
+-+-+-+-+-+-+
| |   |   | |
+ + + + + + +
|   | | |   |
+-+-+ + +-+-+
|           |
+-+-+-+ +-+ +
|         | |
+ +-+-+-+ + +
| |       | |
+-+-+-+-+-+-+
|  D|  D E  |F E  |  F  |
stdout
copy 
Success!  Both mazes match.
The resulting canonical form graph is:
()()(()())(()())
https://ideone.com/CgkW7g
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!