meteor.impala

/* The Computer Language Benchmarks Game
 * http://benchmarksgame.alioth.debian.org/
 *
 * ported to impala from Christian Vosteen's C solution
 */

extern "C" {
    fn println(&[u8]) -> ();
    fn printa(&[i8]) -> ();
    fn print_piece_mask(&[u64]) -> ();
    fn print_char(u8) -> ();
    fn print_int(int) -> ();
    fn print_f64(f64) -> ();
    fn print_meteor_scnt(int) -> ();
    fn print_meteor_lines(i8, i8, i8, i8, i8, i8, i8, i8, i8, i8) -> ();
    fn print_piece_def(&[[i8*4]*10]) -> ();
}

fn range_step(a: int, b: int, step: int, body: fn(int, fn())) -> () {
    if a < b {
        body(a);
        range_step(a+step, b, step, body, return)
    }
}

fn range(a: int, b: int, body: fn(int, fn())) -> () { range_step(a, b, 1, body, return) }

fn range_step_i8(a: i8, b: i8, step: i8, body: fn(i8, fn())) -> () {
    if a < b {
        body(a);
        range_step_i8(a+step, b, step, body, return)
    }
}

fn range_i8(a: i8, b: i8, body: fn(i8, fn())) -> () { range_step_i8(a, b, 1_i8, body, return) }

/* The board is a 50 cell hexagonal pattern.  For    . . . . .
 * maximum speed the board will be implemented as     . . . . .
 * 50 bits, which will fit into a 64 bit long long   . . . . .
 * int.                                               . . . . .
 *                                                   . . . . .
 * I will represent 0's as empty cells and 1's        . . . . .
 * as full cells.                                    . . . . .
 *                                                    . . . . .
 *                                                   . . . . .
 *                                                    . . . . .
 */
static mut board = 0xFFFC000000000000_u64;

/* The puzzle pieces must be specified by the path followed
 * from one end to the other along 12 hexagonal directions.
 *
 *   Piece 0   Piece 1   Piece 2   Piece 3   Piece 4
 *                   
 *  O O O O    O   O O   O O O     O O O     O   O
 *         O    O O           O       O       O O
 *                           O         O         O
 *
 *   Piece 5   Piece 6   Piece 7   Piece 8   Piece 9
 *
 *    O O O     O O       O O     O O        O O O O
 *       O O       O O       O       O O O        O
 *                  O       O O
 *
 * I had to make it 12 directions because I wanted all of the
 * piece definitions to fit into the same size arrays.  It is
 * not possible to define piece 4 in terms of the 6 cardinal
 * directions in 4 moves.
 */
static E     = 0_i8;
static ESE   = 1_i8;
static SE    = 2_i8;
static S     = 3_i8;
static SW    = 4_i8;
static WSW   = 5_i8;
static W     = 6_i8;
static WNW   = 7_i8;
static NW    = 8_i8;
static N     = 9_i8;
static NE    = 10_i8;
static ENE   = 11_i8;
static PIVOT = 12_i8;

static mut piece_def = [
   [  E,  E,  E, SE],
   [ SE,  E, NE,  E],
   [  E,  E, SE, SW],
   [  E,  E, SW, SE],
   [ SE,  E, NE,  S],
   [  E,  E, SW,  E],
   [  E, SE, SE, NE],
   [  E, SE, SE,  W],
   [  E, SE,  E,  E],
   [  E,  E,  E, SW]
];

 
/* To minimize the amount of work done in the recursive solve function below,
 * I'm going to allocate enough space for all legal rotations of each piece
 * at each position on the board. That's 10 pieces x 50 board positions x
 * 12 rotations.  However, not all 12 rotations will fit on every cell, so
 * I'll have to keep count of the actual number that do.
 * The pieces are going to be unsigned long long ints just like the board so
 * they can be bitwise-anded with the board to determine if they fit.
 * I'm also going to record the next possible open cell for each piece and
 * location to reduce the burden on the solve function.
 */
static mut pieces: [[[u64*12]*50]*10];
static mut piece_counts: [[int*50]*10];
static mut next_cell: [[[i8*12]*50]*10];

/* Returns the direction rotated 60 degrees clockwise */
fn rotate(dir: i8) -> i8 {
   ((dir as int + 2) % (PIVOT as int)) as i8
}

/* Returns the direction flipped on the horizontal axis */
fn flip(dir: i8) -> i8 {
   (PIVOT - dir) % PIVOT
}


