/* Author : Anand Krishnamoorthi Compiling: MSVC: cl /EHsc /O2 HamiltonianCycles.cpp GCC : g++ -O2 HamiltonianCycles.cpp -o HamiltonianCycles Usage: HamiltonianCycles rows cols Based on my solution to the Quora Datacenter Cooling Challenge. Description of the problem: http://www.quora.com/challenges#datacenter_cooling Description of the original solution: An elegant, ultra fast solution to the Quora Datacenter Cooling Challenge. In a valid layout of the duct through the rooms in the datacenter: 1) Every room must have exactly 2 connections/edges. Rooms that we own "0" must have an incoming and an outgoing edge. Start room "2" must have an outgoing edge and an imaginary incoming edge. End room "3" must have an incoming edge and an imaginary outgoing edge. Rooms that we don't own "1" are assumed to already have 2 edges. 2) There are no cycles. The following layout is not valid. 2 0--0 | | | 0 0--0 | 0--0--3 Every room above has two edges, but the four rooms in top-right form a cycle. They are not part of the path from room "2" to "3". "A valid layout of the duct is one in which each room has two edges and there are no cycles." Edges can be thought to be direction-less for layout. There are 4 possible edges that a room can have: UP | LEFT --- Rm --- RIGHT | DOWN The LEFT edge of a room is the RIGHT edge of the room to it's left. The UP edge of a room is the DOWN edge of the room above it. If we process the rooms left to right, top to bottom, starting with the room at the top-left corner, then we only need to consider the RIGHT and DOWN edges of a room. The top edge of a room would've been handled when the room immediately above it, in the preceeding row, was processed. Similarly the left edge of the room would already have been handled when the room immediately to the left, in the current row, was processed. An unprocessed room would look like following: | | -- Rm (Or) Rm (Or) -- Rm (Or) Rm (Case A) (Case B) (Case C) (Case D) In Case A, the room already has 2 connections and we can skip to the next room. In Case B and Case C, the room has just one connection and we need to add one more if the room is "0". In Case D, the room has no connections and we must add 2 connections (just 1 if it is "2" or "3"). If an unprocessed room has no connections (Case D), then we must connect it both to the right and down: Rm --- | If and unprocessed room has just one connection, then we need to connect it first to the right, continue solving, then remove the connection and reconnect down to the room below and then solve. Preventing Cycles: A cycle is only formed when a room is connected to the room on its right and there's already a path from the room to the room on its right: 0 -- 0 -- 0 -- 0 0 -- 2 | | | 0 1 0 - -0 0 1 | | | 0 -- 0 0 0 0 1 R0 R1 R2 R3 R4 In the above example, there's already a path from R1 to R2, so connecting R1 right to R2 would lead to a cycle. Therefore to prevent cycles, we need to keep track of the end point (ending room) of the path from a room. 0 -- 0 -- 0 -- 0 0 -- 2 | | | 0 1 0 -- 0 0 1 | | | 0 0 0 0 0 1 R0 R1 R2 R3 R4 In the above example, the path-end-point of R0 is R2 and vice-versa. The end-point of "2" is R4 and vice-versa. When we make a new connection, we update the end-points: 0 -- 0 -- 0 -- 0 0 -- 2 | | | 0 1 0 -- 0 0 1 | | | 0 -- 0 0 0 0 1 R0 R1 R2 R3 R4 After connecting R0 right to R1, the path-end-point of R1 is R2 and that of R2 is now R1. We don't really care about of end-point of R0 at this point. This approach also automatically merges two paths when a connection is made. 2 0 -- 0 -- 0 | | | 0 0 0 0 R0 R1 R2 R3 In the above example, the end-point of R0 is "2" and vice-versa. The end-point of R1 is R3 and vice-versa. When we connect R0 to R1 (this does not introduce a cycle is end-point of R1 is not R0), we get the end-points of R0 and R1 and make them "end-point" each-other. 2 0 -- 0 -- 0 e1 <- endpoint(R0) | | | e2 <- endpoint(R1) 0 -- 0 0 0 endpoint(e1) <- e2 R0 R1 R2 R3 endpoint(e2) <- e1 After connecting R0 to R1 and performing updates as described above, endpoint of "2" is R3 and vice-versa. When a connection is removed, we restore the end-points of the rooms. Memoization "Rooms in a row that is just about to be processed have paths from "2", "3" or other rooms in that row." Row 0 : 2 0 -- 0 -- 0 -- 0 2 -- 0 0 -- 0 -- 0 | | | | | | Row 1: 0 0 -- 0 3 0 0 -- 0 0 3 0 | | | | | | | | Row 2: 0 0 0 0 0 0 0 0 0 0 R0 R1 R2 R3 R4 R0 R1 R2 R3 R4 (layout A) (layout B) In the above example, we've finished processing Row 1 and are about to process Row 2. R0 has a path from "2", R3 has a path to "3". R1 (has an imaginary path to itself), R2 and R4 all have paths to other rooms in the same row. The algorithm relies *only* on the path-end of rooms and the number of connections. This means that processing Row 2 in layout A and in layout B would produce the same results. The path-ends of rooms in an unprocessed row uniquely identifies it in the context of a partial solution. It doesn't matter how the paths themselves are laid out, only the path-ends matter. So the list of path-ends of (the next) unprocessed row, can be used as key in a cache used for memoization. So the result of processing Row 2 in layout A can be memoized and later reused while processing Row 2 in layout B. Efficient Memoization A backtracking solution with memoization would (if implemented for maximum speed) put all the valid path-end combinations of all the rows in the cache. The back-tracking solution keeps recursing from Row 0 to Row R, then backup to Row 0 and again to Row R (where R is the number of rows). This gets memory intensive with a large grid like 14x14. To be memory efficient, we can process strictly row-wise. Rather than processing the next (unprocessed) row immediately after a row has been processed, we can put the unprocessed row in a work list for later processing. We go back to solving the current row, generating all possible valid path-end combinations for the next row. Once we are completely done with the current row, we move on to the next row. The next row becomes the current row. We take each path-end combination from the worklist, apply it back on to the row and process the row, generating valid path-end combinations for the new next row. */ #if defined(__GCC__) #define FORCE_INLINE __attribute__((always_inline)) #elif defined(_MSC_VER) #define FORCE_INLINE __forceinline #define _SECURE_SCL 0 #define _HAS_ITERATOR_DEBUGGING 0 #else #define FORCE_INLINE inline #endif #include #include #include #include #include #include #include #include typedef unsigned long long ullong; struct Vertex { Vertex* path_end; unsigned char edges; unsigned char col; }; struct Edge { Vertex* v1; Vertex* v2; Vertex* v1_path_end; Vertex* v2_path_end; bool created; FORCE_INLINE Edge(Vertex* v1, Vertex* v2) { this->v1 = v1; this->v2 = v2; created = false; assert(v1->edges != 2); // Make sure rooms are not fully connected.. if (v2->edges != 2) { // Check for cycles. This is a key semantic and performance constraint. if (v1 != v2->path_end) { v1_path_end = v1->path_end; v2_path_end = v2->path_end; /* sanity checks*/ assert(v1_path_end->path_end == v1); assert(v2_path_end->path_end == v2); created = true; // Update ends of the merged path to point to each other v1_path_end->path_end = v2_path_end; v2_path_end->path_end = v1_path_end; v1->edges++; v2->edges++; } } } FORCE_INLINE ~Edge() { if (created) { // Restore path end-points. v1_path_end->path_end = v1; v2_path_end->path_end = v2; v1->edges--; v2->edges--; } } FORCE_INLINE operator bool() const { return created; } }; struct LargeInt { static const ullong base = 1000ULL * 1000ULL * 1000ULL; std::vector polynomial; LargeInt(ullong v=0) { assert(v < base); polynomial.reserve(6); polynomial.clear(); polynomial.push_back(v); } LargeInt& operator=(ullong v) { assert(v < base); polynomial.clear(); polynomial.reserve(6); polynomial.push_back(v); return *this; } LargeInt& operator+=(const LargeInt& other) { if (this == &other) { LargeInt tmp = other; *this += other; return *this; } if (polynomial.size() < other.polynomial.size()) polynomial.resize(other.polynomial.size()); ullong carry = 0; for (size_t i=0; i < polynomial.size(); ++i) { ullong term = polynomial[i] + carry; if (i < other.polynomial.size()) term += other.polynomial[i]; if (term >= base) { polynomial[i] = term - base; carry = 1; } else { polynomial[i] = term; carry= 0; } } if (carry) polynomial.push_back(carry); return *this; } void print(std::ostream& os) const { std::string num; num.reserve(1000); int digits_per_term = 0; ullong b = base; while (b/10) { ++digits_per_term; b = b / 10; } for(int p=0; p < int(polynomial.size())-1; ++p) { ullong term = polynomial[p]; for(int d=0; d < digits_per_term; ++d) { num.push_back((term % 10) + '0'); term /= 10; } } ullong term = polynomial.back(); while (term) { num.push_back((term % 10) + '0'); term /= 10; } if (num.empty()) num.push_back('0'); std::reverse(num.begin(), num.end()); os << num; } }; std::ostream& operator<<(std::ostream& os, const LargeInt& large_int) { large_int.print(os); return os; } FORCE_INLINE bool operator<(const Vertex& v1, const Vertex& v2) { return v1.path_end < v2.path_end; } typedef std::map< std::vector, LargeInt > Cache; typedef std::vector< std::vector > Grid; void solve(Grid& grid, const LargeInt& cur_count, int col, Cache& next_row_cache) { const int C = grid[0].size() - 1; int row = 0; if (col == C) { // Current row's been processed. next_row_cache[grid[row+1]] += cur_count; return; } Vertex* vertex = &grid[row][col]; Vertex* vertex_right = &grid[row][col+1]; Vertex* vertex_down = &grid[row+1][col]; if (vertex->edges == 2) return solve(grid, cur_count, col+1, next_row_cache); if (vertex->edges == 0) { // Vertex *must* be connected on both right and down. if (const Edge& edge_right = Edge(vertex, vertex_right)) if(const Edge& edge_down = Edge(vertex, vertex_down)) solve(grid, cur_count, col+1, next_row_cache); return; } // room->connections == 1. // Connect first to the right and explore. if (const Edge& edge_right = Edge(vertex, vertex_right)) solve(grid, cur_count, col+1, next_row_cache); // Then connect down and explore. if (const Edge& edge_down = Edge(vertex, vertex_down)) solve(grid, cur_count, col+1, next_row_cache); } FORCE_INLINE void init_row(std::vector& row) { for(int c=0; c < row.size(); ++c) { Vertex* vertex = &row[c]; vertex->path_end = vertex; // This assignment simplifies connection. vertex->edges = 0; } row.back().edges = 2; } void solve(int R, int C) { std::vector< std::vector > grid; grid.resize(2, std::vector(C+1)); init_row(grid[0]); init_row(grid[1]); Cache cache; cache[grid[0]] = LargeInt(1); for (int row=0; row < R; ++row) { //std::cout << "cache size : " <first; const LargeInt& count = itr->second; solve(grid, count, 0, next_row_cache); } init_row(grid[0]); // We've tampered with row 0, clean it up // Find the number of hamiltonian cycles till this row. // If the next now has just a single active path that starts and // ends at neighboring vertices, then that count is the number of // hamiltonian paths. // We choose vertex 0 and vertex 1. Any two vertices would work just as well. std::swap(grid[1][0].path_end, grid[1][1].path_end); grid[1][0].edges = grid[1][1].edges = 1; LargeInt solutions = next_row_cache[grid[1]]; if (row == 0) solutions = LargeInt(1); std::cout << "HC( " << C << " x " << (row+1) << " ) = " << solutions << std::endl; std::swap(grid[1][0].path_end, grid[1][1].path_end); grid[1][0].edges = grid[1][1].edges = 0; // move on to next row std::swap(cache, next_row_cache); std::swap(grid[0], grid[1]); } } int main(int argc, char** argv) { int R = 0; int C = 0; if (argc == 1) { std::cout << "\nEnter rows : "; std::cin >> R; std::cout << "\nEnter cols : "; std::cin >> C; } else if (argc == 3) { sscanf(argv[1], "%d", &R); sscanf(argv[2], "%d", &C); } else { std::cout << "usage: HamiltonianCycles rows cols" << std::endl; return -1; } if (R*C <= 1) { std::cout <<"rows*cols must be greater than 1" << std::endl; return -1; } if (C > R) std::swap(C, R); std::cout << "Solving for "<< R << " rows and " << C << " cols " << std::endl; solve(R, C); }