The Computer Language
Benchmarks Game

meteor-contest C++ g++ #2 program

// The Computer Language Benchmarks Game
// http://benchmarksgame.alioth.debian.org/
// contributed by Ben St. John

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
#include <memory.h>

using namespace std;

#define FREE(p) {free(p); p = NULL;}

enum {X, Y, N_DIM};
enum {EVEN, ODD, N_PARITY};

typedef unsigned int TUInt32;
typedef unsigned long long TUInt64;
typedef signed char TInt8;

typedef TUInt64 BitVec;

namespace Meteor
{
   static const int N_COL = 5;
   static const int N_ROW = 10;
   static const int N_CELL = N_COL * N_ROW;

   class Piece;

   //------------------------------------

   class Solution
   {
   public:
      static const int NO_PIECE = -1;

      void addPiece(const BitVec & vec, int iPiece);
      void removeLastPiece(void);
      void setCells(void);
      bool lessThan(Solution & r); ///< I don't feel like operator overloading
      string toString(void) const;
      void fill(int val);
      bool isEmpty(void) {return (m_pieces.size() == 0);}
      void spin(Solution & spun);

      Solution(int fillVal);
      Solution() {m_synched = false;}

   private:
      struct SPiece {
         BitVec vec;
         TUInt32 iPiece;
      };
      vector<SPiece> m_pieces;
      TInt8 m_cells[N_ROW][N_COL];
      bool m_synched;
   };

   //------------------------------------

   class Board
   {
   public:
      static const BitVec L_EDGE_MASK =
         (1LL <<  0) | (1LL <<  5) | (1LL << 10) | (1LL << 15) |
         (1LL << 20) | (1LL << 25) | (1LL << 30) | (1LL << 35) |
         (1LL << 40) | (1LL << 45) | (1LL << 50) | (1LL << 55);
      static const BitVec R_EDGE_MASK = L_EDGE_MASK << 4;
      static const BitVec TOP_ROW = 0x1fLL;
      static const BitVec ROW_0_MASK =
         ( TOP_ROW        | (TOP_ROW << 10) | (TOP_ROW << 20) | (TOP_ROW << 30) |
         (TOP_ROW << 40) | (TOP_ROW << 50));
      static const BitVec ROW_1_MASK = ROW_0_MASK << 5;
      static const BitVec BOARD_MASK = (1LL << N_CELL) - 1;

      Board();

      static TUInt32 getIndex(TUInt32 x, TUInt32 y) { return y * N_COL + x;    }
      static bool hasBadFirstRegion(BitVec & toFill);
      static bool hasBadIslands(const BitVec & boardVec);

      void genAllSolutions(BitVec boardVec, TUInt32 placedPieces, TUInt32 iNextFill, const BitVec & maskNextFill);
      void recordSolution(Solution & s);

      Solution m_curSolution;
      Solution m_minSolution;
      Solution m_maxSolution;
      TUInt32 m_nSolutionFound;
   };

   //------------------------------------

   class Piece
   {
   public:
      struct Instance {
         BitVec m_vec;
         BitVec m_allowed;
         TUInt32 m_offset;
         TUInt32 m_w;
         TUInt32 m_h;
      };

      static const int N_ELEM = 5;
      static const int N_ORIENT = 12;
      static const int N_TYPE = 10;
      static const int ALL_PIECE_MASK = (1 << N_TYPE) - 1;
      static const TUInt32 SKIP_PIECE = 5; // it's magic!

      typedef int TCoordList[N_ELEM][N_DIM];

      static const BitVec BaseDefinitions[N_TYPE];
      static Piece s_basePiece[N_TYPE][N_ORIENT];

      static const Instance & getPiece(TUInt32 iPiece, TUInt32 iOrient, TUInt32 iParity);
      static bool checkBaseDefinitions(void);
      static BitVec toBitVector(const TCoordList & coords);
      static void genOrientation(const BitVec & vec, TUInt32 iOrient, Piece & target);
      static void setCoordList(const BitVec & vec, TCoordList & coords);
      static void shiftUpLines(TCoordList & coords, int shift);
      static void shiftToX0(TCoordList & coords, Instance & instance, int offsetRow);
      static void setAllowedPositions(Instance & p);
      static void genAllOrientations(void);

      Instance m_instance[N_PARITY];
   };

