Skip to content

Instantly share code, notes, and snippets.

@Garciat
Last active August 29, 2015 14:15
Show Gist options
  • Save Garciat/557299821af6d314b497 to your computer and use it in GitHub Desktop.
Save Garciat/557299821af6d314b497 to your computer and use it in GitHub Desktop.
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment