/mobile Handheld Friendly website

 performance measurements

Each table row shows performance measurements for this C++ g++ program with a particular command-line input value N.

 N  CPU secs Elapsed secs Memory KB Code B ≈ CPU Load
2,0980.120.12?4343  0% 0% 0% 100%

Read the ↓ make, command line, and program output logs to see how this program was run.

Read meteor-contest benchmark to see what this program should do.

 notes

gcc version 4.8.1 (Ubuntu/Linaro 4.8.1-10ubuntu8)

 meteor-contest C++ g++ program source code

// The Computer Language Benchmarks Game
//  http://benchmarksgame.alioth.debian.org
//  contributed by Kevin Barnes

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

using namespace std;

#define WEST 0
#define EAST 1
#define SW 2
#define SE 3
#define NW 4
#define NE 5

#define BIT ((long long)1)

// constant masks
const long long row_mask = (long long)31;
const long long full_mask = (BIT << 50) - 1;
const long long row_masks[] = { row_mask, row_mask << 5, row_mask << 10, row_mask << 15, row_mask << 20, row_mask << 25, row_mask << 30,
row_mask << 35, row_mask << 40, row_mask << 45 };
const long long all_even_rows = row_masks[0] | row_masks[2] | row_masks[4] | row_masks[6] | row_masks[8];
const long long all_odd_rows = row_masks[1] | row_masks[3] | row_masks[5] | row_masks[7] | row_masks[9];
const long long all_rows[2] = { all_even_rows, all_odd_rows };

const long long even_left_edges = BIT | (BIT << 10) | (BIT << 20) | (BIT << 30 | (BIT << 40));
const long long odd_left_edges = (BIT << 5) | (BIT << 15) | (BIT << 25) | (BIT << 35) | (BIT << 45);
const long long left_edges = even_left_edges | odd_left_edges;
const long long even_right_edges = even_left_edges << 4;
const long long odd_right_edges = odd_left_edges << 4;
const long long right_edges = left_edges << 4;
const long long top_edge = row_masks[0];
const long long bottom_edge = row_masks[9];

const long long illegal_move_masks[6] = {
   left_edges, right_edges,
   bottom_edge | even_left_edges, bottom_edge | odd_right_edges,
   top_edge | even_left_edges, top_edge | odd_right_edges };

// mapping and bit manipulation
inline int location_of( int row, int col) { return row * 5 + col; }
inline int row_of( int location) { return location / 5; }
inline int col_of( int location) { return location % 5; }
inline long long get_bit( long long value, int pos) { return value & (BIT << pos); }
inline long long get_bit( long long value, int row, int col) { return value & (BIT << location_of(row, col)); }
inline long long has_bit( long long value, int pos) { return get_bit(value, pos) ? true : false; }
inline long long has_bit( long long value, int row, int col) { return get_bit(value, row, col) ? true : false;  }
inline void set_bit( long long &value, int pos) { value |= (BIT << pos); }
inline void set_bit( long long &value, int row, int col) { value |= (BIT << location_of(row, col)); }
inline int get_row( long long mask, int row) { return (int)((mask >> (row * 5)) & row_mask); }

inline long long shift_east( const long long mask) { return mask << 1; }
inline long long shift_west( const long long mask) { return mask >> 1; }
inline long long shift_nw( const long long mask) { return ((mask & all_even_rows) >> 6) | ((mask & all_odd_rows) >> 5); }
inline long long shift_ne( const long long mask) { return ((mask & all_even_rows) >> 5) | ((mask & all_odd_rows) >> 4); }
inline long long shift_sw( const long long mask) { return ((mask & all_even_rows) << 4) | ((mask & all_odd_rows) << 5); }
inline long long shift_se( const long long mask) { return ((mask & all_even_rows) << 5) | ((mask & all_odd_rows) << 6); }
inline long long shift_mask( int direction, const long long mask) {
   switch (direction) {
  case WEST: return shift_west(mask);
  case EAST: return shift_east(mask);
  case SW: return shift_sw(mask);
  case SE: return shift_se(mask);
  case NW: return shift_nw(mask);
   }
   return shift_ne(mask);
}


char const* dir_texts[] =       {"WEST","EAST","SW",  "SE",  "NW",  "NE"  };
int rotation_adder[2][6] = {
   { -1,    1,     4,     5,     -6,    -5   },
   { -1,    1,     5,     6,     -5,    -4   } };

