Advent of Code in Haskell 2023 - Day 17, 18 and 19!

[Music] all right welcome to today's stream we're doing ad of code um yesterday I struggled with day 17 again I didn't get part one done and no matter what I tried it was just too slow so I eventually gave in and I did what the good programmers slash good um software Engineers do and I looked at what others had done so I figured uh I rewrote everything from scratch most of the the code I saw was in Python so I uh adapted it a bit for High School uh we're still using the arrays cuz those are quite easy we removed all the uh modification stuff so we don't have like the St modad hang around anymore um and it works for the example and it finishes on the input uh quite fast with um uh a special trick that I figured out so let's go through it again so the paring is the same right we just have an array of weights for the the heat um but we simplify it a lot right so it's quite so now instead of keeping in another array that we're modifying and writing the shortest distance to um to a given position we just keep a uh Heap uh of the positions and the directions the direction we took to get there and uh the length of the path it took to get there and then then we just keep inserting into the speed so if we we're seeing something again um we know that because we're always looking at a heap we're always getting the shortest path uh so far so then we're we're going to get seeing something again then we know we have a shorter path to it then we skip it and then the trick is if we see something again from H the same direction right so we got there from the same direction before um so that that's the trick right so instead of so so I think my Approach would have worked uh given enough time but the problem with it was that we kept trying to maintain all these paths and all the possible paths and then you were going to look at the path in the end and it was just too slow but uh with this implementation we just have two sets you know what we have visited uh so have we seen this note from this direction before and then we have this Heap and this is a nice trick H sets in has are actually just heaps uh except you know the elements have to be unique but in our case the elements are unique so it just works out so instead of um so what I do now is um I say so now we just always turn Okay uh instead of saying okay you can go up down left right we just say you know if you're coming from up you're going to turn if you come from down you're going to turn but trick is then we're going to take three steps at once or uh so we're going to take one step two steps and three steps and we're going to add that all to the Heap at once uh with the shortest path there and then we can always turn cuz if we were have if we would have gotten there in a valid way uh from without turning uh it will already be in the Heap so we don't need to think about that then we simply generate uh so all so we take the steps right so we left or right or up and down and then we just generate all combinations of those right so taking up ah so not all combinations but all uh number of times we can take the steps right so you can go up once twice or three times uh and what we do here is just so we just replicate it right so you have one two and three and then um we figure out from the um from the paths we figure from the the directions we just calculate the path and the direction that we took and then uh we just make sure that they're all in bounds we're not Escaping The Grid and then we map this PF function what does that do well it takes the current path like the current uh length of the path from this node and then uh we just add up the length of the path so we get the new length of the path right and this just involves looking up this array piece so instead of so here is where we would have like be writing it through the array or something like that we don't really need that and now the trick right so these is going to be a list of uh new nodes for the Heap hi little Lenny nice Icelandic keyboard Happening Here um uh she might make a guest appearance later today I have heard I'm getting a vanilla cookies not bad not bad at all um okay so yes what was I saying yes so instead of like creating a list of new nodes we create a set of new nodes uh which is cool because then when you add it to the Heap you just take the union of the two sets what does this do well it makes sure that so it's it's a it's it's a very fast operation right I think it's like log and log M uh like Min n m log M what like the size of the two and because one of them is quite small it's going to be super fast and then we can do this uh this is basically Heap pop right delete find men so we take the smallest element in the Heap and we take take the rest right right so uh what do we gain here now we have a proper binary tree Heap um meaning that so even though popping takes log n and inserting takes log n that's a lot better than uh popping taking o of one which is good but then insertion took o of n right which is not good so now it's super fast uh and it takes 1.6 7 seconds on the doing the example and part one and I'm pretty sure this correct but we I haven't checked it yet so I'm going to pop it in here and see boom we did part one finally continue to part two uh they also going to upgrade to ultra crues so they're even part to steer not only do they have trouble going to straight line but they also have trouble turning so it needs to me a minimum of four blocks to move H okay so before it was minimum one was minimum four however get to start good wobbly and Maxum 10 consecutive blocks without turning in the above example Ultra Clos could follow this pth to minimize heat loss uh 94 here's another example let me just say h so let's just take in these in in Min step Max step and then so instead of saying one and three here we say main step to Max step and then D exra so for the example we're going to be getting uh so cuz this is saying okay we replicated so before we replicated it once up to 10 times nice indeed but now we're doing no I'm want to three times now we're doing it four to 10 times so let me see here main steps this was one and three for the example uh this is going to be four and 10 let me [Music] see 102 still works 94 it gets the example right um 1171 in 6 seconds not too shabby what the least heat loss they can incur boom part two done and dusted so this is also what I figured about day 17 uh ah there's a mward from Jam stre we're not doing a camel though but uh we love those guys anyway uh I've been wearing a lot of their t-shirts on the stream so it's kind of like a double sponsoring anyway uh it works as I expected um because because I had seen what others had done in Python and we adapted that we don't have the he PQ or whatever but we can use sets because uh we and we get you know decent performance right we could make it better by like unboxing the integers or whatever but uh that seems like a lot of trouble uh for something that only take 7 seconds so again first of all what we were doing wrong initially and why I was hacking for like 6 hours and never getting anywhere was I was keep I kept trying to track the path cuz I wanted to debug it but that just made everything super slow cuz I had to build all the possible paths um which was not good uh so and instead of using lists we used heaps okay that took it down from like so this was before was like 1 and 1/2 minute and it went down to to for just part one and it went down to like 1.6 seconds so using the Heap really made a difference and and then the only thing that matters is the direction that we came from and then we just do the turns right and that was also the trick like do three steps at a time so do one and the two and the three steps at a time and then uh we have the uh then we then we can just always turn we're not deciding whether we go up or down and then checking if in case we go up that the path will be valid and all that we just take the steps that we know are valid and then put them in the Heap not just write them to this path right that was also what was messing it up right we had this distance array and we had this parent array and we were trying to make it juggle the things and it was just not working out okay and uh yeah like I said we had the right idea we were at the end taking multiple steps at the same time by generating all the valid paths but uh because we just did it like one step at a time and then we were filtering and adding them it just didn't work out I think also the problem was that we didn't like sync up P we took and the P yeah it was just a mess anyway we did day 17 now let's uh let's go back and do day 18 but I think we're good for now let me see uh so and then again how did I do it well like any good software engineer I uh you just you got to you got to look at what people have done before right you know we're not going to do it like right away but I feel like if you worked at something for six hours and it's just not working out maybe you you should consider uh asking someone seeing what they've done let me see touch day 18. HS module main where I did also have a sneak peak at day 18 and I love these Effects by the way and I it's gonna see it looks like this we're going to do green serum again luckily we already have green serum okay so what are we going to do here so me factor is back one of the first okay so elves already so to make sure the lagon will be big enough they ask you to take a look at the Dig plan your pule input for example r d l d r d l u l u Ru l u then they take the specified M up down left or right clearing one full one M cubes as they go the directions are given as seen from above up forther and right will be East and so on uh each trench is also listed with a color of that edge of the trench okay so let's uh take this example input here now I think um I think it was day 10 that was green theum yes this is indeed green serum okay um we're going to be copying that but let's H say pars of string so what do I need for grain theem [Music] M so de uh north south east west so there is going to be a list of uh let's actually make it up no north south east west okay that's easier uh so it's going to be deer and then a number and then some rgp code [Music] pars stir pars equals map bar sister bar one where pars Prime equal okay so now we are going to I'm sure I have split on somewhere here as well get grab split on oops in day4 we have [Music] it let's go to day 14 it's nice that we you know we done all this pre-work previous days so we can just reuse it okay let me see Power string and let me see uh d uh n s is split on is split on um let play it on space s okay and then we are going to say um we're going to say pars d d read at in n s equals a which just like this uh pars there and now if it [Music] says R is it = to East uh L is equal to West uh D is equal to South First there U is equal to up module no main iio main is equal to read file example [Music] into this will be North actually day 18 let me see day 18 day 18 rolot and scope okay East Six South five okay [Music] nice the Digger starts in one me whole cube in the ground [Music] when viewed from above the above example dig plan would result in the following Loop of trench having been dug out from otherwise ground level trrain okay so let me see um we can actually grab from day 17 also the moons [Music] right d [Music] so this is going to be uh no this is going to be west east north so we're going to get the we're actually going to get it um [Music] it's going to be upside down but that's fine okay [Music] um now we're going to see um part one okay let me just uh part one St equals where um P equals a par St okay and now I'm going to Ma just make path so path is going to be um empty is empty pass a this is D and then times and then we don't care about this one is equal to uh replicate n d concatenated with a path m [Music] so now we're creating the path which is suboptimal but it's okay we we can optimize that away later right let me see path yes m and then we going to say uh moves print part one so this is the path and now go back to day 10 and we want to say um so we had here green area and how did we do it um so if we are going east we add the y coordinate if we're going south we don't do anything if we're going west we deduct right let me see um green [Music] area [Music] GSF isal GSF and let me make this like this green area of um X comma y oh so here we have um so West oh okay so I want so East is adding and okay you're right ah so it's not it's YX right okay green area y comma X and then d [Music] let's see is equal to um where Delta is equal to a GSF is equal to a case D of so we're going east we're going to add um we're going to add y if we're going west we are going [Music] to minus y otherwi is zero and let's see green area DSF plus Delta DS [Music] so we got minus 42 I think we should just take the absolute value when viewed from the above the above [Music] example I think we did the wrong thing let's see West East we should just get 42 okay and the dier starts in a 1 M cub hold in the ground they then take a specific number of meters up down left or right clearing for 1 M Cub as they go let's actually um let's start from 1 one [Music] right all right we're getting the same cuz we're going around the [Music] they then take the speci number of meters up down left or right I think otherwise we are just adding 1 so y + 1 asz we're also counting the uh area of the [Music] Curve [Music] okay this is 60 but we're should be getting [Music] 62 [Music] let me see what is the area of the curve which is to say the length of [Music] a [Music] and then links [Music] as this is 38 let's not count to path [Music] here [Music] let we get this um 80 [Music] number [Music] it did take us a long time to get this uh green area [Music] correct [Music] let's see and what we get here we have [Music] the [Music] oh okay so it cuz it goes it goes north again right it goes east okay so first of all they have dug 38 cubic M of lava so that it is 1 M deep let me see GTI um 62 - 38 [Music] we should be getting [Music] um [Music] okay so because we're going the other way around [Music] also [Music] we're getting 42 38 we should be getting um should be getting 62 so here now we're also counting now we're also counting when we go north and south I think maybe something to do with the corners or maybe not let's see uh South one North minus [Music] one yeah okay they cancel each other [Music] out so the total length if we count all of them is 80 uh is it just 80us [Music] 38 I think so then we get the right number right no then we get the 42 [Music] damage let me see [Music] um so 80us 18 [Music] um ah now I'm doing also minus length paths which is messing me up 80 770 [Music] 16 so here I do get 62 if I count the trenches when I go right and when I go if I count those trenches and then I I think it's because I do add the let's just see what [Music] happens this is certainly 62 which is what it says it should be for the interior of the lava now let's see what it says for the input 52188 answer is too low okay we didn't get right there right on [Music] time any it was too [Music] low and maybe the um directions are just [Music] wrong I think maybe the path so the directions are not really true okay let me [Music] I had this nice uh from function [Music] right H before let's see from X1 X2 y1 X2 Y 2 is equal to so if H X1 is equal to to let's keep it in the same coordinate so if H y1 is equal to Y [Music] 2 if H X1 is less than X2 then to go from X1 to X2 you have to go East else [Music] West X1 X2 if x y1 Y 2 so let me see we add it so North so if then north lse south [Music] then let WR our good old turns function again XY X is equal to uh from XY um turns AIS turns of anything else is equal to empty [Music] list [Music] okay now let's see um most path p m being and let's see MP and we want to see um fthp I want to see uh turns dollar map first [Music] MP oh we running it on the input so it says east east east east south South South South it says let's actually sip these two together length path P length [Music] turns [Music] MP M first MP and I want to see um I want to see sip turns map p with pass p okay yeah so they don't agree and all of them [Music] right so but turns is one shorter than the path because um let me see turns of X is equal to from X 0a 0 and cuz we end in the origin R what is it saying here we go up twice now both of them are the same length and I want to actually flip it around it make make it easier for me to understand it let's see and so we go north I actually want to reverse the path I [Music] think cuz I wanted to start at the [Music] origin [Music] okay then it goes north and it ends up going west okay let me see mp uh MP Ms is equal to turns reverse map F MP now okay this is mpms and we are going to set this with [Music] um map first and and then we're going to make the green area of the mpms uh and it has to be the other way around and then if we're going west we are deducting otherwise we're adding and then we still get [Music] 80 which is off by 18 [Music] m okay so there was no point in all this let's just go back to this thing [Music] I think this is may be also [Music] m maybe I have to do do again kind of these shans right 2 * y + [Music] 1 and then this was supposed to be divide it somehow right 4 4 [Music] 2 [Music] and we had to do something like two four [Music] right [Music] so um 38 uh this is supposed to be something else right [Music] let me [Music] see so we had some um back on day 10 we did this right okay well F7 only contributes [Music] one so then we have these pipes right [Music] so there was like we're going east through a corner [Music] then East [Music] was then the Delta was um 4 * Y and Delta is minus 4 * y we're going north here is zero and if we were going south was also [Music] zero let me see [Music] so here they curve was takes it itself [Music] okay [Music] minus [Music] maybe [Music] is [Music] I think I'm having the same issues as when I was doing cre Earth theing before [Music] ding ding ding ding [Music] ding so we go clockwise [Music] around and then we need to count for the corners all right I think it's because the corners are being counted now right so now the corners are being counted that's that's that's the [Music] problem so let's say we have the path let's see and then we have the okay so we have the path and then we moves path let me print that out and so I really want to look at two points at the same time uh let me see here I really don't care about the AES here I actually don't care about AES at [Music] all [Music] let me do like this map map a x comma y comma D no y comma X comma D comma d so MP is just the list of intern ter y1 y1 comma [Music] D wise oh oops this should be y one red green area Zer [Music] MP [Music] divided by four okay now let's look at D1 and Y 2 D2 and I actually don't care about the y1 and Y 2 it's okay you1 to off um if we're going east east if we are going west [Music] to uh West to West then we deduct now here we go again okay so this is West West so if we are going um East North this is the um this is the seven case Okay so this is a plus 2 * y look at this is 2 * y um if we going east oops east south then we are we can't go east south cuz we are never uh no wait maybe yeah okay we're going east south um then we're in the seven case that's also plus two y okay now this is the East the East West doesn't exist so West West uh West South so this is the FK so this is minus 2 y um then we have the a West North this is - 2 y as well okay and then we have North comma North zero and we have North and then East this is uh two * what this is the F case and we have North West this is the seven case [Music] now South and South and then East this is the LK so that's 2y and South and West minus 2 y m mhm and here I really do need to [Music] add I already do need the X's [Music] here because I need for the last one I need to figure out uh but it did it goes to the origin the last one is um let's see so if I have this is like this let see Delta D1 D2 uh is equal to case the one E2 of it's complaining here that East North is redundant [Music] why [Music] sou I forgot a c come let's keep it the other way [Music] okay just write this function just here Bel tab why uh D1 ah because I didn't write D2 here good pattern matching catching us from disaster now green area GSF I imagine we have one left is equal to where D2 is equal to from YX 2 and is equal to um green area GF plus Delta um y D1 D2 D1 D2 now this should not probably not be like this green area so this is O here doesn't matter but this is oric so we're going to say from to oric and here we say oric so we know so in that case we go back to the origin and then we just have to say 0 comma Z ah no head [Music] MP okay now we're getting Min - [Music] 21 which is not great but it is not [Music] terrible [Music] let's see I think maybe we screwed something up somewhere so east east is four a we go east and then North that's plus two we go east and then South that's plus two [Music] um we go west and then West that's minus 4 we go west and then South that's -2 we go west and then North that's minus two as well now we go uh North North that's nothing we go North and then to the right that's plus we go north and then West that's two and then H we go south South that's zero we go south and east that's correct Southern West is [Music] minus [Music] I think we should flip the sign on all of these uh let me see minus we going to go the other way around then we get 21 now let's say it's a curve area so we're just going to add the curve area here okay so South South is going to be [Music] two this is south and then East then this is two and then this is North and then East okay now west west west two West South was uh one West North plus three east south plus two East North + one right okay now we get 31 we're supposed to get 32 okay but here we divide by two maybe we should just do right way too let's see we are suspiciously closed we are getting the right don't need the curve [Music] here 522 36 that's too [Music] high let's see uh let's keep dividing by four then we here just before so the corners are one and three but um [Music] let's not count calculate the area of the curve here I think they should be two [Music] I feel like cuz we I think I felt like we had green serum like nailed down you [Music] know [Music] ah sorry here I I am skipping a lot maybe that was just the [Music] thing [Music] all right good we got part one done and we just copy pasted our code from day 10 and we had some issues with [Music] um we just had the issue with the so we did the same counting same green area same curve kind of thing except now we count the curve also so we don't deduct the curve but uh we were then when we were doing it we were just dropping things okay um now what is the like much as small someone swwa the color and instruction [Music] parameters oh ooh each heximal code is six heximal whiches long first five distance in meters as a five digigit hexad decimal number the last hex decimal digit and C the direction to [Music] dig the hack set up can quite TR instructions okay now it's going to bite us that we did the path um but that's okay let me see par string um fire Tex G text decimal number let me [Music] see so let's convert these numbers then a five digigit text decimal number okay the last [Music] digit so then let's a part one part [Music] STS let's just write then part let's have this then be a dear what is it actually deer in string let's just have this be dear in and um here we're not going to start by paing let me see pars two here in my pars Prime this also going to be deer in string dear in and we are just going to drop that one and here we're also just going to drop that one for now and um P now path p and now we're just going to ignore this one then part one RS one part one. pars L let's see if it still works it still works so now we got a par two so let me see par two um the last digit so zero means R zero means [Music] r one means D two means L and three means U uh so we take we have the DNN so we don't care about that so we have the S you see we have the have D and the n and the the S and the S will start with a uh parenthesis so Sixx decimal digits Z so one 2 3 four 5 six so this is going to be uh like this and then like hash and then let's see h X digs is a take six s and [Music] uh so and then a deer dig is um going to be um [Music] let's just take five of s and this is a drop five take one do drop take one drop 5 S equals a parts d d d now how to convert from hexad decimal data Char X we have a [Music] we have a we have it how do you [Music] convert hasle convert from base 16 [Music] H show add base FR f h this is uh front base uh [Music] okay go numeric show in at base read bin read de read o read hex nice let's say x num is read H he now now I have to import numeric let's see read file example pr. bars to LS let's see is it correct 461 937 yes okay so it's converting correctly now I think we should um instead of like creating the let's just see what happens okay I let's just see what happens how long does it take for the example for example that's not too bad in the meantime we can uh see what happens here [Music] um [Music] so let's see [Music] um now let's see path D and then NS oh it's [Music] finished all [Music] right it finished in 1 minute that's not too bad I mean so what we could have otherwise done is kind of try to um um instead of instead of um so we kind of just calculate the area of the joints and um yeah so kind of just jumping faster but okay get status get at day 18. example input get status all right we did uh let's just leave it at that we're trying to catch up so we're not going to get commit um day [Music] 18 it push so because it is the 19th today let's just start with two days see if we can catch up yeah I mean like I said we could do this faster right by let me sketch it out sketch for Speed uh just calculate joints uh so we would have instead of replicate then we would just have you know uh East North West uh make sure to in increment the I uh add so so you know East 6 is equal to um East five plus a join Point um East six would contribute East five East six would contribute 6 minus would be then you know - 4 [Music] * would be uh East n would be n -1 * - 4 * y + 2 Etc right that's a sketch we're not going to implement it because we're trying to catch up but I think it would have been good all right let's go on to day 19 which is today's and then we are catching up you know get commit or faster day 18 ding ding ding okay let me start here touch the9 HS input example m module let's see language JY 2021 module main Weare where main iio main equals okay GT2 day19 do HS o day9 and time day [Music] 19 okay let me now do close others I think what saves us here is actually laziness cuz replicate is not generating like this path and this moves right it's not generating the whole thing and then doing it right it's consuming it as it goes um and then because we're careful we we consume we consume right but because we're careful we uh we don't build up like a huge sunk because we make sure that the addition is evaluated right so it works it's kind of cool um you know it's not super fast but it's not slow either because of laziness take that of camers no we love those guys hey and gals uh let me see past the example here now let's close the others we're probably going to have to copy okay uh day [Music] 19 like we're doing good on the stats H A lot of people fell out after day 17 which is fair it was quite difficult so now we're in like the second half oh yes I had sneak peek this before also it's a so it's like an avalanche system a so we have to accept or reject and so there's a workflow and there's some rules and then you send it to the [Music] workflow so it's a funny input that's going to take some uh paing but we will H just start with a split on our favorite let me see um okay and then we are going to do so read file example H print dot pars so pars is going to take a string and uh let's just not do anything yet so par string is equal to [Music] um so let's do here uh so close and items is split on we're going to split on a an empty line liner is equal to close comma items let's see what this gives us X excellent so now we have the flows and items so we're going to say here map ours flow map pars item where pars flow SD okay so here we are going to um have have a name comma rest and and we're going to say take so span not equal to this one okay and then um so that's the name of flow okay then it just says a 26 M A and then rfg what is this rfg okay the part is more than x rule a other because no otherwise because no other Rules match the part parts imately accepted ex musical [Music] shiny [Music] okay name [Music] X okay so I'm just going to I'm going to say here [Music] um I'm just going to drop a rules is going to be filter not equal on rest and then let's return H NM comma let's say here split on rules span St okay now um par item is the is equal to so this is going to be uh like this and then items we are going to say um it I it's is going to be um let's H get the puzzle input I just want I'm wondering if there a lot of workflows okay okay but all the items always have all of the values okay good um filter not equal to [Music] items okay and [Music] um so then we're going to have XM s split on comma it's and we're going to drop the first two here on all of [Music] them uh let's see map drop to doar split on xmus and we are going to return turn item dot dot um language record puns and let's see data item isal item X [Music] in m in a in s h deriving EQ show or [Music] read let me see here GCI we could actually probably get away with pars item cu the syntax is similar um fars item is equal [Music] to read add item [Music] nice quite easy to read the [Music] items okay um so we have the then we have the rules data rule is going to be [Music] um it's going to be one of the one of the um inss it's going to be let me see it's going to take let's not make it too opaque so it's either uh [Music] accept reject or [Music] um let me see a rule so re result let accept or reject or send to string um let's so uh instance so bars right okay [Music] so let see our result a string to result is going to be first result if a is AAL to accept uh par result oh a new follower welcome to the stream reject pars result is Stir is equal to send to [Music] stir now um so a rule is a data rule is a maybe condition result and the data condition condition it if we have a condition it's going to be a a cond it's going to be label which is going to be a [Music] character um it's going to be then it's going to say we're going to say comparison so each rule X larger than 10 m less than so it's either larger or less than H check uh so LT is just B so if it's not LT it's a greater than and then well it's just int okay now pars result pars rule so let's see map pars rule rules so a pars rule s let's see uh split so if if it's only one thing are split on colon um SD this is just nothing comma um um pars re pars result [Music] r bars Ru Tak the string and returns a [Music] Ru oh it's supposed to be like this okay if we you have only one thing it's just a result otherwise it's going to be C comma R split on S the equal a just um ours condition con C comma R result r now pars condition pars con takes in a string we try to say condition condition par con so we're going to have a character here and if this is larger than then Val and s is equal to con con a c uh false uh read at in [Music] val otherwise this is LT and let's just make this uh if LT is equal to less than [Music] then this is just this one actually okay Parts rule print PR no show condition I just say driving so you C or All That Jazz no show result driving show let's see instance show result where let's just say show accept is equal to a show reject is equal to R show send to stir is equal to stir so what I should do is I think I need to like uh look at the uh um I don't remember the over overlapping pragma I want to just do this overlapping cuz you can do this actually but it comes right after here okay where I show nothing comma R is equal to show R show just c r is equal to [Music] um show C show [Music] R okay and now what does it say now let me see here let's not derive this one a show instance show condition where show con lltv V is equal to [Music] um you do L concatenated with if LT then s L's larger than a concatenated way show V okay now we've uh shown all the [Music] rules so I think let's just do part one one where we just send them around [Music] okay okay so uh part one um Str strr is equal to let's just make it take [Music] in string let's actually make this right away just map string list of rules okay import data. map map import qualified qualified data. map as map and then a map. from [Music] list and then we have all the um [Music] so what you would want to do is like symbolic evaluation right where you kind of symbolically evaluate figure out for all these rules um so I'm guessing that the the rules are applied top to bottom system works but it's not keeping with the of weird met for example list first and the ratings all parts beginning named in okay so uh let's see process item m so we get either so we take in the map string roll and we take in a item and we turn true or turn false true or false process item rules [Music] it okay let's see uh where so in so get sent [Music] to [Music] let's do a so match and we take a list Rule and we take an okay so right okay so process item process item okay let's pause this let's say first here a match uh list of Ru and an item and a we get a result okay and then let's see chart to cell chart to item to in here to cell if it's X this is X it's m with is m a is a s match let's see R so if it's nothing we return except I think if there's nothing um [Music] okay let's see match R RS is equal to uh now let's look at the [Music] rule [Music] nothing R so there's no condition we just return R match [Music] adjust and okay so then we have okay this is not cont it's cont and now I want to just see it also here then we do um when I have to open in both windows so this is Con and how this condition look and a where s cell is equal to chart to cell a l and then a comp is equal to um if L then if LT then [Music] else okay so let's just say so so f is equal to um I is equal to chart to cell L apply to I uh this is applied to comp um well just con let's see if [Music] uh chart let's see if chart to cell L it comp well if then R LS match RS a language record wild card it's called the extension that I want okay so now let's see um process item map string rule [Music] item so we're just checking whether it's accepted or rejected process item rules I is equal to uh where so in rule is equal to rules map do bang in okay and um then we say here case a match in our it of accept Pro reject false reject reject send to K here uh this process item period and in and then where process item praying key is equal to um case rules map. bang K send to K Prime is equal to process item okay Prime I just need to go like this process item keep right okay oo another F beay welcome to the stream I hope you are enjoying the AIT of code we are doing day 19 today we started by explaining the solution to day 17 H then we did day 18 which took a bit and now we are doing day 19 part one okay so let's see here part one takes in a whatever this uh map string Rule and then list of [Music] item let me see and um adding up the xas rating for each of the accepted [Music] parts and add up item eight add up item = to x + m + a + S to in part one and then we're going to say rules items is equal to um some map add up a filter process item rules [Music] items 1 9114 h okay it was not uh too slow for the example at least I mean the way to do it is [Music] to make it uh like just figure out like given given what range what items and where but uh okay non-exhaustive functions and function [Music] pars uh maybe I never oh I didn't paste the [Music] input that was quite fast all right we did part [Music] one of uh day 18 not bad or day 19 sorry now let's figure out day two process still isn't fast enough um each of the four ratings can have an integer value ranging from a minimum of one to a maximum of [Music] 4,000 of all possible distinct combinations of ratings your job is to figure out which ones will be accepted it would be super nice here if we had the if we computed the thing like we said we should do let's see uh what is uh okay 4,000 * 4,000 * 4,000 * 4,000 it's a large number but H let me see part two where items is equal to um item over is so all possible X's so one 4,1 1 41 1 41 1 [Music] 4,1 these are all the items from one to 4,000 let's just see what happens [Music] oh we didn't do weet part one I'm being so lazy right [Music] now okay it's not doing great on time for part two which we kind of suspected but uh [Music] okay so I think we need to like make a like a decision tree we have to convert the whole thing into a decision [Music] tree so funny if this work though it works very fast for part one that's for sure that's kind of [Music] nice so what we want ultimately is we want we want a list of ranges [Music] that uh will be accepted and the list of ranges that will be [Music] rejected so let's see let's get cracking this is not going to finish it's not going to run out of memory though I'm pretty confident H top uh but it's going to run for a [Music] while let's just see [Music] import oh it doesn't even start that's [Music] badge all let's not do it this way um let's just first uh inspect the rules Let's Make A Tree um let's make it into a decision tree uh how do we do that let's see um so let's see data we have a rose tree Hogle rose tree tree so we have trees in high school which are actually um just um import dat. Tre three import qualified a data. Tre S3 so we are going to create a uh decision tree and then we're going to view it okay uh let's see deck tree takes in the rules string Rule and returns a um a tree of a conditions I think of uh C okay so uh de tree is equal to um [Music] let's actually make this like this so it has a rules and then we have the current [Music] rules um okay let's do it like this deck Tre uh rules is equal to deck Tre Prime map a rules map. Bang in where Tech Tre Prime of um empty is [Music] just so this is um so we don't have any more rules um then we default to accepting okay so this one is a [Music] node nothing comma accept let's import Tre tree and gu Constructors [Music] now nothing accept and [Music] then Tech Tree takes in rme takes in roll and returns tree condition no what does a condition look like ah no that's not what I want um takes a list of rules and returns a rule and and this so this one is nothing come I accept Okay and now [Music] however okay so we are figuring out the tree here deck tree Prime um if we have a rule and it has no Condition Nothing Comm r if it has no condition then we do node nothing Comm R and then there is no sub tree however deck tree Prime just C comma r R right this is going to be [Music] um I'm not really I don't think this is correct so let's write it down okay so we kind of want to say okay is we have here x we have here you know we want to say like for the first one so the crn you want to say h so it's okay for the first one it's going to be so s less than 1 3 51 so it is a condition and [Music] uh how do [Music] I so right and then if it holds then we have like the tree for PX okay um if it does not hold then we have a QQ said so the notes are conditions which was [Music] correct condition okay [Music] um so let me see here note condition and if there [Music] is let see if there is no condition May believe it's just an error I [Music] guess error no okay so deck tree of um just [Music] see May it's maybe condition let's see like that oh I don't know okay Deion Tre so let's just do this condition here okay just C comma R RS this is going to be tree and then we have the [Music] condition okay then we have a [Music] so then we want to have one sub tree which is like the contion and then we want to have one separate which is the like the RS the rest okay so here we check on the [Music] condition let's [Music] have either condition result and then this is either condition or result okay this is just going to be tree right accept and then nothing okay tree just so if we have de tree here de tree um let's see uh nothing comma R RS is going to be write R and then nothing cuz we're not going to check the condition here we are going to say um [Music] where uh lb we're going to say um lb equals k r of if it's accept then it's just uh tree um right so actually if it's sent to us then we do something uh otherwise it's just always write R uh but I'm always saying tree here I should be saying node right node node and case are of sent to as this is going to be left condition okay left C and it's going to be deck tree Prime of rules map. bang s so let's see deck Tre rules part one so this is the whole tree now let me we want to say a print tree draw [Music] tree [Music] draw tree and I think I think to tree dot map I can probably do fmap toer [Music] where two St so left C is equal to show C to St right R is able to show r and then I don't want to print this I just want to put stir [Music] Len so okay uh let's go back to the example so in um so if s is h less than3 1351 then we send it to PX and pxs is a is less than 2006 to kg6 if x is lesson 1416 then send it to a otherwise we send it to crn ahuh I need this here also so here I just have the condition but it's always like that um this is going to be actually I'll [Music] be aha see and now I have like a nice decision [Music] tree and then ding ding [Music] ding and then we have accept or reject right reject or accept accept or reject it's a nice tree let me see what it says for the input then we'll have a lot bigger tree h [Music] okay it's just a lot bigger so this one actually let's they split the range [Music] right okay so it's so now uh let me [Music] see we're getting there we are doing okay I feel we got the uh tree going let me just uh run it here and as [Music] well we need to um so now we need to figure out how they uh split the range [Music] so in this one right if s is less [Music] than let's see here okay um so let's assume that um so accepted it's going to be like in to INT in to int int to int int to int okay um now okay so let me [Music] see [Music] um so we're going to say take the like the range of acceptance [Music] and we are going to create two [Music] ranges um let you WR here type range equals in comma in okay we have um Range comma range comma range comma range and we have a decision tree tree either condition [Music] result and this is going to split it up into two different [Music] ranges he so we actually we're just going to do like this okay accept it so we have um x h Min X and Max X um o no it's not it's actually a list of ranges okay then it's going to [Music] return let me actually just make this into like a list of list of ranges and we are going to return arranges okay let's see uh ranges [Music] oh accepted ranges uh and then let's see if we are looking at a node right accept we don't care then it's it's equal to [Music] ranges accepted ranges if we're looking at a node right a re checked this is equal to um then none of them are accepted [Music] right this is the um let's have not have this like a let's have this [Music] um map chart range right map chart [Music] range now uh if everything accepted nothing then everything accepted that got there is accepted uh map [Music] map okay so these are the the trivial [Music] cases okay now [Music] um now I'm going to see okay accepted ranges accepted ranges and now we have a node with the left uh condition um how do conditions look [Music] again cond um there going to be Char it's going to be less than and it's going to be Val and then we might have um we won't have um right we'll have um accept tree reject tree is equal to okay so I have the [Music] ranges so now I'm going to say here um split ranges so I have the [Music] C okay let me see uh where affected range is equal to uh ranges map upang C so this is going to be the affected range okay uh the affected range is a list of [Music] ranges so we're going to create now so that for that range we we have to create two branches right those that are will be accepted in that range and those will be rejected in that range um okay so now we're going to say um m SP ranges where so SPL so now we are talking about the right value um SP takes in a range and and returns a a list of ranges which is actually going to be two ranges split [Music] a range Min range Max okay uh let's just return nothing here for now so um accept [Music] ranges [Music] ah okay and let's just say this is um Min range [Music] Max and uh then this is range Max to range Max so affected range so we're actually going to unip AR of range R of range okay so we are going to say AC map is equal to [Music] um Map update map. insert [Music] um and then key and then back a range [Music] um into um ranges okay so this is the accept map and this is the rich map map. insert see r f range ranges okay and then I what I want to do is I want to [Music] say okay this one so this one just actually map. empty okay and now I want to say a map. [Music] union accepted um act map AC map um accept three [Music] accepted ER R map reject three so the ones that are going to be accepted are the ones that are reected in the leftand side and the ones that are accepted in the right hand side okay um okay and they except and then so to split a range like this now I have to see [Music] um f LT B so then we are saying C is less than Val then else we have see is larger than [Music] Val then um so this is the range of accepted [Music] values so this is going to be um this is then just going to be range Min up to Val and this is not inclusive okay um the ones that are going to be rejected accepted are these and the ones that are going to be rejected are val to range Max um so the ones that are going to be if it in this case the ones that are going to be accepted are H Val uh but it's Max so this is min range Max Val and this is a Max rangement Val okay and here it's going to be the ones that are going to be accepted are the ones from a so then then we just actually just it's the same but we flip it so let um below equals [Music] uh and above is these okay this might work ah one like PE coming up not bad so if L then then we accept those below comma above in below comma above else and we accept those above and reject those below [Music] H wow not bad I just got some vanilla cookies let me have one he I'm going to need some paper [Music] though that's good stuff [Music] how let me filter out uh in valid [Music] ranges filter not empty and not mty m x y so uh range from X to Y is non empty uh is equal to so X is less than or equal to Y simple step uh no X will be if x is equal to Y it's actually empty now let me see here what happens uh for example here accepted [Music] so now we have this uh we're doing this part two okay and we have the [Music] um the decision [Music] trade let's see the tree of uh rules is going to be decision tree R let me just uh okay uh D3 so Tre string okay so now we're going to say um ranges H is going to be um so we're just going to uh repeat range uh one to so from from zero um so numbers in the range if it's larger than the bottom and less than the 0 to 4,01 and this is just going to be this and then we're going to say um sip XM a s ranges Char any any and this is going to be map. from list so let me Sprint here ranges is going to be map Char what the range okay so then we need to repeat actually like this m I'm just wondering [Music] um where do we actually [Music] I don't think it's a sister ringes actually I think it's just um I think it's just range [Music] SPL this is just going to be mapchart range map Char [Music] range um okay yeah now it's no longer me see okay now what if I do accept it ranges D [Music] Tre [Music] oh okay and I need a union with here merge r H okay where um so that's the trick right see merge range X1 to y1 um X2 to Y [Music] 2 and now we are getting it back into the intersection problem grab intersection we had some of this in like day five I think uh CER ranges so these are the two ways ranges can enter five rways ranges can intersect okay let's uh let's just do this again so we have a case one X1 y y 1 X2 Y 2 so this one should be empty okay none of these are accepted then we have um X1 X2 Y2 let me make it clearer which one is which I want okay then we have um this case here oh and then we have this case here to X1 y1 Y 2 then we have the case um where they intersect on the so X1 um X2 [Music] y1 y two and I think this is the fifth case um is the other one right X2 and then X1 and then [Music] Y2 and then X Y one [Music] ding okay so how do we check for this if [Music] um y1 is less [Music] than y uh [Music] X2 [Music] if y1 it's nice and X2 then we get the empty range here which is going to be [Music] ah no yeah okay so this is going to be MP range X to y1 here X1 is less than oral to X2 and uh Y2 is less than or equal to y1 it's just going to be X2 to Y2 same here uh X2 less than or equal to X1 and y1 less than or equal to Y 2 let me make sure first that if if one of them is inconsistent so case y1 is large it's less than or equal to X1 X2 Y2 case a X2 is Y 2 is less than equal to X2 so we prefer the same one and if they're both bad then we don't care okay so here y1 is less than or equal to X2 okay and oh this is supposed to be this is the comment right so here we go X1 comma y1 okay and here we have that X1 is less than equal to X2 and and y1 is less than or equal to Y [Music] 2 and X2 is less than or equal to y1 then we get um X2 comma y1 that's where these two intersect now here is probably we're going to say here um X2 less than equal to X1 and X1 less than equal to Y 2 and Y2 less than equal to my one is equal to here the correct range is X1 to Y2 now those are all the cases I can think of so otherwise error merch range uh show merch range X1 y1 X2 Y [Music] 2 [Music] H so then we here we have um if s is less than [Music] guys here um num accepted it's going to be um it's going to be um map Char range um accepted equal to uh in we're going to say a map. LM [Music] um some no product I think they should all be less than [Music] product um map a what y y - [Music] x okay merch range AB case okay this probably has to [Music] be if y1 [Music] is [Music] ch [Music] okay this merge range is just uh we need to have these lists I think and then we can figure out the length of them later map Union with [Music] let's bail on [Music] this and let's see and accepted ranges and then we're going to so accept range 1 [Music] 2006 [Music] ah I think I should [Music] uh I should not I should do num [Music] accepted [Music] then I don't how to do this I don't have to do any range merging um [Music] let's just see here num accepted um map range add to in um accept equals Trace [Music] show orangs [Music] zero [Music] mhm num accepted uh okay this should be char so this should be um so here it's all there's no um merging business going on so we can actually just have it like this and then we can again do this and this is just map JW range and now we we're not going to be doing any of that like merging multiple ranges business I think that's just going to be a big mess uh [Music] um so [Music] here so these are the ones accepted in this branch of the tree so I am going to say um Trace show where na is equal to um map. LMS ranges and then map so for each range how many elements are in the range and then we take the product of that and I'm going to say Trace show rngs na na ooh 164 distinct comp so we're not far away maybe it is if I have X I could do one inclusive [Music] I make a range is a bit bigger [Music] no so here we are looking at the okay let me change this this is going to be um y - 1us x + 1 we are so close though [Music] sh so the ranges are going to be from 1 to 4,000 so the ranges are [Music] inclusive okay um so below the [Music] number well minus one above the number so the number is not there let me see Are we almost there m M and then we do so now this is the number of numbers in the range tin dtin dtin dtin dink I got to the plus one here [Music] we are so close [Music] all of them are good except that [Music] one [Music] 167 these are the it's going to be inclusive okay that we need actually we are off by a few let see um now let's [Music] check this is s is less than [Music] 13550 as this 1 351 in 2006 and next less than 145 if x is larger than 2662 let me count [Music] those okay I think that one is correct now a is less than [Music] 2006 but um H so these are the first two here so if a a is larger than 2006 okay then we have this one and then m is okay then we accept we accept all of these now here uh it's in this Branch so a is larger than 2006 and M is less than 2090 [Music] okay so yeah okay [Music] then it says a larger than [Music] 333 uh reject otherwise reject yeah okay so s has to be larger than [Music] 537 and X has to be less than 2 440 [Music] yeah I mean I think the ranges are being correctly handled so if it's less than that we should accept the ones below and reject the ones above otherwise we should accept the ones above and reject the ones [Music] below [Music] if less than then less than [Music] Co m [Music] there some [Music] um [Music] 16 74 we are so [Music] close [Music] of all possible distinct [Music] combinations so we can have a maximum of Z [Music] yeah and I think I think this is correct right so [Music] then then it's x y - 1 - x so from 0 to 4,01 there should be 4,000 distinct possibilities well it should be 399 I think [Music] m let me see accepted and node right accept uh ranges so if I just accept everything this is um 4,000 [Music] time 4,000 exactly okay so I think the accepted is correct and the ranges are [Music] correct [Music] m [Music] BBE Val is also supposed to be accepted [Music] sh [Music] node right [Music] accept [Music] m distinct combinations of ratings and will be accepted you see cuz I yeah I feel like we are almost there but [Music] um we are getting a too high of an [Music] answer [Music] m [Music] if it's supposed to be inclusive we need [Music] to [Music] I feel like we're quite close we're just we're not getting I think we have the right idea but uh [Music] um okay look at the right to [Music] see [Music] sh [Music] maybe so I feel like we could simplify the tree also [Music] we see simplify um no right accept and [Music] let me see okay is accept node right accept true is accept false is reject all right let me see okay all same let me see uh simplify no a left children a comma B equals let a prime equal simplify a b Prime equals simplify B uh in if in if a prime equals B Prime then a prime else [Music] node node left c a prime B [Music] Prime simplify let me see and now simplify the [Music] tree driving EQ and need to Rive EQ for for salt [Music] also I did not have simplified things I do not have changed the number but it [Music] did uh because because it um cuz it removes one number [Music] right [Music] I think that's what I am messing up here I think that [Music] um yeah I think that's the thing I should simplify and now let's print the tree [Music] again let me see um Tre [Music] string [Music] so I can simplify the tree cuz if both are accept then I could just replace that with accept both are reject I can just replace that with [Music] reject okay and now let's go back to [Music] this and I think the problem is that [Music] that that uh whenever I split it it should be like plus one right so so these are not exactly correct so if less than then it is a range [Music] Min range Min Min range Max with then Val minus one that should be accepted and it should be max range Min Val right right so cuz Val it should be less than or equal to for Val here range Max now if anything above should be accepted it should go from max range mean Val + one um to range Max and what should be rejected is anything from range Min Main Range range Max wow cuz otherwise I was like um dropping one here and there so 174 [Music] that for 090 nice this is the right number that was it okay so what was the problem um problem was that we did we we were not including the value right because the above should be less than or equal to right we were cutting it out on both ends which is not good now let's say not Trace show here oh I don't think it [Music] matters okay we have a new number all right we did day 19 so now we're all caught up did take us a while though but that's okay we did uh we exploited the solution to day 17 uh we chugged through day 18 we got off by being lazy we sketched up how we would do do it but uh we just it's has scho it's fast we didn't have to do too much and then for day 19 we were so close for so long but we just messed up the split but we had the right idea all right let me add get add day9 HS input example get status get commit M D9 you push all right that's all for today we've caught up to everything hey I want to take one last look at day 17 that took so long so what was the trick to day 17 take multiple steps at the same time and then always turn because if you took multiple steps uh you you should turn next keep track of the directions and use sets as heaps don't track the path that kills the performance anyway thank you for tuning in uh we'll be back tomorrow well legally today in Sweden and with day 20 of the Adent of cod all right thank you for tuning in [Music] bye-bye