Skip to content

Instantly share code, notes, and snippets.

@dheerajrav
Last active December 18, 2015 07:39
Show Gist options
  • Save dheerajrav/5748717 to your computer and use it in GitHub Desktop.
Save dheerajrav/5748717 to your computer and use it in GitHub Desktop.
#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<algorithm>
#define INRANGE(i, a, b) (i >= a && i < b)
using namespace std;
class SlidingBlock
{
public:
vector < int > disc;
int n;
int cost;
int empty_slot;
vector< string > record_move;
SlidingBlock();
SlidingBlock( int );
SlidingBlock( vector < int >, vector < string > );
vector < string > getMove();
void makeMove( const string move = string() );
bool solved();
vector < SlidingBlock > branches();
void setCost();
void print();
void readBlock();
bool operator< ( const SlidingBlock& ) const;
bool operator> ( const SlidingBlock& ) const;
};
SlidingBlock::SlidingBlock()
{
SlidingBlock( 3 );
}
SlidingBlock::SlidingBlock( int size )
{
n = size;
}
void SlidingBlock::readBlock()
{
int temp;
for( int i = 0; i < n; i++ )
{
for( int j = 0; j < n; j++ )
{
cin >> temp;
disc.push_back( temp );
}
}
int pos = std::abs( std::distance( find( disc.begin(), disc.end(), 0 ), disc.begin()) );
empty_slot = pos;
setCost();
}
SlidingBlock::SlidingBlock( vector < int > node, vector < string > moves )
{
disc.clear();
n = ( int )sqrt( node.size() );
for( int i = 0; i < ( int )node.size(); ++i )
{
disc.push_back( node[ i ] );
if( node[ i ] == 0 )
empty_slot = i;
}
for( int i = 0; i < moves.size(); i++ )
record_move.push_back( moves[ i ] );
setCost();
}
void SlidingBlock::setCost()
{
int h1 = 0 , h2 = 0;
//setting heuristic 1 => number of misplaced blocks
//setting heuristic 2 => distance of the node to its block
for( int i = 0; i < n; i++ )
{
for( int j = 0; j < n; j++ )
{
int val = disc[ n * i + j ];
if( val != n * i + j && val != 0 )
{
h1 += 1;
int exp_pos_x = ( val ) / n;
int exp_pos_y = ( val ) % n;
h2 += abs( i - exp_pos_x ) + abs( j - exp_pos_y );
}
}
}
cost = max( h1, h2) + this->record_move.size();
}
vector < string > SlidingBlock::getMove()
{
vector < string > movements;
if( empty_slot/n > 0 )
movements.push_back( "UP" );
if( empty_slot%n > 0 )
movements.push_back( "LEFT" );
if( empty_slot/n < n - 1 )
movements.push_back( "DOWN" );
if( empty_slot%n < n - 1 )
movements.push_back( "RIGHT" );
return movements;
}
void SlidingBlock::makeMove( string move )
{
if( move.empty() )
{
vector < string > moves = getMove();
int rand_point_index = rand() % moves.size();
makeMove( moves[ rand_point_index ] );
}
else
{
record_move.push_back( move );
int temp = empty_slot;
if( move.compare("UP") == 0 )
empty_slot -= n;
if( move.compare("DOWN") == 0 )
empty_slot += n;
if( move.compare("LEFT") == 0 )
empty_slot -= 1;
if( move.compare("RIGHT") == 0 )
empty_slot += 1;
swap( disc[ temp ], disc[ empty_slot ] );
}
setCost();
}
bool SlidingBlock::solved()
{
bool answer = true;
for( int i = 0; i < n; i++ )
{
for( int j = 0; j < n; j++ )
{
answer &= disc[ n * i + j ] == ( n * i + j );
}
}
return answer;
}
vector < SlidingBlock > SlidingBlock::branches()
{
vector < string > moves = getMove();
vector < SlidingBlock > valid_branches;
for( int i = 0; i < ( int )moves.size(); ++i )
{
valid_branches.push_back( SlidingBlock( disc , record_move ) );
valid_branches[ i ].makeMove( moves[ i ] );
}
return valid_branches;
}
void SlidingBlock::print()
{
for( int i = 0; i < n; i++ )
{
for( int j = 0; j < n; j++ )
{
cout << disc[ n*i + j ] << " ";
}
cout << endl;
}
}
bool SlidingBlock::operator< ( const SlidingBlock& node ) const
{
for( int i = 0; i < ( int )node.disc.size(); i++ )
{
if( node.disc[ i ] < this->disc[ i ] )
{
return true;
}
else if( node.disc[ i ] > this->disc[ i ] )
{
return false;
}
else
{
continue;
}
}
return false;
}
bool SlidingBlock::operator> ( const SlidingBlock& node ) const
{
for( int i = 0; i < ( int )node.disc.size(); i++ )
{
if( node.disc[ i ] > this->disc[ i ] )
{
return true;
}
else if( node.disc[ i ] < this->disc[ i ] )
{
return false;
}
else
{
continue;
}
}
return false;
}
struct OrderByCost
{
bool operator() ( const SlidingBlock &a, const SlidingBlock &b ) const
{
return a.cost >= b.cost;
}
};
class Search
{
public:
SlidingBlock start;
priority_queue< SlidingBlock, vector < SlidingBlock >, OrderByCost > pq;
set< SlidingBlock > explored;
vector < SlidingBlock > expanded;
Search( int n )
{
start = SlidingBlock( n );
start.readBlock();
searchAndPrint();
}
void searchAndPrint()
{
pushNode( start );
SlidingBlock node = SlidingBlock( start.disc, start.record_move );
setExplored( node );
while( !node.solved() )
{
node = getNextNode();
expanded.push_back( node );
vector < SlidingBlock > valid_branches = node.branches();
//Iterate over neighbors
for( int i = 0; i < ( int ) valid_branches.size(); i++ )
{
if( !isExplored( valid_branches[ i ] ) )
{
pushNode( valid_branches[ i ] );
setExplored( node );
}
}
}
cout << node.record_move.size() << endl;
for( auto i = node.record_move.begin(); i != node.record_move.end(); ++i )
cout << *i << endl;
}
void pushNode( SlidingBlock node )
{
pq.push( node );
}
void setExplored( SlidingBlock node )
{
explored.insert( node );
}
bool isExplored( SlidingBlock node )
{
return explored.count( node ) > 0;
}
SlidingBlock getNextNode()
{
SlidingBlock node = pq.top();
pq.pop();
return node;
}
};
int main()
{
set< SlidingBlock > explored;
int n;
cin >> n;
Search *game = new Search( n );
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment