// path.cc - Don Yang (uguu.org)
//
// Find maze with maximum and minimum path lengths.
//
// 2014-03-18

#include<stdio.h>
#include<string.h>
#include<utility>
#include<vector>
using namespace std;

namespace {

// If true, output maze for debugging
static const bool kOutputMazeToStdout = false;

// Maze dimension
static const int kWidth = 25;
static const int kHeight = 8;

// Maze cell bitmask
static const unsigned int kDoorRight = 1;    // Right cell is connected
static const unsigned int kDoorBottom = 2;   // Bottom cell is connected
static const unsigned int kVisited = 4;      // Maze generator saw this cell
static const unsigned int kTested = 8;       // Maze solver saw this cell

struct Cells
{
   unsigned int bits[kHeight + 2][kWidth + 2];
};

// Coordinates for a single step during maze generation
struct VisitNode
{
   VisitNode(int a, int b, int c, int d) : x0(a), y0(b), x1(c), y1(d) {}

   int x0, y0, x1, y1;
};

// Random number generator
class Prng
{
public:
   explicit Prng(int seed) : lfsr_(seed) {}
   ~Prng() {}

   int NextRand()
   {
      lfsr_ = ((lfsr_ >> 1) ^ (0x68000001 & -(lfsr_ & 1))) & 0x7fffffff;
      return lfsr_;
   }

private:
   int lfsr_;
};

// Stats for maze solver
struct DirectionStats
{
   DirectionStats() { memset(this, 0, sizeof(*this)); }

   typedef unsigned char Count;

   int Up() const { return static_cast<int>(up); }
   int Down() const { return static_cast<int>(down); }
   int Left() const { return static_cast<int>(left); }
   int Right() const { return static_cast<int>(right); }
   int Length() const { return Up() + Down() + Left() + Right(); }

   Count up;
   Count down;
   Count left;
   Count right;
};

// Initialize vector with 4 coordinates in random order
static void GenerateDeltas(Prng *prng, vector<pair<int, int> > *output)
{
   output->clear();
   output->push_back(make_pair(-1, 0));
   output->push_back(make_pair(1, 0));
   output->push_back(make_pair(0, -1));
   output->push_back(make_pair(0, 1));

   for(int i = 4; --i;)
   {
      const int j = prng->NextRand() % (i + 1);
      if( i == j )
         continue;
      swap((*output)[i], (*output)[j]);
   }
}

// Connect two maze cells
static void ConnectCells(int x0, int y0, int x1, int y1, Cells *cells)
{
   if( x0 < x1 )
   {
      cells->bits[y1][x0] |= kDoorRight;
   }
   else if( x0 > x1 )
   {
      cells->bits[y1][x1] |= kDoorRight;
   }
   else
   {
      if( y0 < y1 )
         cells->bits[y0][x1] |= kDoorBottom;
      else
         cells->bits[y1][x1] |= kDoorBottom;
   }
}

// Generate a single maze
static void GenerateMaze(int seed, Cells *cells)
{
   Prng prng(seed);

   // Block off border cells
   memset(cells, 0, sizeof(*cells));
   for(int x = 0; x < kWidth + 2; x++)
      cells->bits[0][x] = cells->bits[kHeight + 1][x] = kVisited | kDoorRight;
   for(int y = 1; y <= kHeight; y++)
      cells->bits[y][0] = cells->bits[y][kWidth + 1] = kVisited | kDoorBottom;

   // Reserve middle area
   for(int x = 10; x < 16; x++)
   {
      cells->bits[4][x] = kVisited | kDoorRight | kDoorBottom;
      cells->bits[5][x] = kVisited | kDoorRight;
   }
   cells->bits[4][16] = kVisited | kDoorBottom;
   cells->bits[5][16] = kVisited;

   // Start marking cells at upper left corner
   vector<VisitNode> visit_stack;
   vector<pair<int, int> > deltas;
   visit_stack.push_back(VisitNode(0, 1, 1, 1));
   while( !visit_stack.empty() )
   {
      const VisitNode node = visit_stack.back();
      visit_stack.pop_back();

      if( (cells->bits[node.y1][node.x1] & kVisited) != 0 )
         continue;

      // Mark path between current cell and previous cell
      cells->bits[node.y1][node.x1] |= kVisited;
      ConnectCells(node.x0, node.y0, node.x1, node.y1, cells);

      // Visit neighbors in random order
      GenerateDeltas(&prng, &deltas);
      while( !deltas.empty() )
      {
         const int dx = deltas.back().first;
         const int dy = deltas.back().second;
         deltas.pop_back();
         visit_stack.push_back(VisitNode(node.x1, node.y1,
                                         node.x1 + dx, node.y1 + dy));
      }
   }

   // Mark exit
   cells->bits[kHeight][kWidth] |= kDoorRight;

   // Unmark entrance
   cells->bits[1][0] &= ~kDoorRight;
}

// Output maze to stdout, to confirm that this program is solving the
// same maze as the perl programs
static void OutputMaze(const Cells &cells)
{
   for(int y = 0; y <= kHeight; y++)
   {
      // Vertical walls
      for(int x = 0; x <= kWidth; x++)
      {
         if( (cells.bits[y][x] & kDoorRight) != 0 )
            printf("   ");
         else
            printf("  |");
      }
      putchar('\n');

      // Horizontal walls
      for(int x = 0; x <= kWidth; x++)
      {
         if( (cells.bits[y][x] & kDoorBottom) != 0 )
            printf("  +");
         else
            printf("--+");
      }
      putchar('\n');
   }
}

// Find solution path length, returns true if a solution has been found
static bool GetPathLength(int x, int y, Cells *cells, DirectionStats *stats)
{
   if( x == kWidth && y == kHeight )
      return true;
   if( (cells->bits[y][x] & kTested) != 0 )
      return false;
   cells->bits[y][x] |= kTested;

   if( (cells->bits[y][x] & kDoorRight) != 0 )
   {
      if( GetPathLength(x + 1, y, cells, stats) )
      {
         stats->right++;
         return true;
      }
   }
   if( (cells->bits[y][x] & kDoorBottom) != 0 )
   {
      if( GetPathLength(x, y + 1, cells, stats) )
      {
         stats->down++;
         return true;
      }
   }
   if( (cells->bits[y - 1][x] & kDoorBottom) != 0 )
   {
      if( GetPathLength(x, y - 1, cells, stats) )
      {
         stats->up++;
         return true;
      }
   }
   if( (cells->bits[y][x - 1] & kDoorRight) != 0 )
   {
      if( GetPathLength(x - 1, y, cells, stats) )
      {
         stats->left++;
         return true;
      }
   }
   return false;
}

// Solve a single maze, output solution length to stdout
static DirectionStats Solve(int seed)
{
   Cells cells;
   GenerateMaze(seed, &cells);
   if( kOutputMazeToStdout )
      OutputMaze(cells);
   DirectionStats stats;
   GetPathLength(1, 1, &cells, &stats);
   return stats;
}

}  // namespace

