Advent of Code 2021 - Day 20

all right day 20 starting now uh i see we have some kind of grid who are we supposed to do with this good i see like a cellular automata a nice um hmm hello i want to see hi this is q minus five c high plus five like that um get me uh hmm there's your it seven right man oh three three [Music] that's the high bit okay seven three eight zero oh what's seven eight seven three that image looks correct f405 good now you got this this bit be on the same 34 what and the first put the on that's insane that means that every pixel is an infinite image they can't all be on maybe they cannot be on off uh correct now okay i got a couple points well yeah that ad wrong submit was actually not good it cost me five minutes okay so what was going on here this is a weird problem um because of that first pixel being on which i definitely did not expect uh okay so what's going on here so we have this grid of numbers and then we're going to apply this cellular automaton rule which is like conway's game of life if you've heard of that um and so the rule is that to calculate if you're on in the next generation so um if you think this is like evolving in generations right so this is the grid on step zero and then we're going to apply some rule uh to each pixel of the grid based on its neighbors figure out what it is on step one and you're supposed to imagine that outside of this grid everything is off uh right there's an infinite sea of dots and so what is the rule so the rule is that you look at your nine neighbors um and then you interpret that as a binary number uh so you know they give this example right these nine neighbors become this binary number which if you read it in this direction is 32 so like this is the high bit of the binary number this is the low bit and then you you're given this rule string 512 characters so you look up in 32 in the string i guess 34 and if it's a hash mark then you're on and if it's a dot then you're off um so you're just supposed to apply so in part one apply this twice how many things are on in part two 50. so the trick here is that but the tricky thing about this is that um if you're surrounded by all off you're supposed to turn on in the next generation which is weird because you know we said that there was an infinite image where everything was off after one step there's actually an infinite number of things on right everything sufficiently far away from the input image is on which seems crazy but on the next step they're all going to turn off because there's another rule that if you're surrounded by on then you turn off um so on the odd number generations uh like there's an infinite pixels on i can't put that into advent of code but on the even number of generations it's finite right so like you know this image is evolving but the whole rest of the grid is flashing from uh you know on to off back to sorry i'm off to on back to off so i would say the tricky part of this problem is handling uh that you know infinite c of on in the uh odd number generations um okay fine so how do we actually do this uh so you know first is just reading in the data so get a rule string uh get the initial state of the grid i decided to represent those pixels uh that we're on as a set um and then the heart of the code is just the step function right which takes the grid and returns the next grid and it also takes the second parameter which is um sort of whether right because of this issue i was talking about where there's an infinite number of on things obviously we can't have an infinitely sized set in our language um so for those generations we're going to keep track of what's off instead of what's on uh so this is telling us if um means g says what pixels are on and equals false means g says what okay um so uh i guess a good point is that um if you're sufficiently far away from the current pixels of interest like you're not going to be interesting right like this guy we know that he's surrounded by off pixels um and so basically we need to this like interesting region can only go by one on every step um so figure out the you know basically find a bounding box for a region right the smallest and largest row in column uh and then iterate through everything in a bounding box widened a little bit yeah i don't need to widen this much but you know it's fine uh and then for each of those pixels just go through all the neighbors calculate um the binary string and then if you know that character of the rule string is on then you're on so uh some details here uh so we said this 2x3 string right so we want the row above us and then our row and then uh the row below us so negative one zero one and then we want the cell to our left you know the cell in our column and the column to our right so negative one zero one on column so it's important that this is ordered right because you start you go go by row right go above you yeah and then column my column um and also the first like the upper left guide to your upper left is the most significant bit right that's the 256th power and then the guy to your bottom right is the ones place um so we need to make sure that we're you know doing that in the right order uh and then there's this on issue right so we want to know if the cell is on we add it to the bit well so we know if it's in g and then whether or not g is on or off depends on this parameter so that's this is like is is the cell r plus dr c plus dc on or not uh and then also our output is supposed to be uh if on equals two we're supposed to output which cells are off and if on equals false we're supposed to output which cells are on um so we need to adjust that by this on parameter as well uh right i think i actually reverse perhaps somewhat counterintuitively uh so i guess this is supposed to be like what we calculate fuji too um maybe instead of being counter-intuitive i'll just fix that so then this should be equals and this should be not equals and on the first iteration it on should be true and let's also pinpoint one [Music] yeah so you know sort of a standard boot for seller talent on thing except for this weird twist of the whole good tuning on uh at every odd generation um that was kind of cool i'm uh you know i should have done better um i angled one of my submissions and then i got locked out for five minutes because i got confused i did not expect this like the whole grid turns on and off so i should have checked really carefully that for that i even looked at some of the outputs and you know saw that but i didn't think too hard enough about it okay so anyway that was day 20. see you tomorrow

Channel: Jonathan Paulson

Views: 1,243

Keywords:

Id: zDCLWtnW0Mg

Length: 26min 45sec (1605 seconds)

Published: Sun Dec 19 2021