Algorithms + Data Structures = Programs - Episode 55: LeetCode in C++ (Part 1)

Episode Date: December 10, 2021

In this episode, Bryce and Conor live code a C++ solution to a LeetCode problem!Date Recorded: 2021-12-05Date Released: 2021-12-10John HancockSuper Computing (SC) ConferenceBoostCon 2011 - Bryce Lelbach: AST Construction with the Universal TreeBoostCon 2011 - Bryce Lelbach: AST Construction with the Universal Tree ~ SlidesBoost SpiritBoost Spirit utreeHPX (High Performance ParalleX)LeetCode ProblemC++ SolutionBQN Programming LanguageC++20 std::ranges::sortC++20 std::ranges::findC++20 std::ranges::equal_rangeC++11 std::distanceC++11 std::iotaC++20 std::views::iotaC++20 std::ranges::partitionC++20 std::ranges::countC++ thrust::counting_iteratorIntro 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

Who would play me in the movie of my life? Shia LaBeouf. I like how Connor had no hesitation. Connor just knew. Welcome to ADSP The the podcast, episode 55, recorded on December 5th, 2021. My name is Connor, and today with my co-host Bryce, we live code a solution to a leak code problem in C++. This is part one of a two-part episode where, in next week's episode, we'll solve the same problem, but in BQM. Nice shorts, by the way. Those are are nice shorts i'm admiring your shorts i'm

wearing shorts yeah i was admiring your shorts i like them they're a good color yeah lululemon baby yeah although it's winter why are you wearing shorts oh it's toasty in my apartment. I haven't even turned the heater on. What is toasty? And if you give it to me in Celsius, I'm not going to be amused. I don't know. I don't know how warm it is in my apartment. I have no idea. But not cold enough to require me wearing pants. Are we recording?

Are we good to go? Of course I'm recording. All right. Here we go, pants. Are we recording? Is this, are we good? Are we good to go? Of course I'm recording. All right. Here we go, Bryce. Are you ready? I also, yeah. Are you ready? In celebration.

So I got too thirsty because Bryce was like 17 minutes late. I was savoring a cupcake. I sent you a polite message informing you that I was savoring a cupcake. That's true. I'm not sure how that took 17 minutes, but I had to open my grapefruit bubbly that I was waiting. But because we're celebrating, because we're celebrating, Bryce, I got another bubbly. And this one's lime. Here we go, folks.

Here we go. Episode, what episode is this? This is episode, like, 56. Woo! Right there, baby. Right there. So a couple things. One, clearly you've never savored a cupcake before. I'll have to change that.

Two, what are we celebrating? Oh, yeah. So remember two episodes ago, I said, oh, I'm not going to get to update the listener on how my 10K race goes because we're going to be talking to the Kneeblers. But I didn't realize that was next weekend. So we're recording today. And I did a 10K in Toronto yesterday and a 10K in Vancouver seven days ago. And I smashed my personal record by two minutes. Previously it was 37 23 and it is now 35 29.

Wow. That is a pretty good 10 K time folks. Let me tell you it's a, yep, it's good. And, I was beat by a 14 year old. That doesn't feel,

um, congrats to Steph. Uh uh i got to admit i was running alongside him in second place like tied for second from like kilometer two and a half to five and i thought this kid's running way too fast he's gonna gas out and then at the five kilometer mark i'm the one that is starting to gas out and then he just like runs away and I'm like I gotta reassess where I'm at someone told me later I should have got his autograph because he's probably gonna end up in like the Olympics or something later on

which is a good point so wait did you finish second in this 10k that 10k that was in Vancouver I finished third because yeah the 14 year old beat me. I haven't ridden my bike.

