Algorithms + Data Structures = Programs - Episode 267: Advent of Code 2025 (Day 2 & 3)

Episode Date: January 2, 2026

In this episode, Conor and Ben chat about Advent of Code 2025 Day 2 and 3!Link to Episode 267 on WebsiteDiscuss this episode, leave a comment, or ask a question (on GitHub)SocialsADSP: The Podcast: TwitterConor Hoekstra: LinkTree / BioBen Deane: Twitter | BlueSkyShow NotesDate Recorded: 2025-12-22Date Released: 2026-01-02Advent of Code 2025Day 2 ProblemDay 3 ProblemC++23 std::views::chunkchunk Hoogle TranslateBQN fn.ChunkBQN ↕ (windows)Ben's Day 3 AoC 2025 in C++Ben's Day 6 AoC 2025 in Pythontranspose Hoogle TranslateConor's Day 2 AoC 2025 in BQNConor's Day 3 AoC 2025 in BQNConor's Day 6 AoC 2025 in BQNIntro Song InfoMiss You by Sarah Jansen https://soundcloud.com/sarahjansenmusicCreative Commons — Attribution 3.0 Unported — CC BY 3.0Free Download / Stream: http://bit.ly/l-miss-youMusic promoted by Audio Library https://youtu.be/iYYxnasvfx8

I definitely don't think about things in recursion, not even initially. And my default way of thinking about things is like the collection-oriented. My collection happens to be an array. Yeah, yeah. But, you know, if you're in Haskell, any other functional language, it's composing operations on these collections. I assume you did that with some kind of hash set or something like that. Yeah, I just threw them in an audit set.

So I was doing these in BQN. You were doing these in C++, I said. Originally in C++, although another aspect of advent of code is that, At some point, dynamic programming rears its head, which is to say memoization. And indeed, this year was no different to previous years, like some time around, I think, of day five or six. In particular, there are graph problems, which immediately become fairly trivial if you can just say, memorize the function.

Is an auto I equals Stoodmax element, begin, end? And why is this elegant? Because you are storing the iterator, aka essentially the index, and the value at the same time in this eye. Welcome to ADSP, the podcast, episode 267 recorded on December 22, 2025. My name is Connor. Today with my co-host, Ben, we chat about Advent of Code 2025 in C++ and BQN, days two and three. It is December. Today, as we record, it's the December 22nd.

Yes, Avent of Code. Have you been doing it? I have, yes. And this year, have you looked at it this year? So this year, it's a little different. Okay. You know, it's a lot of work for Eric every year. Eric spends, you know, he starts, what is it, he starts in spring or something. You know, like it's a significant amount of work for. Eric and his team of testers and you know that kind of those folks who work on it anyway he's

been doing it what 10 years now 2015 was the first one so 2025 now is the 11th one I think that's right and fair play it's just too much work for him to fit into his schedule which means that this year it is only 12 days it's still there but it's cut down to 12 really that that explains a lot. So it's over. It's, you know, here we are 22nd of December, and yes, advent of code is already over. I did not know that. So, I mean, I was not in Toronto at the beginning of December.

I was in Australia. And there, I think it drops at 3 p.m. or 4 p.m., depending on which city in Australia you're in. Okay. I did the first two days. And then the third day, I was, how do I word this, upset by the difficulty of part B. I algorithmically thought about it and knew how to solve it. And I just thought to myself, I did not want to implement this. And so I stopped.

So I got two and a half days into it. And for the listener, if you've been following along, it was the question where you're given a sequence of digits and you need to find, like, the largest part a is find the largest two digit number which is pretty trivial um and there's some criteria that like you know it's in from left to right or something uh it's it's not just extract the two greatest digits i don't think there's there's some extra criteria maybe and then part b is do the same thing but for nine digits which is for day three oh i was shocked interesting uh because it's not algorithmically that difficult yeah i I found day three easier than day two, actually.

All right, well, here we go. We're into it, folks. And I don't even remember what, I don't think I was very happy about day one or day two either. I think day two, I think was easier than day one. I mean, let's just pull it up. Or if you remember, you can, what should we talk about, though? Should we talk about day three first, day one first, day two first?

