// 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

#0	101221102	BEDGHIFEH
#1	000000000	BEH
#2	111111111	BCF
#3	222222222	BAD
#4	000211112	BEFIHEDGH
#5	221011102	BADGHIFEBCF
#6	201100112	BEHIFCBADEF
#7	000111222	BEFIH
#8	012012012	BC
#9	201120111	BEDABCFI
#10	220111122	BADEHGD
#11	221011022	BADG
#12	111000112	BCFIHEBA
#13	001211001	BEFI
#14	111222012	BCFEHIF
#15	220111211	BADEHI
#16	211212212	BCFEBAD
#17	002112210	BEFC
#18	001010221	BEF
#19	100211002	BEFIHG
#20	201212121	BEFCBAD