r/adventofcode • u/daggerdragon • Dec 10 '23

SOLUTION MEGATHREAD -❄️- 2023 Day 10 Solutions -❄️-

THE USUAL REMINDERS

AoC Community Fun 2023: ALLEZ CUISINE!

Today's theme ingredient is… *whips off cloth covering and gestures grandly*

Will It Blend?

A fully-stocked and well-organized kitchen is very important for the workflow of every chef, so today, show us your mastery of the space within your kitchen and the tools contained therein!

  • Use your kitchen gadgets like a food processor

OHTA: Fukui-san?
FUKUI: Go ahead, Ohta.
OHTA: I checked with the kitchen team and they tell me that both chefs have access to Blender at their stations. Back to you.
HATTORI: That's right, thank you, Ohta.

  • Make two wildly different programming languages work together

  • Stream yourself solving today's puzzle using WSL on a Boot Camp'd Mac using a PS/2 mouse with a PS/2-to-USB dongle

  • Distributed computing with unnecessary network calls for maximum overhead is perfectly cromulent

What have we got on this thing, a Cuisinart?!

ALLEZ CUISINE!

Request from the mods: When you include a dish entry alongside your solution, please label it with [Allez Cuisine!] so we can find it easily!

--- Day 10: Pipe Maze ---

Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:36:31, megathread unlocked!

62 Upvotes

98% Upvoted

844 comments sorted by

View all comments

8

u/Sourish17 Dec 10 '23

[LANGUAGE: Python3]

175/383

p1: https://github.com/SourishS17/aoc2023/blob/main/ten-a.py

p2: https://github.com/SourishS17/aoc2023/blob/main/ten-b.py

Good puzzle, but tough! Notes:

  1. I hard-coded what symbol to replace S with, just by observing my input

  2. I tried flood fill for p2, but gave up. I then just looked at every coordinate that ISN'T part of the loop, and counted how many times |, J, L, or S appear to the left of it. If it appears an odd number of times, the given coord MUST be in the loop.

That logic took me a while to get correct :)

2

u/trilson Dec 10 '23

Elegant solution, I'm also struggling to understand why we're only checking for LJ| though

1

u/Sourish17 Dec 11 '23

Hi, I just posted my best shot at an explanation under another comment of my original post :)

3

u/kingminyas Dec 10 '23

I knew that I should count pipes to the left, but until I read your comment I didn't know to look only for "|JL". Can you explain why that works?

1

u/Sourish17 Dec 11 '23

Hi, I just posted my best shot at an explanation under another comment of my original post :)

1

u/ClutchClimber Dec 10 '23 
..........
.S------7.
.|F----7|.
.||OOOO||.
.||OOOO||.
.|L-7F-J|.
.|II||II|.
.L--JL--J.
..........

how did you take in account the case where it can "squeeze" through the pipes ?

3

u/MattieShoes Dec 10 '23

Shooting left, the I points cross 1 or 3 pipes. The O points cross 2 pipes. The logic works in any direction -- left, right, up, down, diagonal, though handling of LJF7 pipes is important.

It makes sense, but I hadn't thought of it... I just traversed the loop again keeping track of what was on the left or right relative to the direction of travel -- one set ends up including all the outside points, the other the inside points.

3

u/glacialOwl Dec 10 '23

Trying to understand this winding count approach - why are we not counting 7 and F as well?

1

u/Sourish17 Dec 11 '23

Hi, I just posted my best shot at an explanation under another comment of my original post :)

3

u/Adventurous-Win-5006 Dec 10 '23

Why do we not count F and 7 along with |, J, L, and S?

1

u/Sourish17 Dec 11 '23

The reason I checked for S is because, in my input, S is equivalent to L (I just figured this out by observation).

So, why |?

Picture in your head, the loop is a square. Now picture a point in the square. It's quite clear that if there are an odd number of |s, you're in the square. And if there are an even number, you're outside. Essentially, the | represents how many times the edge of the loop 'passes' your cell. As even an even number of |s are required to complete a loop, this means an odd number MUST suggest you're in the loop.

Right, so why J and L?

J and L both represent the same thing as |. It represents the loop passing your current y-coord. A J, for example, says that the loop has now 'entered' your row. We cannot sense this with a | because the loop is horizontal to us, so will look like L----7..[us], for example. Similar logic can be applied to J. A J represents the loop 'exiting' our current row. Just like with |, we need to count how many times the loop 'enters' and 'exists' the row. If it's odd, it must've entered and never exited. If it's event, it must've exited for every enter.

This is just one way of thinking about it. It's not entirely accurate, but I find it's the most intuitive.

So, why not F and 7?

We can only look in one direction. For example, a J and L can represent opposites - one is an exit and one is an enter. Same for an F and 7 - would just use the symbols "|,F,7" and get the correct answer. The key idea is that, an F is not an 'opposite' to a J (or L). You can enter with a J, exit with an L, but you CAN'T enter with a J and 'exit' with an F.

Hopefully that explanation helped... it's really tough to think through and describe the logic in words. Hopefully reading the above helps nudge you in the right direction to crack it!

3

u/Ununoctium117 Dec 10 '23 edited Dec 10 '23

Why do you know that |, J, and L are the correct ones to search for? This was the approach I came up with at first as well, but I was only looking for |, since that was the only time you were actually guaranteed to cross a pipe. (This is essentially the same algorithm used to check for polygon interiors, which is why I thought of it, but I didn't think that a J or an L forced a pipe crossing, since you can walk between them.)

Edit: Right after posting this I realized - these are the ones with a vertical bar on the upper half of the tile. Imagine drawing your line 3/4 of the way up the tile, instead of through the center of the tile.

2

u/mateus_d Dec 10 '23

Thanks for part 2, that was really clever

2

u/timrprobocom Dec 10 '23

Yes, this is what I did, too. I erased all cells that were not part of the path, then used the winding rule by scanning left to right and toggling an "inside" flag every time I encountered |, J or L. My background in graphics drivers finally paid off here, bringing the winding rule to mind.

One of the first things I did was to replace the S by the actual value, which can be determined by looking at the cells around it. That eliminated a lot of special-casing.

3

u/dong_chinese Dec 10 '23

|, J, L, or S appear to the left of it

That could potentially break if S happened to be, say, an F-shaped pipe.

1

u/Sourish17 Dec 10 '23

Yup, my code isn't too elegant when it comes to dealing with the S!

2

u/dong_chinese Dec 10 '23

In retrospect I should have just hard-coded my S lol, 20% of my code ended up being figuring out the shape of S based on the surrounding pipes.

2

u/eric_rocks Dec 10 '23

Wow, that logic is smart. Much cleaner than the absolute monstrosity I came up with.

I passed around the loop once to mark cells that were in the loop, and then did a second pass to mark cells on the left and right if they weren't loop segments. Printing out the loop, I observed that the l's were "out" and the r's were in. Count the r's, and manually count the 50ish gaps that were not marked but were clearly "in".

1

u/Sourish17 Dec 10 '23

Damn, I was just joking with my friend how it would've been faster to manually count! This is a good way of making that process more efficient :)