I don't know. I'm not sure I can claim to remember any one day in particular, but, um 2025 all right i got they i got five stars folks all right yeah i've more or less stalled out at 21 stars i haven't done which is so there are 24 total but without vent code you always get the last one for free i think so i so i'm just missing part two of day nine and 10 which are the really difficult part two's and and i guess to follow up on my previous statement when i said that makes a lot of sense my reasoning was that because there's only 12 days, they ratchet up

the difficulty more quickly. That being said, you said you found day three. Yeah, and I don't think that's, you know, I don't think the difficulty ratches up particularly. This year doesn't strike me as having, so in some sense, every year has one or two days that stand out in difficulty.

So this year is no exception there, but I didn't notice a particular steeper ramp of difficulty this year. Okay. But I can say you know, at some point, the harder ones tend to be significantly harder to the point where oftentimes folks use a library

to solve it, like a linear algebra library or whatever it might be, or a graph library. When I come up against questions like that, I tend to, that tends to put me off a bit. Oh, I see. And sometimes I can do them without a library, and sometimes that's where I just stall out. At some point, my brain just says,

well you know if there's a library then the solution exists so the problem isn't interesting anymore it's kind of that train of thought right all right so what should we what should we also too if you had a question in mind that you wanted to to chat about we can chat about that one but uh if not we can chat about day three day two well let's chat about one that you've tackled i think so i'm open to any of them i'm curious uh i'm curious about hearing your day three solution if you think it was easier but the question is should we do day two first and then talk about day three or do day three and then go back to day two let's talk about day two so day two if i refresh my memory you're given these hyphen separated numbers right representing ranges

that represent ranges yeah and then it asks you to find invalid IDs that i believe have the invalidness is that if they have repeated sequences correct so for part one specifically an invalid ID has a twice well one time repeated has as has a repetition of a sequence of digits so any two digit number but it is only a double repetition it's not three repetitions four repetitions right that's important for part one meaning that if you if you slice your digit or not digit. If you slice your number in half, you should have the same two halves or partitions of that string or number. So immediately, it's only numbers with an even number of digits. Yeah. And I think doesn't it actually say that is there only even numbers or

maybe not? Well, you're given, you're given ranges. The task is for you to figure out the sum of all of the invalid IDs. And valid ID is any number in any range which has the property of being in two halves identical. Right. I mean, I did nothing fancy for this. I just brute force this for both parts. The first part, brute forcing it takes no time at all. The second part, so the second part is invalid, not just if you slice it in half, but if you slice it into any equally lengthed partitions. So if you have a nine digit number and you slice it into three parts of length three if those all have the same equal value that is also invalid and you can brute force that with an algorithm that exists in many libraries and it does it exist it doesn't i guess it does

exist in uh c plus plus 23 in the form of chunk um so if you okay if you chunk your number in the form of a string by all potential lengths you know two to whatever i'm i think i might have just done half of the length? I don't even know. But anyways, you do it from two to whatever length could possibly be, and then you just check if any one of those, you know, partitionings of your string is invalid. It takes a couple seconds.

I did this in BQN, but BQN as a primitive for kind of chunking up your window. Anyway, so I did nothing elegant for this. I'm not sure if you had a more elegant solution. Now I have to find my solution. Actually, I said that BQN has a chunk function, but actually it has a Windows primitive. that chunk can be built on top of.

Anyways, I can link to the solutions. They're not pretty because I just kind of hacked this in a few minutes. It worked. I did, interestingly, it looks like I didn't do that. Rather than checking every number in the range, what I did was try to generate all the invalid numbers and then see if they were within the ranges. So I took a approach from the other way.

I didn't enumerate the numbers and check to see if they were. valid, I generated invalid numbers and checked if they were in the ranges. You generated all invalid numbers. I mean, what's the limit? Within the range. Well, I generated invalid numbers specifically within the ranges given. I see. But in doing that, I had to be a little careful because, of course, you can accidentally duplicate a number because the number 1-1-1-1 is invalid in two different ways, right it's in value because it's a full way repetition of ones but it's also a two two repetition of 11 right right and so you have to be sure to account for that kind of thing if they're not double

count numbers i assume you did that with some kind of hash set or something like that yeah i just threw them in an ordered set and i yeah we haven't talked about so i was doing these in bqn you were doing these in c++ i assume originally in c++ although another aspect of aventa code is that at some point dynamic programming rears its head, which is to say, memoization. And indeed, this year was no different to previous years, like sometime around, I think, of day five or six, in particular, there are graph problems,

