Advent of Code: 2025 Day 9

Visualizing a difficult problem.

Day 9 Completed

If you have never heard of Advent of Code (AOC), check it out. I also wrote a post with a detailed explanation of what it is, why to do it, and lessons learned from the last several years of doing it.

Day 9 challenged me. Part I was very simple. Part II made me visualize the data and try many approaches before seeking help. I learned a few new techniques for polygons and some visualization techniques with C#. I almost skipped this post because I wasn’t super successful. I decided to write the details I did understand.

This guide will walk through my learnings and may show small snippets of a solution. I will avoid wholesaling solutions in these posts. My working solutions live here if you want more details.

Day 9 First Thoughts

Reading the example causes me to consider a few things.

• Why is it col, row (y, x)?
• There has to be a math solution, shape space
• Part II might get wild. What about overlaps? They don’t matter in Part I.
• The numbers are large enough to suggest a long
• If you try to map/visualize the ranges that are large, that will take a lot of space.

EASTER EGG FOUND: Slides are fun.

Processing Inputs

processing the input

This part was very simple. The type of Result is *List*<*System*.*Drawing*.*Point*>;.

On a previous day, I wrote my own custom Point class for a 3D space. Somehow, I missed that there is a System.Drawing.Point object. That wouldn’t have mattered since I needed 3 points, but I ended up having to namespace that custom Point object and using the fully qualified version here.

In hindsight, I could have extended this object or provided a similar example; it is a struct. One thing I learned is that you can’t inherit a struct as a base class.

I learned that structs:

• Provide a value type (copy by value, not reference).
• Always provide a parameterless constructor
• They are stored on the stack, not the heap, for memory
• Can’t inherit from other Structs other than System.ValueType
• They can implement an interface

When to use:

• Small, immutable data
• When you want the value semantics
• Performance-sensitive code (less heap)

I had missed adding the namespace 'Shared'; to my custom class, so it was added to the global namespace.

System.Drawing.Point comes from a built-in library that appears to have had limited support in .NET Core on Mac. I spent too much time looking for alternatives due to a Cursor suggestion when I got to Part II and wanted to visualize the path.

TIP: Using Advent of Code to learn about a language or its features is not a straight path. I didn’t spend much time going deep on any topic. I could have just dealt with this conflict and hand-built another 2D point. Or ignored namespacing in my original. I almost did, since that was a previous day’s puzzle. I chose a more iterative path, as long as it doesn’t block me.

dotnet add package --project dotnet/y2025/y2025.csproj System.Drawing.Common --version 10.0.1

I will go over some of the rendering I did with SVG. It was a detour from solving the puzzle, but it turned out to be useful.

Solving for Part I

Part I was trivial. I created a list of all possible pairs of points and returned a tuple of (p1, p2, area). Then it was simply sort by area and pick the largest one.

selecting all pairs and building a tuple

*.SelectMany*((*point1*, *i*) => pointsToCheck.*Skip*(*i* + 1).*Select*((*point2*) => (*point1*, *point2*))) takes the list and a copy of the list from the current position + 1, and returns all possible pairs.

*.Select*(*pair* => (p1: *pair*.point1, p2: *pair*.point2, area: *GetArea*(*pair*.point1, *pair*.point2))) return the tuple with the calculated area.

formula for the area calculation

The area calculation required a very small step to find the width and length. Because the puzzle specifies opposing corners, we have all we need.

We take the absolute value of subtracting the x and y values to find the delta (width or height). Getting the absolute value keeps me from worrying about which x or y is bigger. I add 1 because it’s inclusive; see the puzzle example below, we are allowed to have a single row or column. Effectively, each space is 1x1.

You can easily see the rest without seeing the code; it’s simple.

