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;

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 =;
        int x1 = Integer.parseInt(;
        int y1 = Integer.parseInt(;
        int w = Integer.parseInt(;
        int h = Integer.parseInt(;
        int x2 = x1 + w;
        int y2 = y1 + h; = 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));

public String toString() {
    return String.format("#%s @ %d,%d: %dx%d",, 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 =
                    .filter(v -> v.size() > 1)


    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<>());

    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");

    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) {


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

Show Comments

Get the latest posts delivered right to your inbox.