I mean, I spin in the gym, but I haven't ridden my bike since October because it's cold. But good news. Something, like, happened when I came back from Florida. My, like, cold adaptivity kicked in. And, like, I've been, like, walking around around in like, you know, a t-shirt the past few days. And I've been like, you know what? I, I, now I remember what it was like to be cold in new England as a kid. And I kind of like it. It's not that bad. So something just, something just kicked in. No to the cold. We don't like the cold. No, I do like the cold. I do like the cold. It just took me a little while to get used to the cold and remember that I did like it.

Oh, I got my COVID booster today. Oh, how are you feeling? I'm feeling fine thus far. My arm's a little bit sore. I imagine I'm going to feel not as good tomorrow. Yeah. But what about you? You got a new booster yet?

Are they giving out boosters in Canada? I know that my grandmother got her booster in Vancouver months ago at least. So I know that they are giving them out, but definitely I don't think it's, you know, white dudes in their 30s are allowed to get them yet. At least I haven't heard anything about it. And I would have heard because I've been first through the door every opportunity when they've opened it up for me to get it. Well, you should move on

down to move on down to america and you can get yourself a covid booster um yeah we'll think about it i mean i've got a race in austin texas uh you're going to austin texas i know so that's the thing i'm not sure i'm going because of omicron um and it's on January 23rd. We're recording this. Today is what? The December 5th. So depending on how things unfold. Connor, it's like 2022.

Like, has that hit you yet? What does that mean? Like, it's like 2022. Like, that's the year that it basically is. I mean, that is one plus 2021. You're not understanding what I'm saying. Break it down for me, Bryce. Break it down for me.

In my mind, last year was like 2011. 2011? Yeah. Like where did like the past 10 years go? We're like old men now. 2011 feels like, doesn't feel like yesterday. It feels like three decades ago for me. Yeah, it is starting to feel that way.

Like, in 2011, I guess it depends on what month you want to choose. But, like, I was in, like, halfway through university. I had moved to Toronto for the first time and was working for an insurance company called John Hancock, which is a subsidy at the time it was a subsidiary of Manulife. I mean, that's what I did for eight months of that year. And 2011, that was my,

that was my second, that was my first year at LSU. So I had just come back from my first time at the supercomputing conference, which was in Seattle. And that was like the third tech conference I went to. I'd already been to... Fun fact, most people think that the first conference that I went to is BoostCon 2011, because I talk about how it was such a life-changing experience for me. But actually, I went to the Linux Foundation Collaboration Summit, or it was something with that sort of title, in San Francisco, like a month before that, to talk about

compiling the Linux kernel with Clang and LLVM. And I met Marshall Clow at the Linux Foundation Summit thing. And then I went to BoostCon 2011. And I also saw Marshall Clow. And they were like two very different communities. So I was just like, oh, this guy just goes to every tech conference. What was the first conference that you spoke at? That Linux Foundation. God, I won't remember what the name is.

But that Linux Foundation Collaboration Summit was the first conference I spoke at. In 2011? Yeah. It was the first conference I attended, the first one I spoke at, because they wanted me to talk about compiling Linux with LLVM. That's crazy. Hang on. But you spoke at the first conference that you went to.

Yeah, but that's what I'm saying is that like, so 10 years ago for you, you were sort of already in the C++ community. I was in a whole different education path slash career path. I didn't speak or go to a tech conference until 2019, which was two years ago. know i remember i was there poking you with a stick making you speak it's just crazy to think that of the last decade like 80 of it wasn't doing any of the stuff but like you skip back a decade and you were you were starting that like it's it's uh we do share a lot you know we've mentioned this a couple times about our first languages ti basic and quasi dropping out i mean you actually did drop out or kick got kicked out and i kind of got kicked anyways there's a lot of similarities but when you look when you compare the last decade and where we were at that's totally different um yeah i was not expecting