I originally had some filters to only select pairs where the x’s and y’x didn’t match (avoid a straight line, then I re-read the puzzle, and that was a valid case.

valid single row

The red tiles do have to be opposite corners. This is still true in Part II.

Did we overflow the int?

Yes, the individual numbers were safe enough; finding the area led to a silent overflow. This is something I need to remember to watch for in C#, the overflow is silent, just chops numbers, if I don’t check or catch issues, I wouldn’t know. I will likely use a checked exception in the future or default to long. I had an incorrect submission the first time due to this.

Passing Tests and Failed Runtime

I spent the most time on this after I made the part II tests pass, trivially from my part I, but my answers were incorrect. Something wasn’t right with the data or my approach or both.

What do we do on a real project when a test passes and the expected result is incorrect?

I usually take a step back and dig into my test cases to make sure they represent the problem correctly. Things to check:

• Mocking too much
• Sample sizes are too small
• Simply incorrect data

I don’t usually go this far during AOC, because in the past I spent too much time on test cases, and it made it harder to get the result, which I have a checker for. i.e., it’s a solved problem. If it’s not a solved problem and I need to ensure it’s always correct, the time on tests is worth it.

LESSON LEARNED: I have experienced this before with grid problems in Advent of Code; if the sample data isn’t a good representation of the input, it happens. Looking at the scale of the input, this is likely an over-simplified example. The best thing to do is to examine your data and the example data closely.

Visualizing Data

Inspecting Input

sample of top, middle, bottom

I missed this originally; the list is sorted. I originally looked at the top and bottom and thought they were random. The interesting part is what happens to why in the mid-range (middle of possible values), and what happens in the middle of the set?

The x’s are sorted in descending order to start. After some funkiness in the middle, it switches to ascending. 6 points in the middle break the pattern before switching direction. Y’s are mostly ascending as well, but this is broken around the median values, the center of the image.

There are straightish lines in the data. Lots of fuzziness around the edges, and something in the middle.

Compared to the example, the datasets are very different.

visualizing the example data

This led me to a simple solution for part II that worked on the example but not the real data.

works, for example, not the input data

The only difference from part I is that I calculate all 4 points of the rectangle and check that they are all in bounds. This only works for a rectangular boundary, and the fuzzy edges would wreck edge cases.

Let’s visualize our data.

Part I visualized

This explains a few things:

• Scale, I had to increase my linewidth by a factor of 1000 to even see the lines and labels
• There is a hole
• Edges are jagged, a pair of points might go inside, and outside the boundary
• The sort starts with the middle of the right side/outside edge, circling clockwise, to what I call a corner (start of the hole), filling in the hole, back to the left edge, then continuing clockwise to the start.
• I don’t know that the example data will help. It is possible to generalize a solution, but I didn’t want to spend time on that, so I wrote a separate method for the example.

starting area (outside edge)

I didn’t visualize part I originally; when I got to part II, I started with part I code and applied a visualization.

My next thought was that I learned ray casting, a technique to find where a line crosses boundaries, in the past. Maybe I could apply that technique. I am not certain if there is a simpler solution with this technique; the scale of the data made it a pain. I would have to check every point along the edges to find the hole.

I played with splitting the object in half and only processing one half to make it more viable, and still had issues.

I looked for several hints and came across a few. This graphic was very insightful.

https://www.reddit.com/r/adventofcode/comments/1ppwijf/2025_day_9_part_2_python_some_basic_code_narrowed/

I tried this approach, and I could get close to the top, but the code became too much to check both, and it was confusing. One commenter mentioned that this won’t always work, and it’s absolutely a shortcut based on the particular object. As you can see from my output, the split wasn’t clean, and I didn’t like the amount of code I had, so I bailed.

top half

bottom half, later attempts

This is where I applied the raycast to find maxY and minX.

I even played with splitting vertically and only choosing 1 point from each half. Many attempts were very incorrect or slow.

Along this journey, I got close to a working solution, slow but working, but it was all parallelograms. When I adjusted, my points were missing. Splitting the data in half wasn’t clean enough; I bailed on splitting the halves rather than finding a clean split.

parallegram

Rendering a Polygon

I had to dig a bit for a library to render an SVG. The first one I chose was a paid-only version with an eval for a few runs. I didn’t catch that until it stopped working. My original approach was hand-generating with help from the System.Drawing.Common library. I hit the Windows only wall fairly quickly.

I landed on VectSharp. It’s a really slick and simple library that lets you generate graphics with C#, and several output options, including SVG.

snippet of my simplified draw method

The setup of this graphic requires a zoom, which, because of what I did to achieve that, is called lineWidth.

The page adds equal padding. I commented out the viewport cropping, which was helpful for the halves.

The first thing I do is color green. This was to simplify layering, assuming later objects are added on top.

Then, for each point in the input, I draw a box big enough to be seen. Centered on the point. I also created a white rectangle with text so I could see the points. This became very helpful while exploring. I could open it in a browser and inspect the elements. Search for a coordinate and see where it landed.

Lastly (not shown), if a rectangle is passed in, draw that in blue. At one point, I was curious what all rectangles would look like and drew them all.

I had two polygon drawing methods: my first one and a simpler one. When I was exploring, I added a bunch of junk, so I had to simplify in the end.

The code can be found here: https://github.com/kaltepeter/aoc/blob/4a0d47e0112010290abb4006776bf89395db092d/dotnet/y2025/day_9/Day.cs#L504

My code in general for this day, as it stands, is hot garbage. I left the mess for future reference. In the future, I may want to revisit this problem and create a generalized solution so I can understand it better.

Solving for Part II

Before I walk through my solution. It’s important to call out. If you could not tell, I got stuck. I had to look through a few Reddit posts, and the visualizations helped. When people started talking about Coordinate Compression, that was something I had never done. I googled it and had a hard time finding a solid walkthrough of the basics.

LESSON LEARNED: Sometimes other hints can be misleading, unclear, or not enough for your data. Take each hint with a grain of salt and try to understand it.

This guide was most insightful for the basics. I still need to spend more time digesting it.

This walkthrough was helpful enough to get me over the basics of dealing with the puzzle. I didn’t follow their full solution; I was far enough along that, with my insight into using the corners, I could skip the full generalized solution.

This was one of those days that I spent a lot of time on a possible solution, got stuck, took a hint, got closer, but stuck, and repeated.

Approach:

• Start by compressing coordinates to a map, then get a list of all compressed points.
• Get the corners (shortcut)
• Start like part I, create all possible pairs, but use compressed coordinates
• Filter by pairs that are in any of the corners (shortcut). If you look at the image, 1 point has to be a corner; the compressed image makes it clearer.
• Check whether the edge is in bounds (compression helps the most here)
• Finish just like part I

Why compression?

There are two big reasons I think this was necessary:

• It made checking edges more doable. Less fuzziness on the edges
• It reduced what I had to check, greatly improving performance.

There was another technique I learned about, called prefix sum, that turned out not to be needed with my shortcut. It’s an interesting approach.

There is yet another shortcut here; I only had to check the verticals, based on the compressed image tapering.

Cursor generated compression

I had to have Cursor help me with the compression. I had already spent too much time on this puzzle and didn’t fully understand it at the time. This is an area to revisit for sure.

Part of my struggle was wanting to use a dictionary when most examples used arrays with index lookups, which would require maintaining a sort.

decompressing for the result and generating a SVG

I then decompress the found point and use that as the answer. I still calculated the area on the compressed points to sort and select the largest.

compressed SVG

This graphic shows my rendered compressed image. The edges are much nicer to deal with.

uncompresed edges

compressed edges

The edges are much nicer to deal with, and there are far fewer points.

Was compression necessary?

No. I couldn’t find a solution until I applied compression. After that, I did a run without compression, and it worked.

timing, top is compressed, bottom is uncompressed

Compressed after build runs at 1.2s and uncompressed at 28.52 for user timing. That's not horrible, but I get impatient, and compression clearly helps.

Summary of my Learning

C# collection expressions

• Collection expressions like [..input, ..corners] require a target type
• When used in method chains, the compiler can’t infer the type
• Solution: use input.Concat(corners) instead, which returns IEnumerable<T> and works with LINQ

Pair generation and filtering

• Fixed duplicate pairs: changed .Skip(1) to .Skip(i + 1)to avoid generating both (p1, p2) and (p2, p1)
• Coordinate compression: ensure comparisons use compressed points consistently
• Filtering logic: pairs where at least one point is in top corners OR bottom corners

Key C# concepts reinforced

• Type inference limitations with collection expressions
• LINQ methods: Concat(), SelectMany(), Where(), Skip()
• Coordinate compression: mapping original coordinates to compressed indices for grid operations

Rendering SVGs

• Use a library to render graphics; some won’t work on Mac/*Nix
• Visualizing results
• Intuition around visuals

Thanks for reading. If you find this helpful, leave claps. If there is something you would like to see more of, leave a comment.

References

[embed]Organizing types in namespaces - C# Learn how namespaces help you organize related types.learn.microsoft.com

[embed]How do you use System.Drawing in .NET Core? I've been doing .NET image processing since the beginning. In fact I wrote ...www.hanselman.com

[embed]The checked and unchecked statements - overflow-checking - C# reference Control the overflow-checking context. In a checked context, overflow causes an exception to be thrown. In an unchecked…learn.microsoft.com

[embed]Coordinate Compression Dealing with huge arrays and large numbers.medium.com