Algorithms + Data Structures = Programs - Episode 56: LeetCode in BQN (Part 2)

Episode Date: December 17, 2021

In this episode, Bryce and Conor live code a BQN solution to a LeetCode problem!Date Recorded: 2021-12-05Date Released: 2021-12-17ADSP Episode 55: LeetCode in C++ (Part 1)LeetCode ProblemC++ SolutionBQN SolutionBQN Programming LanguageBQN ∧ (sort)BQN / (indices)APL ⍸ (where)J I. (indices)SmalltalkC++11 std::plusAPL ⍳ (iota)Intro 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

You know what, I'm going to make you put both versions in the show notes, and we're going to see what the listener thinks, because the listener's going to be on my side. The listener's uninformed as well. Welcome to ADSP, the podcast, episode 56 56 recorded on December 5th, 2021. My name is Connor and today with my co-host Bryce, we live code a BQN solution to a leak code problem. This is part two of a two-part episode. I recommend checking out the first episode before listening to this one. so before we hop into part two of this two-part episode i am going to briefly cover the problem description that we're going to be solving so basically it's a toy problem you're given two

inputs a list of numbers and a target value in the form of a single number. And basically what you are asked to return is the indices that the target value would show up if you were to sort the list of numbers that you're given. So for instance, if the list of numbers you're given is 20, 30, 10, and your target value is 20, after you sort that list of numbers, it's going to be 10 20 30 and then the index that the 20 your target value shows up is 1 and if there were multiple 20s so if it was 20 20 30 10 then instead of returning just a single one you'll be returning index 1 and 2 because the 20s would be in the middle indices hope that makes sense now let's hop into the episode. And now let's go and do something similar in BQM. So let's hop over to our next gen APL.

Wait, wait, wait. Finally an APL for your flying saucer? Yeah, that's Marshall Lockbaum's, like, you know, wants it to run everywhere kind of thing. So I think it's a bad motto, but hey. If you're listening, Marshall, don't at me. So first thing we're going to do. You can't at him and you can't at me because it is a bad motto.

You should change it. The first thing we do here, we've got our 1, 2, 5, 3, 2 array, and we're going to sort it, which is a single character. We've got to zoom out here a little bit so you can see the result., we've got our 1, 2, 5, 3, 2 array, and we're gonna sort it, which is a single character. We gotta zoom out here a little bit so you can see the result. Now we've sorted. Now in order to get our sort of elements that are equal to our target,

we just, here our target value is two, and we go equal, and boom, you have a Boolean mask that represents where you had the target value. So the result right now is 0, 1, 1, 0, 0. And there happens to be an algorithm or a glyph in BQN and also J and APL. It's called where in BQN and APL. It's called indices in J. And it's a slash. And if you do this, it just returns you the indices that correspond to those ones. So that is like three characters on top of the two arguments that are sort of in line here,

but let's make this point three. So what's the name of this? It's target indices. So let's call this target indices arrow. And we're going to call this by doing target indices and then copying this over. So we can just turn this into like an inline lambda. Why is there the two there? So that's, it's a binary function.

So there's two arguments and binary functions are infix in apls like bqn wait what are the two arguments so two is the left argument and but why is it taking two as an argument i'm confused oh that's the target value oh okay yeah um less confused now thank you and so we can replace our left argument here, which is W, and right argument, which is X. And so this should give us 1, 2. Wait, what happened with W? So W is our left argument. X is our right argument.

In APL, it's alpha and omega. But we're going to change this to point-free because... Shouldn't... Yeah, okay. All right, all right. I i'm gonna shut up for a minute and let you do your thing and so what we have here is you know a unary operation being applied to our list which is sort and then a binary function that's taking the result of that sorted list and checking whether any of those elements are equal to our target value and

So we can turn this to point free by doing the following we're going to turn this into a fork and Basically This is going to be taking the target value on the left so it's saying take the target value on the left. So it's saying take the target value on the left. And then we're going to do the same thing over here and say, take the one on the right, but we want to compose these together and say, basically after you do this binary function,

apply this unary function. So this is the B one combinator at the Blackbird altogether. You've lost me at some point here. So remember that we have done in the past our forks, which are A, B, and C. So currently, A on the left is our left, meaning given two arguments here, take the left one.

And then equal is our binary function, and on the right is a composition of sort plus right. So first we want to say only take our right argument, and then we want to sort it. And because this is a binary operation, takes two arguments, and then discards the left one, and this is a unary operation. This is an example of the B1 combinator. And then when you compose these things in parentheses, that gives you the golden eagle, a specialization of the EHAP combinator.

