AoC15

// Class Coord
package helpers;

import java.util.ArrayList;
import java.util.Objects;

public class Coord implements Comparable<Coord> {
    public int x = 0;
    public int y = 0;

    public static final Coord UP = new Coord(0,-1);
    public static final Coord DOWN = new Coord(0,1);
    public static final Coord LEFT = new Coord(-1,0);
    public static final Coord RIGHT = new Coord(1,0);

    public Coord(int r, int c) {
        x = r;
        y = c;
    }

    public Coord(String s) {
        x = Integer.parseInt(s.split(",")[0].trim());
        y = Integer.parseInt(s.split(",")[1].trim());
    }

    public Coord() {
        x = 0;
        y = 0;
    }

    @Override
    public int hashCode() {
        return Objects.hash(y,x);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Coord other = (Coord) obj;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        return true;
    }

    public String toString() {
        return "(" + x + "," + y + ")";
    }

    //adds values of o to self
    public void sumSelf(Coord o) {
        x += o.x;
        y += o.y;
    }

    //returns a new coordinate that is the result of this + o
    public Coord sum(Coord o) {
        return new Coord(x + o.x, y + o.y);
    }

    //returns Manhattan distance to coord o
    public int dist(Coord o) {
        return Math.abs(x - o.x) + Math.abs(y - o.y);
    }

    //returns copy of self
    public Coord copy() {
        return new Coord(x,y);
    }

    //returns version with x and y swapped
    public Coord invert() {
        return new Coord(y,x);
    }

    public ArrayList<Coord> directNeighbors() {
        ArrayList<Coord> list = new ArrayList<Coord>();
        for(int yOff = -1; yOff < 2; yOff++) {
            for(int xOff = -1; xOff < 2; xOff++) {
                //if not diagonal or self
                if(xOff == 0 ^ yOff == 0) {
                    list.add(new Coord(x+xOff,y+yOff));
                }
            }
        }
        return list;
    }

    public ArrayList<Coord> allNeighbors() {
        ArrayList<Coord> list = new ArrayList<Coord>();
        for(int yOff = -1; yOff < 2; yOff++) {
            for(int xOff = -1; xOff < 2; xOff++) {
                //if not self
                if(!(xOff == 0 && yOff == 0)) {
                    list.add(new Coord(x+xOff,y+yOff));
                }
            }
        }
        return list;
    }

    //orders coordinates in left-to-right, top-to-bottom order
    @Override
    public int compareTo(Coord o) {
        if(this.equals(o))
            return 0;
        else if(o.y > this.y)
            return -1;
        else if(o.y < this.y)
            return 1;
        else
            return (o.x > this.x ? -1 : 1);
    }

    public Coord left() {
        return new Coord(y,-x);
    }

    public Coord right() {
        return new Coord(-y,x);
    }
}
// Class Range
package helpers;

import java.util.Objects;

public class Range {
    public int from = 0;
    public int until = 0;

    public Range(int fr, int un) {
        from = fr;
        until = un;
    }

    public Range(String s) {
        from = Integer.parseInt(s.split(",")[0].trim());
        until = Integer.parseInt(s.split(",")[1].trim());
    }

    public Range() {
        from = 0;
        until = 0;
    }

    @Override
    public int hashCode() {
        return Objects.hash(from,until);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Range other = (Range) obj;
        if (from != other.from)
            return false;
        if (until != other.until)
            return false;
        return true;
    }

    public String toString() {
        return "(" + from + "," + until + ")";
    }

}

// Main Class
import com.google.gson.Gson;
import helpers.Coord;
import helpers.Range;
import helpers.Tunnel;