   //------------------------------------
   Solution::Solution(int fillVal)
   {
      fill(fillVal);
      m_pieces.reserve(Piece::N_TYPE);
   }

   void Solution::fill(int val)
   {
      m_synched = false;
      memset(&m_cells[0][0], val, N_CELL);
   }

   string Solution::toString(void) const
   {
      string result;
      result.reserve(N_CELL * 2);

      for (int y = 0; y < N_ROW; y++) {
         for (int x = 0; x < N_COL; x++) {
            int val = m_cells[y][x];
            result += ((val == NO_PIECE) ? '.' : char('0' + val));
            result += ' ';
         }
         result += '\n';

         // indent every second line
         if (y % 2 == 0)
            result += " ";
      }

      return result; // copies result. Oh well
   }

   void Solution::setCells(void)
   {
      if (m_synched)
         return;

      fill(NO_PIECE);

      // could be more efficient
      for (TUInt32 iPiece = 0; iPiece < m_pieces.size(); iPiece++) {

         const BitVec & vec = m_pieces[iPiece].vec;
         int pID = m_pieces[iPiece].iPiece;
         BitVec mask = 1LL;
         int nNewCells = 0;

         for (int y = 0; y < N_ROW; y++) {
            for (int x = 0; x < N_COL; x++) {
               if (mask & vec) {
                  m_cells[y][x] = (TInt8)pID;

                  nNewCells++;
               }
               mask <<= 1;
            }
            if (nNewCells == Piece::N_ELEM)
               break;
         }
      }

      m_synched = true;
   }

   void Solution::addPiece(const BitVec & vec, int iPiece) {
      SPiece p = {vec, iPiece};
      m_pieces.push_back(p);
   }

   void Solution::removeLastPiece(void) {
      m_pieces.pop_back();
      m_synched = false;
   }

   bool Solution::lessThan(Solution & r)
   {
      if (m_pieces[0].iPiece != r.m_pieces[0].iPiece) {
         return m_pieces[0].iPiece < r.m_pieces[0].iPiece;
      }

      setCells();
      r.setCells();

      int y;
      for (y = 0; y < N_ROW; y++) {
         for (int x = 0; x < N_COL; x++) {
            int lval = m_cells[y][x];
            int rval = r.m_cells[y][x];

            if (lval != rval)
               return (lval < rval);
         }
      }

      return false; // solutions are equal
   }

   void Solution::spin(Solution & spun)
   {
      setCells();

      // swap cells
      for (int y = 0; y < N_ROW; y++) {
         for (int x = 0; x < N_COL; x++) {
            TInt8 flipped = m_cells[N_ROW - y - 1][N_COL - x - 1];
            spun.m_cells[y][x] = flipped;
         }
      }

      // swap first and last pieces (the rest aren't used)
      spun.m_pieces.push_back(m_pieces[Piece::N_TYPE - 1]);
      spun.m_synched = true;
   }

   //------------------------------------

   Piece Piece::s_basePiece[N_TYPE][N_ORIENT];

   const BitVec Piece::BaseDefinitions[] = {
      0x010f,   0x00cb, 0x1087, 0x0427, 0x0465,
      0x00c7, 0x08423, 0x00a7, 0x0187, 0x008f
   };

   int floor(int top, int bot) {
      int toZero = top / bot;
      // negative numbers should be rounded down, not towards zero
      if ((toZero * bot != top) && ((top < 0) != (bot <= 0)))
         toZero--;

      return toZero;
   }

   TUInt32 getFirstOne(const BitVec & v, TUInt32 startPos = 0) {
      if (v == (BitVec)0)
         return 0;

      static const TUInt32 firstOne[16] =   {
         0, 0, 1, 0,
         2, 0, 1, 0,
         3, 0, 1, 0,
         2, 0, 1, 0,
      };

      TUInt32 iPos = startPos;
      BitVec mask = 0xffLL << startPos;
      while ((mask & v) == 0) {
         mask <<= 8;
         iPos += 8;
      }
      TUInt32 result = TUInt32((mask & v) >> iPos);
      TUInt32 resultLow = result & 0x0f;
      if (resultLow != 0)
         iPos += firstOne[resultLow];
      else
         iPos += 4 + firstOne[result >> 4];

      return iPos;
   }

   TUInt32 countOnes(BitVec v) {
      TUInt32 n = 0;
      while (v) {
         n++;
         v = v & (v - 1);
      }

      return n;
   }

