Kevin Shepherd's solution:
#include <iostream>
#include <map>
#include <set>
#include <fstream>
#include <string>
#include <list>
#define MAX_CELL_DIM 0xFF
#define MAX_TARGET_COUNT 1
#define MAX_X_DIM 1024
#define MAX_Y_DIM 1024
#define STATE_ARRAY_SIZE 0x4000000
#define TARGET_MASK 0x3FFFFFFF
#define TARGET_BITS 0x40000000
#define TARGET_ROLL 30
#define POS_X_MASK 0xC00FFFFF
#define POS_X_BITS 0x3FF
#define POS_X_ROLL 20
#define POS_Y_MASK 0xFFF003FF
#define POS_Y_BITS 0x3FF
#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
unsigned long target_mask = 0;
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;
}
void set_target(unsigned char )
{
packed |= TARGET_BITS;
}
unsigned long get_targets() const
{
return packed >> TARGET_ROLL;
}
void set_targets(unsigned long __targets)
{
packed &= TARGET_MASK;
packed |= (__targets << TARGET_ROLL);
}
bool all_targets() const
{
return ((packed & TARGET_BITS) != 0);
}
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;
std::string path;
};
typedef std::list<Active> ActiveList;
unsigned long state_array[STATE_ARRAY_SIZE];
ActiveList current_states;
unsigned char cell_map[MAX_CELL_DIM+1][MAX_CELL_DIM+1];
unsigned long target_baseline;
unsigned long _cell_width = 0, _cell_height = 0;
unsigned long state_count = 0;
bool is_set_state(State _st)
{
return ( state_array[_st.packed >> 5] & (1 << (_st.packed & 0x1F) ) ) != 0;
}
void set_state(State _st)
{
state_array[_st.packed >> 5] |= (1 << (_st.packed & 0x1F) );
}
bool transition (unsigned char __impulse, const Active & __from);
int main(int _argc, char * _argv[])
{
if (_argc < 2 )
{
std::cerr << "Usage: " << _argv[0] << " <map>" << std::endl;
return 1;
}
std::ifstream _in(_argv[1]);
_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;
}
if (_cell_width * 10 > MAX_X_DIM || _cell_height * 10 > MAX_Y_DIM)
{
std::cerr << "Map too large " << _cell_width * 10 << "x" << _cell_height * 10 << " > " << MAX_X_DIM << "x" << MAX_Y_DIM << std::endl;
return 1;
}
std::string _line;
unsigned long _target_max = 0;
Active _initial_state;
CellCoord _cell_pos;
_cell_pos.y = 0;
memset(cell_map, 1, sizeof(unsigned char [MAX_CELL_DIM+1][MAX_CELL_DIM+1]));
memset(state_array, 0, sizeof(unsigned long [STATE_ARRAY_SIZE]));
unsigned long _open_cell_count = 0;
while (_in.good() && _cell_pos.y < _cell_height)
{
std::getline(_in, _line);
if (_line.size() >= _cell_width)
{
std::cout << _line << std::endl;
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] = 1;
break;
case 'O':
cell_map[_cell_pos.x][_cell_pos.y] = 2;
_initial_state.st.set_x(_cell_pos.x * 10);
_initial_state.st.set_y(_cell_pos.y * 10);
++ _open_cell_count;
break;
case '+':
++ _target_max;
cell_map[_cell_pos.x][_cell_pos.y] = (unsigned char)(_target_max + 2);
++ _open_cell_count;
break;
case ' ':
default:
cell_map[_cell_pos.x][_cell_pos.y] = 0;
++ _open_cell_count;
break;
}
}
++ _cell_pos.y;
}
}
if (_target_max > MAX_TARGET_COUNT)
{
std::cerr << "Too many targets " << _target_max << " > " << MAX_TARGET_COUNT << std::endl;
return 1;
}
else
{
std::cout << "Target count " << _target_max << " Open Cell Count: " << _open_cell_count << std::endl;
}
target_mask = 0xFFFFFFFF >> (32 - _target_max);
std::cout << "Target mask " << target_mask << std::endl;
set_state(_initial_state.st);
current_states.push_back(_initial_state);
bool _found = false;
unsigned long _iter = 0;
unsigned long _prev_target_baseline = 0;
while (!_found)
{
current_states.push_back(Active());
ActiveList::iterator _partition = current_states.end();
-- _partition;
target_baseline = 0xFFFFFFFF;
for (ActiveList::iterator _ax = current_states.begin(); _ax != _partition; ++ _ax)
{
if (transition(0, * _ax))
{
_found = true;
break;
}
if (transition(1, * _ax))
{
_found = true;
break;
}
if (transition(2, * _ax))
{
_found = true;
break;
}
if (transition(4, * _ax))
{
_found = true;
break;
}
if (transition(3, * _ax))
{
_found = true;
break;
}
if (transition(6, * _ax))
{
_found = true;
break;
}
}
current_states.erase(current_states.begin(), ++ _partition);
if (target_baseline != _prev_target_baseline)
{
State _t_from, _t_to;
_t_from.set_targets(_prev_target_baseline);
_t_to.set_packed(0xFFFFFFFF);
_t_to.set_targets(_prev_target_baseline);
std::cout << "Erasing Target base: " << _prev_target_baseline << std::endl;
// states_reached.erase(states_reached.lower_bound(_t_from), states_reached.upper_bound(_t_to));
_prev_target_baseline = target_baseline;
}
++ _iter;
std::cout << '.';
{ // 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::iterator _ax = current_states.begin(), _ay = current_states.end(); _ax != _ay; ++ _ax)
{
unsigned char _content = report_map[ (* _ax).st.get_x() / 10 ][ (* _ax).st.get_y() / 10 ];
if (_content != 0xFF)
{
if ((* _ax).st.all_targets())
report_map[ (* _ax).st.get_x() / 10 ][ (* _ax).st.get_y() / 10 ] = 0xFF;
else
report_map[ (* _ax).st.get_x() / 10 ][ (* _ax).st.get_y() / 10 ] = 0xFE;
}
++ _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 0:
std::cout << ' ';
break;
case 1:
std::cout << '#';
break;
case 2:
std::cout << 'O';
break;
case 0xFE:
std::cout << '*';
break;
case 0xFF:
std::cout << 'T';
break;
default:
std::cout << '+';
break;
}
}
std::cout << std::endl;
}
std::cout << "Iteration: " << _iter << " Count: " << _active_count << " State Count: " << state_count << std::endl;
}
}
if (_found)
{
std::cout << "Solution: " << current_states.back().path << std::endl;
}
return 0;
}
bool transition (unsigned char __impulse, const Active & __from)
{
Active _to(__from);
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;
}
short _new_x, _new_y;
bool _x_two_col, _y_two_col;
do
{
_new_x = _to.st.get_x() + _to.st.get_vel_x();
if (_new_x >= 0)
{
_new_y = _to.st.get_y() + _to.st.get_vel_y();
if (_new_y >= 0)
{
CellCoord _cell_pos;
_cell_pos.x = _new_x / 10;
if (_cell_pos.x < _cell_width)
{
_cell_pos.y = _new_y / 10;
if (_cell_pos.y < _cell_height)
{
unsigned char _cell_content = cell_map[_cell_pos.x][_cell_pos.y];
if (cell_map[_cell_pos.x][_cell_pos.y] != 1)
{
_x_two_col = ((_new_x % 10) != 0);
_y_two_col = ((_new_y % 10) != 0);
bool _collision = false;
if (_x_two_col)
{
++ _cell_pos.x;
if (cell_map[_cell_pos.x][_cell_pos.y] == 1)
_collision = true;
if (_y_two_col)
{
++ _cell_pos.y;
if (cell_map[_cell_pos.x][_cell_pos.y] == 1)
_collision = true;
-- _cell_pos.y;
}
-- _cell_pos.x;
}
if (_y_two_col)
{
++ _cell_pos.y;
if (cell_map[_cell_pos.x][_cell_pos.y] == 1)
_collision = true;
-- _cell_pos.y;
}
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() );
_new_x = _to.st.get_x() + _to.st.get_vel_x();
_new_y = _to.st.get_y() + _to.st.get_vel_y();
_x_two_col = ((_new_x % 10) != 0);
_y_two_col = ((_new_y % 10) != 0);
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 _home = false;
unsigned char _cell_content = cell_map[_cell_pos.x][_cell_pos.y];
if (_cell_content == 2)
_home = true;
else if ( _cell_content > 2)
{
_to.st.set_target(_cell_content - 3);
}
if (_x_two_col)
{
++ _cell_pos.x;
_cell_content = cell_map[_cell_pos.x][_cell_pos.y];
if (_cell_content == 2)
_home = true;
else if ( _cell_content > 2)
{
_to.st.set_target(_cell_content - 3);
}
if (_y_two_col)
{
++ _cell_pos.y;
_cell_content = cell_map[_cell_pos.x][_cell_pos.y];
if (_cell_content == 2)
_home = true;
else if ( _cell_content > 2)
{
_to.st.set_target(_cell_content - 3);
}
-- _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 == 2)
_home = true;
else if ( _cell_content > 2)
{
_to.st.set_target(_cell_content - 3);
}
-- _cell_pos.y;
}
if (_home && !_to.st.all_targets())
_home = false;
if (!is_set_state(_to.st))
{
set_state(_to.st);
++ state_count;
target_baseline &= _to.st.get_targets();
char _buf[2];
sprintf(_buf, "%d", (int)__impulse);
_to.path.append(_buf);
current_states.push_back(_to);
}
return _home;
}
/*
Iteration: 270 Count: 1087958 State Count: 60960443
.
TTTTTTTTTTTTTTTTTTTTTT TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
TTTTTTTTTTTTTTTTTTTTT TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
TTTTTTTTTTTTTTTTTTTTT TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
TTTTTTTTTTTTTTTTTTTTT TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT#TTTT
TTTTTTTTTTTTTTTTTTTT TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
#TTTTTTTTTTTTTTTTTTO ### #TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT #
#T ###TTTTTTTTTTT##### # # ## #TTTTTTTTTTTTTTTTTTTTTTTTTT#TTTT#TTTTTTT
#T####TTTTTTTTTTT### # ## # ###TTTTTTTTTTTTTTTTTTTTTTTT#TT###### TTTT #
### #TTTTT#TTTTT#### ###### #### ###TT#TT#TTTTTTTTTTTTTTTTTTTTTT#T #####TTT#### ## # # ## #
# # # #TT#TTTTT############# ## ## # TT##T#TTTTTTTTTTTTTTTTT#TTTT ##TTTTT# TT ## ## # # ##
# #TT ##T################ # # #TTTTTTTTTT##TTTTTT#TTTTT#### #TTTTTTT#T##### ## ##
# ## #T TT ##################### ###TTTTTTTTTTT##TTTT##TT## ## # #TTTTTTT##### # # ## #
## # # # #TTTT#############################T####T####TTT ### ## #### TTTTTTT### ### # # #
# # TT TTTT# ######################## TT## #### ##TT###### ####### ##TTTTTT## ## #### #
# # # ## TT#TT#T## ######################## #### # ####TTT# ### # # #######TTTTTTTT#T ##T# ######
# #####TT##TTT## ######################## ###### # ## # # # # # ##TTTTTTT#T#TTT#######
# #TT #T TTT ####################### ######## # # # T T ##### # # TTT# #TT#TT ########
# #TT # TTTTT T########################### ####### ### TT# #######T####TT####TT ## # #####
# # T## TTTT# # ############################## ### ### # TTTTTTTTTTTT### ######
## #TT###TT#T#T# # ########################## # #### ## ## ## T TTTTTTTTT## # ######
# ###TTT#TTTTT # # ########################## # # # # # # ##TTTTT#TT### ## # # ###
# ####TT #TT#T TT ## ######### ############# # ##### ## # #TT#TTTT### ## #####
#TTT###T# T TT# ## # ###### ## # # # # # #TTT#TT#T##### ######
# ##TTTTTT# # # # # ######## #### # ## ### ####TTTTT ### # #####
## ### ##TTT# #### ## ############## # ## # # ######## # ## #####
##TTT# ###### ######## # ################ # #T ## ### ### # # # ####
### #TT # ######## ####### ## ## ########### #TT # # # ### ## # #### #####
# ### # ###### ######### # # ######### #TT # ### # #### ## # ###
## #### ####### # # ###### # ########## # #TTT#T#T###T### # ## ## # ##
##### # ################ # ## ##### #### ## # # # #TTTTTTTTTTTT########## # # ##
# # ## ############################ # # # ###TTTTT#TTTTT############ ### #
# ### ############### ############ # ## #TT#TTTT#TTT###########
## # ### # # ########################## ##TTT TT################# #
############## ############## ########### #### # # ####TTTT# #TT############# ###
# ## # ####### ########## ####### # ## ## ### ## ## TTT###TTTT########## # # #
# ######## # ########## # #### ## # #### # ## #TTTT##TTTT###### # ### #
## ######## ## ## ###### #### ## ### ## # ## ##### # TTT#TTTT######## # ### #
# ############## ######### # # # # # # ## #######TTTTTT#T# ###### # ### ## #
# ############### ###### # # # #### # #### ########TTTTTTT#T# ## # # # ##
# ################ ####### # # # # ##### ####### ###TTTTTTTTTTT### ## ## #####
################ ###### ## # # ## ########## ## ####TTTTT##TT # ## #####
# # ############# ####### ### ## # # ##### # ## ## ## ##TTTTTTTT # # ### #
## ##### # ######## # #### # ######## ####### TTT#TTTTT# ### ##
# # # # ##### # # # ## # # ###### ####### ## ## #TTTT# # # #
# ###### #### ### # ## ########## # ### ####### ##T##### # # ####
# ## # # ### ## ## # # # ############ #### ### ######### # # # ##
## # # # #### #### ## # ############# ### # # # ### # ## # ##
# # # ## # ## # ## # # ############# ## ## # #### # ### ### # ###
# # # ## ### # ## ####### #################### #### ########## ######## # #
## # ### # # ## ###### ### ################### #### ### ### # ##### #
## # # ## # # # ## # ### ################ # ####### # # ##### ######
# # # # ### # # # ###### # #################### ############ ## ## ##
# # # # # # # ## ######### # ################################ # # ##########
# # # # ## # ## ##### ###### # ################## ################ #### #######
## # # ####### ## ###### ######## ######## ######################## #### ### ## #
# ####### ## # # ############### ################################## ###### ## # #
# # ####### # ## ####### ####### ### ######################## ##################
# ####### ################## # ## ############################### ##### ####### ##
# # # ## ## ################## # # ### ################################### ## ###
### # # # ### ##################### ## ######################################### # # # #
# # ####### #################### ### ############## ## ######################## ## ## ##
# ######################### #### ##### ### ## ############### ############ # ## ##
## # ######################### # ##### # # ## ## # # #################### ### #
## # ############### # # ## # # ##### #### # ## # ### #########################
# # # ############## # ## # # ### # ######### ###### # ### ###### ### ## # # # #
# # ########## # # ############ ####### # ## ## ############ ### # #
## # ## ####### ### # # ### # # ######## ################### ## # # ##
# # ####### ### # # # # # # ##### ### ## ###### ## ######## ### # ##
# ###### ### # # # # # # # # ## # ### ##### ### ##### ### # ## #
# # # ### # # # # #### # ## # ## #### ## ### # ####### # # ###
### #### # # ## # # ## #### ## ## # # ######## # ###### ## # # ###### #
## # ## # # # ### #### # ### ## ## ## ### ### ### # ### ######
# # # ## # # # + ## # # ## ## # ## ###### # #### # ### ## ####### ######
# # # # ## # #### ## # # # ### # ## ## # ### ## ### # ######
## ### # # # ## # ## # # # ## # ### # ## # ## # # # ######
Iteration: 271 Count: 1064267 State Count: 62024710
Solution: 311310000206444442411000026662662022222020000002000001113333321100000000000220222222266664
2211113022000444440000444044011130466626220033133130132222666662333332666640044444000220311110164666
222222202222222220000013333333110000000022000002222222266226662632662204440000000
Steps: 271, Fuel Usage: 253.
*/