int flip_transform[6] =    { WEST,  EAST,  NW,    NE,    SW,    SE   };
int rotate_transform[6] =  { NW,    SE,    WEST,  SW,    NE,    EAST };
int opposite_transform[6] ={ EAST,  WEST,  NE,    NW,    SE,    SW   };

int two_row_mask = 1024-1;
int bit_counts[32];
int first_bits[32];


typedef struct MaskInfo {
   bool is_legal[2];
   int start;

   MaskInfo() { is_legal[0] = is_legal[1] = true; }
   // bool piece_allowed[10];
};

MaskInfo big_map[1024];

long long flood_fill_actual( long long &mask, const int pos) {
   set_bit(mask, pos);
   if (pos % 5 && !has_bit( mask, pos - 1)) flood_fill_actual( mask, pos - 1);
   if (pos % 5 < 4 && !has_bit( mask, pos + 1)) flood_fill_actual( mask, pos + 1);
   if (pos >= 5) {
      if (!has_bit( mask, pos - 5)) flood_fill_actual( mask, pos - 5);
      if (pos / 10 < 5) {
         if (pos % 5 && !has_bit( mask, mask, pos - 6)) flood_fill_actual( mask, pos - 6);
      } else {
         if (pos % 5 < 4 && !has_bit( mask, mask, pos - 4)) flood_fill_actual( mask, pos - 4);
      }
   }
   if (pos < 45) {
      if (!has_bit( mask, pos + 5)) flood_fill_actual( mask, pos + 5);
      if (pos / 10 < 5) {
         if (pos % 5 && !has_bit( mask, pos + 4)) flood_fill_actual( mask, pos + 4);
      } else {
         if (pos % 5 < 4 && !has_bit( mask, pos + 6)) flood_fill_actual( mask, pos + 6);
      }
   }
   return mask;
}

long long flood_fill_down( long long mask, int row, int col) {
   if (row & row_masks[row]) {
      flood_fill_actual( mask, location_of(row, col));
      return mask;
   }

   while (row < 10 && !(mask & row_masks[row])) {
      mask |= row_masks[row];
      row++;
   }

   if (row < 10) for (int i = row * 5; i < (row + 1) * 5; i++) {
      if (!has_bit( mask, i)) flood_fill_actual( mask, i);
   }
   return mask;
}

long long flood_fill_up( long long mask, int row, int col) {
   if (row & row_masks[row]) {
      flood_fill_actual( mask, location_of(row, col));
      return mask;
   }

   while (row >= 0 && !(mask & row_masks[row])) {
      mask |= row_masks[row];
      row--;
   }

   if (row >= 0) for (int i = row * 5; i < (row + 1) * 5; i++) {
      if (!has_bit( mask, i)) flood_fill_actual( mask, i);
   }
   return mask;
}

typedef struct MaskData {
   long long mask[2];
   int height;
   int min_col[2];
   int max_col[2];

   MaskData() {
      mask[0] = 0;
      mask[1] = 0;
      height = 0;
      min_col[0] = 0;
      min_col[1] = 0;
      max_col[0] = 0;
      max_col[1] = 0;
   }
};

typedef struct RotationData {
   int mask;
   int iMask;
   int cMask;
   int row;
   int positions[5];
   int number;
};

void print_mask( long long mask) {
   for (int row = 0; row < 10; row++) {
      if (row % 2) cout << " ";
      for (int col = 0; col < 5; col++) {
         cout << (get_bit( mask, row, col)?"1":"0") << " ";
      }
      cout << "\n";
   }
   cout << "\n";
}

class LList {
public:
   LList *next;
   LList() { next = NULL; }
};

struct RotationSet {
   int size;
   RotationData rotations[12];

   RotationSet() { size = 0; }

   void add( RotationData &data) { rotations[ size] = data; size++; }
};

class PieceData : public LList {
private:
   void transform( const int matrix [], vector<int> &list ) {
      for (int i = 0; i < list.size(); i++) {
         list[i] = matrix[list[i]];
      }
   }

   int get_offset( vector<int> &directions ) {
      int offset = 0;
      for (int i = 0; i < directions.size(); i++) {
         if (directions[i] == SW || directions[i] == NW || directions[i] == WEST) offset++;
         if (directions[i] == NW || directions[i] == NE) offset += 5;
      }
      return offset;
   }

