The Computer Language
Benchmarks Game

meteor-contest Chapel #2 program

source code

/* The Computer Language Benchmarks Game
   http://benchmarksgame.alioth.debian.org/

   contributed by Kyle Brady and Ben Albrecht
   derived from the C++ implementation by Stefan Westen
 */

use BitOps;

param boardCells = 50,          // Number of cells on board
      boardWidth = 5,           // Number of cells along x-axis
      boardHeight = 10,         // Number of cells along y-axis
      totalMasks = 8192,        // Upper bound for allMasks needed (power of 2)
      piecePermutations = 12,   // Number of permutations for a single piece
      numPieces = 10,           // Number of puzzle pieces
      pieceCells = 5;           // Number of cells that make up a puzzle piece

const boardDom = {0..#boardCells},
      piecesDom = {0..#numPieces};

// Arrays of masks to store all pieces and their possible configurations
var allMasks: [0..#totalMasks] int,
    maskStart: [boardDom][0..#numPieces-2] int;

// Arrays of min and max, and an integer storing the number of solutions
var minSolution, maxSolution: [boardDom] int,
    solutions = 0;

// Masks for evens and left border
var evenRowsLookup, leftBorderLookup: [boardDom] int;

// Predefined masks commonly used throughout program
param maskEven   = 0xf07c1f07c1f07c1f: int, // Even rows of board (0, 2, 4, ..)
      maskBorder = 0x1084210842108421: int, // Right border of board
      maskBoard  = 0xFFFC000000000000: int, // bits of board within 64-bit int
      maskBottom = 0x00000000003FFFFF: int, // Bottom 22 elements of boards
      maskUsed   = 0x00000000FFC00000: int; // Board + 4 additional bits

//
// Find and print the minimum and maximum solutions to meteor puzzle
//
proc main(args: [] string) {

  initialize();

  sync searchParallel();

  writef("%i solutions found\n\n", solutions);
  printBoard(minSolution);
  printBoard(maxSolution);
}


//
// Set up allMasks with pre-filtered piece permutations to search
//
proc initialize() {

  // Set up array of evens and borders masks
  for i in 0..#boardCells {
    evenRowsLookup[i] = (maskEven >> i);
    leftBorderLookup[i] = (maskBorder >> i);
  }

  var totalCount = 0,
      coords: [0..#pieceCells] 2*int;

  /* The 10 puzzle pieces are defined with hexagonal cell coordinates, where
     the first cell of a piece always begins at the origin cell, (0, 0).
     This coordinate system is best conveyed through a diagram:

                         (0, -1)       (1, -1)

                  (-1, 0)       (0 , 0)       (1 , 0)

                         (-1, 1)       (0 , 1)

     Therefore, the cell to the South of the origin can be computed as follows:

        S =    SW   +   SE
        S = (-1, 1) + (0, 1) = (-1, 2)

     The following illustrates the piece shapes and their cell indices:

        Piece 0      Piece 1      Piece 2      Piece 3      Piece 4

        0 1 2 3         0          0 1 2        0 1 2        0
               4         1        3                3          1 2
                      2 3          4                4        3   4
                     4

        Piece 5      Piece 6      Piece 7      Piece 8      Piece 9

           0 1        0 1          0   1        0            0
        2 3 4          2          2 3 4          1            1
                      3                           2 3          2
                       4                             4        3 4

  */
  const pieces: [piecesDom][0..#pieceCells] 2*int =
  [
    [(0, 0), (1, 0), ( 2, 0), ( 3, 0), ( 3, 1)],
    [(0, 0), (0, 1), (-2, 2), (-1, 2), (-3, 3)],
    [(0, 0), (1, 0), ( 2, 0), (-1, 1), (-1, 2)],
    [(0, 0), (1, 0), ( 2, 0), ( 1, 1), ( 1, 2)],
    [(0, 0), (0, 1), ( 1, 1), (-1, 2), ( 1, 2)],
    [(0, 0), (1, 0), (-2, 1), (-1, 1), ( 0, 1)],
    [(0, 0), (1, 0), ( 0, 1), (-1, 2), (-1, 3)],
    [(0, 0), (2, 0), (-1, 1), ( 0, 1), ( 1, 1)],
    [(0, 0), (0, 1), ( 0, 2), ( 1, 2), ( 1, 3)],
    [(0, 0), (0, 1), ( 0, 2), (-1, 3), ( 0, 3)]
  ];

  // Generate bit mask for permutations of all pieces that fit on rows 2 & 3
  for yBase in 2..3 {
    for xBase in 0..#boardWidth {
      // Compute base position for xBase, yBase coordinates
      const pos = (xBase + boardWidth * yBase);

      // Record total number of fitted pieces at this point
      maskStart[pos][0] = totalCount;

      // Loop over piece indices
      for piece in 0..#numPieces {

        // Get x y coordinates of piece cells
        for (coord, pieceCell) in zip(coords, pieces[piece]) do
          coord = pieceCell;

        // Loop over 12 permutations for a given piece (6 rotations * 2 flips)
        for currentPermutation in 0..#piecePermutations {

          // Skip piece 3 and specific permutations
          if piece != 3 || (currentPermutation/3) % 2 == 0 {

            //
            // Overload min function to use for reduction of piece coordinates
            //
            proc min((x1, y1), (x2, y2)) {
              if y1 < y2 || (y1 == y2 && x1 < x2) then
                return (x1, y1);
              return (x2, y2);
            }

            // Serial reduction to find min coords of a given permutation
            var (xMin, yMin) = min reduce for c in coords do c;

            var mask = 0,       // Bit mask representing piece's permutation
                fit = true;     // Track if piece's permutation fits board

            // Offsets for piece coordinates, such that 'island' is not formed
            const xOff = (xBase - yBase/2) - xMin,
                  yOff= yBase - yMin;

            // Set bit mask for given piece's permutation if it fits on board
            for (x, y) in coords {

              var nY = y + yOff,
                  nX = x + xOff + nY/2;

              if nX >= 0 && nX < boardWidth {
                const numBits = nX - xBase + boardWidth * (nY - yBase);
                mask |= (1 << numBits);
              } else
                fit = false;
            }

            // If it fits and is a "good piece", add it to the array of masks
            if fit {
              if goodPiece(mask, pos) {
                allMasks[totalCount] = mask | (1 << (piece + 22));
                totalCount += 1;
              }
            }
          }

          // Permute piece for next iteration
          for (x, y) in coords {
            // Rotation
            (x, y) = (x + y, -x);

            // Reflection
            if currentPermutation == 5 then
              (x, y) = (x + y, -y);
          }
        } // permutations
      } // pieces

      allMasks[totalCount] = 0;
      totalCount += 1;
    } // xBase
  } // yBase

  // Generate bit masks for translation of permutations that fit on rows 2 & 3
  for yBase in 0..#boardHeight {
    // Skip rows 2 & 3, since we already generated their masks
    if yBase != 2 && yBase != 3 {
      for xBase in 0..#boardWidth {
        const pos = (xBase + boardWidth * yBase),
              origPos = xBase + boardWidth * (yBase % 2 + 2);
        maskStart[pos][0] = totalCount;
        var pMask = maskStart[origPos][0];
        const bottom = ((maskBoard >> pos) & maskBottom),
              lastRow = ((maskBoard >> (pos + boardWidth)) & maskBottom);
        while allMasks[pMask] {
          const mask = allMasks[pMask];
          pMask += 1;
          if (mask & bottom) == 0 {
            if (yBase == 0 || ((mask & lastRow) != 0)) &&
               !goodPiece(mask & maskBottom, pos) then
              continue;

            allMasks[totalCount] = mask;
            totalCount += 1;
          }
        }
        allMasks[totalCount] = 0;
        totalCount += 1;
      }
    }
  }

  for filter in 1..7 {
    for pos in 0..#boardCells {
      maskStart[pos][filter] = totalCount;
      const filterMask = ((filter & 1) << 1) |
                         ((filter & 6) << (4 - (evenRowsLookup[pos] & 1)));
      var pMask = maskStart[pos][0];
      while allMasks[pMask] {
        const mask = allMasks[pMask];
        if (mask & filterMask) == 0 {
          allMasks[totalCount] = mask;
          totalCount += 1;
        }
        pMask += 1;
      }
      allMasks[totalCount] = 0;
      totalCount += 1;
    }
  }
}


