public
Last active

Code exploration based on a discussion at http://www.cplusplus.com/forum/lounge/98939/

  • Download Gist
grid.cpp
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
#include <iostream>
#include "grid.h"
 
Grid& Grid::flip(std::size_t pos)
{
switch(pos)
{
case 0: _grid.flip(0).flip(1).flip(3) ; break ;
case 1: _grid.flip(0).flip(1).flip(2).flip(4) ; break ;
case 2: _grid.flip(1).flip(2).flip(5) ; break ;
case 3: _grid.flip(0).flip(3).flip(4).flip(6) ; break ;
case 4: _grid.flip(1).flip(3).flip(4).flip(5).flip(7) ; break ;
case 5: _grid.flip(2).flip(4).flip(5).flip(8) ; break ;
case 6: _grid.flip(3).flip(6).flip(7) ; break ;
case 7: _grid.flip(4).flip(6).flip(7).flip(8) ; break ;
case 8: _grid.flip(5).flip(7).flip(8) ; break ;
}
 
return *this ;
}
 
Grid& Grid::invert()
{
_grid = ~_grid ;
return *this ;
}
 
std::ostream& operator<<(std::ostream& os, const Grid& g)
{
for ( unsigned i=0; i<3; ++i )
{
for ( unsigned j=0; j<3; ++j )
os << (g[i*3+j] ? '*' : '-') ;
os << '\n' ;
}
return os ;
}
grid.h
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
#ifndef EMS_GRID_H
#define EMS_GRID_H
 
#include <bitset>
 
class Grid
{
public:
 
int compare(const Grid & g) const ;
Grid& flip(std::size_t pos) ;
Grid& invert() ;
 
bool operator[](std::size_t pos) const { return _grid[pos] ; }
 
friend std::ostream& operator<<(std::ostream&, const Grid& g) ;
friend struct GridHashFunc ;
 
private:
 
std::bitset<9> _grid ;
};
 
struct GridHashFunc
{
std::size_t operator() (const Grid& g) { return g._grid.hash() ; }
};
 
inline int Grid::compare(const Grid& g) const
{
return _grid.to_ulong() - g._grid.to_ulong() ;
}
 
inline bool operator==(const Grid& a, const Grid& b )
{
return a.compare(b) == 0 ;
}
 
inline bool operator<(const Grid& a, const Grid& b)
{
return a.compare(b) < 0 ;
}
 
#endif
main.cpp
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
#include <fstream>
#include <vector>
#include <unordered_map>
#include <functional>
#include "grid.h"
 
const size_t squares = 9 ;
 
typedef std::unordered_map<Grid,unsigned,GridHashFunc> SolutionMap ;
 
SolutionMap buildSolutionMap()
{
typedef std::vector<Grid> grid_vec ;
typedef std::pair<std::size_t, std::size_t> range_element ;
typedef std::vector<range_element> range_vec ;
 
SolutionMap gridInfo ;
grid_vec grids ;
 
// prime the pump.
gridInfo.emplace(Grid(), 0) ;
gridInfo.emplace(Grid().invert(), 0) ;
grids.push_back(Grid()) ;
grids.push_back(Grid().invert()) ;
 
range_vec ranges(1, range_element(0, grids.size())) ;
bool done = false ;
size_t flips = 0 ;
 
while ( ! done )
{
range_element& range = ranges[flips] ;
for ( std::size_t i=range.first; i!= range.second; ++i )
{
for ( std::size_t j = 0; j < squares; ++j )
{
Grid working = grids[i] ;
working.flip(j) ;
 
if ( !gridInfo.count(working) )
{
grids.push_back(working) ;
gridInfo.emplace(std::make_pair(working, flips+1)) ;
}
}
}
if ( range.second == grids.size() )
done = true ;
else
{
ranges.emplace_back(std::make_pair(range.second, grids.size())) ;
++flips ;
}
}
 
return gridInfo ;
}
 
int main()
{
SolutionMap solutions = buildSolutionMap() ;
 
std::ofstream out ("solutions.txt") ;
 
out << solutions.size() << '\n' ;
 
for ( auto & solution : solutions )
out << solution.first << solution.second << " flips\n\n" ;
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.