   void Piece::genAllOrientations(void) {
      for (int iPiece = 0; iPiece < N_TYPE; iPiece++) {
         const BitVec & refPiece = BaseDefinitions[iPiece];
         for (int iOrient = 0; iOrient < N_ORIENT; iOrient++)
            genOrientation(refPiece, iOrient, s_basePiece[iPiece][iOrient]);
      }
   }

   void Piece::setCoordList(const BitVec & vec, TCoordList & coords) {
      int iCoord = 0;
      BitVec mask = 1LL;
      for (int y = 0; y < N_ROW; y++) {
         for (int x = 0; x < N_COL; x++) {
            if (mask & vec) {
               coords[iCoord][X] = x;
               coords[iCoord][Y] = y;

               iCoord++;
            }
            mask <<= 1;
         }
      }
   }

   BitVec Piece::toBitVector(const TCoordList & coords)
   {
      int y, x;
      BitVec result = 0;
      for (int iCoord = 0; iCoord < N_ELEM; iCoord++) {
         x = coords[iCoord][X];
         y = coords[iCoord][Y];

         int pos = Board::getIndex(x, y);
         result |= (1LL << pos); // to generate a 64 bit representation of 1
      }

      return result;
   }

   void Piece::shiftUpLines(TCoordList & coords, int shift)
   {
      // apply shifts are not so simple in the vertical direction
      for (int iCoord = 0; iCoord < N_ELEM; iCoord++) {
         int & rx = coords[iCoord][X];
         int & ry = coords[iCoord][Y];

         if (ry & shift & 0x1)
            rx++;
         ry -= shift;
      }
   }

   void Piece::shiftToX0(TCoordList & coords, Piece::Instance & instance, int offsetRow)
   {
      // .. determine shift
      int x, y;
      int xMin = coords[0][X];
      int xMax = xMin;
      int iCoord;
      for (iCoord = 1; iCoord < N_ELEM; iCoord++) {
         x = coords[iCoord][X];
         y = coords[iCoord][Y];

         if (x < xMin)
            xMin = x;
         else if (x > xMax)
            xMax = x;
      }

      // I'm dying for a 'foreach' here
      int offset = N_ELEM;

      for (iCoord = 0; iCoord < N_ELEM; iCoord++) {
         int & rx = coords[iCoord][X];
         int & ry = coords[iCoord][Y];

         rx -= xMin;

         // check offset -- leftmost cell on top line
         if ((ry == offsetRow) && (rx < offset))
            offset = rx;
      }

      instance.m_w = xMax - xMin;
      instance.m_offset = offset;
      instance.m_vec = toBitVector(coords);
   }

   void Piece::setAllowedPositions(Piece::Instance & p)
   {
      BitVec & allowed = p.m_allowed = 0;
      BitVec posMask = 1LL;
      TUInt32 iPos = 0;
      for (int y = 0; y < N_ROW; y++) {
         for (int x = 0; x < N_COL; x++, iPos++, posMask <<= 1){
            // check if the new position is on the board
            int xPos = x - p.m_offset;
            if ((xPos < 0) || (y + p.m_h >= N_ROW) || (xPos + p.m_w >= N_COL))
               continue;

            // move it to the desired location
            BitVec pieceVec = p.m_vec << (iPos - p.m_offset);

            if (Board::hasBadIslands(pieceVec))
               continue;

            // position is allowed
            allowed |= posMask;
         }
      }
   }

