WaterJugs Class Reference

the water jugs problem, with up to 4 jugs of at most 65535 units More...

#include <PBeFS/astar/WaterJugs.h>

Public Types
using	state_type = std::uint64_t
	the packed levels
using	cost_type = int
	the cost type

Public Member Functions
	WaterJugs (std::vector< int > capacity, int goal)
	constructor of the jugs of the given capacities, the goal being a jug holding goal units
std::size_t	jugs (void) const noexcept
	the number of jugs
std::uint64_t	initial_state (void) const noexcept
bool	is_goal (std::uint64_t s) const noexcept
std::uint64_t	hash (std::uint64_t s) const noexcept
int	heuristic (std::uint64_t s) const noexcept
template<class F>
void	for_each_successor (std::uint64_t s, int, F &&f) const
	calls f( t , 1 , h( t ) ) for each fill, empty and pour that changes s
std::size_t	num_features (void) const noexcept
	the number of features: one per jug and level
template<class F>
void	for_each_feature (std::uint64_t s, F &&f) const
	calls f( i ) for the feature i of the level of each jug
std::uint64_t	perfect_hash (std::uint64_t s) const noexcept
	the perfect hash: the packed state

Static Public Member Functions
static int	level (std::uint64_t s, std::size_t j) noexcept
	the level of the jug j in the state s

Detailed Description

the water jugs problem, with up to 4 jugs of at most 65535 units

The jugs are empty at the start, and each move fills a jug from the faucet, empties it on the ground, or pours it into another jug until either the first is empty or the second is full; the goal is a jug holding exactly the given level. Every move costs 1, and the heuristic is 0 at a goal and 1 elsewhere, which is consistent. A state packs the level of the jug \( j \) in the bits \( 16 j , \ldots , 16 j + 15 \), and the word is also its perfect hash.

The features of Zobrist hashing are "the jug j holds l units", one for each jug and each level from 0 to its capacity.

Member Typedef Documentation

cost_type

using cost_type = int

the cost type

state_type

using state_type = std::uint64_t

the packed levels

Constructor & Destructor Documentation

WaterJugs()

WaterJugs ( std::vector< int > capacity, int goal )

inline

constructor of the jugs of the given capacities, the goal being a jug holding goal units

Member Function Documentation

for_each_feature()

template<class F>

void for_each_feature ( std::uint64_t s, F && f ) const

inline

calls f( i ) for the feature i of the level of each jug

for_each_successor()

template<class F>

void for_each_successor ( std::uint64_t s, int , F && f ) const

inline

calls f( t , 1 , h( t ) ) for each fill, empty and pour that changes s

hash()

std::uint64_t hash ( std::uint64_t s ) const

inlinenodiscardnoexcept

heuristic()

int heuristic ( std::uint64_t s ) const

inlinenodiscardnoexcept

initial_state()

std::uint64_t initial_state ( void ) const

inlinenodiscardnoexcept

is_goal()

bool is_goal ( std::uint64_t s ) const

inlinenodiscardnoexcept

jugs()

std::size_t jugs ( void ) const

inlinenodiscardnoexcept

the number of jugs

level()

int level ( std::uint64_t s, std::size_t j )

inlinestaticnodiscardnoexcept

the level of the jug j in the state s

num_features()

std::size_t num_features ( void ) const

inlinenodiscardnoexcept

the number of features: one per jug and level

perfect_hash()

std::uint64_t perfect_hash ( std::uint64_t s ) const

inlinenodiscardnoexcept

the perfect hash: the packed state

---

The documentation for this class was generated from the following file:

• PBeFS/astar/WaterJugs.h