codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
// http://nabetani.sakura.ne.jp/hena/ord5railsontiles/ // Input is 9 tiles // Arrange tiles and enter from Tile B, top // Trace the rail and print the tiles traversed until you corss 3 X 3 boundary // boilerplate #include <cassert> #include <string> #include <iostream> using namespace std; // Direction enumeration static const int T=0; static const int L=1; static const int B=2; static const int R=3; // delta axis = { For Top, For Left, For Bottom, For Right}; int dx[] = {-1, 0, +1, 0}; int dy[] = {0, -1, 0, +1}; struct tile { int type; // 0, 1, or 2 bool used[4]; // Whether T, L, B, R are used (to find longest route and detect loops) }; //const size_t maxd = 3; const int maxd = 3; // Max dimension, min is zero const int maxt = 3; // Number of tiles int dir_out [4][maxt]; // Mapping of entry and exit in a tile, 4 inputs for 3 type of tiles /// use_int /// @brief Use a tile internal /// /// @arg [in,out] t tile array /// @arg i[in] tile index (0-2) /// @arg j[in] tile index (0-2) /// @arg dir[in] Direction, one of TLBR const string use_int(tile (&t)[maxd][maxd], int i, int j, int dir) { string s; // Append this tile s += 'A' + i * 3 + j; tile &tt = t[i][j]; // Find the way out from mapping const int new_out = dir_out[dir][t[i][j].type]; // Set this as used (Detect loop) tt.used[dir] = tt.used[ new_out ] = true; // Move to next tile i += dx[new_out]; j += dy[new_out]; // If still inside 3 X 3 boundary, repeat for next tile return s + ( (0 <= i && i < maxd && 0 <= j && j < maxd) ? use_int(t, i, j, 2 ^ new_out) // use while instead of this tail recursion : "" ); } // Actual use void use(tile (&t)[maxd][maxd], int i, int j, int dir, string &out) { const string s = use_int(t, i, j, dir); if( s.length() > out.length() ) out = s; } // test function void test(const char *in, const char *out) { // validate in here for length and character contents static int testnum = 0; string rail; tile t[maxd][maxd] = { { {0} } }; for(int i = 0; i < maxd; ++i) for(int j = 0; j < maxd; ++j) { t[i][j].type = in[i*3+j] - '0'; } #if 0 // find longest rail for(int i = 0; i < maxd; ++i) for(int j = 0; j < maxd; ++j) { if(!t[i][j].used[T]) use(t, i, j, T, rail); if(!t[i][j].used[L]) use(t, i, j, L, rail); if(!t[i][j].used[R]) use(t, i, j, R, rail); assert(t[i][j].used[B]); } #else // Start from B top use(t, 0, 1, T, rail); #endif if(rail == out) cout << '#' << testnum++ << '\t' << in << '\t' << out << endl; else cout << '#' << testnum++ << '\t' << in << "\tERROR:: Expected: " << out << ", Actual: " << rail << endl; } /// init /// @brief Does initialization. Connects the TLBR of each tile void init() { #define CONNECT(TILE_NO,FROM,TO) do { dir_out[FROM][TILE_NO] = TO; dir_out[TO][TILE_NO] = FROM; } while(0) CONNECT(0, T, B); CONNECT(0, L, R); CONNECT(1, L, B); CONNECT(1, R, T); CONNECT(2, T, L); CONNECT(2, R, B); } /// main /// @brief entry point int main() { init(); #define TEST(dummy,SAMPLE_IN,EXPECTED_OUT) test(#SAMPLE_IN, #EXPECTED_OUT) TEST(0, 101221102, BEDGHIFEH); TEST(1, 000000000, BEH); TEST(2, 111111111, BCF); TEST(3, 222222222, BAD); TEST(4, 000211112, BEFIHEDGH); TEST(5, 221011102, BADGHIFEBCF); TEST(6, 201100112, BEHIFCBADEF); TEST(7, 000111222, BEFIH); TEST(8, 012012012, BC); TEST(9, 201120111, BEDABCFI); TEST(10, 220111122, BADEHGD); TEST(11, 221011022, BADG); TEST(12, 111000112, BCFIHEBA); TEST(13, 001211001, BEFI); TEST(14, 111222012, BCFEHIF); TEST(15, 220111211, BADEHI); TEST(16, 211212212, BCFEBAD); TEST(17, 002112210, BEFC); TEST(18, 001010221, BEF); TEST(19, 100211002, BEFIHG); TEST(20, 201212121, BEFCBAD); return 0; } // eof
Private
[
?
]
Run code
Submit