   MaskData mask_for_directions( vector<int> &directions) {
      MaskData data;

      long long mask = 0;
      int start_offset = get_offset( directions);
      int location = start_offset;
      for (int i = 0; i < directions.size(); i++) {
         set_bit( mask, location);
         int addition = rotation_adder[ (location / 5) % 2 ][ directions[i] ];
         //             int row = location / 5;
         //             int other_row = (location + addition) / 5;
         //             char * error = NULL;
         //             if ((directions[i] == SW || directions[i] == SE) && other_row != row + 1) error = "ERROR moving down!";
         //             if ((directions[i] == NW || directions[i] == NE) && other_row != row - 1) error =  "ERROR moving up!";
         //             if ((directions[i] == EAST || directions[i] == WEST) &&row != other_row) error = "ERROR moving to the side!";
         //             if (error != NULL) {
         //               int opposite = opposite_transform[directions[i]];
         //               if (illegal_move_masks[opposite] & mask) {
         //                  cout << error << " directions = ";
         //                  for (int j = 0; j < directions.size(); j++) cout << dir_texts[directions[j]] << " ";
         //                  cout << " [[[ current direction = " << dir_texts[directions[i]] << "]]]" << " opposite unavailable: " << dir_texts[opposite] << "\n";
         //                  cout << "row = " << row << ", other row = " << other_row <<"\n";
         //                  print_mask( mask);
         //               } else {
         //                  addition = 0;
         //                  mask = shift_mask( opposite, mask);
         //               }
         //             }
         location += addition;
      }
      set_bit( mask, location);

      while (!(mask & top_edge)) {
         if (illegal_move_masks[NW] & mask) {
            if (illegal_move_masks[NE] & mask) cout << "ERROR SHIFTING UPWARD\n";
            else mask = shift_ne(mask);
         } else mask = shift_nw(mask);
      }

      for (int row = 0; mask & row_masks[row]; row++) data.height++;
      while (!(mask & right_edges)) mask = shift_east(mask);
      for (int col_on = 0; !has_bit(mask, 0, col_on); col_on++) data.max_col[0]++;
      while (!(mask & left_edges)) mask = shift_west(mask);
      for (int col_on = 0; !has_bit(mask, 0, col_on); col_on++) data.min_col[0]++;
      data.mask[0] = mask >> data.min_col[0];

      if (mask & illegal_move_masks[SE]) {
         cout << "ERROR SHIFTING DOWNWARD\n";
      } else {
         mask = shift_se( mask);
         while (!(mask & right_edges)) mask = shift_east(mask);
         for (int col_on = 0; !get_bit(mask, 1, col_on); col_on++) data.max_col[1]++;
         while (!(mask & left_edges)) mask = shift_west(mask);
         for (int col_on = 0; !get_bit(mask, 1, col_on); col_on++) data.min_col[1]++;
         data.mask[1] = mask >> (data.min_col[1] + 5);
      }

      //cout << "\nDIRECTIONS: " << directions[0] << directions[1] << directions[2] << directions[3] << " [" << start_offset << "]\n";
      //cout << "height = " << data.height << ", min[0] = " << data.min_col[0] << ", max[0] = " << data.max_col[0] <<
      //   ", min[1] = " << data.min_col[1] << ", max[1] = " << data.max_col[1] << "\n";
      //print_mask( data.mask[1]);
      //exit(0);

      return data;
   }

   void compute_rotation_positions( long long board, RotationData &rotation) {
      int pos = rotation.row * 5;
      for (int num = 0; num < 5; pos++) {
         if (has_bit(board, pos)) {
            rotation.positions[num] = pos;
            num++;
         }
      }
   }

   void add_rotation( long long mask, int row, int col) {
      RotationData rotation;
      rotation.row = row;
      rotation.mask = (int)(mask >> (5 * row));
      rotation.number = number;
      long long board = 0;
      for (int i = 0; i < row; i++) board |= row_masks[i];
      for (int i = 0; i < col; i++) set_bit( board, row, i);
      board |= mask;
      for (int i = 4; i >= 0; i--) {
         if (!has_bit( board, 9, i)) {
            board = flood_fill_up( board, 9, i);
            break;
         }
      }
      if (board == full_mask) {
         rotation.iMask = rotation.mask;
         rotation.cMask = 0;
      } else {
         int count = 0;
         long long cMask = 0;
         for (int pos = location_of(row, col); pos < 50; pos++) {
            if (!has_bit(board,pos)) {
               set_bit(cMask, pos);
               count++;
            }
            if (count >= 5) {
               cMask = 0;
               break;
            }
         }
         rotation.cMask = (int)(cMask >> (5 * row));
         rotation.iMask = rotation.mask | rotation.cMask;
      }

      compute_rotation_positions( mask, rotation);
      rotation_sets[row][col].add( rotation);
   }