int main(int argc, char **argv)
{
   if( argc == 1 )
   {
      printf("%s <maze number or maze range>\n", *argv);
      return 1;
   }

   // Collect all ranges
   vector<pair<int, int> > ranges;
   for(int i = 1; i < argc; i++)
   {
      int start, end;
      if( sscanf(argv[i], "%d-%d", &start, &end) == 2 )
      {
         ranges.push_back(make_pair(start, end));
      }
      else if( sscanf(argv[i], "%d", &start) == 1 )
      {
         ranges.push_back(make_pair(start, start));
      }
      else
      {
         printf("%s is not a valid maze number or range\n", argv[i]);
         return 1;
      }
   }

   // Solve mazes
   DirectionStats max_stats, min_stats;
   int max_path = 0, max_seed = 0;
   int min_path = kWidth * kHeight, min_seed = 0;
   for(vector<pair<int, int> >::const_iterator i = ranges.begin();
       i != ranges.end(); ++i)
   {
      for(int j = i->first; j <= i->second && j >= 0; j++)
      {
         const DirectionStats stats = Solve(j);

         // Remember maze with longest path
         if( stats.Length() > max_path )
         {
            memcpy(&max_stats, &stats, sizeof(stats));
            max_path = stats.Length();
            max_seed = j;
         }

         // Remember shortest maze that used all 4 directions.  We
         // only need to test left and up.  Down and right will always
         // be present due to relative position of start and goal.
         if( stats.Length() < min_path && stats.Up() > 0 && stats.Left() > 0 )
         {
            memcpy(&min_stats, &stats, sizeof(stats));
            min_path = stats.Length();
            min_seed = j;
         }
      }
   }

   printf("max path = %d (up=%d, down=%d, left=%d, right=%d), seed = %d\n",
          max_path,
          max_stats.Up(),
          max_stats.Down(),
          max_stats.Left(),
          max_stats.Right(),
          max_seed);
   printf("min path = %d (up=%d, down=%d, left=%d, right=%d), seed = %d\n",
          min_path,
          min_stats.Up(),
          min_stats.Down(),
          min_stats.Left(),
          min_stats.Right(),
          min_seed);
   return 0;
}