Advent of Code 2020 - Day 1

there's always a fun part when you kick off a live stream where you're like i have no idea is there anybody out there but we're going to kick off in about two minutes i'm going to be doing advent of code and the idea is that every day for those of you who have not seen advent of code they release little programming puzzles every day until christmas and uh my plan is to every day i am gonna pick up the latest puzzle and i'm gonna solve it and i'm gonna live stream the solution for fun and because it's interesting to share and because hey it's not like any of us have plans right not like we're going outside and doing stuff uh but first i just want to check that this is streaming and working and see how much latency i've got on the stream here i'm not a seasoned streamer as you can probably tell uh assuming that there's there's no that's that's not good that's not good oh there we go so am i live am i live let's have a look this is very exciting there i'm live oh hello hey renee um volume is a bit low raw i can no not that button uh how can i be louder i can no i'm as loud as i can be i'm cranked way up at this end hey you you be louder or i can bellow ah [Laughter] hello friends right let's do this so advent of code 2020. now the way that i'm going to run this the rules that i set for myself i'm not allowed to look at it in advance so i have no idea what i'm getting myself in for so every day at four o'clockish i am gonna open it up i'm gonna have a look um i'm gonna solve it today we're starting from absolute scratch so uh literally i've got nothing no code uh empty folders so what have i got myself in for let's have a look so advent of code 2020 day one report repair after saving christmas five years in a row you've decided to take a vacation at a nice resort on a tropical island surely christmas will go on without you the tropical island has its own currency and is entirely cash only that doesn't sound coveted safe to me the gold coins used there have a little picture of a starfish the locals just call them stars none of the currency exchanges seem to have heard of them but somehow you'll need to find 50 of these coins by the time you arrive so you can pay the deposit on your room to save your vacation you need to get all 50 stars by december the 25th collect stars by solving puzzles two puzzles will be made available on each day the second puzzle unlocked when you complete the first okay each puzzle grants one star okay good luck before you leave the elves in accounting need you to fix your expense report apparently something isn't quite adding up specifically they need you to find the two entries that sum to 2020 and then multiply those two numbers together for example suppose your expense report contained the following blah in this list the two entries that sum to okay okay okay uh cool so for those of you who've not done advent of code before the way that they they engineer it is everyone gets the same puzzle but everyone gets different inputs hey dan how's it going uh so uh my algorithm will work for you if you log up and you want to steal my code and run my code on your input but you can't get to the next stage by using so when i finish solving this and i get an answer uh my answer will get me through to the next round but my answer won't work for you because everyone has unique input uh let's let's identify myself via twitter hello twitter yeah authorize that all looks fine thank you very much boom okay look at that all right so i need to find the two entries that sum to 2020. now like i said i'm starting from absolute scratch here i've got anything set up i'm going to spin up an empty github repository uh nope that's uh there we go uh and i'm gonna create a folder for each new repository uh advent of code 2020. it's generic username good afternoon generic username nice to see you how are you uh yep that'll do nicely uh advent of code 2020 there we go because repetition's good if i said it twice it must be true uh yeah we'll grab one of those we'll add a git ignore for visual studio uh because that's what i'm using uh choose a license yeah mit because why not um do what you like with it just tell them don't pretend you invented it you can sell it you can copy it if anyone wants to sell my advent of code code you're very welcome to try i will make it public uh boom create repository i love this part all right we'll copy that let's fire up i got a windows terminal here uh d projects github uh git clone uh thing there we go right see the advent of code yep that's good ignore license read me fine right um so i'm gonna do this uh from the start i'm going to do it in c sharp and uh net core or net or net framework or whatever i think.net 5 is now either a thing or it's about to be a thing um and with net 5 there's no core or framework there's just.net 5. um but i'm going to do it in.net using uh c-sharp command liner console applications so since yes there's no rockstar i might do a couple of them in roster last year i tried to do advent of code in rockstar and what happened was the first day i realized i was missing language features so i spent about six hours extending the language syntax and then about two hours implementing the solution and then day two i had the same problem so with the first week of advent of code rockstar got arrays it got string joining it got multi-dimensional arrays and it was literally like it was a full-time job just extending the language syntax enough to be able to do it um but you never know we might if there's a couple of little uh if it's like previous years advent of code kind of splits into uh little standalone exercises and then like bigger ones that build on what you're doing and if we get some little standalone ones i might do some of those in rockstar just just for fun just to see what we can do with it um i'm going to do today on.net mainly because there is no risk at all of me ending up having to extend the net language specification because it's missing a feature uh right let's do a uh where are we um dot net well let's have a look at our input first so if i go back over to my advent of code get your puzzle input okay that is just a big list of numbers um so what do we need to do we need to find the two numbers in there that sum to 2020 and then multiply them together so let's grab that and save that to actually let's do this first i'm going to go into a console i'm going to do a net new console minus o day one gonna go into day one and i'm just going to run it and make sure i get a hello world uh oh an update no thank you not now dot net run boom and it should say hello world cool there we go um so something that i quite often do with new projects is the first thing that i push back up to github is just the uh so add everything git commit minus m and this is literally the command line that i ran to get from there to here dot net new console minus o day one get push there you go so if you can't make your own hello world you can go and clone that and you can steal my hello world instead right let's go into day one and we'll fire up visual studio code yay there we go oh i just done something very weird what have i done i've got obs uh the open broadcasting running on the middle window and it's quite easy to pick up pieces of that by mistake instead of pieces of whatever i'm supposed to be picking up uh okay program.cs let me that color scheme is gonna look horrible on the stream let's pick something [Laughter] hey uh apps eps uh are you apps short for something or are you encapsulated postscript we may never know um i'm glad you've been enjoying it let's that looks kind of friendly uh so there we go that looks nice we can we can see the code there i'll spin with that if you need that bigger just shout on the stream i'll crank it up a little bit so what do we got uh let's go into our advent of code let's find that right click save as uh so d uh where are we github advent of code 2020 day one i'm gonna save that as input.txt okay so far so good right baby steps so uh we need that as a set of numbers so what i'm gonna do is uh let's just go in here and uh file dot read all lines i believe will i need system.io to make that work so file dot read all lines input dot text should give us an array of strings so then we can use link to say uh select for each of those we are going to go s goes to n32 oh that's not right i need system.link because that's not going to work thank you very much so what i'm going to do file.read all lines it reads that file and it gives back each line as a string in an array of strings look spam god the internet is a cesspit all right uh hello ya naruto block user bye bye and you can dick off as well and you get in the bin there you go i know it's great because we've got this really good legislation from the eu about gdpr and not allowing cookies and all that kind of stuff surely dev i'd mod you if i knew how to do that um oh i need 50 followers all right i'm just going to keep writing code and and let the the magic of the the social network self-organize that's what i'm going to do anyway so slash surly dev ah this is probably not gonna work ah cool all right it did work i'm using restream so this is live on facebook and youtube and twitch all at the same time which is possibly a little bit ambitious for somebody with as much streaming experience as i currently have but uh hey fake it till you make it right anyway so file.readall lines gets every line in a text file uh we will take the encodings and nonsense as read for now um but it gives them back as strings and if you add strings together you get two strings joining together we need to add two numbers because we need to find the numbers whose sum is 2020. so uh we need to say uh file.read all lines and then we're going to do a link.select and for each of those strings s we want to go in 32 now we're going to skip validation because i've had a look at that input file the input file yeah it came from a website but everything in it i can see is a digit and it's not random input that we're going to be getting from users while the things aren't going so normally you do like your in 32.tripos and if you get anything that's not an integer you just discard it i think this input is safe and because i just downloaded it i think it's not going to change so we can just do in 32.parse s so that should give us a uh ins equals big list of ins uh last line might fail well let's try it let's do a console.writeline ins um and then i'll do a console actually i'll skip the console.readkey what i'll do is i'll just go in and i'll run.net run this okay so that it printed out nonsense because what it's given us is a select iterator but it hasn't crashed uh yet actually this is interesting um this is interesting because file dot read all lines dot select isn't actually going to do anything i need to put a dot to list on the end of this to force it to actually run because otherwise it just goes all right here's the thing that if you come back to it later we're going to enumerate and pass all of those integers for you but if you just say file read or lines dot select it doesn't actually do anything until we we start pulling things out of that enumeration um boom there we go system okay so we've got a list of it so it's fine input's good validation is good now we want to figure out the let's have a look at the requirements because uh why not it might be important to get this thing right let's jump over here so find so it says the two entries which is interesting so it doesn't say the first two so that suggests there are only two entries in this list that sum to 2020. this is fruity um so what we want to do is we want to start by looking okay there may be a way to optimize this the naive way of running this algorithm is we want to look at the first element in the list and then we want to say right do any of the other elements in this list sum up to 2020. then we want to look at the second element and we're going to say to any of the elements after this some with that one to 2020 third element now we don't need to look backwards because if a plus b equals 2020 we'd have found it when we look to a so we won't then need to when we get to b ask about a again you see what i mean with this like every element because addition is commutative um if we find the first one plus the second one we don't need to worry about second one plus the first one uh so what we can do uh this is probably easiest to do with a loop because let me let me do it with a loop i'm going to see if we can clean up a bit uh and i equals naught i is less than install length this is where someone in the chat is going to go oh no dotnet core framework five whatever has a advent of code solved day one method that you didn't know about um we'll see so uh as one install length doesn't have a length that has count arrays have length actually let's uh yeah that'll do um so uh first equals ins i for int j equals i plus one j is less than insta count j plus plus so this is basically saying all right start at zero one two three but when you're on zero start at one and then that one advanced and then this one start just after that and advance that one so and i equals naught and j plus naught that's fine of uh second equals ins j and at this point if ins i plus ins j equals 2020. uh so at this point we found our match so just console.writeline found it now if i run this what i'm expecting to see here is a single line that just says found it um so let's uh i don't think i've got what does f5 do in vs code at the moment uh net core yep that's fine that's fine all right fine add uh yeah launcher.net called console app that's fine all right run it boom and see what we get eddie yeah yeah yeah all right i'm going to fix this before tomorrow for now i'm just going to do good oldfashion.netrun.net run so i'm expecting to see found it once exactly once okay that's good it means there is a single single pair of correct solutions in our data input so there is vs code we want to know what those actually we don't need to know what the solutions are um we just need to know what the product of them is so ins i multiplied by ins j reason for this is if you look at what the advent of code brief is um multiplying them together produces the correct answer find the two entries that sum what do you get if you multiply them so that's what we need to put in there to get to the next step so the the sort of minimum viable solution here we just want need to know what the product of those two integers is i times into j that's done and at that point uh we can just uh yeah we can just return because we're in maine that'll do fine let's run it see what we get there we go look look at that we got a number so uh let's see if that works uh damn so windows terminal has a ctrl shift c and ctrl shift v for copy and paste which is not quite like uh normal copy paste submit that is the right answer we are one gold star closer woohoo amazing winning at the internet all right uh let's let's push that lot to actually let's just have a quick look at this um so there's two reasons to look back at code we've already done one is could we make it more obvious the other one is could we make it any faster you know their optimization opportunities here um uh highlighting single right clicking one term to copy paste let's try that if i do that and right click and then come over here boom yes you can thank you promo fo we learned something today so let's jump back over here now i'm sure that there could be some interesting optimizations here using uh so there's a method and link called skip which will allow us to jump in halfway through a list and um enumerate uh from that point forward in the list but let's come back to it let's see what's in part two uh so let's continue to actually i'll push that to github then we'll continue to part two so i get uh dot get commit minus um well um so sorry dev says it's annoying that control x cv need the shift key modifier um the whole ascii thing kind of dips control c way back in like 1968 uh as an interrupt character for a mechanical teleprinter um and no operating system sensors had the guts to use control c for something else when you're looking at anything that might once have been printed on a unix terminal so there you go right part two the elves in accounting are thankful for your help one of them even offers you a starfish coin they had left over from a past vacation they offer you a second one if you can find three numbers in your expense report that meet the same criteria so using the above example the three entry okay so there's a set of three numbers in here now which will sum to give 2020 and we need the product of those three so we can we can use exactly the same algorithm what we just need to do is put a third loop inside the second loop that's inside the first loop i think because again the uh we don't need to backtrack so if a plus b plus c equals 2020 then for any given a we can look at all the b's and for any of those b's if we find a matching c that's good but we never need to look backwards there's no risk that we're gonna find a number and we're gonna need to look earlier in our list of inputs so i think i think i think i think uh so that's uh day one so let's just uh split this out um i'm gonna break these out into a couple of methods so that one is class program uh static uh inch solve part one [Music] list of int inputs okay so the input's the same in both cases we're going to read but then we need to do something slightly different with the the integer stuff so if that equals that return that so that breaks that out into a method for us boom there's that let's call that ins okay okay okay why is that complaining there uh because list int ah yes um a little weird quirk of dot net count is a property but in some instances counters author also a method and the uh generic list interface we've defined here is gonna complain that needs to be static list could not ah yes i need system collections generic now i can pull those back out that will work uh what are you complaining about solve part one uh not all code paths return a value all right so if we get there and we haven't found anything we could return zero we could throw a new not implemented exception um let's just return zero that that's probably the easiest option it's not like we're going to be launching rockets with this thing or anything so that's fine and then uh so solve part two is basically solve part one so i'm going to do some copy and paste in there and see if what we can do to to strip it down and make it more interesting so static and solve part two see if we get the correct answer out of this so n i n j is less than that last second and now you can probably guess what's going to come next and k equals uh j plus one uh k is less than in stock count k plus plus and var third equals ins k vs code has some very interesting behavior where in certain circumstances if you type something it thinks you want to wrap whatever's highlighted with the thing you just typed instead of over typing it so now if inst j plus i plus j plus in k equals 2020 return that times that times that so there's all that lot solve part two that's fine that's fine except that return statement needs to be out there right let's see what we get off self part two um console.writeline solve yeah they are yeah absolutely right good spot um yeah so um yeah the comment i've assigned first and second into a variable and then i've completely ignored them so that can actually come out because we're not using it and that can come out because we're not using it and that can come out and that can come out and that can come out because we're not using why code review is important and why pep programming is good so let's see what do we get off south part three uh ins there we go uh part two rather my brain is really not firing on all cylinders today but i asked them to delay the start of advent until i was feeling better and they said no it has to start in december because tradition so here we are uh why are that back in so main ins there that's that's that's that's all right let's run that see what we get ah cd day one dot net run boom there we go okay so highlight right click that'll work let's try pasting that in there that is the right answer you have completed day one woohoo look at that yay and tweet the thing why not tweet everything there we go one click social media engagement right let's have a look at that code and see what we can do to make it a little neater and more elegant because we got a bunch of stuff in here that has been uh kind of replicated from from one method to the other and what would be nice what would be interesting here would be a method so something i often do when i'm playing around with code is i write the signature or i write the function call i wish i could run and then i work out what code i need to write to be able to run that function so the scenario that i've got here so for part one we needed to sum two numbers to give 2020 for part two we needed to sum three numbers to give 2020. [Laughter] and so hey loose how are you doing um so what i'd like to be able to do is i've got this this list of inputs here that's all looking pretty good uh so i'd like to be able to say var solution equals solve which doesn't exist yet and i'm going to say here's my inputs this is how many of them i want to count up and uh this is the sum that i'm looking for let's make that a little bit more explicit here so uh how many inch to sum equals 2 what is it the thing we want the um so let's say how many insta sum and we want that to the the required sum we could call that target i guess naming things is hard way harder than writing code and then console.rightline solution so that's the method that we want so ah you can heckle one of the best ways of learning anything is to go on the internet and tell them what you think the answer is um because if you go on the internet and say uh how do i how do i do this people just be like busy can't be bothered but if you go on there and say something like i'm going to build a dom diffing algorithm you get loads of people going no you do this instead what are you you you simple um uh cunningham's law the best way to get a right answer is to share the wrong one and wait for people to correct you um so it's entirely possible that by the end of this i am going to have learned more.net than i have in years just from people watching the stream and going that's not how we do it anymore uh maybe some rock star later in the thing chris maybe um actually if we got a bit of time i i've nominally put in an hour a day to do this uh some of the advent of code things are easier than others this one we got the two right answers already took about half an hour with 25 minutes to solve it um maybe we could have a go at doing this one in rockstar at the end but first i want to i want to sort of simplify this a bit um so we've got this this method now that i want to write i want to write a method called solve and solve is going to take a uh a list of integer which is the integers that i'm i'm summing it's going to take an int which is how many ins to sum and it's going to take an int which is the required sum so as well we need to stop think for a little bit because i think we can probably this is kind of it smells like recursion it smells like something we could do recursively because in each instance what we want to do is if we've got a particular number we want to see does anything in the rest of our input we've got a scenario here where we've got kind of like a head and a tail thing we've got this number and we've got the rest of the list and if this number plus anything in the rest of that list adds up to a particular sum then we found our two solutions we want to know what it is we are headed for recursion if you don't know what recursion is see recursion um so what i think we want to do here is uh let's uh so so let's let's say var head equals here we go you can tell it's getting a little bit lispy here because i'm about to use a head and the tail on something if our head equals install first so we got that's the first one of our tail equals ins dot skip that's the rest of them now in this instance what we want to do is say if well what's going to be the escape case here so if so so we we we've got a list of things the summer requires some selected elements as the required sum so yeah but what are the selected elements here that's that's the thing we need to ascertain what is the base case in our recursion uh so i think so the the recursive case is going to be all right let's knock the head off the required sum and see what yeah tail and because tail is still going to be a list um so there could be a scenario where yeah so one of the things about recursion i always think like building recursive algorithms is a little bit like building an arch it's like it doesn't make any sense until suddenly it clicks and then the whole thing fits in it it's base case equals if how many insta sum equals two then exactly match on required sum in list so what we wanna look at here is that's all we need to do um so the scenario okay let's start with the the noddy case let's start with the the simplest possible case we got here is actually how many insta sum is one and the required sum is two thirds if we only got one input um then what we need to do is find that number in the list right and then if we got two inputs we need to look at the first one and see what's in the second one it tails the empty let's return otherwise try adding the head to the accumulated total and check against the total so i think instead of adding an accumulator on the total what we want to do is decrement the required sum by the current value of head um so let's look at uh head uh so if head equals required sum return head otherwise we want to uh return solve and at this case it will be so install skip one so ignore the first one um how many insta sum is going to be the same we're kind of ignoring that for now this is no no no how many insta some so there's a there's a guard close in here if we're looking for three but we find one plus two equals two thousand and twenty that's not right it's not strictly recursive this thing needs to decrement by one so if the head is the required sum and the how many insta sum equals one return the head otherwise uh return solve so let's see what we've got here let me just give us a little bit more space and return insta skip one how many insta sum [Laughter] this is the most confused or rather the most stuck i've ever been on a live stream but we'll figure it out so that's fine that's fine that's fine that's fine that's fine that's fine so that's let me just see what happens with this i'm going to try this on and see see how it fits uh okay so install skip is going to complain there because skip returns so that actually needs to be an innumerable of int uh that should give us a solution so let's that's fine that's fine that's fine that's fine uh there we go and i'm going to run that see what it does because it might fail in a way that is enlightening that is definitely enlightening what's at the top of that stack i don't know what happened there ah sequence contains no elements i know why that's happened that's happened because we've knocked things off the stack that needs to be first or default and if head equals default int then we want to return well that that's our blue up that's our you didn't find any numbers case throw new exception under what circumstances in in dot net vs code i have a question for you is it more likely that i need a new style uri parser than that i want to create a new something like seriously where do they get these hints from um right let's try that boom of course but that's not going to be at the top of the stack so let's let's let's put a uh try that lot and equals that console that right like that catch exception ex and console.error.writeline ex dot message there we go and this is the point where you should put a logging framework in but we'll come back to that for another day dot net run that no net earn is not the correct thing dotnet run that thank you you have a good thing or one of your hands moves a little bit faster than the other oh run out of inputs okay that's cool so let's now that's because the number 2020 doesn't appear in our inputs anywhere so let's have a look let's pick something that does 1934 it's very good year let's try that one so there's our program.cs let's see what we get with 1934. run out of inputs interesting why did that not work so uh it's because this number here yeah you want the minus headed and that's not the case where the head didn't match so so we have a we have a scenario here where if the head doesn't match so if we only have if we find the number we're looking for yep we want to return so the accumulator here actually needs to be a multiplier um aside from minus one on the middle parameter or the minus head on the last one yeah yeah so the how many ends to sum is right let me think about this for a second so if the head equals the required sum you have to decrement yeah we do but we kind of don't because we only want to do that when we find a solution we don't want to do it on every every case so if the head is the required sum yeah the return statement logic only applies a place only if how many insta sum equals one uh i i knew we'd get to 40 minutes and some would say try functional instead of recursion uh but i'm fascinated by recursion now because recursion should be possible um we have already solved it of course you know the the product has shipped the client is happy at this point the solution has been implemented um but i'm trying to figure out what we need to do to make this thing so the head is that and if the head is the correct answer so if if the head is base cases here are we've got enough right wait a second that's fine yeah finding no matches will be a normal case ah yeah well actually if that one we want to return one because at some point we're going to need to multiply what we've got in our accumulator by the uh because yeah we want to multiply this match by that much by the next match correct so we need to be able to say uh let me just shrink this down a little bit uh i've got huge chat from the days when i was at the the far end of the room doing this kind of thing there we go that's better so right the base case is we give it a required sum and if we find that we return it and if we don't then yeah the aim the aim is to return the product so let's let's um uh yeah we need to add them at some point so what what we need to do is to decrement the required sum uh so first case scenario find us this number and if you find it return the product of this and the rest of the list yeah that's that's that that okay this this is what i think we need uh if you find the number you're looking for then you want to return uh that multiplied by the solve of yeah this is this is it this is it this is it this is it so head equals that um insta skip one so if we find the number we're looking for return that number multiplied by the solution of that how many ins to sum minus one and uh required some minus head i think that's definitely or that's probably the the syntax we want on the kind of the accumulation the recursive case so if yeah no no that is the case when the list is empty inside the upper if so yeah yeah it is if head equals default end so that that's if the list is empty um actually we can do that with uh if ins dot any so if there aren't any ants return now if there aren't any ins it's gone wrong we're not going to hit the end of the list if there is a solution that exists we should never get to the end of that list so at this point we should be able to throw new exception because in every other case at some point the required sum that we are now looking for will be found if it's a if it's a valid scenario if it's a case that we can actually find then the required sum that we are looking at is going to occur inside the the what we've got somewhere yeah so if we hit the end of the list it means we're looking for something that's not there so that is always going to be an exceptional case thrown your exception no matches found boom so that's gonna blow up uh yeah chris you will if you pick two numbers which there isn't a third um but in that case ah yeah i see what you mean um oh this is fruity [Laughter] yeah because we may have picked started with the wrong two numbers yeah so if that so what the hell do we return how do we what are the different return cases we got out of this right so yeah it is so we need to uh so it's a recursive search so what we need to do is look at base case what do we do if we look for a single integer and we do not find it anywhere in our list um and at that point we probably want to return what do we do if we return zero so if we run out of stuff we return zero there's nothing left um ins equals first dot default and then if head equals required sum return head else return solve and stop skip one how many instasm will be the same and required some will be the same so this this this what we got here this should work for finding a single integer in a list of integers so we should get back if it's in the list it'll return the number we asked for if it's not in the list it'll return zero let me see what this does when we kick this thing off why is that complaining because i'm missing a thing on there so let's don't net run that okay so that's finding 1934 if i change that number to something i know isn't in the input that might be a bit big for an 32 let's run that again zero all right so that that'll give us a number if it exists and it'll give us zero if it doesn't so now what we got to do is say all right so for a given head if we subtract that head from the required sum can we solve the uh equation using what's left in the list hmm so if head is the required sum try this what happens if we so that's gonna knock that one off so all right let's imagine we got a list of numbers one two three four five six seven eight nine and we are looking for three integers that multiply to all the sum three integers that sum to give uh say so exactly three are there multiple ways of getting 16 out of that set of integers uh yeah there are there's two plus six plus eight okay so the input actually has some constraints on it because there can't be multiple solutions that some to give the same thing ah this is fascinating all right we got 12 more minutes i said i wasn't going to spend more than an hour on this if we can get it working recursively in 12 minutes we got it recursively yeah if not hey never mind it was good fun so let's say if instant return zero if not then if [Music] we need a what's 24 keith what do i want to use 24 yeah even the first head you may not you may find may not be part of the numbers you are looking for is exactly right so we've got a uh a lot of scenarios where if seven plus eight plus nine yeah you're right yeah 24. okay so at this point if the head is one then the tail is gonna be look for 23 in two three four five six seven eight nine at which point our recursive case is gonna say the head is now 2 which is saying look for 20 so at this point it'll be 23 minus 2 in uh three four five six seven eight nine at which point the head in our next recursive case is going to be three and we are looking for uh 23 minus 3 20 minus 3 and okay so the integer to uh yeah all right so the how many insta sum that's important we need to decrement that every time we recurse because that's the thing that says this did not result in anything this is your you didn't find anything in this enumeration so at that that point we need to say if yes this is surprisingly complicated to do with recursion and easy to do with loops hang on hang on hang on hang on hang on hang on right [Laughter] hey so i think the uh ah yeah so if you're trying to uh yeah yeah how many instant sum equals one well actually what we want is if if i think how many insta sum is the thing that needs to be decremented every time um so if let's try this how many ins to sum equals zero then this is our bailout case this is you need to stop doing stuff now that that's so at this point we return zero there may be a way so i think that that's the the slight complexity that we got going on in here is that a solve can either succeed or fail and if it succeeds it'll give us back a number which is a product but if it fails it should give us back something that indicates we didn't find anything there we go okay i think we're onto something with this one so if if there's if how many ends to sum is zero or if we have run out of numbers to search then return zero yep otherwise uh if uh yep uh i think i think i think we got two different bailouts yeah the product will be zero but then i need to be able to check whether the product of a kind of it's kind of like a depth first search thing as in for this input you need to then go all the way to the end on all the different possibilities and if any of them return the right solution then you found it but if they don't you've got to go all the way back up to kind of the root of the tree and then recurse down a different branch from there and then all the way back up so i think we've got the edge cases we've got here are if the head equals so if how many is the sum of zero or we've run out of ins we return zero that's fine if how many uh so var head equals in stop first that's the first one so if how many insta sum equals one because we only want to return if we got to the point where we're only looking for one more number right if we're looking for two numbers we can't return anything because we don't know if there's another number left in the stat in the in the list to go with the one we just found so if how many is to sum equals one and head equals the required sum return head otherwise we want to return head multiplied by solve on ins dot s ah what no come on in start skip one how many ins to sum minus one and uh required sum minus head so see what that does i'm i think there is possibly a case in here where uh yeah we probably could do it entirely with link nick uh first you've got to figure out how to solve it then you've got to figure out how to solve it using link okay so that's returning zero that's interesting so at that point um ah hang on so basically there um yeah if anything if we get to a zero then it means we're going down a dead end we need to we need to backtrack and we need to try again so we need to see what that does yes i do so the the font is a thing called uh it's called fire code here and it's brilliant um and it does stuff like if you're in uh vs code so uh double equals goes to one of those triple equals goes to three lines like that um and it's got stuff like not equal to and uh if you're using like f sharp with pipe operators it turns them into little triangles and it's really cool and it's awesome and and you should check it out um uh use the thing called ligatures which if you're into typography and type notes and stuff then then that it is kind of fun uh so um i'm genuinely wondering whether it's possible to do this with recursion and uh it should be because it's a depth first search kind of thing yeah map the sole function over the tail filter the zeros out and return the one number that's left so okay maybe there's a much easier way of doing this generically which doesn't involve recursion uh that goes there they said that is that yes yes yes yes yes yes yes yes uh return solve ins dot skip one actually let's do a nice var tail equals install skip one um uh so tail how many ins to some required some let's see if that does it all right so that's 1934 off instasum is one and required some equals that so if we plug in two and 2020 what do we got oh look at that magic thank you cynthia you're absolutely right so our base case here if we say yeah yeah yeah what was [Laughter] what was missing is that if the number we're looking at doesn't give us any solutions at all what we need to do is then restart kind of the whole solve algorithm with the same uh insta sum and the same required sum but now we need to start at the second element because it could be that the answer is the last three things in the input so yeah that that's what we need is the the base case is so if we run out of anything and run out of inputs we return zero that's our this is a dead end flag and then for each element if this one solves the puzzle we give it back and that then multiplies it by the next one on the stack which multiplies it by the next one on the stack which gives us back the product uh otherwise if what we need to do is to ignore the one we're on and move on and look at the whole rest of the um rest of the puzzle so let's just check that was three 2020 let's see what we get yep which i think that was definitely the answer to part one and that one i'm pretty sure is the answer to part two uh let's punch that in and see whether it gives us the right thing yeah that should be fine submit that oh i already completed it yes return to day one yeah that's fine both parts are complete yeah yep two five seven seven seven eight eight three six two five seven seven seven eight eight three six hey that was fun thank you gang and we're two minutes past five so so it took like a fraction over an hour um and i wouldn't have got that without uh your help so thank you very much for that but there we go we got solutions to both parts of day one and then got this wonderful reusable recursive beautiful solvable solution uh so let me just put a naive solution using four loops for part one and naive solution using four loops for part last part one that's part two isn't it and that's a for finding the product of a set of integers in a list that add up to a given sum boom hooray hmm i am wondering if we can do it with link but anyway that's all for today i'll see you all tomorrow for day two uh so there's apparently a thing you can do in twitch where you send all the people who are watching to somewhere else but i have no idea how that works i'll research that later thank you again that's a lot of fun i'm outta here

Channel: Dylan Beattie

Views: 5,315

Keywords:

Id: dBpXhygf9r8

Length: 65min 14sec (3914 seconds)

Published: Tue Dec 01 2020