Day 6 | Advent of Code 2024

I make educational videos on algorithms, coding interviews and competitive programming.

[Maggrathka]

One improvement you can make to the step 2: Store the path you take initially without adding any new obstacles, and only try and add obstacles in those places.
If we never hit an obstacle we add on our path - there's no point checking that location.

[sunico]

Very nice video! A small improvement is that you don't need to try every single position for the additional barrier. You traverse the path without adding a barrier yet and if the next position hasn't been visited, is inside and isn't a barrier, then you add a barrier and simulate that path. After checking wether or not that leads to a cycle you remove the barrier and continue the algorithm.

[schrummy]

I saw the same thing using set as a first solution, taking about 1.5 seconds. You saying, just put it in a boolean array, made me smack myself... Doing that, I got down to 0.03 seconds. (g++ 14).

[barterjke]

One small optimization: you don't need to place # in places when guard never have been (not X), and if there is no obstacle on adjacent rows and lines.

[gupta_samarth]

There is a way to solve in O(N*M) total, for second part. If we view it as a functional graph, one new obstruction changes upto 4 edges, and you can check for each of the neighboring nodes which is reached first, upto 4 times ( because we can compute steps or say impossible, required to go from a to b in functional graph )

[juanecoperu]

Great work you are doing. Thank you man!

[sidreddy]

Nice. Can't wait to see if there is a more optimized way to solve the second part. Also, can you explain the hash a little further? I used a 3D boolean array to check if we visited the same cell from the same direction

[oisincarroll]

Loving these videos! Really interested to hear if there's a linear time complexity solution. The fact the added hash can 'reflect' the guard from multiple directions makes it much more challenging.

[czitels]

Dobra robota. W końcu ktoś inny niż hindus na tym YT :D.

[YaQzi]

Hey! It would be really cool to see you tackling Everybody Codes event, Quest 19!

[sampro]

Optimization is remember the path you went on and look for obstacles directly to the left of where you were going.
Let's call those Ob_i.
Then you simply need to find locations where adding an obstacle would cause you to change your course and end up running into some Ob_i.

Edit: Similarly the rest of the locations could be found by looking directly backwards from anywhere along your path.

[nlusc-qd]

Hi @Errichto, is there IOI camp 2024 playlist

[DoctorDuckload]

Man I really wonder what you did for Day 9. It was easy enough to come up with two-pointer solution with O(n) time and O(1) space for part 1 but p2 tripped me up. Every other solution I've seen is just wildly inefficient.

[adamgwinnowicz]

I keep getting "Denial of judgement" on my solution. Can someone please explain what this is and how to deal with it?

[abdulrafay]

Isn't it better to use a counter each time you move to another cell, updating it and adding to the count, instead of maintaining a set or boolean array

[jmgaming]

lord errichto pls come back. Start from day 14

[jmgaming]

lord errichto pls come back. Start from day 14

[jmgaming]

lord errichto pls come back. Start from day 14