/* Returns the new cell index from the specified cell in the
 * specified direction.  The index is only valid if the
 * starting cell and direction have been checked by the
 * out_of_bounds function first.
 */
// TODO maybe use return(x) here
fn shift(cell: i8, dir: i8) -> i8 {
   if dir == E {
      cell + 1_i8
   } else if dir == ESE {
      if ((cell / 5_i8) % 2_i8) != 0_i8 {
         cell + 7_i8
      } else {
         cell + 6_i8
      }
   } else if dir == SE {
      if((cell / 5_i8) % 2_i8) != 0_i8 {
         cell + 6_i8
      } else {
         cell + 5_i8
      }
   } else if dir == S {
       cell + 10_i8
   } else if dir == SW {
      if((cell / 5_i8) % 2_i8) != 0_i8 {
         cell + 5_i8
      } else {
         cell + 4_i8
      }
   } else if dir == WSW {
      if((cell / 5_i8) % 2_i8) != 0_i8 {
         cell + 4_i8
      } else {
         cell + 3_i8
      }
   } else if dir == W {
      cell - 1_i8
   } else if dir == WNW {
      if((cell / 5_i8) % 2_i8) != 0_i8 {
         cell - 6_i8
      } else {
         cell - 7_i8
      }
   } else if dir == NW {
      if((cell / 5_i8) % 2_i8) != 0_i8 {
         cell - 5_i8
      } else {
         cell - 6_i8
      }
   } else if dir == N {
      cell - 10_i8
   } else if dir == NE {
      if((cell / 5_i8) % 2_i8) != 0_i8 {
         cell - 4_i8
      } else {
         cell - 5_i8
      }
   } else if dir == ENE {
      if((cell / 5_i8) % 2_i8) != 0_i8 {
         cell - 3_i8
      } else {
         cell - 4_i8
      }
   } else {
      cell
   }
}

/* Returns wether the specified cell and direction will land outside
 * of the board.  Used to determine if a piece is at a legal board
 * location or not.
 */
fn out_of_bounds(cell: i8, dir: i8) -> bool {
   if dir == E {
      cell % 5_i8 == 4_i8
   } else if dir == ESE {
      let i = cell % 10_i8;
      i == 4_i8 || i == 8_i8 || i == 9_i8 || cell >= 45_i8
   } else if dir == SE {
      cell % 10_i8 == 9_i8 || cell >= 45_i8
   } else if dir == S {
      cell >= 40_i8
   } else if dir == SW {
      cell % 10_i8 == 0_i8 || cell >= 45_i8
   } else if dir == WSW {
      let i = cell % 10_i8;   
      i == 0_i8 || i == 1_i8 || i == 5_i8 || cell >= 45_i8
   } else if dir == W {
      cell % 5_i8 == 0_i8
   } else if dir == WNW {
      let i = cell % 10_i8;
      i == 0_i8 || i == 1_i8 || i == 5_i8 || cell < 5_i8
   } else if dir == NW {
      cell % 10_i8 == 0_i8 || cell < 5_i8
   } else if dir == N {
      cell < 10_i8
   } else if dir == NE {
      cell % 10_i8 == 9_i8 || cell < 5_i8
   } else if dir == ENE {
      let i = cell % 10_i8;
      i == 4_i8 || i == 8_i8 || i == 9_i8 || cell < 5_i8
   } else {
      false
   }
}

/* Rotate a piece 60 degrees clockwise */
fn rotate_piece(piece: int) -> () {
   for i in range(0, 4) {
      piece_def(piece)(i) = rotate(piece_def(piece)(i));
   }
}

/* Flip a piece along the horizontal axis */
fn flip_piece(piece: int) -> () {
   for i in range(0, 4) {
      piece_def(piece)(i) = flip(piece_def(piece)(i));
   }
}

/* Convenience function to quickly calculate all of the indices for a piece */
fn calc_cell_indices(mut cell: &[i8], piece: int, index: i8) -> () {
   cell(0) = index;
   cell(1) = shift(cell(0), piece_def(piece)(0));
   cell(2) = shift(cell(1), piece_def(piece)(1));
   cell(3) = shift(cell(2), piece_def(piece)(2));
   cell(4) = shift(cell(3), piece_def(piece)(3));
}

/* Convenience function to quickly calculate if a piece fits on the board */
fn cells_fit_on_board(cell: &[i8], piece: int) -> bool {
        !out_of_bounds(cell(0), piece_def(piece)(0)) 
    &&  !out_of_bounds(cell(1), piece_def(piece)(1)) 
    &&  !out_of_bounds(cell(2), piece_def(piece)(2)) 
    &&  !out_of_bounds(cell(3), piece_def(piece)(3))
}

