MissionariesCannibals.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*---------------------- File MissionariesCannibals.h ----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_MissionariesCannibals
 #define __PBeFS_MissionariesCannibals
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <algorithm>
 
#include <cstddef>
 
#include <cstdint>
 
#include <stdexcept>
 
#include "PBeFS/astar/Domain.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*---------------------- CLASS MissionariesCannibals -----------------------*/
/*--------------------------------------------------------------------------*/

 
class MissionariesCannibals {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/
 
 using state_type = std::uint64_t;               
 using cost_type = int;                          
 
/*------------------------------ CONSTRUCTOR -------------------------------*/

 
 MissionariesCannibals( int m , int c , int b )
  : f_m( m ) , f_c( c ) , f_b( b ) {
  if( ( m < 0 ) || ( c < 0 ) || ( m > 65535 ) || ( c > 65535 ) ||
      ( b < 1 ) )
   throw( std::invalid_argument( "MissionariesCannibals::"
                                 "MissionariesCannibals: bad sizes" ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] static int missionaries( std::uint64_t s ) noexcept {
  return( int( s & 0xFFFF ) );
  }

 
 [[nodiscard]] static int cannibals( std::uint64_t s ) noexcept {
  return( int( ( s >> 16 ) & 0xFFFF ) );
  }

 
 [[nodiscard]] static bool boat_left( std::uint64_t s ) noexcept {
  return( ( ( s >> 32 ) & 1 ) == 0 );
  }
 
/*------------------------- METHODS OF THE DOMAIN --------------------------*/
 
 [[nodiscard]] std::uint64_t initial_state( void ) const noexcept {
  return( pack( f_m , f_c , true ) );
  }
 
 [[nodiscard]] bool is_goal( std::uint64_t s ) const noexcept {
  return( ( missionaries( s ) == 0 ) && ( cannibals( s ) == 0 ) );
  }
 
 [[nodiscard]] std::uint64_t hash( std::uint64_t s ) const noexcept {
  return( ADS::splitmix64( s ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] int heuristic( std::uint64_t s ) const noexcept {
  const int n = missionaries( s ) + cannibals( s );
  if( n == 0 )
   return( 0 );
  int h = 1;
  if( n > f_b )
   h = f_b > 1 ? 2 * ( ( n - f_b + ( f_b - 1 ) - 1 ) / ( f_b - 1 ) ) + 1
               : 2 * n - 1;
  return( boat_left( s ) ? h : h + 1 );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 template< class F >
 void for_each_successor( std::uint64_t s , int , F && f ) const {
  const bool left = boat_left( s );
  const int m = missionaries( s ) , c = cannibals( s );
  const int am = left ? m : f_m - m , ac = left ? c : f_c - c;  // aboard
  for( int dm = 0 ; dm <= std::min( am , f_b ) ; ++dm )
   for( int dc = dm ? 0 : 1 ; dc <= std::min( ac , f_b - dm ) ; ++dc ) {
    const int nm = left ? m - dm : m + dm , nc = left ? c - dc : c + dc;
    if( safe( nm , nc ) && safe( f_m - nm , f_c - nc ) ) {
     const std::uint64_t t = pack( nm , nc , ! left );
     f( t , 1 , heuristic( t ) );
     }
    }
  }
 
/*---------------------- FEATURES FOR ZOBRIST HASHING ----------------------*/
 
 [[nodiscard]] std::size_t num_features( void ) const noexcept {
  return( std::size_t( f_m ) + f_c + 4 );
  }

 
 template< class F >
 void for_each_feature( std::uint64_t s , F && f ) const {
  f( std::size_t( missionaries( s ) ) );
  f( std::size_t( f_m ) + 1 + cannibals( s ) );
  f( std::size_t( f_m ) + f_c + ( boat_left( s ) ? 2 : 3 ) );
  }
 
/*------------------------------ OTHER HASHES ------------------------------*/
 
 [[nodiscard]] std::uint64_t perfect_hash( std::uint64_t s ) const noexcept {
  return( s );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:
 
 // the state with m missionaries and c cannibals on the left bank
 static std::uint64_t pack( int m , int c , bool left ) noexcept {
  return( std::uint64_t( m ) | ( std::uint64_t( c ) << 16 ) |
          ( std::uint64_t( left ? 0 : 1 ) << 32 ) );
  }
 
 // true if m missionaries and c cannibals on a bank are safe
 static bool safe( int m , int c ) noexcept {
  return( ( m == 0 ) || ( m >= c ) );
  }
 
 int f_m;                                        
 int f_c;                                        
 int f_b;                                        
 
 };  // end( class( MissionariesCannibals ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_MissionariesCannibals */
 
/*--------------------------------------------------------------------------*/
/*-------------------- End File MissionariesCannibals.h --------------------*/
/*--------------------------------------------------------------------------*/