And what's awesome is that without any parentheses, or without, like there's two different ways to spell the b1 combinator you can spell it by using this sort of symbol or just by juxtaposing like putting side by side a unary and a binary function and this is a unary function and our specialization of the ehat combinator is a binary function so when you just this is the equivalent of this, just because there's nothing else going on. Wait, why isn't that true for the sort in the right side? Because it's going to eagerly try and make a fork out of this, either a unary or dyadic one. So we need to compose this to say this is a unary function.

So the composition has a stronger operator precedence? Correct. Yes. Dude, just use parentheses. What have parentheses done to hurt you? And we can delete the only remaining two parentheses because this

forms a fork which is a binary operation. And this is a unary operation. So implicitly, this is the B1 combinator. Connor. Boom. Come on. Come on.

Connor, this is strictly less readable than what you had before. I disagree. I disagree. It is beautiful. rules of precedence for the specific operators in this specific language for how you construct this and not like you're assuming that everybody's going to read and understand all of those precedence rules and be able to apply them on the spot to be able to disentangle what this is doing like like if you if if if you use the parentheses here even if I don't know what the specific operations are, I at least would understand the structure of the problem. But that's because you know how parentheses evaluate.

Like the readability of this is informed by your understanding of how parentheses are evaluated. But I only have to understand how one thing evaluates, parentheses. For your form of this, one has to understand how all of these things evaluate and which of these things are binary and unary. I mean the argument you're making here is like, okay, why do we have multiplication? Let's just use addition for everything because then I only have to know one binary operator plus and I can I can still do I can still do exponents and I can still do multiplication by just repeatedly adding it's it's the same argument it's the same argument no no you're saying that like oh parentheses is one thing here I need to know the b1 combinator the two different ways of spelling it the uh the s or it's not an s prime combinator it's a specialization of the e-hat combinator like i have to know all that stuff um and it's like yeah you know i'm gonna make you put both

versions on um in the show notes and we're gonna see what the listener thinks because the listener's gonna be on my listeners uninformed as well uh connor do you want this podcast to be successful if so might i suggest that you not insult the dear listener it's like asking someone that doesn't speak chinese or like no you know any of the radicals it's like oh what do you what do you think about the readability of this of this uh and it's like oh well one of the solutions makes use of something that's in the individual's lexicon they know what parentheses are so they can identify those and go oh i know some of that structure but like that's only because they know that's like it's you know i was just having this conversation with a uh prophet one of the local universities about, you know, small talk versus APL and that APL is very opaque. But like, the point that I made to him is that like, the opacity of a language,

like, and he said that small talk is so much readable, but that's because small talk is so much more similar to English, the language that like everyone knows, just because something is different than the language that you speak, doesn't't like doesn't necessitate that it's actually more opaque like we know what parentheses do therefore this one seems more familiar and it's like well that's like the difference between showing a paragraph of chinese symbols versus a paragraph of chinese symbols with some english words littered in and you you ask which one is is can you make more sense of and it's like well of course the one that has more english words in that you know is is more readable i i i fantastic point the point that you're trying to make i think you are completely wrong and i think i think that when we take this to twitter people are gonna agree with me uh i mean and i i agree you will win on twitter

but that doesn't mean that you're right. That is a fair enough point. All right. Now let's see how we would solve this the efficient way. Oh, yeah, yeah. So that's, I, it's pretty fun. It's pretty fun. So let's, let's comment out this for now. And yeah, let's just, let's build it up in lines again.

So the first thing we want to do is check how many elements are less than our target. And we do that with just two less than our list. And to get equal, we just do two equal list. So how do we do those at the same time? Does that give you the count of elements or does that give you? It just gives you a mask. So all you have to do is a plus reduction. Yeah, I was about to say a reduction.

We need to do composition here. Or not actually composition, it's partial application. We're binding two to the equal sign and the less than sign. So for equal, we get two. two and for less than we get one hang on explain explain what you just did uh so this little circle with the line coming out of it is called i think before but it basically just means like partial application you're binding two as the left argument to your binary operation, either equal or... It's turning that into a unary operation. Yep. And so now that we have two unary operations composed

or juxtaposed, that's the B combinator. So it's the equivalent of just doing one after the other. Which is... I'm confused. You've lost me. What is the little back tick-like thing? That's reduce. The plus is not reduced? The back tick-like thing is reduced?

The plus is a binary operation, as it is in everything like mathematics. Oh, okay. I get what you're saying. It's like the equivalent of std colon colon plus parentheses parentheses that you pass to std reduce. std reduce is a algorithm that takes a binary operation. Yes, I now see what this does. Okay, let's move on. So once you have this, you can basically, let's just catenate them for now. And we can just basically copy and paste this. And instead of this, we want equals. And then we can turn this all into a fork. And so now we have the count of values