//
// Add initial piece to board, then fire off remaining searches in parallel
//
proc searchParallel(in board=0, in pos=0, used=0, placed=0, firstPiece=0) {

  const count = ctz(~board);
  pos += count;
  board >>= count;

  const boardAndUsed = board | used;
  var currentMask = maskStart[pos][0];

  if placed == 0 {
    while allMasks[currentMask] {
      if allMasks[currentMask] {
        const mask = allMasks[currentMask];
        currentMask += 1;
        searchParallel(board | (mask & maskBottom), pos,
                       used | (mask & maskUsed), placed + 1, mask);
      }
    }
  // 1 piece has been placed
  } else {
    while allMasks[currentMask] {
      while allMasks[currentMask] & boardAndUsed do
        currentMask += 1;

      if allMasks[currentMask] {
        const mask = allMasks[currentMask];
        currentMask += 1;
        searchLinearHelper(board | (mask & maskBottom), pos,
                           used | (mask & maskUsed), placed+1,
                           firstPiece, mask);
      }
    }
  }
}


//
// Pretty printed output of board
//
proc printBoard(board) {
  for i in 0..#boardCells {
    writef("%i ", board[i]);
    if i % boardWidth == 4 {
      writeln();
      if i & 1 == 0 then
        write(" ");
    }
  }
  writeln();
}