/* Returns the lowest index of the cells of a piece.
 * I use the lowest index that a piece occupies as the index for looking up
 * the piece in the solve function.
 */
fn minimum_of_cells(cell: &[i8]) -> i8 {
   let mut minimum = cell(0);
   minimum = if cell(1) < minimum { cell(1) } else { minimum };
   minimum = if cell(2) < minimum { cell(2) } else { minimum };
   minimum = if cell(3) < minimum { cell(3) } else { minimum };
   minimum = if cell(4) < minimum { cell(4) } else { minimum };
   minimum
}

/* Calculate the lowest possible open cell if the piece is placed on the board.
 * Used to later reduce the amount of time searching for open cells in the
 * solve function.
 */
fn first_empty_cell(cell: &[i8], minimum: i8) -> i8 {
   let mut first_empty = minimum;
   while(first_empty == cell(0) || first_empty == cell(1) ||
         first_empty == cell(2) || first_empty == cell(3) ||
         first_empty == cell(4)) {
      first_empty++;
   }
   first_empty
}

/* Generate the unsigned long long int that will later be anded with the
 * board to determine if it fits.
 */
fn bitmask_from_cells(cell: &[i8]) -> u64 {
   let mut piece_mask = 0_u64;
   for i in range(0, 5) {
      piece_mask |= 1_u64 << (cell(i) as u64);
   }
   piece_mask
}

/* Record the piece and other important information in arrays that will
 * later be used by the solve function.
 */
fn record_piece(piece: int, minimum: int, first_empty: i8, piece_mask: u64) -> () {
    pieces(piece)(minimum)(piece_counts(piece)(minimum)) = piece_mask;
    next_cell(piece)(minimum)(piece_counts(piece)(minimum)) = first_empty;
    piece_counts(piece)(minimum)++;         
}

/* Fill the entire board going cell by cell.  If any cells are "trapped"
 * they will be left alone.
 */
fn fill_contiguous_space(mut board: &[i8], index: int) -> () {
   if (board(index) == 1_i8) {
      return()
   }
   
   board(index) = 1_i8;
   let indexi8 = index as i8;
   if(!out_of_bounds(indexi8, E)) {
      fill_contiguous_space(board, shift(indexi8, E) as int);
   }
   if(!out_of_bounds(indexi8, SE)) {
      fill_contiguous_space(board, shift(indexi8, SE) as int);
   }
   if(!out_of_bounds(indexi8, SW)) {
      fill_contiguous_space(board, shift(indexi8, SW) as int);
   }
   if(!out_of_bounds(indexi8, W)) {
      fill_contiguous_space(board, shift(indexi8, W) as int);
   }
   if(!out_of_bounds(indexi8, NW)) {
      fill_contiguous_space(board, shift(indexi8, NW) as int);
   }
   if(!out_of_bounds(indexi8, NE)) {
      fill_contiguous_space(board, shift(indexi8, NE) as int);
   }
}


/* To thin the number of pieces, I calculate if any of them trap any empty
 * cells at the edges.  There are only a handful of exceptions where the
 * the board can be solved with the trapped cells.  For example:  piece 8 can
 * trap 5 cells in the corner, but piece 3 can fit in those cells, or piece 0
 * can split the board in half where both halves are viable.
 */
fn has_island(cell: &[i8], piece: int) -> bool {
    let mut temp_board: [i8*50]; // TODO maybe use bool here
    for i in range(0, 50) {
        temp_board(i) = 0_i8;
    }
    for i in range(0, 5) {
        temp_board(cell(i) as int) = 1_i8;
    }
    let mut i = 49;
    while(temp_board(i) == 1_i8) {
        i--;
    }
    fill_contiguous_space(&temp_board, i);
    let mut c = 0_i8;
    for i in range(0, 50) {
        if(temp_board(i) == 0_i8) {
            c++;
        }
    }
    !(c == 0_i8 || (c == 5_i8 && piece == 8) || (c == 40_i8 && piece == 8) || (c % 5_i8 == 0_i8 && piece == 0))
}

/* Calculate all six rotations of the specified piece at the specified index.
 * We calculate only half of piece 3's rotations.  This is because any solution
 * found has an identical solution rotated 180 degrees.  Thus we can reduce the
 * number of attempted pieces in the solve algorithm by not including the 180-
 * degree-rotated pieces of ONE of the pieces.  I chose piece 3 because it gave
 * me the best time ;)
 */