which immediately become fairly trivial if you can just say, memorize the function. And so at that point, if you're in C++, plus, you've got more work to do. But if you're in Python, it's trivial. You can just add the cache. Decorator, yeah, exactly. Or cache, yeah, that's what it's called.

I think we want. Yeah, from Funk Tools, I think, yeah. Yeah. So I switched over to Python for the second half of Advent of Code. Okay. Interesting. So you generated the invalid numbers, which I guess it kind of at first, it seems like it would be a lot of work. But it's not too bad.

Well, it should be less work than enumerating all of the numbers, was my thought. And I was expecting that it would be too much work to just do brute force by enumerating all the numbers. Maybe I was wrong about that. I was certainly right, you know, as advert the code goes on, that is certainly something to bear in mind, like brute force solutions don't cut it for part two in the later stages of advent the code. Yeah, I mean, I also thought that potentially, I knew for part one it would be fine because it's only linear, right?

so it's fine. Part B, I was not convinced, but I thought, ah, it's easy enough to do a brute force, you know, just chunk my numbers up, check if it's invalid. The problem is that you're doing it from like, you know, a chunk length of two to whatever length your integer could be. Right. And that means that you have a nonlinear solution. What the complexity is, I don't actually know. And actually more than the complexity is the fact that you're doing this like partitioning of your string or like number in form of a string and like that is uh you're going to be allocating a bunch and so like i said i wasn't convinced but it ran in like i don't know five or seven seconds or something so i was like oh well it works for me not a pretty solution but like

as long as i'm not waiting five minutes for this thing to run yeah shout out to the speed of bQN's implementation anyway so for this even though it wasn't super pretty i thought it was pretty straightforward but but even even i thought this was i don't know i i wasn't in love with question two i was already being like yeah you know like in years past like i remember question one or two was like i don't know sum up the numbers that are like a new line separated you'd have like a chunk of integers right you'd have to parse those into sub lists and then you just add them up and i was like you know that's what i have a nice little way to start off my 24 day journey and uh by day two i'm I'm already, like, reaching for library functions.

In previous years, actually, in the early days, I tried to solve them without programming sometimes. Oh, yeah, in Excel or whatever. Well, even Excel could be viewed as a form of programming. I mean, I guess I am solving them with programming. But, for example, one of the early, maybe even day one of year one, 2015, very early ones was find the matching close paren, right? You're given a text file with an arbitrary. jumble, well, not jumble, they are matched, but an umptory nesting of different

per N pairs, huge, basically one huge S expression. Right. Right. So, so it's like what character, give, give N, where the end character is the closing perenn for the first character. So I just load it up. Well, yeah, I load it up in Emacs. I type forward S expression, followed by point.

That's the answer. Yeah. Yeah, yeah. Then I guess you just delete the rest or select and count the number of characters or whatever it is. But yeah, so anyways, this problem definitely harder than that. But anyway, so day three. Right, day three. Whereas where I lost it, you're given a, what does this look like, 15 or 20 digits in a row?

And you're asked to find the largest possible joltage, aka number. and what are the criteria? You're choosing two numbers here and you have to keep them stable, so in order. So if there's a nine and an eight, but the eight comes first, you're not allowed to make the number 98. You have to make the number 89.

So that's basically the only criteria. But the numbers don't have to be adjacent. Correct, yeah. So you're finding the subset. Yeah, the largest two-digit number that can be obtained by deleting. some portion of the rest of the numbers, if you're like. Exactly.

And so for me and this one, it's just an outer product or a triangle product, which are very easy to do in array languages where you basically just create every single possible number and then just take the max. I mean, that's an inefficient way to do things, but it works. But then part B. The way I did this, the method that immediately suggests itself to me was, so you've got a range of numbers you've got to pick the first number from

n minus one of that range because you've got to leave yourself at least one number you know you've got to find the max of the n minus one followed by the max of where you found the previous max to the end right that's your number

that's a trivial thing to code up so that's what I did and that and that generalizes two part two as well right wait wait actually so you said you got to find the second number in n minus one

where the the most significant digit you can pick from elements zero through n minus one let's say there are let's say that it's going to be n minus two right because n minus one is the last element but that's confusing things of it