//
// Determine if piece and permutation (mask) at a given position (pos) is valid
//
proc goodPiece(mask, pos) {
   const evenRows = maskEven,
         oddRows = ~evenRows,
         leftBorder = maskBorder,
         rightBorder = leftBorder >> 1;

   var b = (mask << pos) | maskBoard;

   b = ~b;

   while b {
      var a = b & (-b);

      do {
        const s1 = a << 5,
              s2 = a >> 5,
              s3 = (a << 1) & (~leftBorder),
              s4 = (a >> 1) & (~rightBorder),
              s5 = ((a & evenRows) >> 6) & (~rightBorder),
              s6 = ((a & evenRows) << 4) & (~rightBorder),
              s7 = ((a & oddRows) >> 4) & (~leftBorder),
              s8 = ((a & oddRows) << 6) & (~leftBorder),
              aOld = a;
        a = (a | s1 | s2 | s3 | s4 | s5 | s6 | s7 | s8) & b;
      } while aOld != a;

      if popcount(a) % 5 != 0 then
        return false;

      b ^= a;
   }
   return true;
}


//
// Wrapper to set up initial call to recursive searchLinear
//
proc searchLinearHelper(board, pos, used, placed, firstPiece, mask) {
  var currentSolution: [piecesDom] int;
  currentSolution[0] = firstPiece;
  currentSolution[1] = mask;
  begin searchLinear(board, pos, used, placed, currentSolution);
}


//
// Exponential backoff spin-wait lock that yields every so many contested locks
// to avoid potentially starving other tasks. This results in slightly faster
// runtime than just using a sync var because it has lower latency.
//
record BackoffSpinLock {
  var l: atomic bool,
      lockAttempts = 0,
      maxLockAttempts = (2**16-1);

  inline proc lock() {
    while l.testAndSet() {
      lockAttempts += 1;
      if (lockAttempts & maxLockAttempts) == 0 {
        maxLockAttempts >>= 1;
        chpl_task_yield();
      }
    }
  }

