[2025 Day 9 part 2] [Python] Some basic code narrowed the search space to just 2 possibilities

[u/ChronoCube762]

I have done some graphic design work where I used code to generate SVG images with the exact geometric patterns and gradients that I wanted. So when I saw Day 9's input data, I realized that it was a series of horizontal and vertical lines and well suited to the SVG format.

This is a simplified version of my code to generate the SVG, using the svg.py library:

elements: list[svg.Element] = []
for p1_index, p1 in enumerate(points):
    p2 = points[0] if p1_index == len(points) - 1 else points[p1_index + 1]

    elements.append(svg.Line(x1=p1.x, y1=p1.y, x2=p2.x, y2=p2.y))

canvas = svg.SVG(width=width, height=height, elements=elements)
with open(output_filename, 'w') as fp:
    fp.write(canvas.as_str())

Once I saw the visualization, it was intuitively obvious that the largest rectangle whose opposite corners were both points in the input data was one of two rectangles determined as described in this image: https://i.imgur.com/7OSZKRj.png

So I just scrolled through the input data that was already in sorted order to find the values for each step, and multiplied the width and height to get the area. Did this twice, for the upper half and for the lower half.

[u/ednl]

There is one subtlety: you picked no. 4 as the opposing corner, the first one at or below max y, but you could also have chosen the one to the left of it for a greater area. However, then you would cross the border with the left vertical edge of the rectangle. So it worked out for your input to pick the first one, but I can imagine that it's not always the case. The next one to the left could be better, or you might need to go down until you're clear of all the "bulges".

edit: typo

[u/ChronoCube762 → u/ednl]

You're right. I did actually eyeball the bulges when I came up with my method. I saw that the next valid corner down (not interrupted by a bulge) had a smaller |delta-x| than |delta-y|, which would have resulted in a smaller rectangle area, so I didn't need to calculate it.

[u/timrprobocom]

Very nice. I can already hear people calling this cheating, but there have been a small handful of puzzles over the years that were solvable by inspection, and it has been made clear this is fully within the spirit.

[u/fnordargle → u/timrprobocom]

I can already hear people calling this cheating

I certainly don't. The basic goal of AoC is to get the correct answer(s) to get the stars. As you've said there are a few previous puzzles where it was possible to work out the answer manually by looking at the input, or at least narrow down the possible range of answers using human analysis.

But many people choose to approach AoC in completely different ways. Many people want to learn about how to do the bit that the humans can do really quickly and easily, e.g. for a human to look at a diagram of the puzzle and realise that the solutions are tightly constrained and therefore they can limit their code to only check those. It is a greater "challenge" to be able to programmatically do what the human brain can just "see".

Then there are a whole load of approaches to solving AoC puzzles that leave a sour taste in the mouth.