so the first element through the n minus one's element is your choice you're going to pick the max digit of those and then where you found the max digit you go from there to the end to pick your second digit yes okay i understand now sorry and yes that is what generalizes to the next solution yeah unfortunately that how did you implement this with recursion um or a four loop that adjusts in i mean yeah but i mean they're the same algorithm it's I don't think of algorithms as being I don't think of recursion versus iteration as a

as a big difference in algorithms like to me the right way to think about algorithms is recursively how you implement them can be recursively or not right so to me it's the same algorithm either way but I happen to implement it with a with a full loop because it is trivially tail recursive and so you can make a full loop so yeah The reason I didn't, like, so that was what I thought of basically is in, if you kind of visualize this, you can visualize that like N minus one thing as this kind of like sliding trapezoid of where you get to select your numbers from. But then at each row, you have to adjust the range based on the previous index of your number that you found. So, so we should have we meant, have we said what part two actually is? So part one is five, you've got the string of, what is it, 12 numbers, 15 numbers, let's say 15.

Part one is find the largest two-digit number, which can be selected in the stable way we've said. Part two is find the largest 12-digit number that can be selected in that way, where each digit is selected. Yes. Yeah, yeah, 12. For some reason, in my brain, I had stored it as nine, but yeah, 12. 12 is what the question is. And the puzzle, actually, the puzzle input string. are like I don't know 50 60 digit long long strings the the test input is only 15 or so but the

real input you get you get many more digits yeah so the the reason I didn't want to implement it is because I wanted to do this in an array language and I see let me send you my I can link you my solution here yeah and I I am I am guessing that when I see this, there's going to be an index that is used to do the truncation or, you know, kind of limiting that range. Yeah, so if you're selecting two digits, the first one comes from digits, the first through the n minus once, right? If you're selecting 12 digits, the first one comes from, you know, digit one through

n minus 11 and the next digit comes from where you found the first digit through n minus 10 and then the next digit through n minus 9 etc right so this uh i mean this is very elegant link in the show notes folks for it's not that elegant i mean it's it's hacked up it happened to me it happened to be the first thing i thought of and it turned out to be not very much code yeah no but it is elegant in the sense that on line 27 of this solution on the first line inside the for loop is an auto

i equals stood max element begin and why is this elegant because you are storing the iterator a.k.a essentially the index and the value at the same time in this i which is

like essential for defining the actual range where you're looking for the next number. So two lines from the end of the loop, it says let's reset the begin, which is defining your next range to be stood next of I.

So that's very elegant. Those two lines there, and the two lines in between are just doing the math to calculate the number. So really, line 27 and line 30 essential. And I mean, this is maybe the limits

of my proficiency as an array programmer. Whenever you need the index, of a value depending on the problem type it's not always trivial to get that and you end up doing like a secondary like find and drop or take based on or like you get the length of whatever anyway so it's unobvious to me how to elegantly do basically a reduction at the end of the day because that's what's happening to based on the current step of your reduction without having an algorithm like this that returns to you both the index and the value in this case it's in the form of an iterator but you can imagine some other algorithm that returns you a tuple of you know the value

and the index how do you then say like you know drop drop in from this range so that you're not doing your search in the duplicate and so maybe it's maybe a part of the problem is that i should have just chosen a different language although i'm sure there are some listeners that are also listeners of array cast and they're thinking that there is actually a pattern or an idiom that is just not in my tool chest of patterns but so anyways did it make sense what I

if it doesn't make sense to you then it probably didn't make it any sense to the listener the window so what makes this problem maybe interesting in the array language or indeed in a functional language or something in the functional language is that the window is changing size

right so every iteration the end of the window just gets bumped by one. Right. But the beginning of the window is from wherever you found the last thing. So that's increasing... It's dependent on the previous iteration, yeah. Yeah.

Yeah. And in Haskell, I would imagine that the idiomatic solution is just to use recursion because that's how you solve these kinds of recursive things. In an array language, you have access to recursion. I did not want to write a recursive. I think that's what my brain want is like, I can do this recursively or I could do it with like a while loop in some local state, but that would have just hurt my heart because I don't like wall loops with local state. Well, here's how you need to think of it, Conner. Like I said five minutes ago, like the elegant way to think of algorithms is to start with recursion, right?