fn calc_six_rotations(piece: i8, index: i8) -> () {
    let mut cell: [i8*5];

    for rotation in range_i8(0_i8, 6_i8) {
        if piece != 3_i8 || rotation < 3_i8 { 
            calc_cell_indices(&cell, piece as int, index);
            if cells_fit_on_board(&cell, piece as int) && !has_island(&cell, piece as int) {
                let minimum = minimum_of_cells(&cell);
                let first_empty = first_empty_cell(&cell, minimum);
                let piece_mask = bitmask_from_cells(&cell);
                record_piece(piece as int, minimum as int, first_empty, piece_mask);
            }
        }
        rotate_piece(piece as int);
    }
}

/* Calculate every legal rotation for each piece at each board location. */
fn calc_pieces() -> () {
    for piece in range(0, 10) {
        for index in range(0, 50) {
            calc_six_rotations(piece as i8, index as i8);
            flip_piece(piece);
            calc_six_rotations(piece as i8, index as i8);
      }
   }
}

/* Calculate all 32 possible states for a 5-bit row and all rows that will
 * create islands that follow any of the 32 possible rows.  These pre-
 * calculated 5-bit rows will be used to find islands in a partially solved
 * board in the solve function.
 */
static ROW_MASK    = 0x1F;
static TRIPLE_MASK = 0x7FFF;
static mut bad_even_rows:   [[bool*32]*32];
static mut bad_odd_rows:    [[bool*32]*32];
static mut bad_even_triple: [bool*32768];
static mut bad_odd_triple:  [bool*32768];

fn rows_bad(row1: int, row2: int, even: bool) -> bool {
    /* even is referring to row1 */
    let mut row2_shift: int;
    /* Test for blockages at same index and shifted index */
    if even  {
        row2_shift = ((row2 << 1) & ROW_MASK) | 0x01;
    } else {
        row2_shift = (row2 >> 1) | 0x10;
    }
    let block = ((row1 ^ row2) & row2) & ((row1 ^ row2_shift) & row2_shift);
    /* Test for groups of 0's */
    let mut in_zeroes = false;
    let mut group_okay = false;
    for i in range(0, 5) {
        if (row1 & (1 << i)) != 0 {
            if in_zeroes {
                if !group_okay  {
                return(true)
                }
                in_zeroes = false;
                group_okay = false;
            }
        } else {
            if !in_zeroes  {
                in_zeroes = true;
            }
            if (block & (1 << i)) == 0 {
                group_okay = true;
            }
        }
    }
    if in_zeroes {
        !group_okay
    } else {
        false
    }
}

/* Check for cases where three rows checked sequentially cause a false
 * positive.  One scenario is when 5 cells may be surrounded where piece 5
 * or 7 can fit.  The other scenario is when piece 2 creates a hook shape.
 */
fn triple_is_okay(row1: int, row2: int, row3: int, even: bool) -> bool {
   if(even) {
      /* There are four cases:
       * row1: 00011  00001  11001  10101
       * row2: 01011  00101  10001  10001
       * row3: 011??  00110  ?????  ?????
       */
      ((row1 == 0x03) && (row2 == 0x0B) && ((row3 & 0x1C) == 0x0C)) 
          || ((row1 == 0x01) && (row2 == 0x05) && (row3 == 0x06)) 
          || ((row1 == 0x19) && (row2 == 0x11)) 
          || ((row1 == 0x15) && (row2 == 0x11))
   } else {
      /* There are two cases:
       * row1: 10011  10101
       * row2: 10001  10001
       * row3: ?????  ?????
       */
      ((row1 == 0x13) && (row2 == 0x11)) 
          || ((row1 == 0x15) && (row2 == 0x11))
   }
}


fn calc_rows() -> () {
   for row1 in range(0, 32) {
      for row2 in range(0, 32) {
         bad_even_rows(row1)(row2) = rows_bad(row1, row2, true);
         bad_odd_rows(row1)(row2) = rows_bad(row1, row2, false);
      }
   }
   for row1 in range(0, 32) {
      for row2 in range(0, 32) {
         for row3 in range(0, 32) {
            let mut result1 = bad_even_rows(row1)(row2);
            let mut result2 = bad_odd_rows(row2)(row3);
            if !result1 && result2 && triple_is_okay(row1, row2, row3, true) {
               bad_even_triple(row1+(row2*32)+(row3*1024)) = false;
            } else {
               bad_even_triple(row1+(row2*32)+(row3*1024)) = result1 || result2;
            }

            result1 = bad_odd_rows(row1)(row2);
            result2 = bad_even_rows(row2)(row3);
            if(!result1 && result2 && triple_is_okay(row1, row2, row3, false)) {
               bad_odd_triple(row1+(row2*32)+(row3*1024)) = false;
            } else {
               bad_odd_triple(row1+(row2*32)+(row3*1024)) = result1 || result2;
            }
         }
      }
   }
}