you to say oh i like for some reason i thought you were gonna say oh my first time i spoke was like at you know cpp con 2015 or 16 or something because i feel like that's the first youtube talk that i've seen no like that goes that far back there is somewhere a recording of the first talk that i gave at boost con not the first not the talk i gave at the the linux foundation thing um there is a recording of that talk that i gave it boost con somewhere um but like very well hidden because it was bad i stayed up i i was up until 4 a.m the night before it was an 8 a.m talk because i was still making slides and i i recall i made a bunch of really bad star wars references yeah that was this on youtube is this on youtube it might be on youtube all right

and what year is this the year is this boost con 2011 i was talking about um uh boost spirit u-tree um which was a an ast data type for boost spirit which is a parser framework which is the first not not the first thing i worked on in boost but a project that i rapidly gravitated towards um because when i my first exposure to boost was i was using it for this you know as we've discussed before i you know started learning to program to write this game um and then i got you know I learned about Boost because I was using it for this game project. And I very quickly got sidetracked working on, you know, Boost. The thing that I first, my first exposure to Boost was Boost String Algorithms Split.

I don't remember why I needed it, but it was a text-based game that I was working on. They're called MUDs, Multi dungeons or dimensions and uh i think i was using boost string algos split to do some tokenization of input lines um and there was some bug in it and i like reported the bug and like sent a patch to fix the bug um but then i think from there somebody must have told me to use Boost Spirit instead for my parsing needs. And that's sort of how I got from submitting this bug about Boost Format, while he's known these days as being the guy who runs the HPX project, the Parallel Runtime, he was also one of the maintainers and founders of Boost Spirit. And so that's how we initially connected was that I was contributing to Boost Spirit. And then that's, you know, I randomly asked him for a job on IRC having never met him. And that's when he said, you should fly on down to Louisiana.

Yeah. Damn, man, you got started so early. It was really weird. I like started learning C++ and then three months later I was like, I had like commit access to boost and then three months after that i was um you know i was the the the release um manager for one of the boost sphere releases and then like three months after that i was speaking at boost con and then three months after that i was at lsu and three months after that hartman and i were starting our own research group and i have like more responsibilities than than i uh i i

should have had as a 19 or 20 year old college dropout it was a very it was a very crazy period of my life they should make a movie i'd watch it i i i would watch it too who would who would play me in the movie of my life shia labeouf i like how connor had no hesitation connor just knew i just it's it's funny too because like I did not have that pre-prepared but like it's if we're playing like the young version though unfortunately he's a bit too old now but like no no but like young

Shia LaBeouf would be perfect yeah he would absolutely be perfect I don't know why that came to mind so quickly who would play you? I don't know a young Tom Cruise Came to mind so quickly. Who are you? Hmm. I don't know. A young Tom Cruise?

I was thinking Brad Pitt. I was thinking Brad Pitt. Brad Pitt? Tom Cruise? Yeah. No. I'm not. That's generous of you, Bryce. You are a very good looking individual.

I mean, that's. I mean, you said that's very generous of you but you but you led with tom cruise so uh that's only because there was a girl in university that called me tom because she said i look like tom cruise oh speak speaking of girls speaking of girls all right well we should probably we should probably uh get to the podcast. We can do something real brief to round out our talking about whatever we were talking about by doing another real brief leet code in BQN if you want. It's a very short solution, and I was so in love with it. I've been on a tear lately.

But let me share screens first. And actually, maybe we'll do it. We'll see how quickly we can do this. What is it? 637. We probably chatted for 15 minutes. Let's see if we can solve this in both C++. I'll type.

You tell me what to type. And Godbolt. Oh, yeah. So here's the problem. Yeah. Find, or do you want to read it? I'll read it. Find target indices after sorting array. You're given a zero index integer, array nums, and a target element, target. A target index is an index.

Oh, OK. A target index is an index i such that the index of your array nums is equal to the target. And the question asks you to return a list of the target indices of your array nums after sorting nums in non-decreasing order. And if there's no target indices, just return an empty list. So for example, if your list is 1, 2, 5, 2, 3, and your target is 2, after sorting your array nums, it would be 1, 2, 2, 3, 5.