And if you can solve it recursively, you can mechanically translate that to an efficient implementation. You can totally write a four loop, but it doesn't change the essence of the algorithm, right? You can still think of the algorithm as being recursive because many, if not most, algorithms are that kind of divide and conquer. Even when you're working on a linear sequence, in a sense you are shrinking the input every time you're working on the remaining linear sequence.

So you can totally think of algorithms as recursive, and that is separate from your choice of how to implement them, right? Yes. Yes. I mean, I definitely, I definitely don't think about things in recursion, not even initially and not even. I mean, obviously, you know, people say, oh, they get hung up on recursion. I don't get hung up on recursion. I just, I, my, my default way of thinking about things is like the collection oriented. My collection happens to be an array. Yeah. Yeah. But, you know, if you're in Haskell, any other functional language, it's composing operations on these. collections. Yeah. And I totally agree, to be fair, you know, like if you have, for certain operations, we can be used to thinking in those kind of high-level abstractions of the whole meal-oriented approach, working on collections.

But oftentimes when an algorithm isn't, doesn't immediately fit into that model or you don't see how to do it, there are two ways you can go. You can, and you can either go, oh, how can I, you can carry on. And if you're really used to thinking about the whole meal programming approach, so maybe this is how you're thinking of things, you can carry on trying to say, well, how can I munge this data until it eventually gets into a form where I can reduce it, right?

I can think about maybe a scan, followed by, you know, a transform, followed by a reduction, followed by a window, whatever it might be. You know, you can carry on down that row and you can get to an answer, I'm sure.

Or, you know, and maybe this dichotomy is not hard and fast. Or you can think about how would I, you know, the four-loop-based approach, if you like, you know, the working on the indices, let's say, the working on the indices approach, not the full-loop, because that implies maybe iteration. But, yeah, how can I, how can I divide and conquer? How would I work on the indices so that the range shrinks, that kind of way of thing? Yeah, yeah.

That I completely agree with. And I guess when I'm doing advent of code or leak code problems or any kind of like, you know, for fun things. things. I hope that I don't, I hope I can just stay in my default way of thinking. And even if I have to move from that, I still hope that the recursive or, you know, wild loop or for loop version, I can still use all of the primitives that I have. Like, I don't have to write some bespoke thing that's an amalgamation of stuff. And the problem is, is like, not, like, it's not only can I not stay in my collection-oriented programming land or array program

land. When I go to the recursive or four-loop solution, I now need to create basically a function called like max with index. Right. You need to enumerate the collection and carry that along. Yeah. The way that you would do that is first you'd find the maximum and then with that maximum you would go back and like there's not even like a index of first function in array languages, you would have to build a mask of all of the values equal to the maximum and then take the first

Boolean value that corresponds to that maximum and turn it into an index and then take the first of those indices. So it's like you're already jumping through three different hoops just to get the first index of that max value and it's just like there's a scene from

Zootopia where the little rabbit pretends to bleed. Oh yeah. I'll cut that in of it probably won't make any sense, but like, that's what's happening in my brain. And I'm just like, all right, I'm not solving this problem. Well, let me say this to you. Um, this sounds like, you want to work inside

like a putated monad, the enumerated monad, right? You're wanting to work on values which are enriched with their index? Sounds to me like this is lifting into the enumerated monad, which I don't know that it exists, but it sounds like a monad. Right, yeah. I mean, if bundling anything in an optional or whatever, like sure enough, bundling it with an index is a monad as well, right? So maybe, you know, what you're,

What you just said to me is it's kind of clunky and annoying to have to carry around the enumerated state and figure out where you are in the enumeration of the collection. Maybe the way to abstract that is to put the lift yourself into the enumerated monad. And I'm totally making that up, by the way, but it just sounds like the kind of thing that should be available. Yeah, I mean, that is a, it's a fantastic, like, algorithmic idea. Yeah. My initial thought right away is that if you're bundling it with the original index sequence, each subsequent iteration, you're going to now have a non-zero-indexed index from like your new sequence. So like at first you go from zero to whatever. But then the second time, you're at index six. But actually the beginning of your list was at index three. So now I need to back out what the current index is. But wouldn't you be doing something like that manually anyway? Like you're having, if that's part of your answer, you're having to carry along that state.

