Kevin Shepherd's solution:
#include <iostream>
#include <map>
#include <set>
#include <fstream>
#include <string>
#include <list>
#include <unistd.h>
#include <dirent.h>
#define MAX_CELL_DIM 0xFF
#define MAX_TARGET_COUNT 123
#define MAX_X_DIM 2048
#define MAX_Y_DIM 2048
#define POS_X_MASK 0x001FFFFF
#define POS_X_BITS 0x7FF
#define POS_X_ROLL 21
#define POS_Y_MASK 0xFFE003FF
#define POS_Y_BITS 0x7FF
#define POS_Y_ROLL 10
#define VEL_X_MASK 0xFFFFFC1F
#define VEL_X_BITS 0xF
#define VEL_X_SIGN 0x200
#define VEL_X_ROLL 5
#define VEL_Y_MASK 0xFFFFFFE0
#define VEL_Y_BITS 0xF
#define VEL_Y_SIGN 0x10
#define VEL_Y_ROLL 0
#define VEL_MASK 0x000001EF
#define CELL_CLEAR 0
#define CELL_WALL 1
#define CELL_UNREACHABLE 2
#define CELL_START 3
#define CELL_TARGET 4
/*
random.txt
Cells: 100x75
Open Cell Count: 3418
Map size: 1000x750
Target count 1
big.txt
Cells: 173x173
Open Cell Count: 14854
Map size: 1730x1730
Target count 1
random2.txt
Cells: 100x75
Open Cell Count: 3418
Map size: 1000x750
Target count 25
big2.txt
Cells: 173x173
Open Cell Count: 14854
Map size: 1730x1730
Target count 38
*/
bool _opt_fuel = false;
struct CellCoord
{
unsigned char x, y;
bool operator<(const CellCoord & __other) const
{
return (x < __other.x?true:(x > __other.x?false:y < __other.y));
}
bool operator==(const CellCoord & __other) const
{
return (x == __other.x && y == __other.y);
}
};
class State
{
public:
State()
:packed(0)
{}
State(const State & __other)
:packed(__other.packed)
{}
State & operator=(const State & __other)
{
packed = __other.packed;
}
bool operator<(const State & __other) const
{
return packed<__other.packed;
}
bool operator==(const State & __other) const
{
return (packed == __other.packed);
}
void set_packed(unsigned long __packed)
{
packed = __packed;
}
short get_x() const
{
return (short)((packed >> POS_X_ROLL) & POS_X_BITS);
}
void set_x(short __x)
{
packed &= POS_X_MASK;
packed |= ((unsigned long)__x << POS_X_ROLL);
}
short get_y() const
{
return (short)((packed >> POS_Y_ROLL) & POS_Y_BITS);
}
void set_y(short __y)
{
packed &= POS_Y_MASK;
packed |= ((unsigned long)__y << POS_Y_ROLL);
}
short get_vel_x() const
{
return (packed & VEL_X_SIGN)?-(short)((packed >> VEL_X_ROLL) & VEL_X_BITS):+(short)((packed >> VEL_X_ROLL) & VEL_X_BITS);
}
void set_vel_x(short __vx)
{
packed &= VEL_X_MASK;
if (__vx < 0)
{
packed |= VEL_X_SIGN;
__vx = - __vx;
}
if (__vx > 10)
__vx = 10;
packed |= ((unsigned long)__vx << VEL_X_ROLL);
}
short get_vel_y() const
{
return (packed & VEL_Y_SIGN)?-(short)((packed >> VEL_Y_ROLL) & VEL_Y_BITS):+(short)((packed >> VEL_Y_ROLL) & VEL_Y_BITS);
}
void set_vel_y(short __vy)
{
packed &= VEL_Y_MASK;
if (__vy < 0)
{
packed |= VEL_Y_SIGN;
__vy = - __vy;
}
if (__vy > 10)
__vy = 10;
packed |= ((unsigned long)__vy << VEL_Y_ROLL);
}
bool has_vel() const
{
return ((packed & VEL_MASK) != 0);
}
unsigned long packed;
};
struct Active
{
State st;
unsigned short primary, secondary;
std::string path;
Active()
{}
Active(const Active & __other)
:st(__other.st), primary(__other.primary), secondary(__other.secondary), path(__other.path)
{}
Active & operator=(const Active & __other)
{
st = __other.st;
primary = __other.primary;
secondary = __other.secondary;
path = __other.path;
}
};
typedef std::list<Active> ActiveList;
typedef std::map<unsigned long, ActiveList::iterator> NewState;
unsigned long * state_array;
ActiveList current_states;
NewState new_states;
unsigned char cell_map[MAX_CELL_DIM+1][MAX_CELL_DIM+1];
unsigned short cell_number[MAX_CELL_DIM+1][MAX_CELL_DIM+1];
unsigned long _cell_width = 0, _cell_height = 0;
unsigned long _pixel_width = 0, _pixel_height = 0;
unsigned long state_count = 0;
unsigned long _solution_count = 0;
unsigned short _min_primary = 0, _min_secondary = 0;
inline unsigned long compress(State _st)
{
unsigned long x = (unsigned long)_st.get_x();
unsigned long y = (unsigned long)_st.get_y();
return (cell_number[x/10][y/10] * 44100)+((x % 10) * 4410)+((y % 10) * 441)+((_st.get_vel_x() + 10) * 21)+(_st.get_vel_y() + 10);
}
inline bool is_set_state(unsigned long _compressed)
{
return ( state_array[_compressed >> 5] & (1 << (_compressed & 0x1F) ) ) != 0;
}
inline void set_state(unsigned long _compressed)
{
state_array[_compressed >> 5] |= (1 << (_compressed & 0x1F) );
}
bool set_state_if(unsigned long _compressed)
{
bool _new_set = false;
unsigned long _offset = _compressed >> 5;
unsigned long _value = 1 << (_compressed & 0x1F);
if ( ( state_array[_offset] & _value ) == 0)
{
state_array[_offset] |= _value;
_new_set = true;
}
return _new_set;
}
void transition (unsigned char __impulse, unsigned char __primary_delta, unsigned char __secondary_delta, const Active & __from);
void add_trans(const Active & _to);
unsigned long report(const ActiveList & current_states, ActiveList::const_iterator __start, unsigned long _iter);
void check_cells(unsigned char x, unsigned char y);
int main(int _argc, char * _argv[])
{
time_t _start_time = time(0);
if (_argc < 2 )
{
std::cerr << "Usage: " << _argv[0] << " [--fuel] <map-name>" << std::endl;
return 1;
}
std::string _map_name, _prefix_name;
if (!strcmp(_argv[1], "--fuel"))
{
_opt_fuel = true;
if (_argc < 3 )
{
std::cerr << "Usage: " << _argv[0] << " [--fuel] <map-name>" << std::endl;
return 1;
}
_map_name.assign(_argv[2]);
_prefix_name.assign(_map_name);
_prefix_name.append("-fuel");
}
else
{
_map_name.assign(_argv[1]);
_prefix_name.assign(_map_name);
_prefix_name.append("-step");
}
_map_name.append(".txt");
if (access(_map_name.c_str(), R_OK))
{
std::cerr << "Could not open file: " << _map_name << std::endl;
std::cerr << "Usage: " << _argv[0] << " [--fuel] <map-name>" << std::endl;
return 1;
}
std::ifstream _in(_map_name.c_str());
_in >> _cell_width;
_in >> _cell_height;
std::cout << "Cells: " << _cell_width << "x" << _cell_height << std::endl;
if (_cell_width == 0 || _cell_width > MAX_CELL_DIM ||
_cell_height == 0 || _cell_height > MAX_CELL_DIM)
{
std::cerr << "Wrong cell dimensions 0 < cell < " << MAX_CELL_DIM << std::endl;
return 1;
}
bool _has_input = false;
{
DIR * _fdir = opendir(".");
if (_fdir)
{
struct dirent _entry, * _result;
while (!readdir_r(_fdir, & _entry, & _result))
{
int _len = strlen(_entry.d_name);
if (_len > _prefix_name.size() && !strncmp( _entry.d_name, _prefix_name.c_str(), _prefix_name.size()))
{
_has_input = true;
_prefix_name.assign(_entry.d_name);
break;
}
}
closedir(_fdir);
}
}
unsigned long _target_count = 0, _active_targets = 0;
Active _initial_state;
_initial_state.primary = 0;
_initial_state.secondary = 0;
CellCoord _cell_pos;
_cell_pos.y = 0;
memset(cell_map, CELL_CLEAR, sizeof(unsigned char [MAX_CELL_DIM+1][MAX_CELL_DIM+1]));
memset(cell_number, 0, sizeof(unsigned short [MAX_CELL_DIM+1][MAX_CELL_DIM+1]));
while (_in.good() && _cell_pos.y < _cell_height)
{
std::string _line;
std::getline(_in, _line);
if (_line.size() >= _cell_width)
{
for (_cell_pos.x = 0; _cell_pos.x < _cell_width; ++ _cell_pos.x)
{
switch (_line[_cell_pos.x])
{
case '#':
cell_map[_cell_pos.x][_cell_pos.y] = CELL_WALL;
break;
case 'O':
cell_map[_cell_pos.x][_cell_pos.y] = CELL_START;
_initial_state.st.set_x(_cell_pos.x * 10);
_initial_state.st.set_y(_cell_pos.y * 10);
break;
case '+':
{
bool _is_active = true;
if (_has_input)
{
char _buf[4];
sprintf(_buf, "-%02d", _target_count);
if (_prefix_name.find(_buf) != std::string::npos)
_is_active = false;
}
if (_is_active)
{
cell_map[_cell_pos.x][_cell_pos.y] = (unsigned char)(_target_count + CELL_TARGET) | 0x80;
++ _active_targets;
}
else
{
cell_map[_cell_pos.x][_cell_pos.y] = CELL_CLEAR | 0x80;
}
++ _target_count;
}
break;
case ' ':
default:
cell_map[_cell_pos.x][_cell_pos.y] = CELL_CLEAR | 0x80;
break;
}
}
++ _cell_pos.y;
}
}
bool _is_final = false;
if (!_active_targets)
{
cell_map[_initial_state.st.get_x() / 10][_initial_state.st.get_y() / 10] = (unsigned char)(_target_count + CELL_TARGET) | 0x80;
++ _active_targets;
++ _target_count;
_is_final = true;
}
_pixel_width = _cell_width * 10;
_pixel_height = _cell_height * 10;
std::cerr << "Map size: " << _pixel_width << "x" << _pixel_height << std::endl;
std::cout << "Active Target count " << _active_targets << std::endl;
// Find unreachable cells
_cell_pos.x = _initial_state.st.get_x() / 10;
_cell_pos.y = _initial_state.st.get_y() / 10;
check_cells(_cell_pos.x, _cell_pos.y);
unsigned short _open_cell_count = 0;
for (_cell_pos.y = 0; _cell_pos.y < _cell_height; ++ _cell_pos.y)
{
for (_cell_pos.x = 0; _cell_pos.x < _cell_width; ++ _cell_pos.x)
{
if ( (cell_map[_cell_pos.x][_cell_pos.y] & 0x80) != 0)
{
if (cell_map[_cell_pos.x][_cell_pos.y] == 0x80)
{
cell_map[_cell_pos.x][_cell_pos.y] = CELL_UNREACHABLE;
}
else
{
std::cerr << "Unreachable target(s)" << std::endl;
return 1;
}
}
if (cell_map[_cell_pos.x][_cell_pos.y] != CELL_WALL && cell_map[_cell_pos.x][_cell_pos.y] != CELL_UNREACHABLE)
{
cell_number[_cell_pos.x][_cell_pos.y] = _open_cell_count;
++ _open_cell_count;
}
}
}
std::cout << "Open Cell Count: " << _open_cell_count << std::endl;
if (_pixel_width > MAX_X_DIM || _pixel_height > MAX_Y_DIM)
{
std::cerr << "Map too large " << _pixel_width << "x" << _pixel_height << " > " << MAX_X_DIM << "x" << MAX_Y_DIM << std::endl;
return 1;
}
_pixel_width -= 9;
_pixel_height -= 9;
if (_target_count > MAX_TARGET_COUNT)
{
std::cerr << "Too many targets " << _target_count << " > " << MAX_TARGET_COUNT << std::endl;
return 1;
}
unsigned long _state_array_size = 1379 * _open_cell_count;
std::cout << "Allocating state array unsigned long[" << _state_array_size << "]" << std::endl;
state_array = new unsigned long[_state_array_size];
if (! state_array)
{
std::cerr << "Insufficient memory for state array unsigned long[" << _state_array_size << "]" << std::endl;
return 1;
}
memset(state_array, 0, sizeof(unsigned long) * _state_array_size);
ActiveList initial_states;
if (_has_input)
{
std::ifstream _input(_prefix_name.c_str());
unsigned long _in_count = 0;
for (;;)
{
Active _from;
short _value;
_input >> _from.primary;
_input >> _from.secondary;
_input >> _value;
_from.st.set_x(_value);
_input >> _value;
_from.st.set_y(_value);
_input >> _value;
_from.st.set_vel_x(_value);
_input >> _value;
_from.st.set_vel_y(_value);
_input >> _from.path;
if (!_input.good())
break;
initial_states.push_front(_from);
++ _in_count;
}
std::cout << "Input " << _in_count << " Active states" << std::endl;
}
else
{
initial_states.push_back(_initial_state);
}
short _iter = initial_states.front().primary;
-- _iter;
current_states.push_back(Active());
ActiveList::iterator _target_end = current_states.end();
-- _target_end;
if (_opt_fuel)
{
current_states.push_back(Active());
ActiveList::iterator _end_2 = current_states.end();
-- _end_2;
current_states.push_back(Active());
ActiveList::iterator _end_1 = current_states.end();
-- _end_1;
do
{
if (!initial_states.empty())
{
ActiveList::iterator _ix = initial_states.begin();
for (ActiveList::iterator _iy = initial_states.end(); _ix != _iy; )
{
if ( (* _ix).primary > _iter + 1 )
{
break;
}
add_trans(* _ix);
++ _ix;
}
initial_states.erase(initial_states.begin(), _ix);
}
ActiveList::iterator _start = _target_end;
++ _start;
ActiveList::iterator _ax = _start;
for (; _ax != _end_2; ++ _ax)
{
transition(3, 2, 1, * _ax);
transition(6, 2, 1, * _ax);
}
current_states.erase(_start, ++ _end_2);
_ax = _target_end;
for (++ _ax; _ax != _end_1; ++ _ax)
{
transition(1, 1, 1, * _ax);
transition(2, 1, 1, * _ax);
transition(4, 1, 1, * _ax);
}
_ax = _end_1;
for (++ _ax; _ax != current_states.end(); ++ _ax)
{
transition(0, 0, 1, * _ax);
}
_end_2 = _end_1;
current_states.push_back(Active());
_end_1 = current_states.end();
-- _end_1;
std::cout << "Adding States ..." << std::endl;
unsigned long _adding_count = 0;
for (NewState::const_iterator _nx = new_states.begin(), _ny = new_states.end(); _nx != _ny; ++ _nx)
{
set_state( (* _nx).first );
++ _adding_count;
}
std::cout << "Added " << _adding_count << " states" << std::endl;
new_states.clear();
++ _iter;
std::cout << '.';
}
while ( (report(current_states, _target_end, _iter) > 2 || !initial_states.empty()) && (!_is_final || (current_states.begin() == _target_end)));
}
else
{ // steps
do
{
current_states.push_back(Active());
ActiveList::iterator _partition = current_states.end();
-- _partition;
if (!initial_states.empty())
{
ActiveList::iterator _ix = initial_states.begin();
for (ActiveList::iterator _iy = initial_states.end(); _ix != _iy; )
{
if ( (* _ix).primary > _iter + 1 )
{
break;
}
add_trans(* _ix);
++ _ix;
}
initial_states.erase(initial_states.begin(), _ix);
}
ActiveList::iterator _start = _target_end;
++ _start;
for (ActiveList::iterator _ax = _start; _ax != _partition; ++ _ax)
{
transition(0, 1, 0, * _ax);
transition(1, 1, 1, * _ax);
transition(2, 1, 1, * _ax);
transition(4, 1, 1, * _ax);
transition(3, 1, 2, * _ax);
transition(6, 1, 2, * _ax);
}
current_states.erase(_start, ++ _partition);
for (NewState::const_iterator _nx = new_states.begin(), _ny = new_states.end(); _nx != _ny; ++ _nx)
{
set_state( (* _nx).first );
}
new_states.clear();
++ _iter;
std::cout << '.';
}
while ((report(current_states, _target_end, _iter) || !initial_states.empty()) && (!_is_final || (current_states.begin() == _target_end)));
}
delete[] state_array;
time_t _time_taken = time(0) - _start_time;
std::ofstream _log("marsrescue.log", std::ios_base::out | std::ios_base::app | std::ios_base::ate);
std::cout << _solution_count << " solutions in " << _time_taken << " seconds, minimum: " << (_opt_fuel?"fuel":"steps") << " = " << _min_primary << " " << (_opt_fuel?"steps":"fuel") << " = " << _min_secondary << std::endl;
_log << _prefix_name << ": " << _solution_count << " solutions in " << _time_taken << " seconds, minimum: " << (_opt_fuel?"fuel":"steps") << " = " << _min_primary << " " << (_opt_fuel?"steps":"fuel") << " = " << _min_secondary << std::endl;
for (ActiveList::iterator _ax = current_states.begin(); _ax != _target_end; ++ _ax)
{ // output targets
if ( (* _ax).primary == _min_primary && (* _ax).secondary == _min_secondary)
{
std::cout << (* _ax).path << std::endl;
_log << (* _ax).path << std::endl;
}
std::string _output_file;
if (_is_final)
_output_file.assign("final-");
_output_file.append(_prefix_name);
short _hit_target = -1;
short _new_x = (* _ax).st.get_x();
short _new_y = (* _ax).st.get_y();
bool _x_two_col = ((_new_x % 10) != 0);
bool _y_two_col = ((_new_y % 10) != 0);
CellCoord _cell_pos;
_cell_pos.x = _new_x / 10;
_cell_pos.y = _new_y / 10;
unsigned char _cell_content = cell_map[_cell_pos.x][_cell_pos.y];
if ( _cell_content >= CELL_TARGET)
{
_hit_target = _cell_content - CELL_TARGET;
}
if (_x_two_col)
{
++ _cell_pos.x;
_cell_content = cell_map[_cell_pos.x][_cell_pos.y];
if ( _cell_content >= CELL_TARGET)
{
_hit_target = _cell_content - CELL_TARGET;
}
if (_y_two_col)
{
++ _cell_pos.y;
_cell_content = cell_map[_cell_pos.x][_cell_pos.y];
if ( _cell_content >= CELL_TARGET)
{
_hit_target = _cell_content - CELL_TARGET;
}
-- _cell_pos.y;
}
-- _cell_pos.x;
}
if (_y_two_col)
{
++ _cell_pos.y;
_cell_content = cell_map[_cell_pos.x][_cell_pos.y];
if ( _cell_content >= CELL_TARGET)
{
_hit_target = _cell_content - CELL_TARGET;
}
-- _cell_pos.y;
}
char _buf[4];
sprintf(_buf, "-%02d", _hit_target);
_output_file.append(_buf);
std::ofstream _out(_output_file.c_str(), std::ios_base::out | std::ios_base::app | std::ios_base::ate);
_out << (* _ax).primary << " " << (* _ax).secondary << " " << (* _ax).st.get_x() << " " << (* _ax).st.get_y() << " " << (* _ax).st.get_vel_x() << " " << (* _ax).st.get_vel_y() << " " << (* _ax).path << std::endl;
}
if (_has_input)
{
std::string _new_name("done-");
_new_name.append(_prefix_name);
unlink(_new_name.c_str());
rename(_prefix_name.c_str(), _new_name.c_str());
}
return 0;
}
void transition (unsigned char __impulse, unsigned char __primary_delta, unsigned char __secondary_delta, const Active & __from)
{
Active _to(__from);
_to.primary += __primary_delta;
_to.secondary += __secondary_delta;
switch (__impulse)
{
case 0:
_to.st.set_vel_y(_to.st.get_vel_y() + 1);
break;
case 1:
_to.st.set_vel_x(_to.st.get_vel_x() - 2);
_to.st.set_vel_y(_to.st.get_vel_y() + 1);
break;
case 2:
_to.st.set_vel_y(_to.st.get_vel_y() - 1);
break;
case 3:
_to.st.set_vel_x(_to.st.get_vel_x() - 2);
_to.st.set_vel_y(_to.st.get_vel_y() - 1);
break;
case 4:
_to.st.set_vel_x(_to.st.get_vel_x() + 2);
_to.st.set_vel_y(_to.st.get_vel_y() + 1);
break;
case 6:
_to.st.set_vel_x(_to.st.get_vel_x() + 2);
_to.st.set_vel_y(_to.st.get_vel_y() - 1);
break;
}
do
{
short _new_x = _to.st.get_x() + _to.st.get_vel_x();
if (_new_x >= 0 && _new_x < _pixel_width)
{
short _new_y = _to.st.get_y() + _to.st.get_vel_y();
if (_new_y >= 0 && _new_y < _pixel_height)
{
CellCoord _cell_pos;
_cell_pos.x = _new_x / 10;
_cell_pos.y = _new_y / 10;
if (cell_map[_cell_pos.x][_cell_pos.y] != CELL_WALL)
{
bool _y_two_col = ((_new_y % 10) != 0);
bool _collision = false;
if ((_new_x % 10) != 0)
{
++ _cell_pos.x;
if (cell_map[_cell_pos.x][_cell_pos.y] == CELL_WALL)
_collision = true;
else
{
if (_y_two_col)
{
if (cell_map[_cell_pos.x][_cell_pos.y+1] == CELL_WALL)
_collision = true;
}
}
-- _cell_pos.x;
}
if (_y_two_col)
{
++ _cell_pos.y;
if (cell_map[_cell_pos.x][_cell_pos.y] == CELL_WALL)
_collision = true;
}
if (!_collision)
break;
}
}
}
_to.st.set_vel_x(_to.st.get_vel_x() / 2);
_to.st.set_vel_y(_to.st.get_vel_y() / 2);
}
while ( _to.st.has_vel() );
short _new_x = _to.st.get_x() + _to.st.get_vel_x();
short _new_y = _to.st.get_y() + _to.st.get_vel_y();
CellCoord _cell_pos;
_cell_pos.x = _new_x / 10;
_cell_pos.y = _new_y / 10;
_to.st.set_x(_new_x);
_to.st.set_y(_new_y);
bool _hit_target = false;
if ( cell_map[_cell_pos.x][_cell_pos.y] >= CELL_TARGET)
_hit_target = true;
else
{
bool _y_two_col = ((_new_y % 10) != 0);
if ((_new_x % 10) != 0)
{
++ _cell_pos.x;
if ( cell_map[_cell_pos.x][_cell_pos.y] >= CELL_TARGET)
_hit_target = true;
else
{
if (_y_two_col)
{
if ( cell_map[_cell_pos.x][_cell_pos.y+1] >= CELL_TARGET)
_hit_target = true;
}
}
-- _cell_pos.x;
}
if (_y_two_col)
{
++ _cell_pos.y;
if ( cell_map[_cell_pos.x][_cell_pos.y] >= CELL_TARGET)
_hit_target = true;
}
}
unsigned long _compressed = compress(_to.st);
if (!is_set_state(_compressed))
{
bool _should_add = true;
NewState::iterator _ns = new_states.find(_compressed);
if (_ns != new_states.end())
{
if ( (* ((* _ns).second) ).secondary > _to.secondary)
{
current_states.erase( (* _ns).second );
-- state_count;
}
else
{
_should_add = false;
}
}
if (_should_add)
{
char _buf[2];
sprintf(_buf, "%d", (int)__impulse);
_to.path.append(_buf);
++ state_count;
ActiveList::iterator _inserted;
if (_hit_target)
{
if (_to.primary < _min_primary || (_to.primary == _min_primary && _to.secondary < _min_secondary) || !_solution_count )
{
_min_primary = _to.primary;
_min_secondary = _to.secondary;
}
++ _solution_count;
current_states.push_front(_to);
_inserted = current_states.begin();
}
else
{
current_states.push_back(_to);
_inserted = current_states.end();
-- _inserted;
}
new_states[_compressed] = _inserted;
}
}
}
/*
if (_hit_target != -1)
{
char _buf[2];
sprintf(_buf, "%d", (int)__impulse);
_to.path.append(_buf);
unsigned long _steps = _to.path.size();
unsigned long _fuel = 0;
for (std::string::size_type _pos = 0; _pos < _steps; ++ _pos)
{
switch (_to.path[_pos])
{
case '3':
case '6':
++ _fuel;
case '1':
case '2':
case '4':
++ _fuel;
default:
break;
}
}
// target found
}
*/
void add_trans(const Active & _to)
{
unsigned long _compressed = compress(_to.st);
if (!is_set_state(_compressed))
{
bool _should_add = true;
NewState::iterator _ns = new_states.find(_compressed);
if (_ns != new_states.end())
{
if ( (* ((* _ns).second) ).secondary > _to.secondary)
{
current_states.erase( (* _ns).second );
-- state_count;
}
else
{
_should_add = false;
}
}
if (_should_add)
{
++ state_count;
ActiveList::iterator _inserted;
current_states.push_back(_to);
_inserted = current_states.end();
-- _inserted;
new_states[_compressed] = _inserted;
}
}
}
unsigned long report(const ActiveList & current_states, ActiveList::const_iterator __start, unsigned long _iter)
{ // report
unsigned char report_map[MAX_CELL_DIM+1][MAX_CELL_DIM+1];
memcpy(report_map, cell_map, sizeof(unsigned char [MAX_CELL_DIM+1][MAX_CELL_DIM+1]));
unsigned long _active_count = 0;
for (ActiveList::const_iterator _ax = ++ __start, _ay = current_states.end(); _ax != _ay; ++ _ax)
{
unsigned char _content = report_map[ (* _ax).st.get_x() / 10 ][ (* _ax).st.get_y() / 10 ];
report_map[ (* _ax).st.get_x() / 10 ][ (* _ax).st.get_y() / 10 ] = 0xFF;
++ _active_count;
}
std::cout << std::endl;
for (unsigned char y = 0; y < _cell_height; ++ y)
{
for (unsigned char x = 0; x < _cell_width; ++ x)
{
unsigned char _content = report_map[ x ][ y ];
switch (_content)
{
case CELL_CLEAR:
std::cout << ' ';
break;
case CELL_WALL:
std::cout << '#';
break;
case CELL_UNREACHABLE:
std::cout << 'X';
break;
case CELL_START:
std::cout << 'O';
break;
case 0xFF:
std::cout << '*';
break;
default:
std::cout << '+';
break;
}
}
std::cout << std::endl;
}
std::cout << "Iteration: " << _iter << " Count: " << _active_count << " State Count: " << state_count << std::endl;
return _active_count;
}
void check_cell(unsigned char x, unsigned char y)
{
if ((cell_map[x][y] & 0x80) != 0)
{
cell_map[x][y] &= 0x7F;
check_cells(x, y);
}
}
void check_cells(unsigned char x, unsigned char y)
{
if (y > 0)
{
if (x > 0)
check_cell(x - 1, y - 1);
check_cell(x, y - 1);
if (x < (_cell_width - 1))
check_cell(x + 1, y - 1);
}
if (x > 0)
check_cell(x - 1, y);
if (x < (_cell_width - 1))
check_cell(x + 1, y);
if (y < (_cell_height - 1))
{
if (x > 0)
check_cell(x - 1, y + 1);
check_cell(x, y + 1);
if (x < (_cell_width - 1))
check_cell(x + 1, y + 1);
}
}
/*
map-step: 18890 solutions in 1112 seconds, minimum: steps = 139 fuel = 85
6444422202022220200000222000222222000000222022222000000000000000000001111101133322222022222222020000000000002222202022222222220222242013100
6444422202022220200000222000222222000000222022222000000000000000000001111101133322222022222222020000000000002222202022222222220222242013010
6444422202022220200000222000222222000000222022222000000000000000000001111101133322222022222222020000000000002222202022222222220222206003110
6444422202022220200000222000222222000000222022222000000000000000000001111101133322222022222222020000000000002222202022222222220222206003101
map-step-00: 3534 solutions in 1015 seconds, minimum: steps = 282 fuel = 169
644442220202222020000022200022222200000022202222200000000000000000000111110113332222202222222202000000000000222220202222222222022220226100044446604010000046222222222222000222222020000000000022220222222222233131313130202000000000000002222222200000020002222222222202000000000000000000
644442220202222020000022200022222200000022202222200000000000000000000111110113332222202222222202000000000000222220202222222222022220226100044446604010000046222222222222000222222020000000000022220222222222233131313130202000000000000002222222200000020002222222222022000000000000000000
random-step: 10567 solutions in 1242 seconds, minimum: steps = 135 fuel = 103
313310000004444440411000026662662022222020000002000001113333321100000000000220222222266664221111302200044444040440000000110446662222000
313310000004444440411000026662662022222020000002000001113333321100000000000220222222266664221111302200044444040440000000110446626222000
313310000004444440411000026662662022222020000002000001113333321100000000000220222222266664221111302200044444004440000000011046666222000
random-step-00: 24 solutions in 3692 seconds, minimum: steps = 271 fuel = 237
3133100000044444404110000266626620222220200000020000011133333211000000000002202222222666642211113022000444440044400000000130466626220033133131022222626663323222266262244644000022000000146666222222220202022220000013333333110000000022000002222222266226662632662244400000000
3133100000044444404110000266626620222220200000020000011133333211000000000002202222222666642211113022000444440044400000000130466626220033133131022222626663323222266262244644000022000000146666222222220202022220000013333333110000000022000002222222266226662632662244040000000
3133100000044444404110000266626620222220200000020000011133333211000000000002202222222666642211113022000444440044400000000130466626220033133131022222626663323222266262244644000022000000146666222222220202022220000013333333110000000022000002222222266226662632662240440000000
3133100000044444404110000266626620222220200000020000011133333211000000000002202222222666642211113022000444440044400000000130466626220033133131022222626663323222266262244644000022000000146666222222220202022220000013333333110000000022000002222222266226662632662204440000000
*/