# Kevin Shepherd's solution:

```/*
Thank you for setting this challenge.  If nothing else, it has given
me an excuse to buy more RAM.
I read of the challenge in the Dr. Dobb's editorial, and dropped the
magazine to run to my keyboard.
I saw that others have better postal service than I do, and had completed
the basic maps almost a month earlier, so I focused from the beginning
on the more complex challenges using the easier ones as test beds.  I
also vowed to be nicer to my mail carrier in future.

This program is now capable of solving all of the competition maps in
a reasonable time, using an AMD64 2GHz 2GB, though 3 GB are needed for
those involving big.txt fuel calculations, otherwise hours stretch into
days of page swapping.

Each run of the program takes minutes to hours, depending on the problem.
For all but big.txt, the output maps flash by fast enough to appear animated.
That was not the case for earlier program versions.

For multi-target maps, the problem is broken down into successive runs
of the program.
For example, for two targets (T1, T2) and Start ( S ):
Run 1
S->T1
S->T2
Run 2
(S->T1)->T2
Run 3
(S->T2)->T1
Run 4
(S->T1->T2)->S
Run 5
(S->T2->T1)->S

For n targets, the number of runs required is:
the sum for i=0 to i=n of n!/i!

I started with a program implementation which already used most of the C/C++
tricks for speeding the algorithm itself.
As the program gradually improved through minor enhhancements, it became clear
that the key to further improvement in speed came with trading off increased
processing time for decreased memory footprint.

To give an example:
The velocities for x and y are integers as follows:
-10 <= v <= 10
The fastest way to store a value v is in the native word size, e.g. 32-bit.
However this can be packed.  There are 21 possible values for v so it can
be encoded into a byte by adding 10 thus removing the sign. This
actually only takes up 5 bits ( 4 bits and a fraction, to be precise ) so
further space can be gained by roll/mask-ing into 5 bits.
To pack even tighter, two v values can be stored together by multiplying
the second by 21 ( after adding 10 ), so if vx and vy are velocities, then:
packed = ((vy + 10)) * 21 + (vx + 10)
=>
0 <= packed <= (20 * 21) + 20 = 440
so packed can be stored in 9 bits ( 2 ^ 9 = 512 > 440 ) thus saving an
additional bit from 2 x 5-bit.

The above example deals with just two values, whereas the program deals with more,
so the principle extends to further memory space saved at the cost of processing
time.

Eventually I was able to store an entire 1-bit lookup table for all of the states
in the problem, and it fit comfortably into RAM ( even for big.txt ), so that
I could do away with binary trees, etc and the processing overhead involved with
these.

Many further improvements along the same lines ( such as how to compress the
stored paths ) occured to me as I sat watching the map states crawl by.

C/C++ allows this sort of bit manipulation which makes this language particularly
suitable for such programs as this.  However, I noticed that each time I
came up with an optimization, I had to re-write large portions of the code
to fully take advantage of it.  It occurs to me that if we were able to
seperate specification from implementation more completely than is possible
in C++, then the code would be more flexible and easier to improve.
Referring back to the above example of velocity, it would be a huge improvement
to be able to specify velocity, etc. , such as:
v is a member of integers where -10 <= v <= 10
then specify the algorithm in terms of velocity, position, rocket firings.
Then finally specify the mapping of velocity, etc onto binary formats.
The latter specification could then be manipulated independently of the
algorithm.  This would also apply to details such as whether a sequence of values
is stored as a binary tree, lookup table, etc.
This seems to be the goal of generic programming, which tackles algorithms
and containers this way, but C++ does not give us sufficient flexibility to
have , for example, a std::vector of 4.5 bit velocities ( as demonstrated
in the hand coded example above ).  I hasten to emphasize that I am talking
about straightforward and legible code specification.  I am not saying
that any of this is not possible to be coded in C/C++, just that it cannot
be done flexibly enough to be useful, and that if specification and implementation
were more completely sperated, such things would be possible.

- Kevin Shepherd
http://www.scarletline.com/
*/

#include <iostream>
#include <map>
#include <set>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <math.h>
#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_BITS	0x7FF
#define POS_X_ROLL	21

#define POS_Y_BITS	0x7FF
#define POS_Y_ROLL	10

#define VEL_X_BITS	0xF
#define VEL_X_SIGN	0x200
#define VEL_X_ROLL	5

#define VEL_Y_BITS	0xF
#define VEL_Y_SIGN	0x10
#define VEL_Y_ROLL	0

#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 |= ((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 |= ((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)
{
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)
{
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;
};

#define PATH_PREVIOUS_ROLL 8
struct PathType
{
unsigned long	_M_previous_count;
std::vector<unsigned long>	_M_arch;

PathType()
:_M_previous_count(0)
{}
PathType(const PathType & __other)
:_M_previous_count(__other._M_previous_count), _M_arch(__other._M_arch)
{}
PathType & operator=(const PathType & __other)
{
_M_previous_count = __other._M_previous_count;
_M_arch = __other._M_arch;
}
{
int _count = count();
if (_count == 0)
{
_M_arch.push_back(__step);
}
else
{
_M_arch.back() += __step * (unsigned long)pow( (int)6, _count );
}
++ _M_previous_count;
if (count() == 12)
}
void set_previous(unsigned long __prev)
{
_M_previous_count = (__prev << PATH_PREVIOUS_ROLL) + count();
}
unsigned long count() const
{
}
unsigned long previous() const
{
return ((_M_previous_count & PATH_PREVIOUS_MASK) >> PATH_PREVIOUS_ROLL);
}
unsigned long step_count() const
{
return ((_M_arch.size() - (count()?1:0)) * 12) + count();
}
unsigned char get_step(unsigned long __idx) const
{
return ((_M_arch[__idx / 12] / (unsigned long)pow( (int)6, (int)(__idx % 12) )) % 6);
}
};

std::ostream & operator<< (std::ostream & __out, const PathType & __path)
{
for (unsigned long _idx = 0, _idy = __path.step_count(); _idx < _idy; ++ _idx)
{
unsigned short _step = __path.get_step(_idx);
if (_step == 5)
_step = 6;
__out << _step;
}
return __out;
}

struct Active
{
State	st;
unsigned short primary, secondary;
PathType	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);
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;
}
double _state_array_count = (1378.125 * _open_cell_count) + 1.0;
unsigned long _state_array_size = (unsigned long)_state_array_count;
std::cout << "Allocating state array unsigned long[" << _state_array_size << "]" << " Number of States: " << (44100 * _open_cell_count) << 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);
/*
marsrescue big
Cells: 173x173
Map size: 1730x1730
Active Target count 1
Open Cell Count: 14854
Allocating state array unsigned long[20483666] Number of States: 655477312
Input 33496 Active states
.
Cells: 173x173
Map size: 1730x1730
Active Target count 1
Open Cell Count: 14854
Allocating state array unsigned long[20470669] Number of States: 655061400
Input 33496 Active states
.
*/
ActiveList initial_states;
if (_has_input)
{
std::ifstream _input(_prefix_name.c_str());
unsigned long _in_count = 0;
for (;;)
{
Active _from;
short _value;
std::string _prev_path;
_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 >> _prev_path;
_from.path.set_previous(_in_count + 1);
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;
}
++ _ix;
}
initial_states.erase(initial_states.begin(), _ix);
}
ActiveList::iterator _start = _target_end;
++ _start;
ActiveList::iterator _ax = _start;
for (; _ax != _end_2; )
{
transition(3, 2, 1, * _ax);
transition(5, 2, 1, * _ax);
ActiveList::iterator _nextx = _ax;
++ _nextx;
current_states.erase(_ax);
_ax = _nextx;
}
current_states.erase(_end_2);
std::cout << '.';

_ax = _target_end;
for (++ _ax; _ax != _end_1; ++ _ax)
{
transition(1, 1, 1, * _ax);
transition(2, 1, 1, * _ax);
transition(4, 1, 1, * _ax);
}
std::cout << '.';

_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;
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) > 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;
}
++ _ix;
}
initial_states.erase(initial_states.begin(), _ix);
}

ActiveList::iterator _start = _target_end;
++ _start;
for (ActiveList::iterator _ax = _start; _ax != _partition; )
{
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(5, 1, 2, * _ax);
ActiveList::iterator _nextx = _ax;
++ _nextx;
current_states.erase(_ax);
_ax = _nextx;
}
current_states.erase(_partition);
// current_states.erase(_start, ++ _partition);

std::cout << "Adding States ..." << std::endl;
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;

std::vector<std::string>	_previous_path;
if (_has_input)
{
std::ifstream _input(_prefix_name.c_str());
for (;;)
{
short _value;
unsigned short _value2;
std::string _prev_path;
_input >> _value2;
_input >> _value2;
_input >> _value;
_input >> _value;
_input >> _value;
_input >> _value;
_input >> _prev_path;
_previous_path.push_back(_prev_path);
if (!_input.good())
break;
}
}
int _optimal_solutions = 0;
for (ActiveList::iterator _ax = current_states.begin(); _ax != _target_end; ++ _ax)
{ // output targets
if ( (* _ax).primary == _min_primary && (* _ax).secondary == _min_secondary)
{
++ _optimal_solutions;
std::cout << (_has_input?_previous_path[(* _ax).path.previous()-1]:"") << (* _ax).path << std::endl;
_log << (_has_input?_previous_path[(* _ax).path.previous()-1]:"") << (* _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() << " " << (_has_input?_previous_path[(* _ax).path.previous()-1]:"") << (* _ax).path << std::endl;
}
_log << _optimal_solutions << " optimal of " << _solution_count << " solutions" << std::endl;
std::cout << _optimal_solutions << " optimal of " << _solution_count << " solutions" << std::endl;

if (_has_input)
{
std::string _new_name("done-");
_new_name.append(_prefix_name);
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 5:
_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))
{

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
{
}
}
{
/*			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;
}
}
}

{
unsigned long _compressed = compress(_to.st);
if (!is_set_state(_compressed))
{

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
{
}
}
{
++ 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
random-fuel: 9862 solutions in 3920 seconds, minimum: fuel = 57 steps = 156
313110000000000000040040000000000000006644422220200000202000000000000011111002000000000000000333332000000000202022000400001000440000040000000000066640020000
313110000000000000040040000000000000006644422220200000202000000000000011111002000000000000000333332000000000202022000400001000440000040000000000066604020000
random-fuel-00: 35 solutions in 957 seconds, minimum: fuel = 157 steps = 329
31311000000000000004004000000000000000664442222020000020200000000000001111100200000000000000033333200000000020202200040000100044000004000000000004662000202000000032201201002222222222620000022222000626020200006004400000000000004000006222666422220202020202000000000222233333200000000020000222222220000022222222202422624400000000000
map-fuel: 16153 solutions in 1226 seconds, minimum: fuel = 69 steps = 155
66666220020000000220022002200220022002200220022002200000000000000000000000001110000000100000000000033333002002000222000202220020202022222222202420000000000
66666220020000000220022002200220022002200220022002200000000000000000000000001110000000100000000000033333002002000222000202220020202022222222202060000000000
66666220020000000220022002200220022002200220022002200000000000000000000000001110000000100000000000033333002002000222000202220020202022222222242004000000000
66666220020000000220022002200220022002200220022002200000000000000000000000001110000000100000000000033333002002000222000202220020202022222222242000400000000
66666220020000000220022002200220022002200220022002200000000000000000000000001110000000100000000000033333002002000222000202220020202022222222242000040000000
map-fuel-00: 108 solutions in 2067 seconds, minimum: fuel = 146 steps = 318
666662200200000002200220022002200220022002200220022000000000000000000000000011100000001000000000000333330020020002220002022200202020222222222024200000000000066400000040000000000662222262220022020020000000002002222222200200000000000322222222212020202031302020200000000200002200220022002200220022002200220022000000000000
666662200200000002200220022002200220022002200220022000000000000000000000000011100000001000000000000333330020020002220002022200202020222222222024200000000000066400000040000000000662222262220022020020000000002002222222200200000000000322222223202020202021312020200000000200002200220022002200220022002200220022000000000000
666662200200000002200220022002200220022002200220022000000000000000000000000011100000001000000000000333330020020002220002022200202020222222222024200000000000066400000040000000000662222262220022020020000000002002222222200200000000000322222223202020202021303020200000000200002200220022002200220022002200220022000000000000
666662200200000002200220022002200220022002200220022000000000000000000000000011100000001000000000000333330020020002220002022200202020222222222024200000000000066400000040000040000200666662200200220020000000020002222222200020000000000322222222212020202031302020200000000200020022002200220022002200220022002200200000000000
666662200200000002200220022002200220022002200220022000000000000000000000000011100000001000000000000333330020020002220002022200202020222222222024200000000000066400000040000000000662222262220022020020000000002002222222200200000000000322222222212020202031302020200000000200002200220022002200220022002200220020200000000000
666662200200000002200220022002200220022002200220022000000000000000000000000011100000001000000000000333330020020002220002022200202020222222222024200000000000066400000040000040000200666662200200220020000000020002222222200020000000000322222222212020202031302020200000000200020022002200220022002200220022002200020000000000
666662200200000002200220022002200220022002200220022000000000000000000000000011100000001000000000000333330020020002220002022200202020222222222024200000000000066400000040000000000662222262220022020020000000002002222222200200000000000322222222212020202031302020200000000200002200220022002200220022002200220020020000000000
big-step-00: 2219 solutions in 4726 seconds, minimum: steps = 660 fuel = 345
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222020000000000000000000000000000000000333202222222222220202020202020200000000000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222020000000000000000000000000000000000333022222222222220202020202020200000000000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222002000000000000000000000000000000002333222222222220202020202020220000000000000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222000022000000000000000000000000000000000002333222222202222202020202020200000000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222000000202200000000000000000000000000000000000033322222222222202020202020200000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222000000202200000000000000000000000000000000000033322222222222022020202020200000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222000000202000000000000000000000000000000233322222222222020202020202020000000000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222000000202000000000000000000000000000000233322222222220220202020202020000000000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222000000202000000000000000000000000000000233322222222202220202020202020000000000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222000000202000000000000000000000000000000233322222222022220202020202020000000000000000000000000
10 optimal of 2219 solutions
big-fuel: 37239 solutions in 12773 seconds, minimum: fuel = 93 steps = 356
66444000000000000000000000000000000066662222620202020202020202020202020202002000000000000000000000000004100000000000000010000111100000000001000000000000000004444400000000000000000000000000000000311110002200000000000000000000000000033233223220202020202020200000000000022222222200000000020000000000000000000000000000400000020000000000000000000000400000000000
66444000000000000000000000000000000066662222620202020202020202020202020202002000000000000000000000000004100000000000000010000111100000000001000000000000000004444400000000000000000000000000000000311110002200000000000000000000000000033233223220202020202020200000000000022222222200000000020000000000000000000000000000400000020000000000000000000000040000000000
66444000000000000000000000000000000066662222620202020202020202020202020202002000000000000000000000000004100000000000000010000111100000000001000000000000000004444400000000000000000000000000000000311110002200000000000000000000000000033233223220202020202020200000000000022222222200000000020000000000000000000000000000400000020000000000000000000000004000000000
66444000000000000000000000000000000066662222620202020202020202020202020202002000000000000000000000000004100000000000000010000111100000000001000000000000000004444400000000000000000000000000000000311110002200000000000000000000000000033233223220202020202020200000000000022222222200000000020000000000000000000000000000400000020000000000000000000000000400000000
66444000000000000000000000000000000066662222620202020202020202020202020202002000000000000000000000000004100000000000000010000111100000000001000000000000000004444400000000000000000000000000000000311110002200000000000000000000000000033233223220202020202020200000000000022222222200000000020000000000000000000000000000400000020000000000000000000000000040000000
66444000000000000000000000000000000066662222620202020202020202020202020202002000000000000000000000000004100000000000000010000111100000000001000000000000000004444400000000000000000000000000000000311110002200000000000000000000000000033233223220202020202020200000000000022222222200000000020000000000000000000000000000400000020000000000000000000000000004000000
66444000000000000000000000000000000066662222620202020202020202020202020202002000000000000000000000000004100000000000000010000111100000000001000000000000000004444400000000000000000000000000000000311110002200000000000000000000000000033233223220202020202020200000000000022222222200000000020000000000000000000000000000400000020000000000000000000000000000400000
7 optimal of 37239 solutions
big-fuel-00: 2 solutions in 7568 seconds, minimum: fuel = 267 steps = 715
6644400000000000000000000000000000006666222262020202020202020202020202020200200000000000000000000000000410000000000000001000011110000000000100000000000000000444440000000000000000000000000000000031111000220000000000000000000000000003323322322020202020202020000000000002222222220000000020000000000000000000000000000040000000000000000100000000000000000000000000006222222226020202020202020202060202020202020202020202460202022020202200000000000000202222200202000000000000000000000000000006666222222220202020022020200020000200000003332222223020202020200020222420202420202024646024602020202020202020203131202020202120202031312020000000000000000000000000000000000000000033333222220202020202020202000000000000000000000000000
6644400000000000000000000000000000006666222262020202020202020202020202020200200000000000000000000000000410000000000000001000011110000000000100000000000000000444440000000000000000000000000000000031111000220000000000000000000000000003323322322020202020202020000000000002222222220000000020000000000000000000000000000040000000000000000100000000000000000000000000006222222226020202020202020202060202020202020202020202460202022020202200000000000000202222200202000000000000000000000000000006666222222220202020022020200020000200000003332222223020202020200020222420202420202024646024602020202020202020203131202020202120202031312020000000000000000000000000000000000000000033333222220202020202020200200000000000000000000000000
2 optimal of 2 solutions
*/
```