meteor

# The Computer Language Benchmarks Game
# http://shootout.alioth.debian.org/
#
# contributed by Olof Kraigher
# modified by Tupteq

const  global  False  =  0;
const  global  True  =  1;

global  width  =  5;
global  height  =  10

global  rotate  =  {  'E'=>'NE',  'NE'=>'NW',  'NW'=>'W',  'W'=>'SW',  'SW'=>'SE',  'SE'=>'E'};
global  flip  =  {  'E'=>'W',  'NE'=>'NW',  'NW'=>'NE',  'W'=>'E',  'SW'=>'SE',  'SE'=>'SW'  };

global  move  =  {  'E'=>routine(  x=0,  y=0  ){  return  (x+1,  y)  },
                        'W'=>routine(  x=0,  y=0  ){  return  (x-1,  y)  },
                        'NE'=>routine(  x=0,  y=0  ){  return  (x  +  (y%2),  y-1)  },
                        'NW'=>routine(  x=0,  y=0  ){  return  (x  +  (y%2)  -  1,  y-1)  },
                        'SE'=>routine(  x=0,  y=0  ){  return  (x  +  (y%2),  y+1)  },
                        'SW'=>routine(  x=0,  y=0  ){  return  (x  +  (y%2)  -  1,  y+1)  }  };

global  move2  =  move.value();

global  solutions  =  {};
global  masks  =  {  0  :  0  :  10  };

global  valid  =  routine(  x=0,  y=0  )
{  return  0  <=  x  &&  x  <  width  and  0  <=  y  &&  y  <  height  }

stdio.println(  move,  move['E'](  1,  2  ),  stdlib.about(  move  )  );

global  zerocount  =  routine(  mask=0  )
{
     sum  =  0;
     for(  i  =  0  :  49  )  sum  +=  ((1<)  &  mask)  ==0;
     return  sum;
}
#stdio.println( zerocount(10303) );
routine  findFreeCell(  board=0  )
{
     for(  i  =  0  :  height  *  width  -1  )
          if(  board  &  (1<)  ==0  )  return  i  %  width,  i  /  width;
     return  0,  0;
}
routine  floodFill(  board=0,  xy=(0,0)  )
{
     x  =  xy[0];    y  =  xy[1];
     if(  0  <=  x  &&  x  <  width  and  0  <=  y  &&  y  <  height  and  board  &  (1  <<  (x  +  width*y))  ==  0  ){
          board  |=  1  <<  (x  +  width*y);
          for(  f  in  move2  )  board  |=  floodFill(board,  f(x,  y));
     }
     return  board;
}
#stdio.println( floodFill(10303) );

routine  noIslands(  mask=0  )
{
        zeroes  =  zerocount(mask);
        if(  zeroes  <  5  )  return  False;

        while(  mask  !=  0x3FFFFFFFFFFFF  ){
                mask  =  floodFill(mask,  findFreeCell(mask));
                new_zeroes  =  zerocount(mask);
                if(  zeroes  -  new_zeroes  <  5  )  return  False;
                zeroes  =  new_zeroes;
       }
        return  True
}
#stdio.println( noIslands(10303) );

routine  getBitmask(x=0,  y=0,  piece={''})
{
        mask  =  1  <<  (x  +  width*y);

        for(  cell  in  piece  ){
                (x,  y)  =  move[cell](x,  y);
                if(  0  <=  x  &&  x  <  width  and  0  <=  y  &&  y  <  height  )
                        mask  =  mask  |  (1  <<  (x  +  width*y))
                else
                        return  False,  0
       }
        return  True,  mask
}
#stdio.println( getBitmask(0,1,{'E'}) );

routine  allBitmasks(piece:list<string>,  color=0)
{
     isValid,  mask  :  int  =  0;
     bitmasks  :  list<int>  =  {};
     for(  orientations  =  0  :  1  ){
          for(  rotations  =  0  :  (5  -  3*(color  ==  4))  ){
               for(  y  =  0  :  height-1  ){
                    for(  x  =  0  :  width-1  ){
                         (  isValid,  mask  )  =  getBitmask(x,  y,  piece);
                         #stdio.println( isValid, mask, x, y, piece );
                         if(  isValid  and  noIslands(mask)  )  bitmasks.append(mask);
                    }
               }
               for(  i  =  0  :  piece.size()-1  )  piece[i]  =  rotate[piece[i]];
          }
          for(  i  =  0  :  piece.size()-1  )  piece[i]  =  flip[piece[i]];
     }
     return  bitmasks
}
#stdio.println( allBitmasks({'E'},1) );

global  masksAtCell  :  list<list<list<int>  >  >  =  {};
for(  i  =  0  :  width*height-1  ){
     ls  :  list<list<int>  >  =  {};
     for(  j  =  0  :  9  )  ls.append(  {}  );
     masksAtCell.append(  ls  );
}
#stdio.println( masksAtCell );

routine  generateBitmasks()
{
        pieces  =  {{"E",  "E",  "E",  "SE"},  {"SE",  "SW",  "W",  "SW"},
                {"W",  "W",  "SW",  "SE"},  {"E",    "E",  "SW",  "SE"},
                {"NW",  "W",  "NW",  "SE",  "SW"},  {"E",    "E",  "NE",  "W"},
                {"NW",  "NE",  "NE",  "W"},  {"NE",  "SE",  "E",  "NE"},
                {"SE",  "SE",  "E",  "SE"},  {"E",  "NW",  "NW",  "NW"}};

        color  =  0;
       for(  piece  in  pieces  ){
            local  masks  =  allBitmasks(piece,  color);
            masks.sort(@{@0<@1});
            cellMask  =  1  <<  (width*height  -  1);
            cellCounter  =  width*height  -  1;
            j  =  masks.size()  -  1;

            while  (j  >=  0){
                 if(  (masks[j]  &  cellMask)  ==  cellMask  ){
                      masksAtCell[cellCounter][color].append(masks[j]);
                      j  =  j-1;
                 }else{
                      cellMask  =  cellMask  >>  1;
                      cellCounter  -=  1;
                 }
            }
            color  +=  1;
       }
}

#generateBitmasks();
#stdio.println( masksAtCell );

global  to_go  =  0;

routine  solveCell(cell=0,  board=0)
{
     if(  to_go  <=  0  ){
# Got enough solutions
          return;
     }elif(  board  ==  0x3FFFFFFFFFFFF  ){
# Solved
          addSolutions();
     }elif(  board  &  (1  <<  cell)  !=  0  ){
# Cell full
          solveCell(cell-1,  board);
     }elif(  cell  <  0  ){
# Out of board
          return;
     }else{
          for(  color  =  0  :  9  ){
               if(  masks[color]  ==  0  ){
                    for(  mask  in  masksAtCell[cell][color]  ){
                         if(  mask  &  board  ==  0  ){
                              masks[color]  =  mask;
                              solveCell(cell-1,  board  |  mask);
                              masks[color]  =  0;
                         }
                    }
               }
          }
     }
}


routine  addSolutions()
{
     s  =  '';
     mask  =  1;
     for(  y  =  0  :  height-1  ){
          for(  x  =  0  :  width-1  ){
               for(  color  =  0  :  9  ){
                    if(  (masks[color]  &  mask)  !=  0  ){
                         s  +=  (string)  color;
                         break;
                    }elif(  color  ==  9  ){
                         s  +=  '.';
                    }
               }
               #mask <<= 1;
               mask  =  mask  <<  1;
          }
     }
# Inverse
     ns  =  '';
     for(  y  =  0  :  height-1  )
          for(  x  =  0  :  width-1  )
               ns  +=  s[  (width  -  x  -  1  +  (width  -  y  -  1)  *  width  +  50)  %  50  ];

# Finally append
     solutions.append(s);
     solutions.append(ns);
     to_go  -=  2;
}

routine  printSolution(solution)
{
     for(  y  =  0  :  height-1  ){
          for(  x  =  0  :  width-1  ){
               i  =  x  +  y*width;
               stdio.print(  solution[i:i],  ' '  );
          }
          stdio.println();
          if(  y  %  2  ==  0  )  stdio.print(  ' '  );
     }
     stdio.println();
}

routine  main(  n  =  1  )
{
     to_go  =  n;
     generateBitmasks();
     stdio.println(  'masks',  masks  );
     solveCell(width*height  -  1,  0);
     stdio.printf(  "%d solutions found\n",  solutions.size()  );
     printSolution(  solutions.min()  );
     printSolution(  solutions.max()  );
}