pixelated.d

import std.conv;
import std.stdio;
import std.range;
import std.random;
import std.algorithm;

struct Pair(T, U)
{
  T fst;
  U snd;
  
  auto opAdd(const ref Pair!(T, U) p) const
  {
    return Pair!(T, U)(fst + p.fst, snd + p.snd);
  }
}

alias Coord = Pair!(int, int);

struct Matrix(T)
{
  int m, n;
  T data[];
  
  this(int m, int n)
  {
    this.m = m;
    this.n = n;
    this.data = new T[m * n];
  }
  
  bool inBounds(int i) const
  {
    return i >= 0 && i < m * n;
  }
  
  bool inBounds(int i, int j) const
  {
    return i >= 0 && j >= 0 && i < m && j < n;
  }
  
  bool inBounds(Coord p) const
  {
    return inBounds(p.fst, p.snd);
  }
  
  ref auto opIndex(int i)
  {
    return data[i];
  }
  
  ref auto opIndex(int i) const
  {
    return data[i];
  }
  
  ref auto opIndex(int i, int j)
  {
    return this[i * n + j];
  }
  
  ref auto opIndex(int i, int j) const
  {
    return this[i * n + j];
  }
  
  ref auto opIndex(Coord p)
  {
    return this[p.fst, p.snd];
  }
  
  ref auto opIndex(Coord p) const
  {
    return this[p.fst, p.snd];
  }
}

struct Board
{
  int colors;
  Matrix!int data;
  
  this(int colors, int width, int height)
  {
    this.colors = colors;
    this.data = Matrix!int(height, width);
  }
  
  auto size() const
  {
    return data.m * data.n;
  }
  
  auto idxToCoord(int i) const
  {
    return Coord(i / data.n, i % data.n);
  }
  
  auto coordToIdx(Coord c) const
  {
    return c.fst * data.n + c.snd;
  }
  
  auto neighbors(Coord cur) const
  {
    return
      [Coord(-1, 0), Coord(0, -1), Coord(0, 1), Coord(1, 0)]
      .map!(x => x + cur)
      .filter!(x => this.data.inBounds(x))
      .array;
  }
  
  auto neighbors(int i) const
  {
    return neighbors(idxToCoord(i)).map!(x => this.coordToIdx(x)).array;
  }
  
  void randomize()
  {
    foreach (i; 0..data.m * data.n)
    {
      data.data[i] = uniform(0, colors);
    }
  }
  
  void inflate(string path)
  {
    auto f = File(path);
    
    int i = 0;
    foreach (line; f.byLine)
    {
      foreach (int j, c; line)
      {
        data[i, j] = cast(int)(c - '0');
      }
      i += 1;
    }
  }
  
  auto toString() const
  {
    return
      iota(0, data.m)
      .map!(i => iota(0, data.n).map!(j => data[i, j]).map!(to!string).joiner)
      .joiner("\n");
  }
}

auto shift(T)(ref T[] arr)
{
  auto x = arr[0];
  arr = arr[1..$];
  return x;
}

struct Island
{
  int color;
  int[] elements;
  
  alias elements this;
}

auto findIslands(Board board)
{
  auto visited = new bool[board.size];
  Island[] islands = [];
  
  foreach (int i; 0..board.size)
  {
    if (visited[i]) continue;
    
    auto queue = [i];
    
    auto color = board.data[i];
    
    int[] island = [];
    
    while (queue.length > 0)
    {
      auto nx = queue.shift;
      
      if (visited[nx]) continue;
      
      if (color == board.data[nx])
      {
        visited[nx] = true;
        island ~= nx;
        queue ~= board.neighbors(nx);
      }
    }
    
    island = island.sort.uniq.array;
    
    islands ~= Island(color, island);
  }
  
  return islands;
}

auto islandsAdjacency(Board board, Island[] islands)
{
  auto adjacency = new int[][islands.length];
  
  auto idxmap = new int[board.size];
  
  foreach (int i, island; islands)
  {
    foreach (elem; island)
    {
      idxmap[elem] = i;
    }
  }
  
  foreach (i, island; islands)
  {
    int[] friends = [];
    
    foreach (elem; island)
    {
      foreach (neigh; board.neighbors(elem))
      {
        if (island.color == board.data[neigh]) continue;
        
        friends ~= idxmap[neigh];
      }
    }
    
    adjacency[i] = friends.sort.uniq.array;
  }
  
  return adjacency;
}

auto zipWith(alias f, Ranges...)(Ranges ranges)
{
  return zip(ranges).map!f;
}

struct NatSet
{
  int count;
  bool[] table;
  
  this(const ref NatSet ns)
  {
    count = ns.count;
    table = ns.table.dup;
  }
  
  this(int n)
  {
    count = 0;
    table = new bool[n];
  }
  
  this(int n, int[] arr)
  {
    this(n);
    insert(arr);
  }
  
  private void recount()
  {
    count = cast(int)table.count!(x => x);
  }
  
  auto contains(int n)
  {
    return table[n];
  }
  
  void insert(int n)
  {
    if (!table[n])
    {
      count += 1;
    }
    
    table[n] = true;
  }
  
  void insert(int[] arr)
  {
    foreach (x; arr)
    {
      table[x] = true;
    }
    
    recount;
  }
  
  void insert(NatSet ns)
  {
    foreach (i, x; ns.table)
    {
      table[i] |= x;
    }
    
    recount;
  }
}

auto isSubsetOf(const ref NatSet lhs, const ref NatSet rhs)
{
  foreach (x, y; lockstep(lhs.table, rhs.table))
  {
    if (x && !y)
    {
      return false;
    }
  }
  
  return true;
}

struct SolveState
{
  NatSet domain;
  int[] border;
  int[] steps;
}

auto solve(Board board)
{
  auto islands = board.findIslands;
  auto adjacency = board.islandsAdjacency(islands);
  
  auto level = [SolveState(NatSet(board.size, [0]), adjacency[0], [])];
  
  while (true)
  {
    SolveState[] next = [];
    
    foreach (state; level)
    {
      foreach (color; 0..board.colors)
      {
        auto domain = NatSet(state.domain);
        int[] border = [];
        
        foreach (friend; state.border)
        {
          if (islands[friend].color == color)
          {
            domain.insert(friend);
            
            foreach (poop; adjacency[friend])
            {
              if (!domain.contains(poop))
              {
                border ~= poop;
              }
            }
          }
          else
          {
            border ~= friend;
          }
        }
        
        if (state.domain.count == domain.count)
        {
          continue;
        }
        
        auto steps = state.steps ~ color;
        
        if (domain.count == islands.length)
        {
          return steps;
        }
        
        border = border.sort.uniq.array;
        
        auto child = SolveState(domain, border, steps);
        
        next ~= child;
      }
    }
    
    assert(next.length > 0);
    
    SolveState[] reduced = [];
    
    next.sort!"a.domain.count < b.domain.count";
    
    foreach (i; 0..next.length)
    {
      bool skip = false;
      
      foreach (j; i+1..next.length)
      {
        if (next[i].domain.isSubsetOf(next[j].domain))
        {
          skip = true;
          break;
        }
      }
      
      if (!skip)
      {
        reduced ~= next[i];
      }
    }
    
    level = reduced;
  }
}

void main(string[] args)
{
  auto p = args[1..$].map!(x => x.parse!int).array;
  
  auto board = Board(p[0], p[1], p[2]);
  //board.randomize;
  board.inflate("board.txt");
  
  board.toString.writeln;
  
  board.solve.writeln;
}