Well, so I mean, the, the, the, if you're not doing that kind of enumeration, you, if you're just doing some kind of like, if you build a primitive that returns you a tuple of the first max with index, you can then just apply that at every iteration where you don't need to do. the like yes you're you're definitely doing the same work every time but you're avoiding the now I need to subtract the sum of all my indices from the current index to get the correct offset but it is it is food for thought but that also the other thing is even if you had this like enumerate monad thing that's not really trivial either in an array language because you can do like a zip with index pattern but then I guess you are I think you are I probably does work. You could do a max on that two-element array. The enumeration monad is very similar to the state monad or even the environment monad, right? Because it's not really

writable. You're never reading it. So maybe it's just a small variation on that. Yeah. I mean, maybe there's actually a nicer way to do this where, like I'm thinking now in like Haskell brain, where it's like instead of getting the max, you just go, there's a bunch of, yeah, it's been a while since I did any, well, have I ever done any real Haskell programming? Probably not. But it's been a while since I've been working with the libraries. There was a data dot split dot list or list dot split at one point that had a bunch of like chunk before, chunk after. If there was some like split at max or split at value, you'd still need the value. So I mean, if you calculated the max and then you did a split, I don't know. I don't know.

I'm sure there are things like that. And the great thing about advert of code is that, any route to the solution is fine as long as you learn something right so it's not it's not cheating to look at someone else's solution and learn a new technique you can totally do that yeah yeah well here's a challenge to the listener if you did have been a code listener in a functional or array and you've got this kind of and that's that's why i said and ben he was like well is it elegant i threw this together but that's the thing that is very elegant it's on line 27 is that you for free with an X element. You get the index and the value in an elegant fashion.

You get the iterator. Yeah, exactly. And it's stored all in one thing with a, you know, a de-reference operator to get the value. So it's not even like you're unbundling something into a two-touple or a pair and then using each one. It's quite elegant. It's very nice.

And in the instances where you need this index to do this kind of operation, this is a very, very nice way to solve it. And it's one of the things that I miss when I'm in array languages. is this. And that's why if you ever live in NumPy, they have all these variations of like ARG with Max or like they have all these like index versions of like these minimum and maximum reduction functions so that you can get the index because it is a common thing that you need to do or it's not just the maximum value. You need some index for some subsequent operation. And so they have all these duplicate operations basically, Arg Max and Argmin and all that stuff,

which is kind of, you know, there's some quote that says, you know, design patterns. or just addressing language deficiencies or something like that. It's, you know, like, Argmax and Argmin is one of these things for, like, an algorithmic deficiency. Like, if you, if you, uh, are, are needing to do this kind of thing, it's because we don't actually have a good, good way to do it. Anyway, so should have done it in C++ folks is the moral of this story. Well, I'm not sure that's the moral.

And I'm actually curious how you do this in Python, too, right? Because you don't have iterators that you can back out the, index from elegantly, right? You're probably doing some, you know, Lenn on, even if you use iterators. Actually, I don't know

familiar. Can you get just the index from an iterator if you're in iterator land? I don't actually know the answer to that question in Python. I've never written Python code that did that.

I don't know. Well, that was day two, day three of Avent of Code. Any other highlights that you want to mention? I mean, like I said, I haven't done anything from day three onwards but were there any favorite problems or and also too have you have you been chatting with michael about his Haskell experience because that was where this all the segue uh i have i have

you know for many of us advent of code starts out with the best of intentions and we make it through two or three days as you've experienced so i don't think michael has made it a lot further than you have but but yes uh he and i you know in the first you know in the first few days we talked about our different solutions we talked about how we'd solve solved it in Haskell. And I have to say that for a beginner in Haskell, his Haskell code is pretty nice, you know. It's a function composition and declarative style, of course. Of course, Michael is well versed in that kind of thing. But Haskell is new to him. But he seems to have taken to it very well. Interesting. Maybe we'll have to have Michael on and we can chat about his however

of many days of Aventive code, a Haskell experience. Because Haskell, I mean, people forget, but it used to be my favorite language before I discovered APL and friends. It was a short-lived favorite language period, but... You should try day six. Be sure to check these show notes, either in your podcast app or at ADSP thepodcast.com for links to anything we mentioned in today's episode, as well as a link to a get-up discussion where you can leave thoughts, comments, and questions.

Thanks for listening. We hope you enjoyed, and have a great day. I am the anti-brace. Yeah.