  inline proc unlock() {
    l.clear();
  }
}

// Minimally contended lock that serializes calls to recordSolution()
var recordSolutionLock: BackoffSpinLock;


//
// Recursively add pieces to the board, and check solution when filled
//
proc searchLinear(in board, in pos, used, placed, currentSolution) {

  if placed == numPieces {
    recordSolutionLock.lock();
    recordSolution(currentSolution);
    recordSolutionLock.unlock();
  } else {
    const evenRows = evenRowsLookup[pos],
          oddRows = ~evenRows,

          leftBorder = leftBorderLookup[pos],
          rightBorder = leftBorder >> 1,

          s1 = (board << 1) | leftBorder,
          s2 = (board >> 1) | rightBorder,
          s3 = (board << 4) | ((1 << 4) - 1) | rightBorder,
          s4 = (board >> 4) | leftBorder,
          s5 = (board << 5) | ((1 << 5) - 1),
          s6 = (board >> 5),
          s7 = (board << 6) | ((1 << 6) - 1) | leftBorder,
          s8 = (board >> 6) | rightBorder;

    if ~board & s1 & s2 & s5 & s6 &
       ((evenRows & s4 & s7) | (oddRows & s3 & s8)) then return;

    const count = ctz(~board);
    pos += count;
    board >>= count;

    const f = ((board >> 1) & 1) |
              ((board >> (4 - (evenRowsLookup[pos] & 1))) & 6),
          boardAndUsed = board | used;

    var currentMask = maskStart[pos][f];

    while allMasks[currentMask] {

      while allMasks[currentMask] & boardAndUsed do
        currentMask += 1;

      if allMasks[currentMask] {
        const mask = allMasks[currentMask];
        currentSolution[placed] = mask;
        searchLinear(board | (mask & maskBottom), pos,
                     used | (mask & maskUsed), placed + 1, currentSolution);
        currentMask += 1;
      }
    }
  }
}


//
// Check a given board as a solution and record it
//
proc recordSolution(currentSolution) {
  var board, flipBoard: [boardDom] int,
      pos, b1, count = 0;

  for i in 0..#numPieces {
    var mask = currentSolution[i];
    const piece = ctz(mask >> 22);
    mask &= maskBottom;
    b1 |= mask;
    while mask {
      const currentBit = mask & (-mask);
      count = ctz(currentBit);
      board[count + pos] = piece;
      flipBoard[49 - count - pos] = piece;
      mask ^= currentBit;
    }
    count = ctz(~b1);
    pos += count;
    b1 >>= count;
  }
  if solutions == 0 {
    minSolution = board;
    maxSolution = board;
  } else {
    compareSolution(board);
    compareSolution(flipBoard);
  }

  solutions += 2;
}


//
// Determine whether a solution is a min or max solution
//
proc compareSolution(board) {

  for i in 0..#boardCells {
    if board[i] < minSolution[i] {
      minSolution = board;
      break;
    } else if board[i] > minSolution[i] then break;
  }
  for i in 0..#boardCells {
    if board[i] > maxSolution[i] {
      maxSolution = board;
      break;
    } else if board[i] < maxSolution[i] then break;
  }
}

    

notes, command-line, and program output

NOTES:
32-bit Ubuntu one core
chpl Version 1.14.0
Copyright (c) 2004-2016, Cray Inc.


Fri, 07 Oct 2016 23:31:56 GMT

MAKE:
mv meteor.chapel-2.chapel meteor.chapel-2.chpl
/usr/local/src/chapel-1.14.0/bin/linux32/chpl --fast meteor.chapel-2.chpl -o meteor.chapel-2.chapel_run
rm meteor.chapel-2.chpl
11.77s to complete and log all make actions

COMMAND LINE:
./meteor.chapel-2.chapel_run --n=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