   void build_piece( vector<int> &directions) {
      vector<MaskData> base_masks;
      for (int i = 0; i < 2; i++) {
         for (int j = 0; j < 6; j++) {
            base_masks.push_back(mask_for_directions(directions));
            transform( rotate_transform, directions);
         }
         transform( flip_transform, directions);
      }

      for (int mask_on = 0; mask_on < base_masks.size(); mask_on++) {
         MaskData data = base_masks[mask_on];
         for (int row = 0; row <= (10 - data.height); row++) {
            for (int col = data.min_col[row % 2]; col <= data.max_col[row % 2]; col++) {
               long long mask = data.mask[row % 2] << (row * 5 + col);
               long long board = mask;
               if ( row >= 3) board = flood_fill_down( board, 0, 0);
               else board = flood_fill_up( board, 9, 4);
               if (board == full_mask) {
                  add_rotation( mask, row, col);
               } else {
                  int count = 0;
                  for (int t = 0; t < 10; t++) count += bit_counts[ (int)((board >> (t * 5)) & row_masks[0])];
                  if (count % 5 == 0) {
                     add_rotation( mask, row, col);
                  }
               }
            }
         }
      }
   }

public:
   int number;
   RotationSet rotation_sets[10][5];

   PieceData( int d1, int d2, int d3, int d4, int piece_number ) : LList()  {
      number = piece_number;
      vector<int> directions;
      directions.push_back(d1);
      directions.push_back(d2);
      directions.push_back(d3);
      directions.push_back(d4);
      build_piece( directions);
   }

   PieceData( int d1, int d2, int d3, int d4, int d5, int piece_number ) : LList() {
      number = piece_number;
      vector<int> directions;
      directions.push_back(d1);
      directions.push_back(d2);
      directions.push_back(d3);
      directions.push_back(d4);
      directions.push_back(d5);
      build_piece( directions);
   }
};

// GOLBAL VARIABLES MUH-HA-HA-HA
LList *head;
LList *tail;

