#2024 AoC Day 6

177 messages · Page 1 of 1 (latest)

spice talon
#

Hmm, we may be getting to the point where pure brute force might be just a little bit too much brute force... ||my solution takes about a minute to run, which isn't too long, but it is pretty long for this early in the week||

#

296/112

mint nest
#

uh, Part 2...

cunning gyro
#

My part 2 took 9 minutes. I am desperate to find some optimization somewhere lmao

#

My part 2 now takes 8 seconds.

mint nest
#

There's a trick, I have no idea what it is...

#

otherwise, brute force, which I do not what to do...

cunning gyro
#

My initial code took ||about 6 minutes||, then I realized I ||should really be hashing the visited squares in some way so that I'm not searching down an increasingly long list every single cycle||, and now my code runs in ||~20 seconds (if you saw this earlier, I found a bug)||

robust flicker
#

My part 2 finishes very quickly but is wrong 😛

#

This is somehow trickier than I expected. I wonder what I messed up...

obtuse jay
#

I'm puzzled on part 2 ||I get it to run fast enough but it's saying my count is too low. I'm just brute forcing by trying to place one additional obstacle at every spot visited in the first path and then re-checking for a loop. It seems like if I was really too low, I should be missing valid loops, which should make my code fail to terminate... It also works on the test input, which isn't helping...||

stiff zenith
#

This is the first problem I'm actually having significant difficulty on

#

No I'm not done yet

robust flicker
#

same

stiff zenith
#

part 2 that is. part 1 was straightforward

robust flicker
#

and I don't feel like I should be having such difficulty, but I am

#

part 1 was great

stiff zenith
#

no i can see the difficulty

robust flicker
#

if the thing I'm doing now pans out, so can I

mint nest
#

I am brute forcing, and it should be done in ... an hour or so

robust flicker
#

well, that (unsurprisingly) escalated my runtime significantly

#

answer is still too low you say

#

I suppose I shall get brute-forcier

#

(I'd really rather not, though; it'll take so long)

oak yacht
stiff zenith
#

how can you tell

oak yacht
#

It felt harder than the earlier days

#

(the only real metric, if you want data, is looking at how long the top 100 leaderboard takes to fill up - which was nearly 9 minutes today as opposed to nearly 4 yesterday)

robust flicker
#

I figured out how to get the same wrong answer somewhat more quickly

oak yacht
#

Is this the "fail fast" thing the startup folks are always talking about

stiff zenith
oak yacht
#

I don't know how true that is

#

maybe?

robust flicker
#

at least somewhat

cunning gyro
#

There’s def a few that are confirmed

oak yacht
#

probably the majority of the top 100 are still playing fair, I think

cunning gyro
#

Not sure what percent of it

#

(and by confirmed I mean they pretty much blatantly admit it via their github repos)

robust flicker
#

OK, I've somehow been on this for a while. If someone doesn't mind, ||I've been assuming that all the loops would come from turning at obstacles. That's... right, right? like, there's no other way to turn||

obtuse jay
#

Okay, poked around on Reddit and finally got the help I needed. ||I was forgetting to check for multiple neighboring obstacles, so you may have to change your facing more than once per step...||

#

Hit a corner case dead on the nose, I guess?

robust flicker
#

that is, unfortunately, not my problem

obtuse jay
#

How are you checking for loops? Like, what's your condition?

robust flicker
#

good to know I was right to check it though

robust flicker
# obtuse jay How are you checking for loops? Like, what's your condition?

Currently, ||before I start moving the guard around, I hit up each obstacle and ask, "if I start at any of the four possible turns around this obstacle, does it end up in a cycle or go off the map?" I keep all the ones that result in a cycle and add those paths to the visited nodes tracking I use to look for completing cycles in the guard path||

#

||For each step the guard takes, I'm checking, "if there was an obstacle here and the guard were to turn, would it run into a path from before (which would cause a cycle)?" so I didn't separate the tracking||

#

well, I know another wrong answer

#

