Advent of code 2024: day 12
and we're live what's going on YouTube it's time for another day of Advent of code today we're tackling tackling day 12 and we'll dive in here very shortly interested to see what we have for us today um see what kind of problem we have hopefully we can solve it in a reasonable amount of time looking forward to diving in and and seeing um I haven't seen I don't think we've seen a parent child node problem in a while um or yet so I'm thinking maybe we might have some sort of tree problem coming up uh feels kind of appropriate to to see one of those um we'll see excited to dive in and see what we might be getting into here I'm also looking forward to um holding my skills a little bit further and uh just kind of seeing how we can improve dayto day I may end up doing a review uh yesterday I got tripped up a little bit because they said that the stones would come out in order but actually the order wasn't important to the final problem which led me down a 45 minute journey of inefficiency so hopefully I take a little bit more time today and think through the problem I'm going to get my iPad out ready I think through the problem a little bit further before I start putting in code together and maybe we can do it the right way the first time this time yeah minute 54 hey what's going on glad you joined just getting ready to start Aven of code day 12 got a minute and 30 left does anybody have any uh predictions on what the problem might be for today uh whether we're going to be tackling a grid problem or some sort of string rex or maybe a node Pro a tree problem parent child relationships any thoughts I was thinking about day 12 from last year uh was a node problem where we had to Traverse paths uh starting at start which was the root node and ending at end distinct paths along the way other big caves and small caves so wonder if we'll do something similar to that today or maybe we'll get into something else got 19 seconds all right let's into day 12 Garden groups why not search for the chief historian near the garden and his massive Farm there's plenty of food so that the stor grabs something to eat while they search you're about to settle near a complex arrangement of garden plots when some Elves ask if you can lend a hand they'd like to set up fences around each region of garden plots but they can't figure out how much fence they need to order or how much it will cost they hand you a map your puzzle input of the garden plots each garden plot grows only a single type of plant and is indicated by a single letter on your map when multiple garden plots are grow growing the same type of plant and are touching horizontally or vertically they form a region for example okay this 4x4 Arrangement includes garden plots growing five different types of plants a b CDE e in each group into their own region in order to actually to calculate the cost of the fence around a single region you need to know that Region's area and perimeter the area of a region is simply the number of garden plots the region contains the above Maps type AB and C plants are each in a region of area four the type e plant are in a region of area three and type D plant are in a region of one okay got it each garden plot is a square and so has four sides the perimeter of a region is the number of sides of garden plots in the region that do not touch another garden plot in the same region the type A and C plants are each in a region with a perimeter 10 K the type B and E plants are reach in a region with perimeter a and the lone D plot forms its own region with perimeter 4 um hold on each Garden so has four sides the perimeter of a region is the number of sides of garden plots in the region okay so one two 3 4 plus the top is eight two sides is 10 okay got it 1 two 3 4 1 two 3 4 5 6 7even 8 for B okay got it visually indicating the sides of plots in each region that contribute to the perimeter using okay yep got it plants of the same type can appear in multiple separate regions and regions can even appear within other regions regions can appear in other regions okay so this what these X's multiple separate regions got it one containing all of the O garden plots and the other the four x regions each have area one and perimeter four R contain 21 type zero plants is more complicated in addition to its Outer Edge contributing a perimeter of 20 its boundary with each X region contributes an additional four to its perimeter for a total perimeter of 36 due to Modern business practices the price of fence required for a region is found by multiplying the Region's area by its perimeter the total price of fencing all regions on a map is found by adding together the price of fence for every region on the map in the first example region a has a price of 4 * 10 which is 40 okay we'll deal with the pricing in a little bit the second example the region with all the O plants has price 21 Etc here's a large example it contains a regional r a region of I another region of I okay region of M region of s so it has a total price of 1930 what is the total price of fencing all regions on your map okay let me just look at the puzzle input real quick well that's fun it almost looks like a picture okay okay got it okay so this is what I think we can do my thoughts are if we start at 0 and we crawl out in the four directions um and we try to build a reg region based on the four directions uh let me look here for a second I don't know if we have to worry about angles I don't think so let me look here if we can see what that type of plant is indicated by a single letter which growing at the same type of plant that are touching horizontally or vertically so we only have to worry about up down left and right so we we start here at position R and we grow out for each letter that matches and if once we find a letter that doesn't match we stop processing and we process all these and then we keep a map of visited locations um once we're done with that we go to the the next iteration next next so on until we get to an unvisited location we build that region go to the next one we build out that region and we Mark all the visited ones as we go and then eventually we get down to a set of all our visited and then we loop back through all our visited sets and we determine if um what the value is I think that should be fine um we're really just looping through this once and then for each one we're being selective about which records we check next to build our region and plot and then we continue through until we find one that hasn't been processed and we'll have to look through every single one of these records once to do that uh I think that's going to be okay so that's the approach I'm going to take and we know that our test input is 1930 so we'll come back here change this to 1930 and then as far as our reading of our data um we're just looking at strings here so we're going to come back here and we'll use our and we'll save that and that should give us all of our records and we'll worry about the the scoring of each one separately because we have the two perimeters but let's let's let's Loop through [Music] this and then we can say [Music] for right so we know we we've got that and thanks Matthew actually my gitlab repo if you are interested um I try to take a test driven to approach this since we know what the end result is supposed to be um but you're more than welcome to pull it down yourself and use it or pull from it or you know it's up to you um just going to call this [Music] step and I need a visited [Music] list we'll just make it a map of string uh [Music] whoa and so we'll do [Music] [Music] [Music] this is an in this is a string and this will be um yeah I it's it's good practice to go through these um I haven't you know I've done some of admin code over the last couple of years but it's fun to tackle these problems and kind of see what we can get uh you know what we can produce um this is row and then this should be visited [Music] key row column and uh we'll do yeah we could do an empty struct there if we' really wanted to make the uh the value smaller but not going to worry so much about that and so we're going to pass our our grid in here and we're going to pass in our character and we're going to pass in our um our map a streamable [Music] and because we are going to step uh and then we want [Music] a our Direction so we can say [Music] for we're going to step we're going to pass our Matrix in I'll we're going to pass our V in we're going to pass our Direction in and we're going to pass our visited in um this what this doesn't do is return back our uh the things that matter right so I think that's the last thing we need to do is return back a set of set of ins um yeah so first thing we're going to say is if uh M do well okay okay we're not going to use B here we're going to use we're going to do a position instead [Music] um yeah so we'll do R comma C and we have a Direction so we'll say if m dot plus equal uh dur sub zer and C plus equal dur sub one and we'll say if M do inbounds R comma c um it we'll say if not then we return return that so we know we're off the map and uh we should do NR because I want to maintain the original for our next check we'll call this NC this will be fine n r and N C and then we can say if NR equal to I'm sorry if M sub R Sub C [Music] uh we'll say not equal then we return so these are kind of like the guard Clauses and then finally um if if we are good then we can say essentially what this is which means um we can step and we want to do NR NC and then all of the directions so anytime we step somewhere we want to go there again uh and then one more caveat is that if we've already visited so if it's not in bounds if the values aren't equal and if we've already visited we return the empty set and then we can [Music] otherwise set visited equal true me no I don't know any assembly I've looked at some but I've not done anything professional or um in detail with assembly is there a particular project you have in mind that you'd like to look into further I wouldn't mind giving it a look I mean so so we're going to set the visited a true so we don't come back to this particular node and then um so one last thing I want to do is we need to uh for lack of a better name [Music] [Music] [Music] [Music] so this should then set R to this each time and then R is always going to append whatever the sub piece is so we should get our grouping of letters that match so then uh this is going to be our groups and yeah so this is going to be [Music] that so we're going to pend the entire group so that we have all of the index positions in each group so we can come back and analiz um but I think we're going to start there uh we'll go with that so now if [Music] we and [Music] something like that something like that first try nope score yeah okay uh yeah we can get rid of that for now all right you know it's late and I've been doing this pretty much non-stop I'm making all kinds of mistakes there we go okay um lots of empty slices I to not have quite what I was expecting let's just log the first group that it's a little bit clear on what's going on here right okay yeah just a whole bunch of those yeah so they should never be nil um ah this is NR NC this has to be NR n then see okay that might be part of my problem here yeah there we go okay but there is still one issue which is [Music] here um I need to do two things first is maybe I can reduce reduce this but I'm going to just go ahead and do this for now um and keep it in here so we're going to keep one at this higher level so as we go through that whole Loop um we're going to check and if we've already visited we're not going to visit again otherwise we visit it for the first time and we're going to do our new group [Music] ah okay so there is a little bit of an issue here [Music] as and then this is going to be new group equal to a pen new group dot dot dot and then we do groups equal to um append groups new group probably just call this group let's make our variable names a little bit [Music] better so we've got 11 let's just count this real quick one 2 3 four five 6 7 8 9 10 11 okay perfect so I think we got the right groups and then if we look our first group is uh that's actually our second group let's change our logging real quick um we'll log the zero index group just so we don't go crazy and we've got one Zer one one why did we get one zero as our zeroth group we're missing we're missing that oh that is because this should be R comma c um here and here so we we start the group off with the index that we're on at that level which is 0 0 and there we go so and then 24 is the last one there so zero one two and then was there a 32 there's a 32 okay perfect so okay so the region of R plants with price is 12 * 18 which is 216 so now we've got our groupings so let's look at R here we've got one two three four 5 6 7 8 9 10 11 12 so 12 is the the area right so like the area if we look back here at area in order to calculate the cost of the fence around a single region you need to know that Region's area in Perimeter the area of a region is simply the number of garden plots the region contains so now if we come at through here and we say okay [Music] for we can say our [Music] area and then we've got the so this is going to be a little bit more challenging um so how would we do this what's the is there a way to calculate an area of [Music] points this just like a Normal area so we've got one two yeah okay so is it something like we did like uh [Music] [Music] what's the what's the calculation here there's got to be like just a way to do with math [Music] ex yeah is there some way to just like we know that the top here 1 2 3 4 just trying to think here if there's a way where we can determine this I mean if I go through each grouping and I check each point if to calculate I could start at the first point and I can check all the directions and if there is a character of the same then we don't count it but if there's either out of bounds or or a character but different we count it and then so we would basically be recalculating every grouping considering the size of the graph that we have right now I don't think that's going to be that terrible um maybe we just try that and kind of see where we land and so and we'll go with our Matrix again [Music] yeah and then from here we've got a grouping and so we can say um for [Music] [Music] [Music] [Music] yeah so we can say if in bounds um P sub Z Plus dur sub Z and then we'll say p sub one plus dur sub [Music] one say if not then we'll do perm um and then continue and then we're going to return perm and we'll put an in here okay so now that's go if we know that we're out of bounds we know that we're on the edge and we'll calculate both of those for a given thing otherwise uh if we can just say or um yeah I'll just do this because this will be easier to articulate actually we'll just call R CU we don't have another one [Music] so if our current position is not equal to rc um so if either of these conditions are true so we're not in bounds or the letter doesn't match then we're going to increment and that's going to be our perimeter so now it will be oh we'll call it [Music] perm [Music] okay so much for that keyword shortcut uh all right M and then we pass in our group and then our sum or our score is plus equal area times perm and then why is it not like this our score equal to 0.0 maybe and then we return [Music] score yeah let's try that out for our test here awesome so now we'll grab our input for the seventh time apparently um place that here and see if it will run in in a reasonable amount of time that wasn't confusing all right awesome part one done let's take a look at part two fortunately the elves are trying to order so much fence that they qualify for a bulk discount under the bulk discount instead of using the perimeter to calculate the price you need to use the number of sides each region has each straight section of fence counts as a side regardless of how how long it is consider this example again the region contains type a plant has four sides as does each of the region contains plants of type B D and E however the more complex region contain the plants of C has eight sides see this new method of calculating the per region price by multiplying the Region's area by its number of sides region a through e have price Etc okay I don't understand using perimeter to calculate the price you need to use the number of sides so C has eight what is considered a side did it tell us here perimeter using and the sides of the plots in each region that contribute to the perimeter using okay so why does why does c of eight on why does c have eight 1 two 3 4 5 6 7 8 n no I don't understand this a has four sides one two 3 four okay I see and then C has 1 2 3 4 4 five 6 7 8 okay I understand now so that's kind of fun um all right well let's see how to if we think this through a little bit um if I start here and I check to my left I know that I can get a side row if it's not similar to what we're doing parameter I can check to my top and I know I can get a top row and then I could iterate to the next one and that's also a third so one two 3 right we go down to the next C we go over to the left we already have that column cataloged as a side so we're not going to record it again but if we try to go down that's not us that's a row now then we go over here okay so very similar but instead of recording the r and the C I'm just going to record the the rows and the columns if you will that we're in and that'll give us our our sides per a per a thing and if we're out of bounds that will be a so if I go to the right that is a Col that is a column and if I go if I go vertical that's a column if we go horizontal that's a row um and so we'll catalog okay right so so then let's do sides so let's come back here let's create a part two we could probably condense this down uh later but for now it'll just be easy enough to copy and paste and then instead of doing perimeter we're going to do sides and we're going to create a funk called sides we'll borrow from [Music] our um perimeter one it's very similar pattern so we'll copy it [Music] yeah a little bit more complex but not too much [Music] more so what we need is I mean we could just do I mean this is this will work in and um [Music] full and calls so this will give us our ability to anytime we reach a condition instead of just blindly adding it we're going to add we're going to add to this and we're going to say I don't know I did it continue here but um we'll do rows um yeah we'll break this into two so what we can do is and we'll do slice of in and we'll do matrix. dur up [Music] down and then that and then we're going to do the same thing here but the difference is and the reason we're doing it twice is because instead of doing all four directions we're going to catalog slightly differently so and this is going to be dur left and dur right so now if we're going up and down we know that we want to catalog our rows so this will be rows oh this is goang [Music] and then we can just do the length of rows plus the length of calls and that should be it um we don't actually have to count this anymore and our same test input produces 126 so we'll go back to our test we'll put in a 126 here and we will rerun our test and we've got 1930 for part two expected 126 actual 1930 ah that would be why all right th2 so what didn't I do right here let's see yeah let's let's just put some logging out real quick so what I can do is [Music] is have you uh doc jolas have you coded in ging before or like what language are you most familiar [Music] with and let's just go ahead and do our group [Music] gotcha so area 12 sides 10 okay so I got that one right area four sides four that one's right 14 area sides 22 so why didn't I get C right so C nice glad to hear that I'm pretty close I'm not particularly fast at these I'm just kind of enjoying the process of going through them um and I figured I'd document it here so our our C's are wrong what else do we have here 146 1428 so our area is right we know that but the sides are off so 16 why do we not get 16 one 2 3 four let me go back here and see Matrix dur up D down left and dir right so we're going to do both oh did I have these do I have these reversed if I go up I want that column and if I go left I want the row I think I have these reversed okay well 12 and 9 four and four 14 13 okay maybe not if I go to the left no no I do I do want the row go to the left I want the row go to the right I also want the row [Music] still G be the same result yeah so if I go if if I'm here if I'm here and I go to the right which is J I want this I want to catalog that and I if I know there's an edge here then we're going to track that let's look at this the side a little bit more maybe I'm missing something in the calculation for the side the e-shaped region has an area of 17 has 12 sides so 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 okay hold on 12 sides Y 2 3 4 five let's go back to our simple example a is four one two three four oh wait a second has four sides under the bulk discount using the perimeter to calculate the price you need to use the number of sides each region has each straight section of fence counts as a side regardless of how long it is each straight section of fence so but I mean shouldn't this actually be eight I mean I don't make the rules here but two 3 4 five six 7 8 I just don't understand what it's asking for here each straight section of fence counts as a side regardless of how long it is do we one let's at B for second as do each of the sectors BD and E so one 2 3 4 a has it because it's one two three and four right okay so that that makes sense C of 8 makes sense but why would my algorith not work [Music] so go to sleep Siri this is Rose this is [Music] calls yeah 12 and 10 4 and four 146 still getting last this one wrong here so let's look let's look at this 1422 for the C's so I need to go to the larger example draw this out okay so the problem is this gapping right here so it's not the way I'm calculating it is wrong because I'm just assuming that it's the row which allows me to capture this but because there is other C's in that row that are at different positions columnwise that's why it doesn't work okay so I know what the problem is now how do I how do I correct for that um oh really h that was interesting okay so we need to can I look at this from a different perspective if I'm here and I go here no yeah I had a CPU Spike I don't know why it should be getting better let me see OBS is having some issues here let me try closing some [Music] things see if that might help that's what I get for a streaming on a MacBook Air let's see here it still says poor well let me Focus okay I appreciate that um so if I what if I took a different approach here and instead got all of the positions outside yeah it's an it's an M2 it's an M2 it actually just it's done pretty well this is the first time that I saw that it's had issues um so i' I've streamed a couple of times um actually this is my 12th live stream video actually to be more precise so maybe I have too much going on here um okay sorry let me Focus um so I like to finish this up here so if I yeah I'm not sure it's my CPU is spiking like crazy I think maybe I just had something going on not sure um so if I if I Traverse this I I think I'm close but it's the continuous side part right that that is an issue where we've got this side here and then there's this this break and then like it's it's not it's not contiguous is the thing so think I have to be a little bit smarter about it's not just the row and column I have [Music] to I have to walk so if if I'm at a point and I can check all the surrounding points and if one of them is a point I can check so if we go down and there is there's that is considered a side because there's not another C then I can check the left and the right and if there's one to my left then I can utilize that and consider consider that as part of a side and follow that chain but if I'm if I'm heading left so like here I'm heading left so I head the direction I head a direction and I continue to follow that direction and when that is broken that is considered a side and that's cataloged and then that's visited and then I can check the other point for the other side and the other point for the other side and I can go I can continue in that direction of left and then I guess my visited would have to be the the point and the side in which we are visiting on uh I'm not sure if that sounds crazy or not but I think I think that's what we have to do here I think so so this isn't going to work so we know that's not that's not it and [Music] [Music] okay [Music] so if we come here we visit um we're going to [Music] go I think this is how we want to do it maybe I come with a better function name great if I hit the right key um but for a given Direction so the visited here is is going to be this saying that we visited this node in in full but we're also going to have um if but we don't want just this we're going to do a f.s print s print F and we're going to do the key and uh we'll do the direction so [Music] yeah there we go so we're going to check to see if we've visited a specific Direction um or if we found an edge at a specific Direction and we're in if we have we're not going to we're not going to calculate that one again [Music] um maybe follow Edge question mark um and so if we go up and we find that we're not inbound or that position is not equal so then we're going to want our RNC [Music] and our Direction [Music] and really what we want to do here is we just want to follow the edge in either direction and all we're going to do is if this is true then we want to set visited for that specific Edge um so and then we want to we want to recursively call um visited so we want to recursively call follow Edge so we we are [Music] right and then we call [Music] let me call M visited RC and then dur so the dur for the follow Edge is not so if we if we're on R and C we want to go left to right and we want to go right and we want to do that on p 0 and P1 because we want to go right to left of that um but we also need a checker which will be [Music] that so essentially if we were to look at look at this at least this is my [Music] plan we go black here and then we go 72 maybe do 64 and then if we change the font something a little bit more Monaco sure and maybe we zoom out just a little bit and then I will bring up my tablet well I got to change the font of my tablet because for some reason it's not the same um I don't know why that is but it that is what it is Ben low let's try that go bold why not okay so the idea is that I'm going to start at some position we'll say we'll start at position C and we're going to check all these surrounding areas and anytime I find that we are on an edge because that area is either out of the bounds I'm going to so like if we look at this one here that is out so we know we have an edge here I'm going to proceed to the next C or the next one to the right and the next one to the left and I'm going to determine if if this is a part of that same Edge in that direction and if it is I'm going to catalog that in the map and for that given Direction and so then that should give me the ability of you know if we go back to we maybe use this other side here starting here and I check the left side and I see that there is no um Edge then I will go down to the next C because that is in the horizontal fashion and I will check and I will see that it's part of that same Edge and then I will go down to the next one and in this case that's not a part of this Edge because there is another C here um and so that one does not count as being part of that edge so that stops the calculation on that edge then I'll go to the next point or the next Direction which is up and I see that we have another edge here so this is a new Edge because it's a new Direction and I will check the next C and see that it's a part of that same direction on that same plane and then we'll go to that next character and no that does not included and then that c at that edge has been processed already so we count that and then we just kind of go around and we keep doing that until every Edge is fully processed and I think we'll get to an end so at least that's the that's the plan that's the strategy so we follow the edge and really all following the edge is going to do is is going to Mark visited um on the appropriate um characters so we set visited to true for a given Direction it's great I don't know why it's uh an arrow here but okay maybe because this yeah not sure okay so right um so we don't want RNC we check RN C and then we're going to Mark visited true and then we're going to follow the edge until we get to an end so when we follow the edge we are so R is equal to [Music] [Music] [Music] [Music] so this is our original R and c and this this is our check R and check C so if in bounds check R check C and if M of um so let me actually do so the first thing is um M subr sub c um if that doesn't [Music] equal r m sub new R new see then we continue so that's basically saying that it's not the or we return so that's saying that if if it's not the same character going left or going right then we want to return and then if it is the same character then what we want to do is we want this is actually NR and NC so that's that new character and if the check which is going to be the direction so it's going to be above or below depending on what direction we were heading so we're going to go to the left go to the right check above or check below uh depending on what iteration we're on and we're going to see if that that is true then the NR and the NC is going to be at the check not the direction we're heading but the check in this case that's the check and so we are going to indicate that is true and then since this is also true we're going to follow the edge again passing inv visited um [Music] so if we're not in bounds or it's not the letter we're currently on we're on an edge right um then we also want to say if not m. inbounds NR n c then we return so that way if we ever get off all the way to the left or all the way to the right all the way up all the way down we just return and then we continue to follow the edge and it's going to be NR NC and the direction is going to continue to be the same and the check is going to be considered the same check so we're going to recursively follow that until we return so as long as that we are we have something out of bounds and we're following along the edge we're going to follow that edge and so that is going to give us that and so how do we how do we turn that into an ed or a score or side so I think then what that just means is that each time we iterate and we get to this point it is just incrementing and so we've got to do the same thing for this but now we have to inverse left dur up and uh I'm sorry durite and then this is dur up and dur down so I think if we do that that'll ensure that we don't double visit anything um okay and then this should be just sides at this point awesome so same input I think we just run day 12 now awesome there we go that's the right answer we got a gold star way to go uh let's clean some stuff up real quick let's just kind of walk through this um I think that worked out pretty well our strategy at least that we that we walk through here um worked out the first time at least efficiently enough um it's some seconds so I'm not you know not too worried about it I mean I'm sure there might be some way to optimize here we can look at that in a second just clean up some of the logging here yeah um so let's kind of review let's look at part one so part one we just need to go through and create all the groups uh thanks man appreciate it um so just kind of in group one we went through we walked through using a map uh using a visited node for the specific uh row and column marking all the keys or all the locations in a unique map and then anywhere we would step to all of the surrounding locations I think we could actually reduce this into just a um well maybe not um but we step through all the surrounding locations and if they were the same character we continue to recursively step so we could look at that here we have a couple of guard Clauses so if we're not in bounds um if it's not the same character or if we've already visited previously any of those conditions we exit um otherwise we set visited true because we're visiting that node for the first time and we step through all the directions kind of recursively the thing that's kind of neat about this is that um since we do that that means that each iteration we go through here of each value um since we visited it in the subgrouping uh we'll just skip a whole bunch until we get to the next you know fresh group and then work through that so I think that's pretty pretty efficient and then last we we just go through and calculate the area which is the length of the group and then the perimeter uh and then set the score to that adding up perimeter was pretty straightforward we just walked through and kind of calculated all of the uh inbounds um in that same kind of Direction directional uh thing and then finally um to round it off we had to for part two was very similar but we had to determine the sides as opposed to the perimeter and so the way that I chose to do that was to kind of Follow The Edge so we start by finding a point in the Grid or the grouping and then we visit that point and then we go through a set of directions and then if we find an edge for a single point we follow the edge in either direction just marking everything that is on that edge and so that gave us the ability of in a condition where we had a turn or a change of a side that we were able to catalog that but we could still catalog all the flat sides so once I implemented that correctly um we were good to go problem solved um I think I could probably reduce some of this repeat code here uh I might do that off stream here and do some refactoring but I think this was pretty successful so I appreciate you guys hanging out you have any questions dark Joel is about go or anybody if you have any questions or just about anything at all I can willing to answer those or we can just hang out for a bit no all right well I appreciate everybody hanging out was great uh great having everybody and uh
2025-01-06 11:03
