pixelated.cpp

#include <tuple>
#include <vector>
#include <random>
#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <boost/dynamic_bitset.hpp>

struct Matrix
{
  int m, n;
  int *data;
  
  Matrix(int m, int n)
    : m{m}, n{n}, data{new int[m * n]}
  { }
  
  Matrix(const Matrix&) = delete;
  
  ~Matrix()
  {
    delete[] data;
  }
  
  auto size() const {
    return m * n;
  }
  
  bool in_bounds(int i) const
  {
    return i >= 0 && i < m * n;
  }
  
  bool in_bounds(int i, int j) const
  {
    return i >= 0 && j >= 0 && i < m && j < n;
  }
  
  int& operator[] (int i)
  {
    return data[i];
  }
  
  int operator[] (int i) const
  {
    return data[i];
  }
  
  int& at(int i, int j)
  {
    return data[i * n + j];
  }
  
  int at(int i, int j) const
  {
    return data[i * n + j];
  }
};

struct Board
{
  int colors;
  Matrix pixels;
  
  Board(int width, int height, int colors)
    : colors{colors}, pixels{height, width}
  { }
  
  void randomize()
  {
    std::random_device rd{};
    std::mt19937 gen{rd()};
    std::uniform_int_distribution<> dis{0, colors - 1};
    
    for (int i = 0; i < pixels.m; ++i)
    {
      for (int j = 0; j < pixels.n; ++j)
      {
        pixels.at(i, j) = dis(gen);
      }
    }
  }
  
  void inflate(std::string filename)
  {
    std::ifstream ifs{filename};
    std::string line;
    
    for (int i = 0; i < pixels.m; ++i)
    {
      std::getline(ifs, line);
      
      for (int j = 0; j < pixels.n; ++j)
      {
        pixels.at(i, j) = static_cast<int>(line[j] - '0');
      }
    }
  }
  
  std::string stringify() const
  {
    std::ostringstream oss;
    
    for (int i = 0; i < pixels.m; ++i)
    {
      for (int j = 0; j < pixels.n; ++j)
      {
        oss << pixels.at(i, j);
      }
      
      oss << '\n';
    }
    
    auto str = oss.str();
    
    str.erase(str.end() - 1);
    
    return str;
  }
  
  template <typename Func>
  void foreach_neighbor_of(int i, Func f) const
  {
    int idiv = i / pixels.n;
    int imod = i % pixels.n;
    
    // up
    if (idiv != 0) {
      f(i - pixels.n);
    }
    
    // left
    if (imod != 0) {
      f(i - 1);
    }
    
    // right
    if (imod != pixels.n - 1) {
      f(i + 1);
    }
    
    // down
    if (idiv != pixels.m - 1) {
      f(i + pixels.n);
    }
  }
};

std::ostream& operator<< (std::ostream& os, const Board& board)
{
  return os << board.stringify();
}

struct Island
{
  int color;
  std::vector<int> elements;
  
  Island(int color)
    : color{color}
  { }
  
  Island(Island&& rhs)
    : color{rhs.color}, elements{std::move(rhs.elements)}
  { }
};

template <typename Container>
void uniquify(Container& cont)
{
  std::sort(std::begin(cont), std::end(cont));
  
  auto last_unique = std::unique(std::begin(cont), std::end(cont));
  cont.erase(last_unique, std::end(cont));
}

auto find_islands(const Board& board)
{
  std::vector<bool> visited(board.pixels.size(), false);
  std::vector<Island> islands{};
  
  std::vector<int> visit_queue{};
  
  for (int i = 0; i < board.pixels.size(); ++i)
  {
    if (visited[i]) continue;
    
    visit_queue.clear();
    visit_queue.push_back(i);
    
    auto color = board.pixels[i];
    
    Island island { color };
    
    int visit_head = 0;
    
    while (visit_head < visit_queue.size())
    {
      auto j = visit_queue[visit_head];
      visit_head += 1;
      
      if (visited[j]) continue;
      
      if (color == board.pixels[j])
      {
        visited[j] = true;
        
        island.elements.push_back(j);
        
        board.foreach_neighbor_of(j, [&] (int x) { visit_queue.push_back(x); });
      }
    }
    
    islands.emplace_back(std::move(island));
  }
  
  return islands;
}

auto islands_adjacency(const Board& board, const std::vector<Island>& islands)
{
  std::vector<std::vector<int>> adjacency{};
  std::vector<int> elem2island{};
  
  adjacency.reserve(islands.size());
  elem2island.reserve(board.pixels.size());
  
  for (int i = 0; i < islands.size(); ++i)
  {
    for (int elem : islands[i].elements)
    {
      elem2island[elem] = i;
    }
  }
  
  for (auto&& island : islands)
  {
    std::vector<int> friends{};
    
    for (int elem : island.elements)
    {
      board.foreach_neighbor_of(elem, [&] (int neighbor) {
        if (island.color == board.pixels[neighbor]) return;
        
        friends.push_back(elem2island[neighbor]);
      });
    }
    
    uniquify(friends);
    
    adjacency.emplace_back(std::move(friends));
  }
  
  return adjacency;
}

struct NatSet
{
  int count;
  boost::dynamic_bitset<> table;
  