oh, wait

#

... never mind

#

dang it

obtuse jay
#

||So, it's not just about crossing a previous path. The actual looping condition is whether or not you're at the same point with the same facing as some time in the past. So you can just keep a set/list of positions and facings and compare at each new step.||

robust flicker
#

That's basically what I'm doing; ||I keep a set of (coordinate, direction) pairs||

obtuse jay
#

Hmm, yeah I'm not sure then

#

If you're correctly detecting loops and handling the catch I struggled with, I dunno what's wrong, at least not without looking at your code.

#

Could try looking on the AoC reddit, some people have kindly posted small example inputs with corner cases to try out.

heady tiger
#

very frustrated with today. my part 2 code works for the example and every additional sample input I found on reddit, but my answer is somehow too high. I've accounted for the corner cases mentioned above, or at least I think I have. maybe sleep will help...

dapper spruce
#

are you accidentally ||placing an obstruction on your starting position?||

robust flicker
#

no, ||the result between forcibly removing it and not is the same||

olive parrot
#

So, my optimization for part 2 was ||to run part 1, and only try adding obstacles on the places visited in part 1. Obviously the guard can't hit an obstacle that isn't in a square they would have visited.|| Good enough to get it down to 10 seconds in otherwise poorly optimized code.

robust flicker
#

not sure why I'm currently failing those, but I am

#

oh

#

it's because I'm dumb and stupid

#

no, that didn't help

#

I tried to be too smart, I think

olive parrot
#

Want someone to take a look at your code and see if anything looks suspicious?

robust flicker
#

not anymore; I've figured out what's missing on it

olive parrot
#

Oh. Yeah, I picked an approach that's not the fastest code, but... it was really hard to get wrong. The older I get, the less time I want to spend debugging.

dire oxide
#

I just cut my semi-brute-force p2 execution time from 20m to 5m

#

still a long time, but much better

robust flicker
#

good news

#

I could adapt and still be "smart"

#

that or I'm about to find out this is not good news

#

which is what I get for being up at 2:30 AM

#

welp

#

time to give up on intelligence

mint nest
#

my code took 2 1/2 hours to run, I have an answer, and it is...

#

GOOD!

#

Wow! That was not the way to do it, but it was indeed done!!

robust flicker
#

FINALLY

#

I did indeed try too hard to be smart

#

I switched to the basic way and then still had to fix one thing but I got there

#

target/release/d06p2 0.34s user 0.05s system 99% cpu 0.391 total

#

I'll take that as a runtime

oblique tendon
#

I think I oopsed into a "nice" brute force for this, given my runtime being ~60ms.
|| Solve the maze normally. The only places obstructions can make loops are squares that the guard visits. And I just brute forced that, because for my data set that was only a few thousand. https://github.com/javajawa/aoc/blob/mainline/2024/day6/part2/main.go

However, I could probably do a lot better by recording the direction(s) a cell was visited because you cna qiuckly scan for if it would hit another obstacle. ||

mint nest
#

that's what I did ||only place obstacles on the path|| but...

spice talon
# mint nest that's what I did ||only place obstacles on the path|| but...

That's an optimisation I probably should have done but ||I figured the grid was, like, 100×100 and my answer for part 1 was in the thousands, so I just assumed it was touching basically every square and it wasn't worth it... Turns out the grid is much bigger than that, and it was only in the low thousands, so it prob would have helped...||

mint nest
#

Still, in each "loop" I either changed direction or moved, so corners were never a problem.

dire oxide
#

oh hey, one extra optimization and I went from 5m30s to 10s

#

I think I'm happy to stop there

mint nest
#

Still, let's see those Excel sheets go!

dire oxide
rapid olive
#

my score on actually remembering to not start something else i'm not going to finish by 9 pm pacific every day is pretty abysmal this year 😛

olive cloak
#

Had to go out for dinner before I could finish, but I was apparently on the right track, caused part 2 only took 3.5 minutes to run.

#

