Advent of Code 2021 - Day 6

hello explorers and welcome to another video today we are going to tackle day six of the advent of code and we are up bright and early exactly when it releases so just a few seconds has gone so let's just jump right into it so here the sea floor is getting steeper maybe the sleigh keys got carried this way a massive school of flowing lanternfish swims past they must spawn quickly to reach such large numbers maybe exponentially quickly you should model their growth at rate for sure although you know nothing about the specific species of lanternfish you make some guesses about their attributes surely each land of each creates new landed fish once every seven days however this process isn't necessarily synchronized between every lanternfish one lanta fish might have two days until it creates another landfish while other might have four so you can model each fish as a single number that represents the number of days until it's create a new landfish furthermore you reason and new land to fish should surely need slightly longer before it's capable of producing more land to fish two more days for each cycle so suppose you have atlanta fish with the interval timer value 3 after one day its interval timer becomes 2 after another day the interval time it becomes 1 and after another day the interval timer becomes zero after another day the interval timer resets to six and it should create new land to fish with the interval of eight after another day the first lanternfish have an interval timer of five and the second lanta fish have an interval timer of seven atlanta fish that creates new fish resets its timer to six not 7 because 0 is included as a valid timer value the new length of fish starts with an interval timer of 8 and does not start counting down until the next day realizing that you're tr what you're trying to do the submarine automatically produces a list of ages of several hundred nearby land to fish your puzzle input for example suppose you were given the following list three four three two this list means that first fish has the interval timer of three the second fish has an interval timer of four and so on until the fifth fish which has the interval timer of two simulating this fish over several days would produce as follows initial state and then they go to this so it will reset to six and this up here will be eight and then after three days these two will produce a new land the fish okay so here that one produces a new land to fish so it goes over here and then it becomes six these two produce new lambda fish and becomes six and then this becomes six so when these have arrived down here they start over at six and so on each day a zero becomes a six and adds eight to the end of the list well other number decreases by one if it was present at the start of the day in this example after 18 days there are a total of 26 fish after 80 days there would be a total of 5 900 find a way to simulate land to fish how many land fish would there be after 80 days and then we have our own puzzle input so we need to save that first off and so let's do this uh day six so let's do some simulation so first off we need to have our initial fish here and let's see how day day five is modeled here or day6 is modeled um so they it's just one line with a bunch of numbers okay so we actually don't really need to have this reader that we usually use we could just say that we have um string test and that would be those numbers and then we will have the data would be the actual input it will be a long line but it will be fine sound now we can skip that part and just consider um string as our test split on that and now we need a fish cloth of course we need a fish cloth so let's see here new claws fish so days to reproduce and that would be eight to start with and then we will have public static void final uh let's see here public and void [Music] inc day and then we will just take day to reproduce minus minus and fish child and so let's see if this fish has a child this day and so if days to reproduce is equal to zero then days to reproduce is equal to six and we will return a new fish and public void in it in days so we need to be able to set days to reproduce so we need to have a start value there and if not we return null so now we can have a fish that will be increased every day and then we will check if every fish has a new child after after we have done other things so here we will have a list of fish see so all the fish is in the sea and new arraylist and we will fix that list as well so let's start here by creating a new fish fish and then we'll take this fish and we will initiate with [Music] so we will have a bunch of fishes there and we will set an initial values for them then we need to do something for 80 days 80. so first we will um have a for loop of every fish nc in the sea under the sea let's see here um has shine fish shine if child is not equal to null then we will add it to the c fish there we go and then we will have another one uh which will increment the days here increment days and that could be just like that and down here we will have a c size print that out let's see what that says what that gives us for the first oh we started day five which is the wrong day so let's run run day six instead we got zero okay so that's interesting how could we get zero fishes in the sea that's not really reasonable right um so let's see here we have the test input we will oh that's very reasonable um i would say if we don't add any fishes to the sea then we don't have any fishes in the sea let's just add some fishes to the sea sex for co-modification okay so we can't add to a list while so we will have a new list of fish children new arraylist so here we'll add to the children list and then we will have um them added down here so c and all children so let's go for that then we got fifteen hundred fifteen thousand eight hundred and twenty and that's not the right number so if we go one earlier just to see that we didn't no so we we did something else that was not correct so let's see here if we go here we debug this then we should have five fishes in the sea that's correct and we can give the fishes to string like that and we just have days we we skip the rest of this fish thing and so let's see here if we do that and restart this what do we get uh they should be more readable yeah so now we have three days four days three days one day two day okay next iteration they have gone down one so that's correct oh we iterate that before we so we need to add the children after we have uh incremented that day let's see what happens then well it got less so let's see there we have a zero oh the fishes need to be reset to seven so we can increment that day as well could that be it so now it becomes six yeah yes and then we get two new fishes so this seems reasonable yeah so now we have five nine three four so first off we needed to add the children afterwards and the fish incrementation as we do that after we have checked if we have new children we have the problem that the counter will be increased for the ones that have exactly now reproduced so we need to set that one higher so let's see what we get if we do the full data set now go over to data run that instead then we get 352 1995 so let's put that in and see what we get you get a gold star i get a gold star everybody gets a gold star nice let's go over to part two uh let's see part two suppose the land to fish live forever and have unlimited food and space would they take over the entire ocean after 256 days in the example above there would be a total of two six nine eight four four five seven five three nine lanta fish how many atlanta fish would there be after 256 days okay so if we just change this to 256 and change over to our test data we will get what it will take a little while so this is probably a space problem could we fit it into the space allotted to us and it takes a little while to run and we hear the computer ramping up hopefully we don't crash so now we are talking moth here this is probably something that you could simplify by using more math and if i can i will simplify it by using more cpu and memory yeah so we ran out of java heap space that was expected and soon [Music] we will get more and more and more memory usage here and we will use quite a lot of it so we need to figure out a smart way of using a lot of memory um so having that many um fishes would not work but if we do it as a string we conserve a lot of space right so let's go back to the earlier examples of 80 days here and remove our arraylist we will stop reading things and we don't have any children so we go through the list of our test data a string work data equal to test so let's go through each work data and we will split that on that instead and here we'll do int children equal to zero and we'll also have string new work data and that's an empty string like that and we will also have a boolean first equal to false oh true uh if if first if not first then new work data is equal to no no no no we can fix that with the children later on so let's see we go here and we will string yeah string children we have a counter for that already so integer parse int of f and fish so we just have the number of the fish here if the fish is equal to zero then it needs to reproduce so we will take children and add that and fish will become seven [Music] okay no now the fish becomes six else fish we decrement fish and new work data is equal to fish plus a new comma so that's what we do then and here we will take work data will become new work data [Music] for foreign so let's see here each next round there will become a child so we decrement every of uh every yeah so here we go up to six again yeah so now we just need to figure out how to add the new children so perhaps it's even better to just have like that first falls through if not first we will add to children an extra comma and it's at first to false down here so now i'm doing this everything with just um just adding oh for instance we we could do now we need one less so the first one we don't need that on and then we can just have children here and then we when we are done we will just check the work data divided by two so perhaps we can just do like that and then skip the last line that could be also if f is blank continue so let's see here if we check this out how could is this working so we have work data which is that yeah so we should go up here [Music] okay work data became something totally different um [Music] work data plus children down here let's try that again so we go through here and we will pick up the first fish and decrement that and add it again so now we will have a new work data and then we'll do the same again new work data now we need to add to the new work data of course why didn't i do that [Music] always good when you debug let's try it again so we get a new work data we add to it we get new values and then we go up here to the next so we get that work data which was this one right um yeah so if we run this through we should get the same result we got the same result and we hopefully used a lot less memory in the process if we change up to days could we do this there's a lot of loops a lot of work going into it but it might be doable at least we're not using um same amount of memory here as before using a lot less memory even though strings are not the most conservative memory structures we have there are less than full classes at least but it can take a while to run this so let's see i'm wondering here now that i'm sitting and thinking about this doesn't every fish contribute to the final result equally so if we have one fish and it reproduces and creates offspring that offspring will create new offsprings in the same tempo the independent of the other fish so perhaps we can make this simpler by changing this up and doing each fish by themself so for instance if we do work data because that will also mean a lot less memory to use in each iteration so work data test split on that so that will be our work data now we just put the full algorithm in here like that and then we will take this work data and increment to fishes like that add it to fishes and then we will print that out if we do that we should get the same result over 80 days yes and hopefully that will be faster because we will only look at one fish at a time so hopefully this will work better with less memory and faster even over 256 days perhaps we even could use reuse our fish model that we had before and it still will take a while to run of course and there will be a lot of parsing a little a lot of loops and so on but we will use less memory so we have around 300 fishes here instead of five so if this takes an hour to run then we don't have 300 hours to run the other things but if it's a couple of minutes we can do it see here 300 divided by 5 is 60 so anything that we come up to is multiplied by 60 so if it's three minutes it's three hours another thing we can do is making using more cores so that will make a little use a little bit more memory but will take a little bit less time so then each fish would be one core and count their fishes and get the result back um so let's create a new fish core cuts that's hardcore and it will implement callable implement method call so that will get give you an integer back and the fish public fish core we have a string of work data this work data is equal to work data great field or start data like that and then we will just take everything in here into our fish core and that's what we want to return and then we'll take string so then each core can work on one fish pretty much and return our value in that case we would have a for loop of what we had here and then we will have fish core work work work work and let's see here we would have something called x q door executor service we would execute a service and that would be a um let's see execute our service i want one of those new fixed thread pool executors let's say that we have five threads in our pool submit callable task fish core where data yes so we want to get the result back from our callable so we submit a task we will get the future back okay last future arraylist add that future um with callable example so we want to have all the results back um so we get some futures but we want all the results back and we have a get here for each of these so we await the termination and we get the result list and then we have a shutdown there we wait for hours instead and we will have this function as well result get result list yeah we can call it result list that's fine by me um so we get the number and we will add that to fishes that and go back so let's go back to 80 stop this one and see if we can run this in five course and get the right result okay so let's change that to five seconds as they suggested one two three four five there we got the result and we also need to have es shut down so we actually shut down the service one two three four five and there it shut down so we can go back here and have 256 instead and try that and hopefully this will be in endless time and we are back and it has been a while i started this early this morning and now it's really late this evening it's not the next day yet but it's pretty close so it's a quarter to um midnight so and we have actually a result here you see that we have a really large number here and it's uh 6 million let's see so it's a million million so yeah really large number uh let's see if it is the correct number so let's switch over here put it in and submit yeah you get a gold star i get a gold star everybody gets a gold star so we actually found the right value and the reason why it took so long is because the tests with the thing that i survived to build took five hours to run and then i had to run the real data which also took five hours to run because i figured out how to do this in a really nice way so it will take not as much time and you see here that i have results for different values and this is because there are five different kinds of fishes depending on which day they start either they start of day five four three two or one and then i just figure out how many of those fishes there are and multiply my results with that and you see each run here took four hours four hours four hours and the last one took five hours and 19 minutes and of course i ran these in parallel so i used five processors or five threads over five hours in order to get this result so let's go through a little bit what i've been through here so first off i thought okay this would never fly with just having a bunch of classes so let's try to do this with strings instead that was extremely slow did not fly at all next up i tried to implement something that took an output stream and then read a lot of bytes and so on and i ran out of memory and i tried with the byte buffer ran out of memory so the last solution was actually to use files on disk so with this i've also used 25 gigabytes of data because i realized that the 256 here that's a byte so if i remove for instance one or so i will end up in the range of a byte then i just can use bytes and save them to disk and first off we have an executor service here so i started up something here i ran it with six threads in case i got more than that and then i put a bunch of jobs up here and i take this days counter that we have up here so the number here four one and so on so pick that day's counter and i see if i have any jobs that is on that specific day and if not i will create a new fish core which is a job with uh the number of total days minus the days that have already elapsed with this specific fish or how many needs to elapse until the fish will reproduce so i will decrement that value there and create a job id data directory where it will put files and then i will increment the job id and if i find multiple of this i will increment this counter that i will multiply with for each of these jobs so for instance up here if we got one then we will create one then here we will increment and increment and so on and then i will invoke all those jobs wait five seconds after uh everything is invoked and then just start waiting for the results here and when everything is done i will add my fishes up and print out the last result so if we look here this is the last result we printed out and i also have printed the duration here so these five up here is the actual fish core that's reporting back so let's look at the fish core we can start at the beginning here where i have some private variables i have a temp temporary directory it's a working folder where it will save different files and i have a start value and this is the value that the number of days it starts on so it's the number of total days minus the days the fish needs to wait until it can reproduce and i will create my temp folder here and i will start the output file as zero so the first file that i will write to is zero and then i will just print that specific number into this specific file so i start up with a file with one byte in it and then i have this little call function here where i start off with an a big integer where i will save my value with it which is fishes i will start the little instance here so i can see how long it takes and then i will create a bite array um days to live and i will have that at 32 kilobytes in order to write read data from disk pretty fast and then i have this file id that i can increment so the first thing i do is open the file in my temp directory here with file id 0 which is the first one and i will have a read variable that is zero so that's how many bytes i have read and then i will increment my file id and create an output file because this is where i want to write my data when i'm done if i read anything then i can continue but if i haven't read anything i want to break down here and don't go any further and i should have had these close before these yeah but it doesn't really matter if i close the last file but if i haven't read anything then i have don't have any more fishes to handle so then i will break so this while loop here uh so i will break out of this while true here so this while loop here will read the file and read these byte um buffers uh over and over so i read a byte buffer and i will set that i have read anything if the byte array is not uh minus one which is i couldn't find anything any data so i found some data here and then i will go through j until the number read so i can increment through the full buffer and then i will take the first value of the buffer and i will increment over that value so if we say that this is days that the this fish will reproduce and then i will take the first time and i will decrement seven because seven is the amount of days that it takes for the fish to reproduce again it says six but it's actually six until zero which is seven so it's actually seven days until the next time it can reproduce and if the value is less than or more than minus nine which is the time it takes for the new fish the new child in until it can reproduce so if the time is less than nine days or more than nine days i will type that value out if it's less then this fish will never reproduce again so i will put that to zero so i know that i don't get any minus value and get anything strange there so this fish will not reproduce anymore it's a zero so next time it will not be handled in this function up here because you see here that i had to take this byte which is assigned value and remove the sign and if i hadn't put this to zero here and got the minus value then this would be a really large value and i don't want that very important and after i have run through this for loop here i will add one fish because now i have handled one fish and then i will read the next one and the next one and the next one until i've read all the fishes of this file and that will actually create perhaps a doubly large file so it will uh be a very much larger file and then i will flush the values out after each of these uh red procedures and then i will close that file and that i will start over so as i incremented the file id here the next time i come up here i will read file number one and i will write to file number two and so on and so on so i will get directories with files in them i'm not sure if this is showing here but here we have a directory and we have a bunch of files in this directory with different sizes i think this was uh a director with something large so here i actually ended up with two files of one gigabyte in size um so that's what i used in order to get this result and i tried a lot of different things until i actually found something that worked um and i guess if you are good at math and paid attention in school you could do this just on the back of a napkin with pen and paper but as i don't really figure out all these permutations and so on i wanted to do it the more brute force way of actually creating a model and running it through and calculating how much the fishes will reproduce i hope that you found this interesting i hope that you learned something today if you have a more elegant solution you probably have leave that in the comment section down below if you like this video give it a like share it with your friends and colleagues if you haven't subscribed yet please do that and i really hope to see you in the next video [Music] [Music] [Music] you

Channel: Daniel Persson

Views: 359

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: Zx_G9TVcR_Q

Length: 57min 8sec (3428 seconds)

Published: Mon Dec 06 2021