   void Piece::genOrientation(const BitVec & vec, TUInt32 iOrient, Piece & target)
   {
      // get (x,y) coordinates
      TCoordList coords;
      setCoordList(vec, coords);

      int y, x;
      int iCoord = 0;
      int rot = iOrient % 6;
      int flip = iOrient >= 6;
      if (flip) {
         for (iCoord = 0; iCoord < N_ELEM; iCoord++)
            coords[iCoord][Y] = -coords[iCoord][Y];
      }

      // rotate (if necessary)
      while (rot--) {
         for (iCoord = 0; iCoord < N_ELEM; iCoord++) {
            x = coords[iCoord][X];
            y = coords[iCoord][Y];

            // I just worked this out by hand. Took a while.
            int xNew = floor((2 * x - 3 * y + 1), 4);
            int yNew = floor((2 * x + y + 1), 2);
            coords[iCoord][X] = xNew;
            coords[iCoord][Y] = yNew;
         }
      }

      // shift vertically
      // .. determine shift
      int yMin = coords[0][Y];
      int yMax = yMin;
      for (iCoord = 1; iCoord < N_ELEM; iCoord++) {
         y = coords[iCoord][Y];

         if (y < yMin)
            yMin = y;
         else if (y > yMax)
            yMax = y;
      }
      TUInt32 h = yMax - yMin;
      target.m_instance[EVEN].m_h = h;
      target.m_instance[ODD].m_h = h;

      shiftUpLines(coords, yMin);
      shiftToX0(coords, target.m_instance[EVEN], 0);
      setAllowedPositions(target.m_instance[EVEN]);

      // shift down one line
      shiftUpLines(coords, -1);
      shiftToX0(coords, target.m_instance[ODD], 1);
      // shift the bitmask back one line
      target.m_instance[ODD].m_vec >>= N_COL;
      setAllowedPositions(target.m_instance[ODD]);
   }

   const Piece::Instance & Piece::getPiece(TUInt32 iPiece, TUInt32 iOrient, TUInt32 iParity) {
      return s_basePiece[iPiece][iOrient].m_instance[iParity];
   }

   // ------------------------------------

   Board::Board() :
   m_curSolution(Solution::NO_PIECE), m_minSolution(Piece::N_TYPE),
      m_maxSolution(Solution::NO_PIECE), m_nSolutionFound(0)
   {
   }

   bool Board::hasBadFirstRegion(BitVec & toFill)
   {
      int iPos = getFirstOne(toFill);

      // grow empty region, until it doesn't change any more
      BitVec region;
      BitVec rNew = 1LL << iPos;
      do {
         region = rNew;

         // grow right/left
         rNew |= (region & ~L_EDGE_MASK) >> 1;
         rNew |= (region & ~R_EDGE_MASK) << 1;

         // simple grow up/down
         rNew |= (region >> N_COL);
         rNew |= (region << N_COL);

         // tricky growth
         BitVec evenRegion = region & (ROW_0_MASK & ~L_EDGE_MASK);
         rNew |= evenRegion >> (N_COL + 1);
         rNew |= evenRegion << (N_COL - 1);

         BitVec oddRegion = region & (ROW_1_MASK & ~R_EDGE_MASK);
         rNew |= oddRegion >> (N_COL - 1);
         rNew |= oddRegion << (N_COL + 1);

         // clamp against existing pieces
         rNew &= toFill;
      }
      while ((rNew != toFill) && (rNew != region));

      // subtract empty region from board
      toFill ^= rNew;

      TUInt32 nEmptyCells = countOnes(toFill);
      if (nEmptyCells % 5 != 0)
         return true;

      return false;
   }

   bool Board::hasBadIslands(const BitVec & boardVec)
   {
      BitVec toFill = ~boardVec & BOARD_MASK;

      // a little pre-work to speed things up
      BitVec row = (Board::TOP_ROW << ((N_ROW - 1) * N_COL));
      bool filled = ((row & toFill) == row);
      while ((row & toFill) == row) {
         toFill ^= row;
         row >>= N_COL;
      }
      // undo the last row, so regions stay connected
      if (filled)   {
         row <<= N_COL;
         toFill |= row;
      }

      while (toFill)    {
         if (hasBadFirstRegion(toFill))
            return true;
      }

      return false;
   }

