Skip to main content

Day 3: No Matter How You Slice It

· 2 min read

First problem with a more complicated input and problem. I solved these by making a class defining a claim (containing the id, position, size) and another class defining the canvas (containing a matrix of claims touching each square inch). The claims are created by parsing each line with a regular expression.

My first big dilemma was between using a mathematical approach to find the regions of conflict between each pair of claim and using a matrix and just record everything in a matrix. I checked the input for the problem and noticed there was over 1200 claims with areas under 100x100 inches. Calculating the regions for all the pairs requires O(n²) calculations which would amount to around 1.5M calculations, while using a matrix would require O(nm²) updates to the matrix which would be at most 12M. Evaluating the individual calculations at a larger cost than an update, I opted for the matrix solution as it seemed easier to solve the first part of the solution.

Upon reading the first part of the problem, I started with a simple matrix of integers counting the number of claims on each square. The solution was then to count the number of squares where there was only one claim.

When I arrived at the second part of the problem, I noticed my solutions wouldn't work as is, but the changes wouldn't be too large. I started by changing my matrix of integers to a matrix of lists of claims, allowing me to specify which claim was touching which square. Once this was done (and my first part was still working), I added some data in the claims to know which claim it conflicted with and how many claims it was in conflict with. With that, I simply returned the identifier of the claim that had no conflicts.