Advent of Code 2018: Day 3

Part 1

Part 1 involves taking a collection of "claims" which are rectangles, and calculating how many points exist in at least two claims.

My solution is slow because of creating a Point for each coordinate. It could be sped up by replacing the Point with something lighter. It could also be sped up by doing a first sweep through the claims to find any pairs which overlap (using an appropriate data structure such as an R-Tree) and then calculating the overlap between overlapping pairs. The code for that is a bit more complicated so I didn't bother... Maybe I'll come back to it sometime.

Part 2

Part 2 just requires us to find the claim which does not overlap any others. For this I can reuse most of the code from part 1. I get all claims which have at least one overlapping claim, and then remove that from all claims.

import java.awt.;
import java.util.
;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;

class Claim {
private final String id;
private final Point p1;
private final Point p2;

// Example: #188 @ 397,394: 20x26s
private static final Pattern CLAIM_STRING_PATTERN = Pattern.compile("#(\\d+) @ (\\d+),(\\d+): (\\d+)x(\\d+)");

Claim(String claimString) {
    Matcher matcher = CLAIM_STRING_PATTERN.matcher(claimString);
    if (matcher.find()) {
        String id = matcher.group(1);
        int x1 = Integer.parseInt(matcher.group(2));
        int y1 = Integer.parseInt(matcher.group(3));
        int w = Integer.parseInt(matcher.group(4));
        int h = Integer.parseInt(matcher.group(5));
        int x2 = x1 + w;
        int y2 = y1 + h;

        this.id = id;
        this.p1 = new Point(x1, y1);
        this.p2 = new Point(x2, y2);
    } else {
        throw new IllegalArgumentException(String.format("Not a valid claimString: %s", claimString));
    }
}

@Override
public String toString() {
    return String.format("#%s @ %d,%d: %dx%d", this.id, p1.x, p1.y, p2.x - p1.x, p2.y - p1.y);
}


List<Point> calculateContainedPoints() {
    List<Point> containedPoints = new ArrayList<>();

    for (int x = p1.x; x < p2.x; x++) {
        for (int y = p1.y; y < p2.y; y++) {
            containedPoints.add(new Point(x, y));
        }
    }

    return containedPoints;
}

}

class OverlapDetector {
/** Count the number of points which exist in at least two claims. */
static int countOverlappingPoints(Collection claims) {
return (int) calculatePointsToClaim(claims).values().stream()
.filter(o -> o.size() > 1).count();
}

/** Collect all claims which do not overlap any other claims. */
static Collection<Claim> findNonOverlappingClaims(Collection<Claim> claims) {
    Set<Claim> nonOverlappingClaims = new HashSet<>(claims);

    Set<Claim> overlappingClaims =
            calculatePointsToClaim(claims).values().stream()
                    .filter(v -> v.size() > 1)
                    .flatMap(Collection::stream)
                    .collect(Collectors.toSet());

    nonOverlappingClaims.removeAll(overlappingClaims);

    return nonOverlappingClaims;
}

private static Map<Point, Set<Claim>> calculatePointsToClaim(Collection<Claim> claims) {
    Map<Point, Set<Claim>> overlaps = new HashMap<>();

    for (Claim claim : claims) {
        for (Point point : claim.calculateContainedPoints()) {
            overlaps.putIfAbsent(point, new HashSet<>());
            overlaps.get(point).add(claim);
        }
    }

    return overlaps;
}

}

public class Claims {
public static void main(String[] args) {
if (args.length < 1) {
System.err.println("Error: First argument must be claims string");
System.exit(1);
}

    String claimsString = args[0];
    Collection<Claim> claims = parseClaimsString(claimsString);

    int overlaps = OverlapDetector.countOverlappingPoints(claims);
    System.out.println(String.format("Counted %s overlapping coordinates", overlaps));

    for (Claim nonOverlappingClaim : OverlapDetector.findNonOverlappingClaims(claims)) {
        System.out.println(String.format("Non overlapping claim: %ss", nonOverlappingClaim));
    }
}

private static Collection<Claim> parseClaimsString(String claimsString) {
    return Arrays.stream(claimsString.split("\n"))
            .map(Claim::new)
            .collect(Collectors.toList());
}

}

Advent Of Code runs until December 25. You should get involved!

Show Comments

Get the latest posts delivered right to your inbox.