that are less than our target and the count of values that are equal to our target and once okay wait what okay you have those two cat counts but then what what what is the concatenate catenates just putting them next to each other so this is this evaluates to one okay all right and this evaluates to two right but the this is perhaps a bad input example because... Oh yeah, sure. Yeah, because the correct result is also, is the same as... The first two elements. Yeah. Or the correct elements for it to return are,

I don't know what I'm saying. So yeah, I just multiplied all the elements in the target value by 10. So now we have 10, 20, 50, 30, 20. And the result is that you get- No, no, no, but hang on. That doesn't change anything because the correct output indices are one and two.

Oh yeah, yeah, sure. Let's do- And the answer to how many elements are less than the target is one and how many elements are equal to the target is two. So you'd have to change the order. Or just add a bunch more 20. So now I have 10, 20, 50, 30, 20, 20, 20.

So you've got four elements that are equal to 20. I am satisfied. One that's less. And so what we can do now is we can just add iota, which looks different and it's called range in BQM. And I think this, actually, this isn't going to work, so we need to do this. And so now we've got one still evaluating as our left, and then we've got iota, which is zero index, so it's one two three and then all we have to do is replace our catnate with plus and now you're adding one to every single one of the iota values so you're going

to end up with one two three four boom that's crazy um and and this is like hang on hang on let me process let me process yeah okay i guess that works that's clever now can you lift out the oh let's go there let's go there. Let's go there, man. I love where your head's at. I love where your head's at. So yeah, Bryce is basically asking, because we've got a lot of commonality here.

Basically, the plus reduce, and then basically binding the target value to our binary operation. The only thing that's different between those two is one's using a less than or a greater than, a less than, I guess, and one of them is using an equal. So let's see if we can do that.

Let's go to, and actually, so we're not actually, wait, the first thing we should do is pass 20 in here because we have a unary function where we have the 20 hard-coded. That's not good. And so... You're trying to keep it point-free, aren't you? Wait, does this actually work?

I never did this before. Oh my god! That is so beautiful. Oh my god. Can I get rid of the parentheses here now, too? He's just a madman, people. Wow. That is so beautiful.

Can we get rid of the parentheses? We cannot. And why does that not work? Because, yeah, we need this whole thing to evaluate as a single operation. So what we have now here is parentheses plus reduce greater than, end parentheses, plus parentheses range dot plus reduce equals. You know what the scariest thing is? The scariest thing is that that actually kind of makes sense to me.

And let's see if we can factor out. Yeah. Now, what we're trying to factor out is the plus reduce. The plus, yeah. And then some operation because we should only need to do that. So really what we're doing is we want the left and right binary functions on our dyadic fork to just be greater than and equals. So we want the greater than to be on the left and the equals to be on the right. And then we're going to use something called the psi combinator, which basically takes two arguments, pre-processes both of those arguments by applying a unary operation, in this case, reduction or summation. And once we've done that,

I think it's K here. What do we want to do? We want basically to call range on one of these values, which we're going to need to compose like this. And then the other one is just we're not doing anything to it. That doesn't look like that worked, did it? That did not produce the desired result. So let's see what happens when we delete this and we just use cat nation here. So we get 310.

How would this possibly give you the right result? You got rid of less than. No, it's over here. Oh, I missed that. Although, actually, yeah, there was an extra plus sign in there. You're right. Oh, my God. But so we did it.

We did it. No, wait. No way. That works? Yeah. What did we have before, though? Because I'm not actually sure which one. That was very nice.

We have that with a plus. And then? Then, yeah, the little dot. with a plus. Yeah, plus. And then... Then, yeah, the little... The dot. Then you had a dot, too. So why is the reason that this one ends up being... Wait, wait, wait. You had a dot between the rain...

Oh, yeah, that's right. That's right. Boom! Check out my BQN knowledge! Yeah, Bryce, you're leveling up. Wow. Isn't that phenomenal? Wait, wait, did we check that the original one works?

Yep, they still give the same result. Oh, boy. That is phenomenal. That is phenomenal. Like, there's something, you know, say what you will about readability and, you know, practical use of this and whether people would actually, but, like, there is something, there's something just so beautiful. So,

so like, it's just, it's, it's exactly what is needs to be done. Nothing more, you know? So when you write the parallel version of this, you presumably don't want to do it with two actual count of passes.

You just do it with one pass. Yeah. So I'm not sure how you just test you you can do both the count for equal and the count for less than in the same the same time yeah yeah i'm not exactly sure how a compiler because this is a fork well i mean i think if you look at the second version here that we have where we lifted out the um or no yeah if you look at the second version here that we have where we lifted out the, or no, yeah, if you look at the, switch the order of those two there, switch the order of those, those two definitions, because that, yes, that's the most refined version. If you look at this final,