And then you just need to return all the indices that are equal to your target value. So because two is your target value, that corresponds to index one and index two. All right. I understand. You're only ever given one target. Correct. One target. And so the second example is the same list. One, two, five, two, three. Your target now is three. And if you sort this once again, it's one, two, two, three, 3. Your target now is 3. And if you sort this, once again, it's 1, 2, 2, 3, 5. And the 3 is in index 3. So that's your answer. The third example is target equal to 5, same list. If you sort it, 5 is going to be the last number in the list, which will be equal to index 4. And then if your target is 4, that value doesn't show up in 1 2 5 2 3 so you end up with

an empty list let's head over to so let's copy let's copy or actually we can do it straight in here what are we talking about what are we talking about um let's zoom in and change this to auto um so we've got target indices as a function. It takes a vector of ints. Why is there a class here? I'm so confused. That's just the way that it works for leet code. That should be a function.

And actually. Who do I call about that? The leet code folks. That's some Java nonsense. How do you want to solve this, man? What do you want to do? Well, so, I mean,

my first thought is that we want to sort the array, but I was actually, I was actually wondering whether we could, I wonder if they have, I wonder if they have C++20. What do you think? So, I mean, obviously we have to sort the array, but I'm just wondering whether we can somehow...

We have to perform the work that would be involved in sorting the array, but I wonder whether calling std sort is actually the best way to do this. Connor tried calling std ranges sort um and discovered that leak code yeah i think they only have c++ 17 um have c++ 20 which is not shocking to me given that the like leak code structure for a problem is like very clearly like 90s object-oriented C++. No offense to anybody that works at LeetCode, but a little bit of offense was intended. So we've sorted our array.

What do we want to do next? Go back up to the problem. Actually, you know what? We definitely... We're switching to Gobbolt because I want C++20. I ain't messing around. So you want to find, I mean, call std find. Why do we need st find the first element in the sorted list that matches

the target. And what we really need is like an equal range, something like that. It's not an algorithm. It is an algorithm. There we go. See, I know stuff.

I guess we need to do include range. Yeah, forget find. We should just be calling equal range, right? Which is not actually a C++20 thing. Equal range was an algorithm pre-C++20, before there was a notion of ranges in the language. Or the notion of ranges in the language that we currently have. But equal range, you give it a pair of iterators and a value, and it returns you a pair of iterators,

which is all the elements that are equal to the value, and it expects that the input sequence is partially ordered with respect to the value, which is going to be the case here because we've done this sort. Wait, okay, hang on, hang on, hang on. We only need to sort until, I'm not convinced that we need to sort the entire array, right? Because we only need to sort up until we've gotten to the target that we're looking for.

And I'm wondering if there's some clever sorting algorithm that lets us only sort. So what is this going to return? This is going to return us probably a pair. A pair, yeah, a pair. Whoa, whoa, whoa, what are you doing? Shouldn't we be destructuring that? They're going to be iterators, but yeah, we probably can do that.

So let's do first. Okay, so we have the iter iterators and it wants us to return the indices well then we're going to take those iterators those are going to be random access iterators so we can just we can just

we can just do some some pointer arithmetic so yeah we have currently we have we can just do some pointer arithmetic. So yeah, currently we have std colon colon ranges colon colon sort. And then we've got structured bindings, f comma l equals std colon colon ranges colon colon equal range. And if we dereference both f and l, it gives us the values 2 and 3. And so now we just need to get the indices which correspond to basically what?

Wait, why is it giving us two? Yeah, so what we need to do is we need to just do some iterator arithmetic here. Yeah, yeah, sure. You can call distance. Sure. Oh, you just want to figure out like how many there are. Sure. Fine. That's okay. I have no objection with that. Oh, actually we can use IOTA here. That was what I was thinking.

Yeah, because if the answer is more than one element, then they're going to be consecutive. So we just need to figure out the starting value for iota, which is going to be the distance from the beginning of the input to that first element that we found and we'll want iota for the size of the output is going to be

