import java.awt.image.BufferedImage;
import java.io.IOException;
import java.util.*;
import java.util.stream.Collectors;
import javax.imageio.ImageIO;
//to avoid autoboxing, use Arrays instead.
public class Graph {
private Map<Integer, Set<Integer>> adj;
private BufferedImage image;
private int hits = 0;
public static void main(String[] args) throws IOException {
Graph G = new Graph();
CC cc = G.new CC(G);
System.out.println("connection count = " + cc.count());
System.out.println("total pixel with dots = " + G.hits);
System.out.println("there is one star with 2 pixels, which is formed by 2 adjacent 1 pixel stars, therefore 99 instead of 100");
cc.id.values().stream().collect(
Collectors.groupingBy(i -> i, Collectors.counting()))
.values().stream().filter(i -> !(i == 1 || i == 4 || i == 9)).forEach(System.out::println);
}
public Graph() throws IOException {
this.image = ImageIO.read(Graph.class
.getResource("night-sky.png")); //the image
int width = image.getWidth();
int height = image.getHeight();
System.out.println("width=" + width + ", height=" + height);
adj = new HashMap<>();
for (int v = 0; v < width * height; v++) {
if(getBrightness(image, v) != 0) {
adj.put(v, new HashSet<>());
}
}
for (int i = 0; i < width * height; i++) { // Add edges.
int row = i / width;
int col = i % width;
if(getBrightness(image, i) == 0) {
continue;
}
hits ++;
for (int rowRange = -1; rowRange <= 1; rowRange++) {
for (int colRange = -1; colRange <= 1; colRange++) {
int j = (row + rowRange) * width + col + colRange;
boolean invalid = rowRange * colRange != 0
|| (rowRange == 0 && colRange == 0)
|| row + rowRange < 0 || col + colRange < 0
|| row + rowRange >= height
|| col + colRange >= width;
if (!invalid && getBrightness(image, j) != 0) {
addEdge(i, j);
}
}
}
}
}
private static int getBrightness(BufferedImage image, int index) {
int width = image.getWidth();
int row = index / width;
int col = index % width;
int p = image.getRGB(col, row);
int r = (p >> 16) & 0xff;
int g = (p >> 8) & 0xff;
int b = p & 0xff;
return r + g + b;
}
public int V() {
return adj.size();
}
public int E() {
return (int)adj.values().stream().flatMap(i -> i.stream()).count();
}
public void addEdge(int v, int w) {
if(adj.get(v) == null) {
System.out.println("v = " + v + ", w = " + w);
}
adj.get(v).add(w);
adj.get(w).add(v);
}
public Map<Integer, Set<Integer>> getAdj() {
return this.adj;
}
class CC {
private Set<Integer> marked = new HashSet<>();
private Map<Integer, Integer> id = new HashMap<>();
private int count;
public CC(Graph G) {
for (int s : G.getAdj().keySet()) {
if (!marked.contains(s)) {
dfs(G, s);
count++;
}
}
}
private void dfs(Graph G, int v) {
marked.add(v);
id.put(v, count);
for (int w : G.getAdj().get(v))
if (!marked.contains(w))
dfs(G, w);
}
public int count() {
return count;
}
}
}