import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class AdventOfCode {
    public static void main(String[] args) {
        ex15();

    }

    public static void ex15() {
        String[] inhalt;
        HashMap<Coord, Coord> sensorsToBeacons = new HashMap<>();
        Coord beac, sensor;
        int dist = 0;
        int highestX = 0, lowestX = Integer.MAX_VALUE;
        int highestY = 0, lowestY = Integer.MAX_VALUE;
        try {
            inhalt = Files.readString(Paths.get("./files/AoC/AoC15.txt")).split("\n");
        } catch (IOException e) {
            System.out.println("file error");
            return;
        }
        for (String zeile : inhalt) {
            sensor = new Coord(zeile.split(": closest beacon is at ")[0].replace("Sensor at x=", "").replace("y=", ""));
            beac = new Coord(zeile.split(": closest beacon is at ")[1].replace("x=", "").replace("y=", ""));
            sensorsToBeacons.put(sensor, beac);
            lowestX = Math.min(sensor.x, lowestX);
            lowestX = Math.min(beac.x, lowestX);
            lowestY = Math.min(sensor.y, lowestY);
            lowestY = Math.min(beac.y, lowestY);
            highestX = Math.max(sensor.x, highestX);
            highestX = Math.max(beac.x, highestX);
            highestY = Math.max(sensor.y, highestY);
            highestY = Math.max(beac.y, highestY);
            dist = Math.max(sensor.dist(beac), dist);
        }
        System.out.println("ex15: " + ex15_getNumberOfBeaconsNotPossibleForY(2000000, sensorsToBeacons));

        long t0 = System.currentTimeMillis();

        int minX = 0, maxX = 4_000_000;

        HashSet<Range> beaconsCantBeHere;
        for(int i = minX ; i <= maxX ; ++i) {
            beaconsCantBeHere = ex15_getBeaconPossible(i, minX, maxX, sensorsToBeacons);
            if(beaconsCantBeHere.size() > 0) {
                int untilMin = Integer.MAX_VALUE;
                for(Range beacons : beaconsCantBeHere) {
                    untilMin = Math.min(beacons.until, untilMin);
                }
                System.out.println("ex15_2: y: " + i + " - " + beaconsCantBeHere + " - " + ((long)(untilMin+1) * 4_000_000 + i));
            }
        }
        System.out.println("Time Used in millis: " + (System.currentTimeMillis() - t0));

    }

    public static int ex15_getNumberOfBeaconsNotPossibleForY(int rowToCheck, HashMap<Coord, Coord> sensorsToBeacons) {
        Coord beac;
        int dist, bss = 0;
        HashSet<Integer> beaconsCantBeHere = new HashSet<>();
        for(Coord sens : sensorsToBeacons.keySet()) {
            beac = sensorsToBeacons.get(sens);
            if(beac.y == rowToCheck) {
                beaconsCantBeHere.add(beac.x);
            }
            if(sens.y == rowToCheck) {
                beaconsCantBeHere.add(sens.x);
            }
        }
        bss = beaconsCantBeHere.size();
        for(Coord sens : sensorsToBeacons.keySet()) {
            beac = sensorsToBeacons.get(sens);
            dist = sens.dist(beac);
            int distToRow = Math.abs(sens.y - rowToCheck);
            if(distToRow > dist) {
                continue;
            }
            for(int i = 0 ; i <= (dist - distToRow) ; ++i) {
                beaconsCantBeHere.add(sens.x + i);
                beaconsCantBeHere.add(sens.x - i);
            }
        }
        return beaconsCantBeHere.size() - bss;
    }

    public static HashSet<Range> ex15_getBeaconPossible(int rowToCheck, int minX, int maxX, HashMap<Coord, Coord> sensorsToBeacons) {
        Coord beac;
        int dist;
        HashSet<Range> beaconsCantBeHere = new HashSet<>();
        for(Coord sens : sensorsToBeacons.keySet()) {
            beac = sensorsToBeacons.get(sens);
            if(beac.y == rowToCheck && (beac.x <= maxX) && (beac.x >= minX) ) {
                beaconsCantBeHere.add(new Range(beac.x, beac.x));
            }
            if(sens.y == rowToCheck && (sens.x <= maxX) && (sens.x >= minX) ) {
                beaconsCantBeHere.add(new Range(sens.x, sens.x));
            }
        }
        int min, max;
        for(Coord sens : sensorsToBeacons.keySet()) {
            beac = sensorsToBeacons.get(sens);
            dist = sens.dist(beac);
            int distToRow = Math.abs(sens.y - rowToCheck);
            if(distToRow > dist) {
                continue;
            }
            min = Math.max(Math.min(sens.x - (dist - distToRow), maxX), minX);
            max = Math.min(Math.max(sens.x + (dist - distToRow), minX), maxX);
            beaconsCantBeHere.add(new Range(min, max));
            beaconsCantBeHere = ex15_collapseHashSet(beaconsCantBeHere);
        }
        beaconsCantBeHere = ex15_collapseHashSet(beaconsCantBeHere);
        beaconsCantBeHere = ex15_collapseHashSet(beaconsCantBeHere);
        beaconsCantBeHere = ex15_collapseHashSet(beaconsCantBeHere);
        if(beaconsCantBeHere.size() > 1) {
            return beaconsCantBeHere;
        }
        return new HashSet<Range>();
    }

    public static HashSet<Range> ex15_collapseHashSet(HashSet<Range> beaconsCantBeHere) {
        HashSet<Range> newBeacons = new HashSet<>();
        HashSet<Range> toRemove = new HashSet<>();
        for(Range beacons : beaconsCantBeHere) {
            newBeacons.add(beacons);
            for (Range beaconsOther : beaconsCantBeHere) {
                if(beacons == beaconsOther) {
                    continue;
                }
                if(beacons.from <= (beaconsOther.until + 1) && (beacons.until + 1) >= beaconsOther.from) {
                    Range newBeacon = new Range(Math.min(beacons.from, beaconsOther.from), Math.max(beacons.until, beaconsOther.until));
                    newBeacons.add(newBeacon);
                    if(!newBeacon.equals(beacons)) {
                        toRemove.add(beacons);
                    }
                    if(!newBeacon.equals(beaconsOther)) {
                        toRemove.add(beaconsOther);
                    }
                }
            }
        }
        for(Range beacons : toRemove) {
            newBeacons.remove(beacons);
        }
        return newBeacons;
    }
}