Day 10: Pipe Maze | Advent of Code 2023

[@mcg6762]

For part 1 there is no need for a search algorithm. There is only one way to go for each step. Just iterate through the path without queues and stuff. When you get back to the start node divide the loop length by two.

[@m1geo]

Agreed. I just did a while loop matching on the next char mapping on the direction to go. Used refinding the S to break the loop. Half the number of steps, and you're done!

[@lukastonneman7151]

Well, BFS is a generic graph travelsal algorithm and a great tool in many sitations. This problem can be described as graph theory problem, "Find the number of nodes in this cyclic, single-child, graph", and I'm guessing William had it memorized from previous execises, so this might have been the fastest for him to implement. But yes becasue this is such a simple graph, other (possibly easier) mehtods also work.

[@AlfredZhong]

Really solved my problem. I had no idea about the part2 as I have never heard of the Ray Casting Algorithm. 😂Thank you.

[@mcg6762]

For part 2 I created a bigger map (double height and double width) where there is always room between pipes and on the perimeter. Then just fill the outside with the loop tiles as barriers. Anything left is inside. I like your solution though and a good algorithm to know.

[@enricd]

really interesting second part, I was checking now how else could be done as I came with another idea: the pipe is leaving all inner dots at its right side (from the point of view of the pipe at every moment) and the outer dots at the left side. This is when navigating the pipe clockwise, for counter-clockwise left side is in and right side out, then you declare every empty square next to the pipe as either inner point or outer, and propagate that to their empty square neighbors until all square are identified as pipe, inner or outer. But really interesting the ray casting idea, thanks for the clear and short video explanation!

[@TheFrogfather1]

I think that your solution was not quite correct but was accurate enough to work on your input. When I tried your solution with my puzzle input I got the message that the answer was wrong but it was correct for someone else. My own solution got the same answer. HyperNeutrino's video takes the view that how horizontal runs of pipe are treated depends on which way the pipes leading up to the horizontal run are pointing. If they're pointing in the same direction then that section can be ignore otherwise it's treated as a single crossing.

[@terryaney73]

I agree. Had to come up with an algorithm based on HyperNeutrino's explanation.

[@TheFrogfather1]

@@terryaney73 yup still ended up taking way too long!

[@terryaney73]

​@@TheFrogfather1 The runtime or coding it up? It was a def this year's toughest puzzle to date.

[@TheFrogfather1]

@@terryaney73 Runs reasonably fast - 87microseconds. Coding it took rather a long time (although I do have a day job!)

[@77Zamien]

This was really smart! My solution was scaling up the input so each character was translated to a 3 * 3 matrix where I actually did mark the write the '-' character to XXX for example. The same for all others. This way I did have a tight maze so I could to a flood-fill on the outside. This way all 3 * 3 that only contained points were located on the inside and I could add them up. But was a lot of code and time compared to your solution :) Have to look into raytracing algorithms :)

[@velitskylev7068]

Gj for implementing this, though.

[@TheTrienco]

I feel stupid now. I did it pretty much the same way, but it never occurred to me, that the order of the corner pieces doesn't matter. So I ended up with storing the "start corner" and then compared when I got to the "end corner". That's 10 lines that could have been 1

[@womogenes]

I did that too for my first solution-shoutout to my friend Marvin for showing me this faster way afterwards 😄

[@TheTrienco]

@@womogenes I admit, seeing it, it makes total sense why it works, but I doubt I would have ever thought of that myself.

[@groff8657]

When I switch the combination ("J", "L", "|") with ("F", "7", "|"), the inversion counter counts extra numbers... idk why.

[@bes0143]

I had same problem, the 'S' symbol caused it. You have to determine which symbol was the starting one and replace 'S' with it. It worked fine for me.

[@groff8657]

@@bes0143 Can you elaborate what you mean by starting symbol? the symbol at the start of the line? Symbol next to 'S' on the left?. Start of the pair FJ or L7?

[@bes0143]

Starting symbol is 'S'

[@groff8657]

@@bes0143 That’s not what I asked but thanks.

[@Torbeng]

@@groff8657 Think about it. The 'S' symbol is your starting node... You have to get the coords of it and replace it with the corresponding symbol which fits. The 'S' itself. He explained everything and that is what you asked for

[@0xRichard]

why didn't inlcude `7, F` in this counting ` count += line[k] in {"J", "L", "|"}` ? I'm sorry to ask silly question here.

[@womogenes]

each one of the 7s should be paired with an L, and each of the Fs should be paired with a J.

[@CurtisAutery]

@@womogenesI think you can just count the pipes, then.

[@mihirbpi]

Do you have any tips for learning these more obscure algorithms like ray casting etc. I had no idea about it which made part 2 much harder until I got some hints pointing to ray casting. Is it just a matter of experience or do you have a resource you use? BFS, DFS, etc. are p well known.

[@mtlee8977]

For me, I want to know "how to decide whether a point is in a polygon?" to solve part2. So I searched that question. That question leads me to ray casting algorithm.

[@nilsollrogge9934]

There are edge cases for which your solution doesnt work. For my input your sol was off by 5

[@womogenes]

Interesting-do you know what the edge cases are? I wonder if it has to do with the S character

[@TheTrienco]

@@womogenes the S tripped me up at first, too. One column got messed up until I just replaced the S with the matching pipe (mine was a corner, so I got a lot of false inside tiles).

[@rubenbernecker8900]

I had the same issue. Turns out you have to replace S with the value of pipe it would normally represent. For instance, if your S position allows you to move both up and down, the pipe it represents is '|'. Next, mark this position S (now the character this pipe actually represents) as part of the loop and your answer should be correct. Edit: the reason why this matters is because if you shoot your ray from the point you are checking towards the left (as he did in the tutorial) and your 'S' represents a '|' pipe (this will depend on your puzzle input), you WILL get a different result as this counts as an extra intersection.

[@m1geo]

Ouch! Today was trixxy!

[@finnpomfret]

I was about to do a flood fill with the cords doubled until I realised that you could just check how many I J L %2=1 pieces there where to the right