   // recursive vs iterative?
   void Board::genAllSolutions(BitVec boardVec, TUInt32 placedPieces, TUInt32 iNextFill, const BitVec & maskNextFill)
   {
      BitVec pieceVec;
      int pieceMask = 1;
      int y = iNextFill / N_COL;
      int isOddLine = y & 1;

      for (int iPlacedPiece = 0; iPlacedPiece < Piece::N_TYPE; iPlacedPiece++, pieceMask <<= 1)
      {
         TUInt32 iPiece = iPlacedPiece; // leftover from when I remapped it

         // skip if we've already used this piece
         if (pieceMask & placedPieces)
            continue;

         // try to fit piece
         bool skipFlippedOdd = (iPiece == Piece::SKIP_PIECE);
         for (int iOrient = 0; iOrient < Piece::N_ORIENT; iOrient++)
         {
            if (skipFlippedOdd && ((iOrient / 3) & 1))
               continue;

            // get the particular piece in the particular orientation
            const Piece::Instance & p = Piece::getPiece(iPiece, iOrient, isOddLine);

            // check if the new position is allowed on the board
            if (!(p.m_allowed & maskNextFill))
               continue;

            // move it to the desired location, if possible and
            pieceVec = p.m_vec << (iNextFill - p.m_offset);

            // check if piece conflicts with other pieces
            if (pieceVec & boardVec)
               continue;

            // add the piece to the board
            boardVec |= pieceVec;

            if ((boardVec != pieceVec) && hasBadIslands(boardVec)) {
               // remove the piece from the board vector
               boardVec ^= pieceVec;
               continue;
            }

            // mark piece as placed
            placedPieces |= pieceMask;
            m_curSolution.addPiece(pieceVec, iPiece);

            // recur if not done
            if (placedPieces != Piece::ALL_PIECE_MASK)   {
               // need to find the next unfilled cell
               TUInt32 iCell = getFirstOne(~boardVec, iNextFill + 1);
               BitVec mNextFill = (maskNextFill << (iCell - iNextFill));

               genAllSolutions(boardVec, placedPieces, iCell, mNextFill);
            }
            else {
               // done, record piece/solution and end recursion
               recordSolution(m_curSolution);
            }

            // remove the piece before continuing with a new piece
            boardVec ^= pieceVec;
            m_curSolution.removeLastPiece();
         }

         placedPieces &= ~pieceMask;
      }
   }

   void Board::recordSolution(Solution & s)
   {
      m_nSolutionFound += 2; // we add the solution and its rotation

      if (m_minSolution.isEmpty()) {
         m_minSolution = m_maxSolution = s;
         return;
      }

      if (s.lessThan(m_minSolution))
         m_minSolution = s;
      else if (m_maxSolution.lessThan(s))
         m_maxSolution = s;

      Solution spun;
      s.spin(spun);
      if (spun.lessThan(m_minSolution))
         m_minSolution = spun;
      else if (m_maxSolution.lessThan(s))
         m_maxSolution = spun;
   }

} // namespace

using namespace Meteor;

int main(int argc, char * argv [])
{
   const int N_SOLUTION = 2098;
   TUInt32 nSolMax = N_SOLUTION;
   if (argc > 2)
      return 1; // spec says this is an error
   else if (argc == 2)
      nSolMax = *((TUInt32 *)argv[1]);

   Board board;
   Piece::genAllOrientations();
   board.genAllSolutions(0, 0, 0, 1LL);

   cout << board.m_nSolutionFound << " solutions found\n\n";
   cout << board.m_minSolution.toString() << '\n';
   cout << board.m_maxSolution.toString() << endl;

   //   if (nSolMax != N_SOLUTION)
   //      return 1;

   return 0;
}

    

NOTES:
64-bit Ubuntu quad core
g++ (Ubuntu 7.2.0-8ubuntu3) 7.2.0


Mon, 30 Oct 2017 21:58:17 GMT

MAKE:
/usr/bin/g++ -c -pipe -O3 -fomit-frame-pointer -march=native   meteor.gpp-2.c++ -o meteor.gpp-2.c++.o &&  \
        /usr/bin/g++ meteor.gpp-2.c++.o -o meteor.gpp-2.gpp_run  
meteor.gpp-2.c++: In member function ‘void Meteor::Solution::addPiece(const BitVec&, int)’:
meteor.gpp-2.c++:198:30: warning: narrowing conversion of ‘iPiece’ from ‘int’ to ‘TUInt32 {aka unsigned int}’ inside { } [-Wnarrowing]
       SPiece p = {vec, iPiece};
                              ^
rm meteor.gpp-2.c++

1.45s to complete and log all make actions

COMMAND LINE:
./meteor.gpp-2.gpp_run 2098

PROGRAM OUTPUT:
2098 solutions found

0 0 0 0 1 
 2 2 2 0 1 
2 6 6 1 1 
 2 6 1 5 5 
8 6 5 5 5 
 8 6 3 3 3 
4 8 8 9 3 
 4 4 8 9 3 
4 7 4 7 9 
 7 7 7 9 9 

9 9 9 9 8 
 9 6 6 8 5 
6 6 8 8 5 
 6 8 2 5 5 
7 7 7 2 5 
 7 4 7 2 0 
1 4 2 2 0 
 1 4 4 0 3 
1 4 0 0 3 
 1 1 3 3 3