because we'll just yeah I see what you're doing there so you're creating a std vector with default initialized ints. And then you figure out how many there are by taking the distance from the start of the equal range to the end of the equal range. And then that start should be s there. I'm not doing a great job of explaining this for the listener um but uh but yeah okay so i mean there's there's two things that you got to figure out here um which is how

many um how many indices are you returning and you do that by computing the distance between the the iterator to the start of the equal range and the iterator to the end between the iterator to the start of the equal range and the iterator to the end of the equal range. And then you need to figure out what is the first indices index that you're returning. And you figure that out by computing the distance from the first iterator in the input

to the first iterator that matched the first iterator of the equal range. And then you create a vector of n elements, which is however many elements you've determined are in this equal range. And then you do a stood iota on that vector. And the initial value for the iota is the distance from that starting distance that you computed which was the distance from the beginning iterator to the input to the first iterator from the equal range yeah that made sense to me i'm not sure that anybody that's listening is gonna

i mean i think it was pretty clear. You know, you sort. You stood range is sort. Then you stood range is equal range. Then you have to do a little sort of figuring out what is the index of the start of your equal range. And then you need to create a vector and then use IOTA to fill the indices using that sort of start. But do you really need to sort the entire thing? You don't need to sort it at all, technically. But, I mean, this is the direction I was hoping you'd go.

Because it's, I mean, if you look at the input... Hey, in my defense, the first thing I said is, well, my intuition is to sort it, but I'm wondering if we don't have to do that. So when you tell me later that I don't need to actually sort this thing, I just want it on the record that my first gut reaction was i don't think we have to sort this yeah the reason that i don't think that we need to sort this and that it's inefficient to sort this is um you don't care about the order of the things after the the target index you don't

even really care about the order before either. Right. That's that also is true. Right, right, right, right, right.

All you care about, all you care about is how many are in each of those, those groups. Exactly. Exactly. So you can technically do this in linear time. But do we use partition here? I mean,

if I were going to solve it in the linear time method, I'd just do two count ifs. Count if less, count if equal. Then you've got your values that you need in order to use IOTA. Walk me through that. So here are your target values, too. Count if less than two is going to give you one. And then count if equal what bastard that's very clever

and then count if equal gives you you're basically so so here in our solution that we're looking at we have n which is the number of equal elements and then start which is the distance between the equal range beginning of the equal range result of equal range and the start of the equal range, result of equal range, and the start of the array. You can get those two values by just doing countifs with lambdas, one that checks less than target value, one that checks equal to. However, I'm glad you went with the sort because we're going to hop over to BQN now, and we're looking at 1, 2, 3, 4, 5, 6, 7 lines. But you could code golf this.

If we had access to like thrusts um uh counting iterator we could just we could reduce the last three lines into a single line with a range constructor and sort of creating this in place in a constructor instead of having a costed iota why aren't we why aren't we returning an iota view here um because the question asks you to turn a vector and those are not implicitly. The question is ill-formed. You can't do anything with views. The question meant to ask you to return a view or a range. That's true.

Let's see what happens if we go. We delete these last three lines, and we go return stood. Is it views or view? View iota and we're gonna go with start and start plus n and you said it was views but actually maybe that's because I'm not including the range header. Compiling, compiling and it looks like that is correct.

So yeah, we've reduced it. If we loosen the restrictions of this to one, two, three, four, five lines of code, first one sort, second one is range is equal range. Then there's two stud distances to get n and start, and then we're returning a views iota using start and start plus n. So not too bad, five lines. Pretty nice in my opinion.

Sure, there's more performant code doing the linear stuff, but I like this solution quite a bit. And now let's go and do something similar in BQM. So let's hop over to our next-gen APL. Stay tuned for part two next week. Thanks for listening. We hope you enjoyed, and have a great day.