Advent of Code 2021 Day 19 (Rust)

hi it's jocelyn i'm about to do advent of code day 19. all right so we have a few scanners each with probably 3d coordinates beacon scanner the scanners do not know their own positions okay so we're determining the positions of the beacons and scanners okay so they also can be rotated um okay and we know that okay so we know that one scanner will have 12 the same beacons of other scanners okay wow this is this is crazy okay well let's start by parsing um so i've learned this from before we can do lion's thought i think it's byrep there we go um so the first line should match scanner zero or scanner or whatever number um we don't actually need to parse it um just because um just because each one is incremented by one so we can just do um lines dot next just to get the next line and then um if lines or the line is empty um then we're gonna break out of this otherwise it's a location so i don't think there's like a split twice function so we'll do um xyz is equal to line dot split on comma dot unwrap oh no it's just not done wrap then we'll say let x is equal to xyz dot next and same for y and sun and that is a point so we'll say um yeah we'll just say scanners is equal to effect.new and for each scanner let's see [Music] we'll find the location of the beacons so that's also fact new and then we will push beacons x y then now we need to parse these as well um these are going to be i-64s and they need to be unwrapped okay and scanners dot push beacons and eventually we need to break out of this so if lines dot next dot is none then we are done and let's just make sure we parse this correctly so the print line um which i'm going to print so first of all the number of scanners and then also just the scanners okay so here it says that we have 38 scanners uh which makes sense because we go from zero to 37 and the first one is seven seven four minus four five eight five two so i think that we parse that correctly that was the easy part i think with the first i think first of all we need to figure out how to rotate them um let's see i said something about degrees okay so due to magnetic alignment each scanner is rotated to some integer number of 90 degree turns around all of the x y and z axes gosh okay this is going to take a while and geometry is never my strong point i'm going to assert here that we have um exactly 24 different ones as our nice hint in the example keep us we do not have 24 how many do we have 48 okay oh i see the because the axes are relative to each other oh my god i just do my geometry is just like so bad this is what i want okay just can't read python okay now 26 minutes in we can actually get our list of rotations this is this is pretty great okay oh my goodness so for checking every pair of scanners and then for every pair of scanners we're checking 24 different rotations and then we're looking for 12 different overlaps by trying to position them such that they're overlaps what does that look like so we have it's a 30 um we have 38 scanners so 38 scanners um times we need every pair of two scanners um so yeah that's roughly that's roughly 38 squared which is enough that's 1444. you can't see my calculations here i'm just trying to back of the envelope calculation and then for every pair of those there's 24 different orientations that the first character a pair could be in we don't need to rotate both of them because once you rotate one um the other will have that same rotation that's three thousand that's thirty-four thousand or thirty-five thousand um and then we need to align them so each one each one of these scanners has um how many like how many points is that um i don't see a good way of getting this i'm just going to use sword count roughly 26 so um for each of these things we're considering there's 26 squared and now we're looking at 23 million um things to consider in order to find the matching pairs and once we find the matching pairs of things um once you find the matching pairs of of scanners then we have some have to reassemble them so is this practical at all um yes this is practice it is practical to cons to consider 23 million things i think okay yeah let's do this so for scanner in scanners dot hitter dot enumerate we're going to look at all the scanners that come after that one so for other scanner in scanners starting at i plus one um that should be good that will be um we'll need to compare the two scanners so for the first scanner we're going to look at all the different rotations and we're going to compare that to the first orientation of the second scanner you don't need to rotate both of them because i think the um the trick there rotating when it's sufficient to see if any of the if it's actually going to work okay all right this actually begins i got this yeah i got this see i forget how to do this so for the 24 different directions we're going to do this i'll probably get a clippy warning on how to improve that and then over here we're going to do four locations or for rotate yeah in rotations x y zen then we're going to i guess thought interior dot memory then we can say beacon.i push that point something like that and then we can say scanners.push beacons and that's what i meant to do the first time i just wasn't thinking as clearly as i could have about that okay this probably needs to be referenced okay so let's find all the potential off thoughts so this will be okay so [Applause] four we're doing this again for i beacon in um actually we don't we don't need the yeah we're just getting the list of possible offsets here so for beacon and beacons um and then for other beacon [Music] beacons potential offsets is going to be a hash map from the number of or from the offset to the number of offsets that meet that so something like beacon dot sorry beacon dot zero minus other beacon dot zero and then the same thing for the other two um dimensions might make sense to make types for these if we're gonna do a lot of this which i think they might be so potential offsets dot the entry for that offset um or defaults we're gonna implement that by one and then we should find lots of these that have at least 12 in common so potential offsets we're going to say dot into header dot filter i'm going to filter um to see if the count um we'll fix that in a second is greater two or equal than i think we said 12 in here is that right yeah 12. um and then we're going to map this to we just care about the offset and then we're going to collect that into the into offsets so let potential offsets now as a vector is equal to that a semicolon um what else do we need okay i'm just gonna give this let's see i mean i can probably figure this out but it's just easier to do oh i see this it's probably easier here to give this potential offset to type which will just be a hash map from point to view size point to count wonderful and this is taking a while but it does eventually finish so now we can list our point which is a good sign because that's a lot of the computation we need to do and we should get some potential assets i am suspicious oh what did i what am i doing here okay um of course oh my god look at that so now we have some potential potential offsets so it looks from this just that like potential offset slot length is either zero or one i'm just gonna start that so if potential offsets um okay and that's not going to compile it's not going to compile oh it is it just it wants to be empty okay so if let's um offset is equal to potential offsets dot um i guess we can do pop now we know we have an offset and a rotation and two pairs so now we can make a list of scanners that align with each other as along with their rotation between each other um yeah the rotation between each other and the dimensions between earth yeah the translation between each other so here we go it's probably easier to say scanners um numerate dot skip i plus one because i'm the first one first iteration you want to get the very first one this is the same it just gives us um the index of the other scanner so if we found a badge then we're going to say i j and we need to know the rotation between the two of them so we're going to also do and enumerate here so this fully describes the relationship between those two alignments um there we go okay and i want to print that just to see what that looks like so now that we have all the alignments it's probably an easier problem to figure out how those all tied together um but i still need to think about how we're doing that so if we found something that's not at the canonical axis then i think we need to rotate everything we found so far that's in that universe to match the rotation we just found so we'll have sets of scanners that'll that we know all have the same system okay so this variable is going to contain um sets of scanners that are all in the same same rotation so if k is not equal to zero then we need to rotate scanner and any of the other scanners in the same system um to be in that new system and then we add j to that system okay that makes sense so we're going to i'm going to make another loop here and call this outer and then say if k is not zero then break outer which just gets us back into this loop um i'm going to say let mute next um realignment is equal to none and then in this case i'm going to say next realignment is equal to a sum and that's high in j we need to rotate that by k otherwise we can just add to our alignment or our aligned array um and um here we're going to check next realignment um otherwise we're done i'm going to panic here just because just like to make sure that this logic is working that we're getting our next realignment and we'll figure out the system's thing in a second wonderful so that's exactly what we expected um so now that we're here we're going to say we're going to see if there's already a system that contains i and j so um systems is going to be a vector of hash sets of indices since these all have the same rotation just two so just an a element we want all of the elements um so filter let's see um items items should contain i or jay [Music] because it could contain i and j and that's even harder so let's get the let's get the one that contains i and the one that contains jane um anyway it's easiest if we don't have if system i and system j are both are birth none so we're going to deal with each of these cases separately and add them as you need to so in this case we're going to rotate eye we're going to rotate eye by um by rotation i so that looks like scanners at i is equal to actually we'll say the point of all the point so point is equal to scanners i at the rotation of i and that should be one point shin tints because scanners is oh no those are the points yes these are the points at that okay then we're going to find the knee rotation so rotations is equal to now it's the same logic as as we did here i might make a function for this in a second so this is just making it so the first rotation is rotation eye something like that um except this would now be do something fun so and really we could take it like that this is fine i think but it's easier just to like clone it okay um this is never going to finish but we can say we can now insert a system that that contains both of these so wonderful so we got past the first part and now we're at another situation so let's figure out what the next situation to handle is so at least this um that will be this hi let's see yes some system i and j does not have a system let's look at that one next hopefully that is the um hopefully that's the next one because that's the one i know how to i can just like think about how to solve right now um line 120 it's not okay maybe it's this one it is okay so let's look at this i'm curious what system is what system j is and what i j than the rotation is okay so we're rotating zero by nine to match nine and then we're trying again and we're saying that now we need to rotate zero by 11 to match 9. so something is odd here in our order here the first one is not necessarily the original demo i guess the 11th one is well this is super hockey but i'm going to say that we just swap those two does that work no it's not that nice wonderful okay so um that i guess lee is the case where i is not in the system but j is and this should be unreachable noun perfect oh no never mind it's it's this one where we have going to have to rotate everything in system i'm i'm i think it's worth extracting this into a function let's see so systems um it's like a fine mute no this okay there's intermediate but i can't get them both the same time so we need to we're going to need to enumerate these okay so in this case we just care about the index of system i so something that we're going to just like insert date into that system after we've rotated everything in system i um so what does that look like that's for i in system i we need to do the same thing as we did here i'm going to extract this into a new function in a moment but for now i'm just going to do this oh this is super cool okay supposed to panic at line 150 so this is the tricky part um because j is already part of a system and i is already part of a system oh actually no it doesn't we we still just need to rotate the ones in i in this case um but we do need to okay we do need to combine these two systems over here so um so first of all let's assert that they're different and we'll say min is equal to system i dot min system j and we have something similar for the max um and then we can remove the max one and we'll want to add it to the min one oh it panics if it's out of bounds so something like that and i don't think this case ever happens just because j is always greater than i well it does i'm a bit confused that happens but that's not going to stop us okay so similar to the first case we just need to rotate i um this is the mass okay we just need to rotate i um but instead of pushing we're just going to say systems at system j dot insert fine and now we should have everything aligned so oh my god look at that and all the rotations are zero um oh my god i can't believe we did those so after doing these rotations so it's saying okay i think we just got the sign here backwards great okay now we're just going to continue this again we need to extract this but i'm going to do that later it's easy right now just to duplicate up oh my god it's working okay i'm just gonna assume this is all working now then we can say we can go back to what we had before which is scanner sql scanners [Music] rotation dot collect and this needs to be planned and this is going to be a vector and then for all the points so for scanner and scanners for a point in points oh my gosh it's amazing here for pointing points um see we're going to insert this in two points and then we're going to return the length of points which is a size and that is fair we do not need that zero anymore okay you might need this example so i'm going to be ready to use it if i need to i'm going to actually just publish notes on files so example1.txt but we have an answer which is 457 and that's right all right continuing on to part two how far apart to the scanner is gap largest manhattan distance between any two scanners rather than points this is obnoxious because we're moving okay so we need to keep track of how much we move the scanners um that is super annoying okay i'm going to rename part a to solve and we're going to calculate them both at the same time so this is just so this offset i is what's relevant here that's the offset you know that's the amount that we're moving i we're not moving j we're moving i so we're just going to make a um yeah we're going to make a move which is a hash map and it's going to be a hash map between a point and sorry it's going to be attachment between the um uh sensor number which i guess is also your size um and the amount is moved by so here we're going to move um here we're going to move everything in system i by offset i so that's just going to look like mode dot entry i or default we're going to add those two vectors so e dot zero plus equals offset i dot zero and same for one and two and i can add this 457 over here okay these are 64's oops and we'll need this in all the other cases we do this which is here here here [Music] okay that's great now we can figure out the movement the maximum movement between an arbitrary item and the longest by going through this movement array i called the movement yeah it's called move into it our um dot max by key which is going to take we don't care about the first item and it's going to take x y zen and we want x plus y plus that mathematician distance um and then we're going to assert that they're the maximum [Music] um no actually those are just distances okay we're just comparing all of them so we have max distance which starts at zero and max distance is equal to max distance or the maximum of the distance between these two um p1.0 minus p2.0 absolute value plus that for the other two points or the two dimensions rather [Music] something like that and we're going to return that distance as well is an i-64 hmm because it's a hashmap not a vector there's definitely a default for a two ball all right so now it's running we'll just take a while but hopefully this time we shall get a maximum distance um so this unwrapper default we could have used just like a vector to store all of the movements and we need that because whatever the last j is that one is like gonna be at zero zero zero and it's not going to happen moved so that one um yeah so that one we don't have entry for and that's i wasn't expecting it to pass i guess that means that this isn't working because that's just tracking what would move the last iteration we need to track how the systems move throughout all this process now most of the reason this is so slow right now is because we are not skipping the ones that we know already good we could just continue from where we left off as far as i know this last case is kind of scaring me this none system j um no it's actually still fine it means we got to an eye in the eyes on the system but j is already in one okay that's still fine so we could continue where we left off i think um just like as an optimization but for now we have an answer and my answer is too high oh we need to we might need to rotate dammit we're not rotating those points that is nasty okay right of course something like that can't believe it okay um yeah here we go with the other example so i think once i'm finished this i'm just going to go to bed but there's a few issues still with this um mainly is that we're well there's two there's two main issues that are just gross first of all this should be really its own function uh that can be isolated to its own thing um the second thing is this align thing that we're generating we only need to generate in the last one otherwise we can just skip the first eye because that's all aligned and that would make this run a lot faster rather than needing to rerun it whenever there's a rotation anyway we have an answer that answer is smaller than the previous answer so i'm optimistic and you got it right all right wow this one is hard since long it was pretty interesting though i had a lot of fun with this one anyway see you tomorrow

Channel: Jocelyn Stericker

Views: 509

Keywords:

Id: tYcEIFwvIwY

Length: 62min 15sec (3735 seconds)

Published: Sun Dec 19 2021