OK I solved the problem, but I haven't computed the asymptotic complexity.
I did it through Dynamic Progamming, where I defined the problem recursively, and also adding a culling criteria for a good speedup.
Here is the recursive problem statement:
Find the smallest fencing set in a such that there is no path from a startArea to a border.
The recursive problem is provided with:
- a
grid containing natural, pre-existing walls
- a
startArea
- a
Border definition
- a pre-existing set of
fences that were placed and cannot be removed
- a maximum number of fences
N
Return the following:
- If a fencing is found, return a
List of the fences
- If no fences are required, return an
empty list
- If the fence size must exceed
N walls, return <invalid> (e.g. null)
The solution to this statement was done using this observation:
Any fencing should contain at least one wall on the optimal path from the start area to the border (Otherwise, that path would be valid and be used to escape)
Therefore, a way to solve the recursive problem statement is as follows:
Initialize the recursive algorithm by providing:
- The initial world
- The startArea,
- The border definition (e.g. cell must be on the frontier of the grid)
- An empty list of initial fences
- A maximum number of fences set to
Positive_Infinity (no constraint)
Then recurse as follows:
- Generate the shortest
path from startArea to the border without passing through existing fences
- If no path leads to the exit, return the pre-defined
fences
- Rationale: the path is blocked, the existing fencing is sufficient, no need to add any
- If the pre-defined
fences have at least Nelements, return <invalid>
- Rationale: the pre-defined fences are insufficient, so at least
N+1fences would be required. Since a solution with N fences is known to exist, no need to investigate further
- Initialize
bestLength as the input maximum number of fences N as
- Initialize
bestPath as ìnvalid
- Iterate over each
location along the path (excluding cells that are in the startArea, which I assume cannot be walled off)
- generate a solution to the recursive problem as follows:
- the input
grid containing natural, pre-existing walls
- the input
startArea
- the input
Border definition
- the pre-existing set of
fences plus the current location
- the maximum number of fences
bestLength
- If the solution is
<invalid>, continue iterating
- If the solution exists
- Store it as
bestPath
- Update
bestLength its length
- If the solution length is
N+1 return it
- Return
bestPath
Basically, we're walling the best paths as we find them. As we wall on, the path changes and we wall that.
The best bit IMO is the culling mechanism, similar to a beta-pruning.
Dirty complexity analysis (The grid is NxN):
- The path has a length
N, we're iterating over its length.
- Each recursive iteration creates a path of length N (normally it's longer, but I'll ignore that). Thanks to culling I'll make this a complexity of
log(N) only
- At each step we're performing BFS so
N.log(N)
Total Complexity: N².log(N)²` (maybe? I don't know what I'm doing)
Here's a Java version of it:
MinimalFenceSolver.java (main class)
The problem is constructed in the main, and solved is static methods.
public class MinimalFenceSolver {
public static final Predicate<Location> borderDetector = loc -> ((GridWorld.GridLocation)loc).isBorder();
public static void main(String[] argc){
GridWorld world = new GridWorld(10, 10, 0);
// Find best fence
List<Location> startArea = new ArrayList<>();
startArea.add(world.at(5, 4));
findBestFence(world, startArea);
}
private static List<Location> findBestFence(GridWorld world, List<Location> startArea) {
List<Location> bestFence = findBestFenceRec(world, startArea, new ArrayList<>(), Integer.MAX_VALUE);
return bestFence;
}
private static List<Location> findBestFenceRec(GridWorld world, List<Location> startArea, List<Location> fencePrefix, int bestLengthYet) {
List<Location> bestFence = null;
int bestLength = bestLengthYet;
// Iterate
World fencedWorld = world.withWall(fencePrefix);
Path shortestPath = EscapePathfinder.begin(fencedWorld).setStart(startArea).setEnd(borderDetector).solve();
if(!shortestPath.exists()){
return fencePrefix;
}
if(fencePrefix.size() >= bestLength){
return null; // Culling
}
for (Location loc : shortestPath.fullPath()) {
if(!fencePrefix.contains(loc) && !startArea.contains(loc)){
List<Location> newfence = new ArrayList<>(fencePrefix);
newfence.add(loc);
List<Location> bestChild = findBestFenceRec(world, startArea, newfence, bestLength);
if(bestChild != null){
if(bestFence == null || bestChild.size() < bestLength) {
bestFence = bestChild;
bestLength = bestChild.size();
}
}
}
}
return bestFence; // null if no fence found
}
}
World.java interface for a world definition
public interface World {
Location at(int i, int j);
/**
* Removes walled Locations in the input, return the result
* @param neighbours (untouched)
* @return a List of Locations, none of which has any wall in it
*/
List<Location> noWalls(List<Location> neighbours);
}
Location.java interface
public interface Location {
CellType getType();
List<Location> neighbours();
}
CellType.java enum
public enum CellType {
WALL, EMPTY
}
GridWorld.java an implementation of a World that lives on a Grid
Contains its own Location implementation. Has the ability to be temporarily decorated with additional fences using the GridWorldWithWall subclass.
public class GridWorld implements World{
private final GridLocation[][] world;
final int nx;
final int ny;
public GridWorld(int nx, int ny, long seed){
this.nx = nx;
this.ny = ny;
Random rand = new Random(seed);
world = new GridLocation[nx][ny];
for(int i=0; i<nx; i++){
for(int j=0; j<ny; j++){
CellType locationType = rand.nextBoolean() ? CellType.EMPTY: CellType.WALL;
world[i][j] = new GridLocation(locationType, i, j);
}
}
}
public GridLocation at(int i, int j){
return world[(i+nx) % nx][(j+ny) % ny];
}
public String toString(){
StringBuilder builder = new StringBuilder();
for(int i=0; i<nx; i++){
for(int j=0; j<ny; j++){
builder.append(world[i][j].type == CellType.WALL ? "#" : ".");
}
builder.append("\n");
}
return builder.toString();
}
private static final int[][] offsets = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public class GridLocation implements Location{
private final CellType type;
private final int i;
private final int j;
public GridLocation(CellType type, int i, int j) {
super();
this.type = type;
this.i = i;
this.j = j;
}
@Override
public CellType getType() {
return type;
}
@Override
public List<Location> neighbours() {
List<Location> result = new ArrayList<>();
for(int[] offset: offsets){
result.add(GridWorld.this.at(i + offset[0], j + offset[1]));
}
return result;
}
public boolean isBorder(){
return i==0 || j==0 || i==nx-1 || j==ny-1;
}
public String toString(){
return (type == CellType.WALL ? "#" : ".") + "(" + i + ", " + j + ")";
}
public boolean equals(Object obj){
if(!(obj instanceof GridLocation)){
return false;
} else {
GridLocation other = (GridLocation) obj;
return other.i == this.i && other.j == this.j;
}
}
}
@Override
public List<Location> noWalls(List<Location> neighbours) {
return neighbours.stream().filter(cell -> cell.getType()!=CellType.WALL).collect(Collectors.toList());
}
public World withWall(List<Location> walls) {
return new GridWorldWithWall(walls);
}
private class GridWorldWithWall implements World {
public List<Location> walls;
public GridWorldWithWall(List<Location> walls) {
this.walls = walls;
}
@Override
public Location at(int i, int j) {
return new LocationWithWalls(GridWorld.this.at(i, j));
}
@Override
public List<Location> noWalls(List<Location> neighbours) {
List<Location> noWalls = GridWorld.this.noWalls(neighbours);
noWalls.removeAll(walls);
return noWalls;
}
private class LocationWithWalls implements Location{
private final GridLocation location;
public LocationWithWalls(GridLocation location) {
this.location = location;
}
@Override
public CellType getType() {
if(GridWorldWithWall.this.walls.contains(location)) {
return CellType.WALL;
}
return location.getType();
}
@Override
public List<Location> neighbours() {
List<Location> neighbours = location.neighbours();
neighbours().removeAll(walls);
return neighbours;
}
}
}
}
Pathfinder.java (Interface)
This is an overkill fluent interface in case you want to try other solvers, if you manage to make a good heuristic for the border, a-Star can be used here
public interface Pathfinder {
public static interface PathStartSetter {
PathEndSetter setStart(Iterator<? extends Location> startSupplier, Predicate<Location> startTester);
default PathEndSetter setStart(final Location start){
return setStart(
new Iterator<Location>() {
boolean provided = false;
@Override
public boolean hasNext() {
return !provided;
}
@Override
public Location next() {
if(provided){
return null;
} else {
provided = true;
return start;
}
}
},
loc -> loc.equals(start)
);
}
default PathEndSetter setStart(final List<Location> start){
return setStart(start.iterator(),
loc -> start.contains(loc)
);
}
}
public static interface PathEndSetter{
public PathSolver setEnd(Predicate<Location> endTester);
default PathSolver setEnd(final Location end){
return setEnd(loc -> loc.equals(end));
}
default PathSolver setEnd(final List<Location> end){
return setEnd(loc -> end.contains(loc));
}
}
public static interface PathSolver{
public Path solve();
}
public static interface Path{
List<Location> fullPath();
Location pathAt(int step);
public boolean exists();
}
public static class NoPath implements Path {
@Override
public List<Location> fullPath() {
return null;
}
@Override
public Location pathAt(int step) {
return null;
}
@Override
public boolean exists() {
return false;
}
}
}
Dijkstra.java (The Typical BFS solver)
Feel free to skip reading it, it's vanilla dijkstra, but it does implement my convoluted Pathfinder interface
public class Dijkstra implements Pathfinder{
public static DijkstraStartSetter begin(World world) {
return new DijkstraStartSetter(world);
}
public static class DijkstraStartSetter implements PathStartSetter {
private final World world;
public DijkstraStartSetter(World world) {
this.world = world;
}
public DijkstraEndSetter setStart(Iterator<? extends Location> startSupplier, Predicate<Location> startTester) {
return new DijkstraEndSetter(world, startSupplier, startTester);
}
}
public static class DijkstraEndSetter implements PathEndSetter{
private final World world;
private final Iterator<? extends Location> startSupplier;
private final Predicate<Location> startTester;
public DijkstraEndSetter(World world, Iterator<? extends Location> startSupplier, Predicate<Location> startTester) {
this.world = world;
this.startSupplier = startSupplier;
this.startTester = startTester;
}
public DijkstraSolver setEnd(Location end){
return new DijkstraSolver(world, startSupplier, startTester, end);
}
public DijkstraSolver setEnd(Predicate<Location> endTester){
return new DijkstraSolver(world, startSupplier, startTester, null);
}
}
public static class DijkstraSolver implements PathSolver{
private final World world;
private final Iterator<? extends Location> startSupplier;
private final Predicate<Location> startTester;
private final Location end;
public DijkstraSolver(World world, Iterator<? extends Location> startSupplier, Predicate<Location> startTester, Location end) {
this.world = world;
this.startSupplier = startSupplier;
this.startTester = startTester;
this.end = end;
}
public Path solve(){
Queue<Location> open = new LinkedList<>();
List<Location> closed = new ArrayList<>();
Map<Location, Location> parents = new HashMap<>();
while (startSupplier.hasNext()) {
open.add(startSupplier.next());
}
while(!open.isEmpty()){
Location current = open.remove();
closed.add(current);
List<Location> neighbours = world.noWalls(current.neighbours());
for (Location n : neighbours) {
if(open.contains(n) || closed.contains(n)) {
continue;
}
open.add(n);
parents.put(n, current);
if(n == end){
return makePath(parents);
}
}
}
return new NoPath();
}
private Path makePath(Map<Location, Location> parents) {
StandardPathBuilder path = StandardPath.begin();
Location current = end;
while(!startTester.test(current)){
path.add(current);
current = parents.get(current);
}
path.add(current);
return path.buildReverse();
}
}
}
Sorry for the amazingly long post and over-engineered solution! I just loved the Question so much I got carried away.
