SequenceScore.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*-------------------------- File SequenceScore.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_SequenceScore
 #define __PBeFS_SequenceScore
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <cstdlib>
 
#include "PBeFS/astar/SlidingTile.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS SequenceScore ---------------------------*/
/*--------------------------------------------------------------------------*/

 
template< int W , int H >
class SequenceScore {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
 using Base = SlidingTile< W , H >;                  
 using state_type = typename Base::state_type;       
 using cost_type = typename Base::cost_type;         
 using board_type = typename Base::board_type;       
 
 static constexpr int cells = Base::cells;           

 
 explicit SequenceScore( const board_type & start ,
                         const board_type & goal = Base::korf_goal() )
  : f_base( start , goal ) , v_goal( goal ) {
  for( int c = 0 ; c < cells ; ++c )
   v_goal_cell[ goal[ c ] ] = c;
  if constexpr( ( W == 3 ) && ( H == 3 ) ) {
   const int ring[ 8 ] = { 0 , 1 , 2 , 5 , 8 , 7 , 6 , 3 };
   for( int k = 0 ; k < 8 ; ++k )
    v_next[ ring[ k ] ] = ring[ ( k + 1 ) % 8 ];
   v_next[ 4 ] = -1;
   }
  else {
   for( int c = 0 ; c < cells - 1 ; ++c )
    v_next[ c ] = c + 1;
   v_next[ cells - 1 ] = -1;
   }
  // the tile that follows t: the next of its goal cell, wrapping around to
  // the first tile of the sequence after the last one
  for( int t = 1 ; t < cells ; ++t ) {
   const int c = v_goal_cell[ t ];
   int n = v_next[ c ];
   if( n < 0 )
    n = ( W == 3 ) && ( H == 3 ) ? 0 : 1;
   v_follower[ t ] = goal[ n ];
   }
  }
 
 [[nodiscard]] state_type initial_state( void ) const noexcept {
  return( f_base.initial_state() );
  }
 
 [[nodiscard]] bool is_goal( state_type s ) const noexcept {
  return( f_base.is_goal( s ) );
  }
 
 [[nodiscard]] std::uint64_t hash( state_type s ) const noexcept {
  return( f_base.hash( s ) );
  }

 
 [[nodiscard]] cost_type heuristic( state_type s ) const noexcept {
  const int centre = ( W == 3 ) && ( H == 3 ) ? 4 : 0;
  int m = 0 , sc = Base::tile( s , centre ) != v_goal[ centre ] ? 1 : 0;
  for( int c = 0 ; c < cells ; ++c ) {
   const int t = Base::tile( s , c );
   if( t == 0 )
    continue;
   const int g = v_goal_cell[ t ];
   m += std::abs( g % W - c % W ) + std::abs( g / W - c / W );
   if( ( v_next[ c ] >= 0 ) &&
       ( Base::tile( s , v_next[ c ] ) != v_follower[ t ] ) )
    sc += 2;
   }
  return( m + W * sc );
  }
 
 template< class F >
 void for_each_successor( state_type s , cost_type , F && f ) const {
  f_base.for_each_successor( s , 0 , [ & ]( state_type t , cost_type c ,
                                            cost_type ) {
   f( t , c , heuristic( t ) );
   } );
  }

 [[nodiscard]] const Base & base( void ) const noexcept { return( f_base ); }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:
 
 Base f_base;                                    
 board_type v_goal;                              
 int v_goal_cell[ cells ] = {};                  
 int v_next[ cells ] = {};       
 int v_follower[ cells ] = {};          
 
 };  // end( class( SequenceScore ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_SequenceScore */
 
/*--------------------------------------------------------------------------*/
/*------------------------ End File SequenceScore.h ------------------------*/
/*--------------------------------------------------------------------------*/