int num_placed = 0;
int num_found = 0;
int num_to_find = 0;
int tries[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
RotationData *active_rotations[10];
set<string> found_boards;

void create_piece_maps() {
   tail = head = new PieceData( NW, NE, EAST, EAST,  2);
   tail->next = new PieceData( NE, SE, EAST, NE,  7);
   tail = tail->next;
   tail->next = new PieceData( NE, EAST, NE, NW,  1);
   tail = tail->next;
   tail->next = new PieceData( EAST, SW, SW, SE,  6);
   tail = tail->next;
   tail->next = new PieceData( EAST, NE, SE, NE,  5);
   tail = tail->next;
   tail->next = new PieceData( EAST, EAST, EAST, SE,  0);
   tail = tail->next;
   tail->next = new PieceData( NE, NW, SE, EAST, SE,  4);
   tail = tail->next;
   tail->next = new PieceData( SE, SE, SE, WEST,  9);
   tail = tail->next;
   tail->next = new PieceData( SE, SE, EAST, SE,  8);
   tail = tail->next;
   tail->next = new PieceData( EAST, EAST, SW, SE,  3);
   tail = tail->next;
}

void print_board( string board_string) {
   for (int row = 0; row < 10; row++) {
      if (row % 2) cout << " ";
      for (int col = 0; col < 5; col++) cout << board_string[row * 5 + col] << " ";
      cout << "\n";
   }
   cout << "\n";
}

void print_results() {
   cout << num_found << " solutions found\n\n";
   print_board( *found_boards.begin());
   print_board( *found_boards.rbegin());
}

void add_board_string( const char * board_string) {
   string s = board_string;
   if (found_boards.count(s) == 0) {
      found_boards.insert(s);
      num_found++;
      if (num_to_find == num_found) {
         print_results();
         exit(0);
      }
   }
}


void board_found() {
   char board_string[51];
   memset(board_string,'x',51);
   for (int i = 0; i < 10; i++) {
      for (int j = 0; j < 5; j++) {
         board_string[active_rotations[i]->positions[j]] = '0' + active_rotations[i]->number;
      }
   }
   board_string[50] = 0;
   add_board_string( board_string);
   for (int i = 0; i < 25; i++) { char c = board_string[i]; board_string[i] = board_string[49 - i]; board_string[49-i] = c; }
   add_board_string( board_string);
}

void find( int row, int board) {
   while ((board & 31) == 31) {
      row++;
      board >>= 5;
   }
   MaskInfo &info = big_map[board & two_row_mask];
   if (!info.is_legal[row % 2]) return;
   int col = info.start;


   PieceData *start = (PieceData *)head;
   do {
      PieceData *piece = (PieceData *)head;
      head = piece->next;
      piece->next = NULL;
      RotationSet *rotations = &(piece->rotation_sets[row][col]);
      for (int i = rotations->size-1; i >= 0; i--) {
         //tries[num_placed]++;
         RotationData *rotation = &rotations->rotations[i];
         if ((board & rotation->iMask) == rotation->cMask) {
            if (num_placed == 9) {
               active_rotations[num_placed] = rotation;
               board_found();
            } else {
               active_rotations[num_placed] = rotation;
               num_placed++;
               find( row, board | rotation->mask);
               num_placed--;
            }
         }
      }
      if (head == NULL) head = piece;
      else tail->next = piece;
      tail = piece;
   } while (start != head);
}

void find_all() {
   num_found = 0;
   num_placed = 1;
   found_boards.clear();
   PieceData *start = (PieceData *)head;
   for (int odd = 0; odd < 2; odd++) {
      do {
         PieceData *piece = (PieceData *)head;
         head = piece->next;
         piece->next = NULL;
         if (head != start) {
            RotationSet *rotations = &(piece->rotation_sets[0][0]);
            for (int i = rotations->size-1; i >= 0; i--) {
               if (i % 2 == odd) {
                  RotationData *rotation = &rotations->rotations[i];
                  active_rotations[0] = rotation;
                  find( 0, rotation->mask);
               }
            }
         }
         if (head == NULL) head = piece;
         else tail->next = piece;
         tail = piece;
      } while (start != head);
   }
}


void create_utlity_maps() {
   for (int i = 0; i < 32; i++) {
      bit_counts[i] = 0;
      for (int j = 0; j < 5; j++) if ((1 << j) & i) bit_counts[i]++;
      for (first_bits[i] = 0; (1 << first_bits[i]) & i; first_bits[i]++);
   }

   // build starts
   for (int i = 0; i < 1024; i++) big_map[i].start = first_bits[i & 31];

   // build legality
   int legal_count = 0;
   for (int i = 0; i < 1024; i++) {
      for (int odd = 0; odd < 2; odd++) {
         int legal = 2;
         int bit = 1;
         while (legal && bit < 32) {
            if (i & bit) {
               if (legal == 2 && bit > 1 && ((bit >> 1) & i) == 0) legal = 0;
               else legal = 2;
            } else if (legal == 2) {
               if (((bit << 5) & i) == 0) legal = 1;
               else {
                  if (odd) {
                     if ( (bit < 16) && (((bit << 6) & i) == 0)) legal = 1;
                  } else {
                     if ( (bit > 1) && (((bit << 4) & i) == 0)) legal = 1;
                  }
               }
            }
            bit <<= 1;
         }
         if (legal == 2 && ((bit >> 1) & i) == 0) legal = 0;
         big_map[i].is_legal[odd] = legal ? true : false;
         if (legal) legal_count++;
      }
   }
}

int main (int argc, char * const argv[]) {
   num_to_find = 2098;
   if (argc > 1) sscanf(argv[1],"%d", &num_to_find);

   create_piece_maps();
   create_utlity_maps();
   find_all();
   print_results();

   return 0;
}

 make, command-line, and program output logs

Mon, 28 Oct 2013 18:39:33 GMT

MAKE:
/usr/bin/g++ -c -pipe -O3 -fomit-frame-pointer -march=native  -fopenmp meteor.c++ -o meteor.c++.o &&  \
        /usr/bin/g++ meteor.c++.o -o meteor.gpp_run -fopenmp 
meteor.c++:98:2: warning: ‘typedef’ was ignored in this declaration [enabled by default]
 };
  ^
meteor.c++:174:2: warning: ‘typedef’ was ignored in this declaration [enabled by default]
 };
  ^
meteor.c++:183:1: warning: ‘typedef’ was ignored in this declaration [enabled by default]
 };
 ^
rm meteor.c++
1.47s to complete and log all make actions

COMMAND LINE:
./meteor.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 

Revised BSD license

  Home   Conclusions   License   Play