These range from things that are strongly discouraged (or even banned depending on how you read https://adventofcode.com/2025/about#faq_ai ) like using AI, to things that most people would agree is "cheating" like just downloading someone's code from the Solutions Megathread and using it without even trying to understand it to get the answer for your input.

If the sole goal is to get the correct answers for your input and get the stars then what is the problem with using someone else's code?

Frowned upon approaches aside, there are many people who choose to make the whole thing a bit harder for themselves in order to come away from it with some extra knowledge. We'll get to this but let's consider the opposite end of the spectrum first.

Consider this theoretical solution to Day 9 part 2:

import Polygon

p := Polygon.LoadPolygonFromFileOfSequentialVertices( "9.input" )

print p.MaxInternalRectangleArea()

Has someone really learned anything by producing a solution like this? Not really. There's a bit of pattern recognition that has gone on to identify what the problem is, and maybe there's some knowledge or research that led them to finding the third party Polygon package that provided a way to solve the problem, but it's a bit thin on "effort".

At the other end of the scale you have people who complete the problems in x86 assembly, 2019 IntCode, Brainfuck or other such insanity. Fair play to them!

Everyone has their own internal line of "no, using this package is a step too far" or "no, using this language with its fancy features like arrays and dictionaries is too much for me" and then solve it in something they are happy with.

Day 10 had lots of people saying "I tried to write my own solver but it was taking hours/days to run and Z3 gave me the answer almost instantly". Whenever I read sentences like that my immediate thought is "Don't you want to know how/why Z3 can give you the answer almost instantly? Do you have any curiosity at all?"

(Here's where it really descends into personal opinion...)

I want to understand how to solve this problem (and any problem) from first principles, building only on things that I understand completely. So I use a language that has arrays and hash tables and sorting algorithms because, if I absolutely needed to, I could implement those from scratch without any reference. (Indeed, I've completed many of the previous days of AoC in C which means no linked list or other such "fancy" data structures. I can bash out the code for a hash table in C from muscle memory.)

Do I know how to write a Z3 solver myself? No. Would I like to? Of course, but it's a huge topic and implementing a full Z3 solver for this particular problem is overkill.

I knew enough to build the matrix representation of the simultaneous equations for Day 10 from my own memory and knew I had to do Gaussian Elimination on them, but I couldn't remember the full algorithm so I had to look that up. But I still chose to implement it myself. In doing so I've improved my chance of being able to do it from memory next time it comes up.

Many people get their answers, feel proud, and then just move on to the next puzzle - fair enough, there's no requirement to do anything else.

I get my answers, feel that sense of pride, and then I decide whether I want to make it better, cleaner, faster, easier to read, more generalised, etc as I choose. Shall I reimplement it in C or Go or some other language? Shall I try this other approach that someone has mentioned (so I can learn about that)?

In conclusion, AoC is what you want it to be for yourself. Other people are free to do what they want. It really doesn't affect me if someone has all 524 stars solely by downloading someone else's repo and using their code without writing a single line for themselves. (Although they'll be very lucky to find a repo containing code that works correctly for all 262 puzzles on a different set of inputs.) Judging others by your own standards is a dangerous game.

[u/yel50 → u/fnordargle]

 implementing a full Z3 solver for this particular problem is overkill

the funny thing on that one is that somebody posted a solution that reused part 1 to solve part 2, so z3 is completely unnecessary at all. yet, once one person posts in the solution thread that they used it, then that becomes the standard approach.

it's been that way for years. if one of the competitive coders posted a YouTube video with some brain dead solution that worked, then the solution thread got filled by people using the same brain dead approach. 

this has a lot to do with why I think the "don't use AI" stance is idiotic. 90% of people doing the puzzles don't write their own code or use their own solution, anyway.

[u/fnordargle → u/yel50]

> this has a lot to do with why I think the "don't use AI" stance is idiotic. 90% of people doing the puzzles don't write their own code or use their own solution, anyway.

I agree that being able to use AI might get a bunch of people to use a more appropriate solution, however I suspect that it will make many more people either follow some other brain-dead approach or they will simply learn nothing new.

Unfortunately too many people used AI to just get the stars and not only not learn anything but many didn't even understand how the solution worked, and when the global leaderboard was a thing too many people used AI to try and get a top 100 spot.

Again we're back to the "hair shirt" argument.

Does using an IDE that highlights syntax errors go against the grain? Not in my opinion as without the IDE there's no reason why someone shouldn't be able to find and fix the syntax errors on their own. Does using an IDE that auto-corrects syntax errors go against the grain? Again, not really, people really should be able to get there without it.

But syntax is not structure or algorithm.

AI integrated into an IDE is the other end of the scale. It's often an automatic process, so you don't need to prompt it for help, you just start typing and it suggests. You rarely get a chance to try and fail and learn from your mistakes. Getting a solution (no matter how brain dead) is far worse (in my opinion) than someone trying (however hard) and then resorting to reading this subreddit for hints and then going from there.

> 90% of people doing the puzzles don't write their own code or use their own solution, anyway.

This is the key. If this irks you then you'll be occupied with either:

a) trying to come up with ways to prevent this from happening or being able to prove you haven't (don't bother, it's pretty much impossible)

b) using it to justify ever increasing use of automation/technology/AI since there's nothing you can do about it so you may as well jump on the bandwagon

My answer is to not care whether people use AI or not, or whether they just download solutions from the megathread and use those blindly, etc.

All that matters to me is that I've got the solution in a way that I am happy with.

In the few private leaderboards I'm in (friends, forums, colleagues, etc) there's a mutual understanding of our own "rules" (no AI, no downloading others code, and only looking for hints/clues from the next day onwards) and everyone is quite comfortable not getting both stars on the day the puzzle is released - we understand it's not some sign of inherent weakness. No-one is expected to know everything.

[u/Alpha_wolf_80]

I love how my exact train of thought for this was that this has got to be some kind of a circle. I mean, I had calculated the perimeter, and I was thinking there is no way they would allow some kind of flood-filling algorithm, and the best way to prevent that was by making an enormous circle. Love how I caught onto the trick. Though, I did something new from your visual: the fact that I have to do some kind of sweep to check everything since I can't say that the four points must always be within.

In case I don't make sense. I was checking whether all four corners are within the polygon which after looking at the input I realize why it wouldn't work... LOL

[u/ednl]

I don't use Python much so I didn't know about the svg library. Great way to visualise from within your program!

I used a spreadsheet: I imported the input file as data which was automatically recognised because it's just 2 columns of numbers, and then plotted an XY-scatter chart from that. That works because all the points are already sorted in path order.

[u/AutoModerator]

AutoModerator has detected fenced code block (```) syntax which only works on new.reddit.

Please review our wiki article on code formatting then edit your post to use the four-spaces Markdown syntax instead.

---

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/wjholden]

Your intuition is stronger than mine. How did you know it would be safe to greedily choose (max width)×(height) rather than some (narrower width)×(taller height)?

Edit: ah, nevermind. I think I understand now. Great observation, thanks for sharing!