2021 advent of code - day 05 solutions

hello and welcome to another day of advent of code in day five we're dealing with lines and plotting points and there's been a few similar problems to this in past advent of codes as this actually i had a very straightforward approach to this that i don't have to think too much about i'm gonna walk you through how i did my solution so this is what the input looks like uh and again this is a problem where some people spend a lot of time on parsing i'm gonna show you how i approach the parsing and that might help you out but anyway in part one we're going to be plotting all of the non-diagonal lines so there will be three types of lines in this one will be i think this is yeah this is a horizontal line uh this one is a diagonal line uh do we have a vertical line somewhere this is a very small vertical line yeah so you will see three different types of lines ones that change in x ones that change in y and ones then change in both and they may be in either of the 45 degree angles in part one we're going to plot all of the non-diagonal lines and we're going to find all of the points which the lines cover at least or more than one time and so we're basically looking at all the squares that have a value greater than one and in part two we're going to do the same except we're going to also plot the diagonal lines cool so the way that i thought about this problem is i wanted a point space where i'm just going to plot the lines this is kind of just the easiest way to think about this i'm sure there's another solution where you do line intersection and figure out the points that way and it's much much faster but i just went for the simplest thing that works and so we're going to do that and to represent my space i kind of had three ideas for that one is just use a dictionary where i plot the points in there a better solution to that would have been a default dictionary where i don't have to check whether the point exists to increment it i can just say that it's always starting at zero or i can use a specialized data set that's very specific to this problem which is a counter i guess it's not specific to this problem it just works really well for this problem uh so we're gonna use a counter a counter is basically a dictionary that maps to zero but it has some other useful things like finding the most common values inside of it i did a video on counter so i will link that in the description uh points equals collections dot counter and we're going to allocate things inside of this we're actually going to use both the coordinates as the the key here so if we give this a type annotation uh because my pi is actually going to explain here this is going to take a tuple int as its key so we're going to have x and y values as the key here all right so let's look over the input and parse it for line in input s dot split lines and this is where we get to the parsing so when i saw this parsing i thought okay we're going to split apart these two chunks first so then we can have numbers separately and then we can parse based on the comma here so um 0.1 or i guess start and end is equal to line dot split and we can split on this little string here so we're just popping out the middle here and then uh actually i called this x one s and y one s is equal to start dot split on a comma and x two s y two s is similar n dot split on a comma and then x1 y1 x2 y2 equals and x1 y1 x2 and y2 and so that should get us our um that should get us our points parsed to oops python3 pi object is not subscriptable oh yeah right i always forget to add my little future report one day i'll be working in python 39 plus this one is not defined oh yeah these need underscore s's on the end of them of course so i get for recording in the morning just got out of bed there we go okay cool so we're past the parsing port now so now we need to figure out whether these are vertical or horizontal lines and then plot those points inside of this collection here and basically to do that if they're a vertical line that means the x's are going to be equal and if they're a horizontal line that means the y's are going to be equal and so we can say if x1 is equal to x2 that means we're dealing with a vertical line so we're only going to be plotting across these points now these lines could actually go up or they could go down and so when i was when i was trying to solve this i got a little bit tripped up on that and uh basically i turned all lines that were going down into lines that were going up because they're they're equivalent they're just in the other direction and then the way i did that was by setting y it was from looping from the minimum value to the maximum value so i did four y in range min y0 and y2 and max y1 two and we have to actually add one here because we want to include the endpoint of our line uh range by default is non-inclusive because it's typically used for four loops uh over a um a sequence okay cool now that we have our y ranges we can plot those points so we can say points and we can pick either x1 or x2 it doesn't matter because they are equivalent here and we're just going to say points plus equals one and we don't have to do any validation on whether this value already exists that's kind of the magic of counter here now we're also going to do the same thing for our horizontal lines and when i initially implemented this i just did else because i didn't read the problem very closely i didn't realize there were diagonal lines you can't do else here you are actually going to have a hanging if chain that doesn't have an else we're going to say l if y1 equals y2 so this is the case for horizontal and we're actually going to write basically the same code as this here except instead of y we're going to use x for all of these and then we're going to do points x and again you can pick y 1 or y 2 plus equals 1. this will plot all of our points uh so after we run this we will see that we get a counter that basically has positions and some of those positions have the value too some of them have the value one and we don't really care about the zeros uh because we're not we're not bothering to count those there and so after we've plotted the points we need to figure out how many of them are greater than one and now you could just count them here manually or you could count them by looking looping over every value or you can use a cool method on counters let's see i just forget the name of the method in one sec uh todd is it most common yeah so most common will sort the values by them the most common values and so we can basically loop over that until we see something that's not a two and increment a count each time so you can say equals zero for kv in points dot most common if v is greater than two or greater than one right then count plus equals one otherwise if we find a v that's equal to one we can just break out of this loop and we're done and so at the end we print the count so that is how i solve part one let's make sure that's correct and it is that is the value we expect cool so that's part one part two we have to handle the diagonals and the diagonals are a little bit more complicated but interestingly enough we'll actually simplify the code after this so i'm just going to leave this code alone we're just going to modify it in place you can uh you know if you want this for part one there you go uh for the part two we have to handle the diagonal lines and so there are two well i guess there's kind of four types of diagonal lines like up left down or upright down left up left down right but you don't have to consider them all in those cases you can really just worry about which which direction the x's and the y's have to change and then do kind of a loop based on that so that was how i solved it so uh we basically have two chunks of if statements here like if x1 is greater than x2 that means that means that x2 is actually going backwards so we're moving the x to the left so i said the x difference is let's actually do this in the other direction if x1 is less than x2 that means we're moving forward so x difference is one otherwise we know that we're moving backwards so x distance is negative one or x difference and we do the same thing for y if y one is less than y two then yd equals one otherwise yd is positive or negative one once we have that we can basically make a loop over all of the positions of this line so we can say x y equals x one y one uh while x y does not equal x to y two we're basically making a loop here and we can say points uh x y plus equals one now um the way this loop works we're actually actually not going to the end properly here um so we could either do it like this where we do points x y afterwards which i think is a little bit clunky or we can make this one further xd and then yd i think that works i didn't actually do that in my solution so we'll see how that goes uh and then after that that that's basically it so we've added we've added diagonal lines here and we should have the solution now we clearly do not because i forgot to increment the values x plus x d y plus y d and now we get 12. cool now a really nifty thing that i noticed about this problem when i was implementing it in sql light is this bit of code here can actually solve these parts too with a little teeny tiny change uh so if we get rid of this part up here and we de-dent this it doesn't quite solve it right now it actually loops forever because these are not fully diagonal lines but we just have to add one more case in here so if we do l if x one is greater than x two we have this otherwise the difference is zero because they are the same that basically represents our vertical lines and then we do the same thing here uh l if x y one is greater than y two otherwise y d equals zero so now we have the three cases the horizontal vertical and diagonal all handled directly here and you'll see we get the same solution so i i made this nice little simplification in in my sequel light solution but anyway that's it that's that's day five hopefully you enjoyed and i will see you around for the next day you

Channel: anthonywritescode

Views: 554

Keywords:

Id: TcPzuic_Mn0

Length: 12min 0sec (720 seconds)

Published: Sun Dec 05 2021