  NatSet(const NatSet& rhs)
    : count{rhs.count}, table{rhs.table}
  { }
  
  NatSet& operator= (const NatSet& rhs)
  {
    count = rhs.count;
    table = rhs.table;
    return *this;
  }
  
  NatSet(NatSet&& rhs)
    : count{rhs.count}, table{std::move(rhs.table)}
  { }
  
  NatSet& operator= (NatSet&& rhs)
  {
    count = rhs.count;
    table = std::move(rhs.table);
    return *this;
  }
  
  NatSet(int max, std::initializer_list<int> elems)
    : count{0}, table(max, false)
  {
    insert(elems);
  }
  
  void insert(int e)
  {
    if (!table[e])
    {
      count += 1;
    }
    
    table[e] = true;
  }
  
  template <typename Container>
  void insert(const Container& cont)
  {
    for (auto&& x : cont)
    {
      table[x] = true;
    }
    recount();
  }
  
  bool contains(int e) const
  {
    return table[e];
  }
  
  bool is_subset_of(const NatSet& rhs) const
  {
    return table.is_subset_of(rhs.table);
  }
  
private:
  void recount()
  {
    count = table.count();
  }
};

struct SolveState
{
  NatSet domain;
  std::vector<int> border;
  std::vector<int> steps;
  
  SolveState(const SolveState& rhs)
    : SolveState{rhs.domain, rhs.border, rhs.steps}
  { }
  
  SolveState& operator= (const SolveState& rhs)
  {
    domain = rhs.domain;
    border = rhs.border;
    steps  = rhs.steps;
    return *this;
  }
  
  SolveState(SolveState&& rhs)
    : domain{std::move(rhs.domain)}
    , border{std::move(rhs.border)}
    , steps {std::move(rhs.steps)}
  { }
  
  SolveState& operator= (SolveState&& rhs)
  {
    domain = std::move(rhs.domain);
    border = std::move(rhs.border);
    steps  = std::move(rhs.steps);
    return *this;
  }
  
  SolveState(NatSet ns)
    : SolveState{std::move(ns), {}, {}}
  { }
  
  SolveState(NatSet ns, std::vector<int> border)
    : SolveState{std::move(ns), std::move(border), {}}
  { }
  
  SolveState(NatSet ns, std::vector<int> border, std::vector<int> steps)
    : domain{std::move(ns)}, border{std::move(border)}, steps{std::move(steps)}
  { }
};

auto solve(const Board& board)
{
  auto islands = find_islands(board);
  auto adjacency = islands_adjacency(board, islands);
  
  std::vector<SolveState> level{};
  
  auto init = NatSet{board.pixels.size(), {0}};
  
  level.emplace_back(init, adjacency[0]);
  
  std::vector<SolveState> next{};
  
  while (true)
  {
    next.clear();
    
    for (auto&& state : level)
    {
      for (int color = 0; color < board.colors; ++color)
      {
        NatSet domain{state.domain};
        std::vector<int> border{};
        
        for (int friend_ : state.border)
        {
          if (islands[friend_].color == color)
          {
            domain.insert(friend_);
            
            for (int poop : adjacency[friend_])
            {
              if (!domain.contains(poop))
              {
                border.push_back(poop);
              }
            }
          }
          else
          {
            border.push_back(friend_);
          }
        }
        
        if (state.domain.count == domain.count)
        {
          continue;
        }
        
        std::vector<int> steps{state.steps};
        steps.push_back(color);
        
        if (domain.count == islands.size())
        {
          return steps;
        }
        
        uniquify(border);
        
        next.emplace_back(std::move(domain), std::move(border), std::move(steps));
      }
    }
    
    std::sort(std::begin(next), std::end(next), [] (const SolveState& a, const SolveState& b) {
      return a.domain.count < b.domain.count;
    });
    
    level.clear();
    
    for (int i = 0; i < next.size(); ++i)
    {
      bool skip = false;
      
      for (int j = i + 1; j < next.size(); ++j)
      {
        if (next[i].domain.is_subset_of(next[j].domain))
        {
          skip = true;
          break;
        }
      }
      
      if (!skip)
      {
        level.emplace_back(std::move(next[i]));
      }
    }
  }
}

template <typename Container>
void print_container(std::ostream& os, const Container& cont)
{
  os << '[';
  
  auto it = std::begin(cont);
  auto ot = std::end(cont);
  
  if (it != ot) {
    os << *it;
  }
  
  ++it;
  
  for ( ; it != ot; ++it) {
    os << ", " << *it;
  }
  
  os << "]\n";
}

int main()
{
  Board board{16, 9, 6};
  //board.randomize();
  board.inflate("board.txt");
  
  std::cout << board << std::endl;
  
  /*
  auto islands = find_islands(board);
  
  for (auto&& island : islands)
  {
    for (auto&& x : island.elements)
    {
      std::cout << x << ' ';
    }
    std::cout << '\n';
  }
  
  auto adjacency = islands_adjacency(board, islands);
  
  for (auto&& row : adjacency)
  {
    for (auto&& x : row)
    {
      std::cout << x << ' ';
    }
    std::cout << '\n';
  }
  */
  
  auto answer = solve(board);
  
  print_container(std::cout, answer);
  
  return 0;
}