Instructions
Requirements and Specifications
Source Code
/**
* CS4102 Spring 2022 -- Unit D Programming
*********************************
* Collaboration Policy: You are encouraged to collaborate with up to 3 other
* students, but all work submitted must be your own independently written
* solution. List the computing ids of all of your collaborators in the comment
* at the top of your java or python file. Do not seek published or online
* solutions for any assignments. If you use any published or online resources
* (which may not include solutions) when completing this assignment, be sure to
* cite them. Do not submit a solution that you are unable to explain orally to a
* member of the course staff.
*********************************
* Your Computing ID:
* Collaborators:
* Sources: Introduction to Algorithms, Cormen
**************************************/
import java.io.File;
import java.util.*;
public class TilingDino {
private static class Edge {
private final int from;
private final int to;
private int capacity;
public Edge(int from, int to, int capacity) {
this.from = from;
this.to = to;
this.capacity = capacity;
}
}
private Object[] ff(Edge[][] graph, Map<Integer, Location> map) {
int source = 0;
int target = graph.length - 1;
int flow = 0;
List<Edge> path = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
visited.add(source);
while (dfs(graph, source, target, path, visited)) {
int min = Integer.MAX_VALUE;
for (Edge e : path) {
if (e.capacity < min) {
min = e.capacity;
}
}
flow += min;
for (Edge e : path) {
graph[e.from][e.to].capacity -= min;
graph[e.to][e.from].capacity += min;
}
path.clear();
visited.clear();
visited.add(source);
}
List<Edge> edges = new ArrayList<>();
for (int i = source + 1; i<target; i++) {
Location location = map.get(i);
if (!location.isEven()) {
continue;
}
for (int j = source + 1; j<target; j++) {
if (graph[i][j] == null) {
continue;
}
else {
if (graph[i][j].capacity == 0) {
edges.add(graph[i][j]);
}
}
}
}
return new Object[]{flow, edges};
}
private boolean dfs(Edge[][] graph, int curr, int target, List<Edge> path, Set<Integer> visited) {
if (curr == target) {
return true;
}
for (int i = 0; i <= target; i++) {
if (!visited.contains(i) && graph[curr][i] != null && graph[curr][i].capacity > 0) {
visited.add(i);
path.add(new Edge(curr, i, graph[curr][i].capacity));
boolean result = dfs(graph, i, target, path, visited);
if (result) {
return true;
}
path.remove(path.size() - 1);
}
}
return false;
}
/**
* This is the method that should set off the computation
* of tiling dino. It takes as input a list lines of input
* as strings. You should parse that input, find a tiling,
* and return a list of strings representing the tiling
*
* @return the list of strings representing the tiling
*/
public List<String> compute(List<String> fileLines) {
List<String> result = new ArrayList<>();
int rows = fileLines.size();
int cols = fileLines.get(0).length();
char[][] map = new char[rows][cols];
for (int i = 0; i<rows; i++) {
map[i] = fileLines.get(i).toCharArray();
}
Map<Location, Integer> mapping = new HashMap<>();
Map<Integer, Location> rMapping = new HashMap<>();
int counter = 0;
int evens = 0;
int odds = 0;
for (int i = 0; i<rows; i++) {
for (int j = 0; j<cols; j++) {
if (map[i][j] == '#') {
counter++;
Location location = new Location(i, j);
mapping.put(location, counter);
rMapping.put(counter, location);
if (location.isEven()) {
evens++;
}
else {
odds++;
}
}
}
}
if (evens != odds) {
result.add("impossible");
}
else {
Edge[][] graph = new Edge[counter+2][counter+2];
for (int i = 1; i<=counter; i++) {
Location loc = rMapping.get(i);
if (loc.isEven()) {
graph[0][i] = new Edge(0, i, 1);
graph[i][0] = new Edge(i, 0, 0);
Location upLocation = new Location(loc.row-1, loc.col);
if (mapping.containsKey(upLocation)) {
int index = mapping.get(upLocation);
graph[i][index] = new Edge(i, index, 1);
graph[index][i] = new Edge(index, i, 0);
}
Location downLocation = new Location(loc.row+1, loc.col);
if (mapping.containsKey(downLocation)) {
int index = mapping.get(downLocation);
graph[i][index] = new Edge(i, index, 1);
graph[index][i] = new Edge(index, i, 0);
}
Location leftLocation = new Location(loc.row, loc.col-1);
if (mapping.containsKey(leftLocation)) {
int index = mapping.get(leftLocation);
graph[i][index] = new Edge(i, index, 1);
graph[index][i] = new Edge(index, i, 0);
}
Location rightLocation = new Location(loc.row, loc.col+1);
if (mapping.containsKey(rightLocation)) {
int index = mapping.get(rightLocation);
graph[i][index] = new Edge(i, index, 1);
graph[index][i] = new Edge(index, i, 0);
}
}
else {
graph[counter+1][i] = new Edge(counter+1, i, 0);
graph[i][counter+1] = new Edge(i, counter+1, 1);
}
}
Object[] flow = ff(graph, rMapping);
int size = (int)flow[0];
if (size == evens) {
List<Edge> edges = (List<Edge>)flow[1];
for (Edge e : edges) {
Location evenLoc = rMapping.get(e.from);
Location oddLoc = rMapping.get(e.to);
result.add(oddLoc.col + " " + oddLoc.row + " " + evenLoc.col + " " + evenLoc.row);
}
}
else {
result.add("impossible");
}
}
return result;
}
private static class Location {
int row;
int col;
Location(int row, int col) {
this.row = row;
this.col = col;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Location location = (Location) o;
return row == location.row && col == location.col;
}
@Override
public int hashCode() {
return Objects.hash(row, col);
}
public boolean isEven() {
return (row + col) % 2 == 0;
}
}
}