most refined version, I think that it's pretty clear from that that you can figure that the compiler can figure out to do it in one pass because you only have the one reduction there. It's one reduction that's being applied to two different sequences, right? Right, right. But, well, it's two pseudo sequences. Yes, it's two pre-processed sequences. But, like, those two reductions can't be fused why not because at

the end of the day they are pre-processed sequences that come from the same source sequence but the interim sequence is different right um yes but i'm pretty sure the compiler could figure out that i'm pretty sure the compiler could could figure this out and do this in a single pass. You just figure out, hey, I need to transform, you know, for each element, I need to transform it into these two different pre-processed pseudo elements and then feed it into this reduction. Yeah. I mean, I think it's pretty clear to you and I that we could write, you know, a thrust reduce that does this in a single pass. Yes. And I mean, I think it is also the case that all of the information that the compiler would

need to do that optimization should be here too. That is true, really. Yeah. You're just getting a pair of numbers out of this. And ultimately, you could do this in a single reduction that is doing a basically projection. You're doing a unary operation that modifies it. And then you're doing a summation for both of those.

Now we just have to go right set compiler. Yeah. Or more accurately, you have to go right set compiler and I will get popcorn watch. Yeah. Isn't this crazy though? It is crazy. It is.

Like it's, it's elegant. It's phenomenal. Like, um, and that's the thing is I solved this and initially was like, oh my goodness, this is one of the most beautiful, you know, BQN expressions I've seen. And then like was trying to fall asleep, was dead tired at like midnight the other night on Friday and was just like holy smokes you don't need to sort and then I like jumped out of bed went to BQN wrote these things didn't actually I have it literally uh you can here I'll show you on my other screen this is my other computer and and it actually has the exact same things. But you'll note that the twos are still – we did even better here.

I want to note that right now Connor is sharing his screen with me, and I'm looking at BQN. And Connor has also taken his laptop where previously I saw his smiling face and now that is pointing at a different computer screen that also has BQN on it. So Connor is sharing two separate video streams of BQN with me right now. Yeah. Wouldn't it be crazy to, if, if this, cause really this here is, we are like, this is basically,

this could be a combinator that like, I think in J a dyadic hook probably does something like this, where this is like the equivalent, like where it says two juxtapositions of a binary and a unary function yeah or apply the unary to one of them to the right one and then take the left argument just as is and then apply the binary operation like this would be possible although in j they chose you know dyadic and unary hooks to mean something different than they do like hooks don't exist in apl and we use the b1 combinator and the b combinator but you could spell this with some kind of you know other

combinator here which would then even make it i think even more but then that's once again it's like you know here's psi it's it's that's the question is how much do you expect people to know and in my opinion these composition patterns like once it's like entering the matrix like once you once you start to see them like you can't you can't un they're everywhere it's all that's that's that's that would be exiting the matrix entering the matrix means that you're would mean that you're like unaware of the reality of nature exiting the matrix would be the thing that you're looking for but anyways i just got nerd owned nerd owned boom uh but you should put that that last one back so that we can show the uh show the user the the listener the dear listener um yeah if they're if they're still listening yeah if they're still listening this is uh i don't i don't know how many

more of these bqn episodes we can do before we start like they are the most fun episodes for you and i to do but i can't tell they're probably the worst to listen to yeah it's got it yeah they are if they are let us know we'll uh hey we have some fun interviews coming up. Don't worry. It's not all Connor and Price discovering BQM. Maybe we got to do a YouTube stream. I think that's going to be the solution here is that we got to have a YouTube channel. Well, I wasn't even sure what... ESP the YouTube channel. Yeah, I wasn't even sure what we were potentially...

Because last time we were talking about how we were gonna delve into thrust partition but i feel like we got to organize that with uh allison and we'll just do like yeah we'll take half day off to yeah allison is uh is one of the engineers on my team who is the the lead for uh thrust and cub you know what do you think of the on the matrix note are you worried or concerned or excited about the new movie? I actually am not that big a fan of the Matrix. I just saw an opportunity to nerd on you and nerd on you. Like, I know that there's a new movie. I don't really care about it that much.

Fair enough, fair enough. We'll let the listener react to that i'm sure a few people have been insulted anything else we should say while we're uh before we close out this episode i feel like this ended up being like an hour so i don't know if we're gonna have to cut this into two parts or i should just leave this all as one i'm taking a look we're looking at an hour and three minutes but i mean but like 20 of those minutes was us talking about our dating life that you're gonna have to cut out yep we've been we've been bryce and i we joke about starting a second not podcast but like series on this podcast where fridays we release technical content and you

know mondays we release uh our dating podcast but uh that's probably not gonna happen so yeah probably we're gonna cut that out as well maybe we'll see we're gonna get ourselves in so much trouble connor why is that it's our podcast we talk about what we want yes but there are sometimes consequences for the things that we choose to say thanks for listening we hope you enjoyed and have a great day