/* Calculate islands while solving the board.
 */
fn boardHasIslands(cell: i8) -> bool {
   /* Too low on board, don't bother checking */
   if(cell >= 40_i8) {
      return(false)
   }
   let current_triple = ((board >> (((cell as int / 5) * 5) as u64)) & TRIPLE_MASK as u64) as int;
   if ((cell / 5_i8) % 2_i8) != 0_i8 {
      bad_odd_triple(current_triple)
   } else {
      bad_even_triple(current_triple)
   }
}


/* The recursive solve algorithm.  Try to place each permutation in the upper-
 * leftmost empty cell.  Mark off available pieces as it goes along.
 * Because the board is a bit mask, the piece number and bit mask must be saved
 * at each successful piece placement.  This data is used to create a 50 char
 * array if a solution is found.
 */
static mut avail: i16 = 0x03FFi16;
static mut sol_nums: [i8*10];
static mut sol_masks: [u64*10];
static mut solutions: [[i8*50]*2100];
static mut solution_count = 0;
static mut max_solutions = 2098;

fn record_solution() -> () {
   for sol_no in range(0, 10) {
      let mut sol_mask = sol_masks(sol_no);
      for index in range(0, 50) {
         if (sol_mask & 1_u64) != 0_u64 {
            solutions(solution_count)(index) = sol_nums(sol_no);
            /* Board rotated 180 degrees is a solution too! */
            solutions(solution_count+1)(49-index) = sol_nums(sol_no);
         }
         sol_mask = sol_mask >> 1_u64;
      }
   }
   solution_count += 2;
}

fn solve(depth: int, mut cell: int) -> () {
   if solution_count >= max_solutions {
      return()
   }

   while (board & (1_u64 << (cell as u64))) != 0_u64 {
      cell++;
   }

   for piece in range(0, 10) {
      let piece_no_mask = (1 << piece) as i16;
      if (avail & piece_no_mask) == 0_i16 {
         continue()
      }
      
      avail ^= piece_no_mask;
      let max_rots = piece_counts(piece)(cell);
      let piece_mask = &pieces(piece)(cell);
      for rotation in range(0, max_rots) {
         if (board & piece_mask(rotation as i8)) == 0_u64 {
            sol_nums(depth) = piece as i8;
            sol_masks(depth) = piece_mask(rotation);
            if depth == 9 {
               /* Solution found!!!!!11!!ONE! */
               record_solution();
               avail ^= piece_no_mask;
               return()
            }
            board |= piece_mask(rotation);
            if !boardHasIslands(next_cell(piece)(cell)(rotation)) {
               solve(depth + 1, next_cell(piece)(cell)(rotation) as int);
            }
            board ^= piece_mask(rotation);
         }
      }
      avail ^= piece_no_mask;
   }
}

/* qsort comparator - used to find first and last solutions */
fn compare_solutions(elem1: &[i8], elem2: &[i8]) -> i8 {
   let mut i = 0;
   while i < 50 && elem1(i) == elem2(i) {
      i++;
   }

   elem1(i) - elem2(i)
}

// searching is linear time, qsort n*log(n)
fn find_minmax(mut ary: &[[i8*50]], size: int) -> (&[i8], &[i8]) {
   let mut min = &ary(0);
   let mut max = &ary(0);
   for i in range(1, size) {
      let sol = &ary(i);
      if compare_solutions(min, sol) > 0_i8 {
         min = sol;
      } else if compare_solutions(max, sol) < 0_i8 {
         max = sol;
      }
   }
   (min, max)
}

/* pretty print a board in the specified hexagonal format */
fn pretty(b: &[i8]) -> () {
    for i in range_step(0, 50, 10) {
      print_meteor_lines(b(i), b(i+1), b(i+2), b(i+3), b(i+4), b(i+5), b(i+6), b(i+7), b(i+8), b(i+9));
    }
    println("");
}

fn main(n: int) -> () {
    max_solutions = n;
    calc_pieces();
    calc_rows();
    solve(0, 0);
    print_meteor_scnt(solution_count);
    let minmax = find_minmax(&solutions, solution_count);
    pretty(minmax(0));
    pretty(minmax(1));
}