Advent of Code 2021 - Day 20

hello explorers and welcome to another video today we are going to look at day 20 of advent of code and day 20 let's just jump right into it so day 20 with the scanners fully deployed you turn their attention to mapping the floor of the ocean trench when you get back to the images from the scanner it seems just random noise perhaps you have combined the image alignment algorithm and the input image your puzzle input to clean it up a little for example and then we have this algorithm first here and then we have the image so the first section is the in image enhancement algorithm and normally given in a single line but it has been wrapped in multiple lines for this example for legibility the second section is the input image a two-dimensional grid of light pixels and dark pixels the image enhancement algorithm describes how to enhance an image by simultaneously converting all pixels in an input image into an output image each pixel of the output image is determined by looking at the three by three square of pixels centered by the corresponding input pixel image pixel so you determine the value of the pixel at 510 in the output image um nine pixel from the input image needs to be considered uh five nine five four ten fourth uh eleven five nine five ten five 5 11 and so on these are the nine input pixels that are combined into single binary number that is used as an index of the image enhancement algorithm and then they show how to combine them to the get the binary number the binary number represents the decimal of 20 uh 34 and then you will use this 512 characters long uh thing that you had as an enhancement to find your nine bit number and then you will have that as your character in here so it's a light pixel in this case the process can be repeated to calculate every pixel of the output image through advances in image technology the image has been operated on here are infinite in size every pixel of an infinite input image needs to be calculated exactly based on irrelevant pixels of the input image the small input image you have is only a small region of the actual infinite input image the rest of the input image consists of dark pixels for the purposes of this example save to save on space only a portion of the infinite size input and output images will be shown um the starting input image therefore looks something like this more dark pixels uh and the applying the image algorithm to every pixel simultaneously gives the output image that obtain further advances in technology the output can be done a second time and then you get this uh through thoroughly truly incredible now a small details are really starting to come through after enhancing the original input images twice 35 pixels are lit start with the original input image and apply the enhancement algorithm twice being careful to account for the infinite size of the images how many pixels are lit in the resulting image and they have said multiple times here that this is infinite in size which means that we will have a large canvas so making this a binary thing that you can enhance is not really something that i want to get into so i will create a class called lit pixels which will keep the actual um place and then i want to create a bunch of these lit pixels and put them into a set and then calculate the pixel position for each in this set and then we can handle it as an infinite amount um even if we go to really large numbers um so that's my current thought here um it's gonna be a little bit of a hassle to get that up and running but i think it's worth it um so i will do some work and get back to you and we are back and we have a result 57 17 so let's see if that is the correct result here put it in and no not the right answer it's too high interesting so i will look into this and debug some and see what i get out of this and we are back and i try to figure out what was wrong with my earlier attempt and i realized that the big problem i had was with this string here because we have an infinite amount of values and the first one here is a lit pixel which means if we have something where it's total darkness that will become a lit pixel which is really bad for us because then we will have an infinite amount of lit pixels um so my solution to this was moving from what i had here where i took a bunch of pixels around one pixel and then try to figure out which lit pixels i had around that and then return the result of that because i have this is a lit pixel here and it goes through and create this binary string from all the things around it and then we will say if this is lit or not just returning a boolean and i used it up here in order to figure out how many lit pixels i had around me so i could do an easily approximation but if you have an infinite amount of it you have a lot of problems when you have something that flips back and forth and that's the reason they said two times so what i actually did was i took and put everything at the x and y position of 50 and i read in at x and y position of 50 and i knew that i have approximately 100 of them and then i lit went through the list and looked if i had any lit pixels and i added new lit pixels and i went from 40 to 200. so i went through a lot of them and then when it i did that two times and when i was done with that i went through and checked if the pixels that i created in the last iteration here was a little bit inside of that i went through all of them and counted them up how many lit pixels i had and that got me to 53 54. i really hope that this is the right one and yes you get a gold star i got a gold star everybody gets a gold star so we figured that one out but you can still can't quite make out the details of the image maybe you just didn't change it and enhance it enough if you enhance the starting input a total of 50 times you have uh three um three three five one pixels are lit in the final output image and start again with original input image and enhance it 50 times okay so we need to have a larger canvas here um so let's go back to the old result here and say that we have we start what at 100 like that so we have a start pixel of what 100 we have a max of 500 um and we want to comment this one out and here we we start at 100 and we go to 500 so let's uh change this up so we start at um 90 um like that and then goes to 200 now we can go from zero to 500 and no problem there like that and we want to do this multiple times so let's go here and say for ins i i less than 50 i [Music] um let's say um plus plus yeah so now we do it 50 times like that we have a large canvas we can remove this last part here and then we need to count it out so let's do a let's do 10 pixels in like that into 490 so we don't get any spill out in the edges i think we can do just five pixels that's fine like that and we will count that up and if we do that for the original it will take some time and we will probably have a couple of pixels um but if we have 100 pixels in every directions we should be able to do this 50 times without creating any spill over or any issues because we have a large enough canvas and i believe that this was uh 100 in yeah so 100 so maybe we don't need 500 let's say 300 instead um so we will go a bit faster and 395 295 like that and we are back and we have a result for the 50 times running it so let's see if that is correct no it's too high you guessed that and it's too high so i have still not removed enough i guess of the canvas so let's see here let's do a little larger canvas then and remove a little bit more so let's do 20 pixels there and let's see here now let's keep the cam now a little larger canvas 400 and 50 here 50 here and then 350. let's hope that that is so this was too high was that it yeah so we will keep that too high and let's run this again see if we get a lower number and we are back again and i actually made the canvas a bit larger so 150 400 i ran 400 all the way up to those iteration 50 times and then i was thinking that the if there were any craft that was building in the edges it could build up to 50 pixels in so i made it 70 pixels in both directions and then we got a smaller number from 24 000 to 16 000 so let's see if that is the correct value let's go back here and go down here and put in 16 hundred and thirty four uh it's too low weird and we are back again and last time it was too low the time before that it was too high and i think i figured it out now first off i forgot to update this start x value which is important so we have some buffer in the beginning with 200 pixels it's 100 wide so we have 200 pixels at the end as a buffer as well it probably will grow about 50 pixels but we know that there can be some craft at the edges when we run 50 times so i wanted to remove 70 pixel on each side in order to remove most of the craft that could build up and what we got was 18 260 nice so let's see if that is the right solution yes you get a gold star i got a gold star everybody gets a gold star nice so we have sold day 20. i hope that you found this interesting i hope that you learned something today if you liked this video give it a like share it with your friends and colleagues if you didn't like it give it a dislike and you can share it as well if you have any comments or suggestions that are lit made more complex than that leave them in the comment section down below or if you solve this totally different then i'm very excited to read about that as well if you haven't subscribed please do that and i really hope to see you in the next video [Music] [Music] [Music] you

Channel: Daniel Persson

Views: 37

Keywords: advent of code, advent of code 2021, advent of code in java, java jdk 17, challenge, कोड का आगमन, कोड 2021 का आगमन, Aufkommen des Codes, advento do código

Id: pT-m7jz_zm4

Length: 16min 7sec (967 seconds)

Published: Mon Dec 20 2021