||The main thing was to make a list of all the obstructions, check if any were in line with the guard in the direction he's facing, and jump him to the nearest one directly (generating a list of spaces in between to track the visited spots), turn, and start again.
Much better than moving them one step at a time.
Then part 2 is just running it with a new obstruction, for every spot on the map.
Since they jump from point to point, the list of places they were standing and directions facing was small enough to not take too long to check if they'd been there before, and would be in a loop||

olive cloak
spice talon
stiff zenith
#

like it feels like a hint even though nothing was spoiled

crude shuttle
#

Reading these times really makes me wonder how inefficient python is. I did a simple brute force solution in java without any optimisations (|| parse the input as a 2d char array, copy that array, put an obstacle in every possible place (as a loop, only one obstacle at a time), run through one step at a time updating the array with a char that signifies the direction it was visited in, stop if you encounter a position that you've visited in the same direction||) and it runs in ~1s.
That solution has one bug (||if a loop exists where every sqaure is visited twice from different directions it won't be recognized ||) but i figured that it was so rare that it wouldn't come up and was right

limpid thorn
#

I just did it all the dead simple way ||a step at a time, and trying adding an obstacle in every position||. Even in python and without the extra optimization of ||only checking the squares from part 1|| that was good enough for a solution in 38s. Adding the optimization dropped it to 7s.

#

That was with ||using a set for tracing visited, not a list (which I didn't even think about)||. That might be why some solutions are so much slower.

spice talon
# crude shuttle Reading these times really makes me wonder how inefficient python is. I did a si...

from things I've worked on in the past, for pure cpu-bound number-crunching, Python code and the equivalent C code (identical algorithms, no additional optimisations) is a speedup of a factor of around 50 to 100 or so. At least, I had one particular past project (rendering a video from some pre-calculated data) that was pure bitshifting and numbercrunching, and re-implementing it in C from Python ran 80x faster. Obviously if your Python code uses any external native libraries (numpy, etc) or is io-bound (or even memory-bound) then that'll reduce the difference.

limpid thorn
#

Switching from CPython (3.12.6) to pypy (7.3.17) dropped it further to 2.5s

#

for this kind of pure python number crunching pypy can often give you a 10x boost

#

it's slower on real-life code because it needs to emulate cpython in order for libraries written in C to work

heady tiger
#

in broad strokes my algorithm matches what a lot of people seem to be doing.

austere inlet
#

Hello ||brute force|| my old friend

#

Took 58 seconds to run. I can be smarter about it but I don't care! Got too much work to do today to optimize.

heady tiger
jade chasm
#

oh, no i don't think part 2 is happening in spreadsheets lol

#

also did the classic dumb dumb submitting part 1 lol

#

was hoping to make it all the way through week 1, but that will not happen unless i think of something clever

#

will say: re brute force starting to not cut it anymore, that last year the seed map was day 5 and that one was way way worse for brute force than this i think

stiff zenith
#

still tossing and turning the problem in my head

#

can i request a hint

heady tiger
#

what are you stuck on?

jade chasm
#

i mean, it sounds to me from reading that the naive brute force thing works fine, even if it's a little slow

heady tiger
#

"brute force" for part 1 is definitely feasible. the input is small enough.

olive parrot
#

it will work for part 2 as well, though there are a lot of ways you can optimize it to bring the run time down to "fast" instead of "it'll finish sometime today"

olive parrot
jade chasm
#

earlier messages seem to indicate sailboat is stuck on part 2, not part 1

olive parrot
#

Ah, yes.

#

Then yeah.. which part is giving you issues? detecting when ||it loops||? Figuring out candidates to test ||for loops||? (Spoiling merely to hide the p2 twist for people who haven't got there yet)

stiff zenith
olive parrot
#

You don't need to be that clever. 🙂

stiff zenith
#

oops

heady tiger
#

my solution for that (and I think most peoples') is to ||keep a list of every coordinate you've visited, and the direction you were facing when you were there. as soon as you hit a duplicate, you know you're in a loop||

olive parrot
#

A pretty easy approach is to ||store a set/list of previous guard (position,facing) pairs that you've seen so far||

oblique tendon
#

I went for specifcally ||obstacles reached and the direction, to reduce the size of the list (at cost of slightly longer to spot the loop)||

stiff zenith
jade chasm
#

that's more of a solution than a hint to your particular problem, i think

olive parrot
#

I suppose it's a solution for that one aspect.

#

ok, backing out to the level of hint... ||you can get away with just brute forcing whether you've been in a particular situation before||

crude shuttle
stiff zenith
#

this isnt even the first problem i had to solve with my code. the first one was that it was way too slow to begin with ||because i was checking every square every time instead of just keeping track of where the guard was||

#

so i thought i had to come up with a trick for part 2

olive parrot
#

Oh, yeah. I almost did that in part 1, then I was like "there's no way that's going to work, let me separate those details"

stiff zenith
#

i thought my implementation might have been better for part 2. and it wasn't

#

💀

jade chasm
#

i'm not really sure trying to predict what part 2 is is worth it that often. they zag when you thought they'd zig most of the time. this time i thought part 2 would be (only spoiled for saying something part 2 is not) ||putting the same grid repeating forever and trying to detect a loop on that||

olive parrot
#

ah, yeah. that is a thing they do commonly. (the specifics of your guess, I mean. But it does apply to the first part too)

crude shuttle
stiff zenith
#

solved day 6 part 2

#

takes roughly ~35 seconds

#

also i made a cool visualization of loops

SPOILER_image.png
#

||they are. more complicated than i thought||

#

saaaame

SPOILER_image.png
#

not THAT long for me but like. augh bugs

stiff zenith
buoyant ledge
#

it seems like I solved part 2 with ||pure luck, cos I decide I'm in a loop after the guard has taken over N steps, and my N just happened to be high enough. But also low enough that it only takes a bit over a minute to do.||

#

technically, based on what sailboat has said, ||that would mean that for an input that's M by M characters, I believe you'd know you definitely looped if you made M*M*4+2 steps - because you had to visit at least one square 5 times and repeat a facing direction, and a bonus step for stepping off the grid. And that solves in 2 and a half minutes.||

warm fossil
#

so... ||testing 130^2 oisitions is... long||

austere inlet
#

Yeah, took 58 seconds!

#

I figure it would be a lot faster to test ||only the positions in front of the guard|| but I only thought of that after I applied brute force.

jade chasm
#

it's only like 17 thousand, that's nothing!

warm fossil
#

My code is taking a lot longer than 58s... 😐
after 1min its only tried 70 (singlethread)

heady tiger
#

are you ||making a copy of your map data for every single check||?

warm fossil
#

||my loop check is probably the slowing piece... I'm keeping a history of position+directions and if there's a history object with the same value its a loop. Its a long list tho||

jade chasm
#

yeah you should use a hashed lookup for that probably

heady tiger
#

(Assuming that makes sense for your language/algorithm)

warm fossil
#

||The big problem was the history search. Its a lot quicker now. though still not fast enough... I'm not reloading from disk every time though, its an in-memory instantiation||

robust flicker
#

looking at all these times: how not brute-force was my brute force?

mint nest
#

me with my 2 1/2 hour run time look at you, with your inability to go watch a movie while running code...

warm fossil
#

||I had 2 array searches in my algorithm that were massively slowing it down. One for obstacles and another for the state history. Cleaned those into simpler hash-maps of obstacles and it is much quicker. Took 1 minute and a half||
||Annoyed that the hash thing didn't occur to me... especially since the hash lookup was way simpler||

olive cloak
#

Dang

#

That's a pretty big improvement

warm fossil
#

||This is the first time I've used objects which meant I was slower than I could have been I just felt holding the Guard as an object with a map containing the objects that moves itself made sense||

robust flicker
oblique tendon
olive cloak
#

For part 2 they could || Looper. I loved that movie ||