Bryce 0:00

Oh, I should have worn my Hawaiian shirt. Oh, what was I thinking? That would have gotten a laugh out of you. Damn. Mistakes, mistakes, mistakes. I'll put that clip at the beginning of the episode, so uh I wear I am wearing my pineapple swim trunks, though.

Conor 0:23

Welcome to ADSP the podcast episode 53, recorded on both November 13th and 23rd, 2021. My name is Connor, and today with my co-host Bryce, we catch up and chat about Bryce being in Florida and then dive into solving an algorithm leak to problem.

Bryce 0:41

So I I was I'm in I'm in Florida visiting uh my parents because um they hate the cold weather. My my mother went to uh to Cornell for undergrad and University of Chicago for law school, which are two of the colder options for college in the continental United States. I'm sure you as a Canadian are like, yeah, yeah, yeah, that's cute. But uh after that, she was like, I'm done. I'm gonna like move to Florida and go become the first female lawyer at and like the first like female lawyer, the first like Jewish lawyer, the first like northern lawyer at this good old boy's law firm um in uh in Florida. And then she had me down here, and then for some reason she was like, let's try New England again. Um, although she had never actually lived in New England growing up, she grew up in Long Island, but let's try the tri-state area again. So then we moved up to Connecticut, um, and then I grew up there, and then there was one year, and she she married my stepdad who lived in Connecticut his whole life, and he's like, I'm never leaving Connecticut. Then there was one year where there was this freak uh blizzard, although these days with climate change, those just happen all the time. But there was this freak blizzard, and they lost power for uh like two weeks, and then my stepdad was like, Alright, I'm I am now ready to give Florida a try. And so now my parents live in Florida, and uh so I was packing uh to come down and visit them, and I thought I did uh a reasonable job of packing, like I didn't bring any more stuff than I needed, I just had a carry-on bag, um, which is like a new thing for me. Like a few years ago, I would almost always check luggage, but this time I was just like, I'll just fit it all in a carry-on bag. I don't need to bring every possible rice outfit. But um then I get here and I'm unpacking, and I realize I have two different headsets, the one that I use for recording and telecons, um, and then the my noise canceling ones, plus my ear pods, plus the microphone for recording the podcast, and the boom filter. And I'm like, hmm, I'm pretty sure that that like a fifth of my luggage was recording equipment. What has happened in my life? I blame Connor.

Conor 3:19

I mean, you should also blame COVID. It's like uh COVID, COVID created all these virtual meetings and whatnot.

Bryce 3:26

So I should, but am I going to?

Conor 3:30

So you're in Florida right now. Damn. Florida. I am I've heard about Florida.

Bryce 3:36

I would love to be outside and recording so that I could make you uh feel jealous about the cold city that you're in, but uh in the interest of audio quality, I am in the most the the room that I determined was best, um, although I I do think there's a bit of an echo because they have like very high ceilings, but there's nothing really I can do about that. And it is inevitable, even though I I I warned my parents about 10 times recording this podcast today. Need you to not come in and disturb me. It is inevitable that my mother is gonna burst in at some point and see whether I need water or cookies or tea or some other thing. This lady is always trying to feed me. She's trying to fatten me up, man. She's trying to fatten me up.

Conor 4:28

Isn't that what moms are for? You know, they gotta make sure they gotta make sure you're you know, there's something about uh yeah, moms and and uh even if you're not hungry, you could be hungry shortly, and so we gotta make sure that uh that doesn't happen.

Bryce 4:43

She's always planning her next meal. Always planning her next meal. What are you doing for Thanksgiving?

Conor 4:49

I'll be working. I mean, I'm in Canada, so the real Thanksgiving already took place in October.

Bryce 4:54

That is a pack of lies. Um I have I I of course know that Connor is Canadian and was setting him up for some trolling there. But uh but that's that's cute that you think that you have the real Thanksgiving.

Conor 5:07

Also, too, let's just rewind. So you're back in you're back in Florida, or you're in Florida.

Bryce 5:11

Technically, back in Florida is accurate because it it is a little known fact that I I I I tend to try to keep hidden from the world, although I am now saying it on our podcast.

Conor 5:23

So Which I believe all 7 billion people in the world do listen to our podcast. So you've uh you've uh definitely been out in here.

Bryce 5:30

I I was technically speaking born in Florida, so that makes you a Floridian. Technically speaking, back home. Yeah.

Conor 5:38

Um so I heard that uh I heard that a couple years or year, was it a year ago, COVID, COVID no longer exists in Florida, hey?

Bryce 5:45

Oh yeah, yeah, yeah. This is I I mean, this is the free state of Florida. I I I was joking with I've never actually been to Miami. I've been to pretty much all the other major US cities. Um and they're opening uh when I was in Louisiana, they had this chain of this is this is gonna be a change, this is gonna be a tangent, but we're going there. They had this chain of um fast food restaurants called Raising Canes, and they served one thing, um, chicken fingers, and like fries, but like chicken fingers and fries, and that was it. Um and they had this sauce that was like, I would, I would, Connor, I would sell you down the river for a thing of this sauce. Like, it is it is good. It is really, really good. Um, but they're like only in like Louisiana and like they've been spreading out in like other parts of the south. Um the this the ch I I lived near the first of the stores, which is right next to the LSU campus, um, the the founding store. And the story is that the guy who founded this restaurant chain, um he was a business major, and this was his, you know, for their final project for one of his business classes, you had to come up with a a business model for, you know, some something. And he came up with this business model for a restaurant. And the basically the premise was that, you know, it was a fast food restaurant that had one thing on the menu, and that um because they had one thing on the menu, you know, they had fewer ingredients that they needed to source. They could source like higher quality ingredients, um, you know, that that there were fewer things that their staff had to learn how to make. So like they could just do one thing really, really good. Um, and apparently the the professor was like, this is a like a dumb idea, like, and gave the project to C. And the and the guy was like, Well, I'm gonna go start my um, you know, my very successful business. Um, anyways, they're opening up raising canes um in Miami, um, which is like the the closest to me or a relative um that that that I get one right now. I'm waiting for them to open one in New York, but that'll take you know a few decades. But so I keep telling my mom, you know, I'm I'm gonna come down to visit her solely so we can go drive four hours to Miami to get these chicken fingers. Um and so I was joking the other day with her that we're gonna have to go to get to Miami while Florida is still a part of the United States.

Conor 8:15

I was I was trying to figure how this is gonna come back to Florida and you know Florida and you know, if we've got listeners in Florida, uh good on you.

Bryce 8:26

If they they know it, they know. If if we have listeners in Florida, they get it. They get it. Because uh I'm Floridian, I get it. I get it.

Conor 8:33

Like I mean, I'm not sure. This is uh I'm not sure. I mean, we're not gonna say anything, so it's fine to mention, but there's a YouTube channel that was previously called All Gas, No Breaks, and then there was like a lawsuit thing, then they had to rebrand, so now it's Channel 5 News. Have you heard of either of these?

Bryce 8:50

No.

Conor 8:51

I will send you a link. I'm not actually sure if I feel comfortable. I'll have to watch a couple of the videos and then I'll we will link a video. Um, but it's this guy, his name's Andrew Callahan, and he records these five to like 10-minute videos where he just puts himself in the most not awkward, but just like crazy situations, and then ends up interviewing these folks that are just let's just say very unique and have um interesting worldviews and a lot of conspiracy theory types. Like, you know, one of his most viral ones was when he got himself into like a flat earth conference um and was interviewing a bunch of people. Anyways, he's got a bunch of them in Florida uh on Miami Beach during sort of spring break. Um, he's got one in like Fort Lauderdale. Um I have I have myself have never been to Florida. Um I'm not sure if I should rectify that. Um most of what I see on the internet says that I shouldn't.

Bryce 9:52

Um there are there are cool parts of Florida, like Tampa's kind of cool, Miami's cool, Key West is kind of cool. There's other parts of Florida that are probably cool. Yeah, maybe one of one of these days I'll we we used to we had uh there were two very famous C committee meetings held in Jacksonville, and um oh the stories I could tell you both about those meetings and about the the venue in the city. Um yeah, it was it was memorable. It was memorable. Those were two of my most memorable committee meetings.

Conor 10:30

Jacksonville Squared. We'll have to do an episode on that later.

Bryce 10:35

Alright, so you got a topic for today?

Conor 10:38

Are we doing what we we we missed out on last time? So at this point we've been recording for 10 minutes. We have 10 to 15 minutes of recording of the start of the leak code problem.

Bryce 10:51

Yeah.

Conor 10:52

Do we want to do that today?

Bryce 10:54

Alright, alright. So yeah, so then let's do the leak code problem. Um and then we can start our redesigning thrust sequence series. I don't know why I said sequence.

Conor 11:05

Alright, so probably probably the way I'm gonna cut this up is we'll do that little intro thing. Oh, yeah, it's too bad too, because I'm flying, you're in Florida. I'm flying to Vancouver this weekend uh for a 10K race where I hope to set a personal record, but folks aren't gonna hear that if that happened for like a month because we've got part one of this, part two of this, then we're recording with uh Eric and his dad, Eric Niebler. That's gonna be exciting. So that's probably gonna be one or two more episodes. It's gonna be like four episodes. But, anyways, alright. So we'll cut the beginning of this Florida, Bryson, Florida pluses.

Bryce 11:46

Oh, I should have worn my Hawaiian shirt. Oh, what was I thinking? I wouldn't have gotten a laugh out of you. Damn.

Conor 11:52

Don't worry. I'll put that mistakes. I'll put that clip at the beginning of the episode.

Bryce 11:56

So uh I wear I am wearing my pineapple swim trunks, though.

Conor 12:02

Alrighty. Um, I'm also wearing shorts and a t-shirt, but I'm inside. I guess you're inside too.

Bryce 12:07

Um yes, but but I am in Florida. You are in Toronto, um like the ice city.

Conor 12:16

Yeah, it is supposed to snow today. Um although I will say, we gotta turn that down. Uh Toronto's becoming more and more of an attractive city to live in because Vancouver is like the other top city in Canada, but they had forest fires in the summer and they got flooding right now.

Bryce 12:33

I've I've been to Vancouver and I'm into Toronto. I both I love both cities, but like I think I feel like Toronto's like a city on a different level than Vancouver.

Conor 12:42

Really?

Bryce 12:42

Yeah.

Conor 12:44

Interesting. I mean, most there's a there's a saying a lot of people from BC and Vancouver call Ontario unterrible because it doesn't have as man it doesn't have mountains, it's admittedly not as beautiful from a geography point of view.

Bryce 13:01

So, listener, it's important to understand Canadians very nice to non-Canadians, not at all nice to other Canadians.

Conor 13:09

No. Uh we always are saying sorry. It's that's like how you can tell a Canadian. One time, here's a story. One time I went down across the border because I was at a concert in Windsor, which is just across the border from Detroit. And so I drove through Detroit to some like, I don't know, a couple outlet malls to do some shopping, which I don't even know why I did it, because I don't really like shopping, but hey, I was told that's what you're supposed to do. Anyways, I stopped off at the subway and then ordered a subway sandwich. And at the end was just, I just said thank you. And she said, Oh, you must be from Canada. And I said, What? How do you how did you know that? And she's like, Oh, like Americans don't say thank you just for making them a subway sandwich.

Bryce 13:51

Oh, yeah, that's definitely true. I would not I would not do that.

Conor 13:55

Anyways, alright, so this is the end of this episode. We are now going to. Alright, so how did I do this last time? So Wait, wait, wait, wait.

Bryce 14:04

We're not gonna do a whole episode just about me in Florida. You gotta give people some like some. Oh no, no, no, no.

Conor 14:10

So the end of the episode is that we're gonna cut in the 10 to 15 minutes that we still have left from last time recording, which was the introduction of the leak code problem. This page.

Bryce 14:25

All right, so I just have a feeling that I'm gonna be put on the spot at some point.

Conor 14:31

There'll be one question at the end of this, but I'm not gonna expect you to know any APL. So here. The question is actually let's bring up let's bring up the lead code question. I'll try and uh I'll try and hide the title. Um, and then I'm gonna share my screen. And then first I'll just ask you.

Bryce 14:48

Oh, I'm not gonna put you on the spot. There'll be one question at the end. Oh, let me hide the title, then I'll ask you a question.

Conor 14:55

Uh a window. And we'll share this one. There we go. We will hide the bookmarks, make it a little bit cleaner. Alright. Can you read the question for the listener and answer it in C if you'd like?

Bryce 15:09

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers. Wait, what?

Conor 15:19

That's actually poorly written. It should say move all the even integers to the beginning of the array. And all of the odd integers to the end. So what algorithm, you can play along, listener, what algorithm in C can you use to solve this? Woohoo!

Bryce 15:36

Um I mean, like, but I I I'm confused because like that's so easy. It's pretty clearly partition, yeah.

Conor 15:43

I mean, so here's the thing. Our C developers that are algorithm woke will be like, yeah, I mean, that's you just expl you literally just explained what partition does. I don't even need to think like about a fancy language. That's literally what partition does. However, partition doesn't exist in every language, and I'm sure we have a few non-C devs. And even if we have like a closure listener right now, they're going partition, that's not what partition does. Partition and closure uh is an anamorphic algorithm that like splits things up so it's closer to like a chunk than it is the partition in C. And partition is actually one of the most overloaded in terms of what it does across programming languages.

Bryce 16:21

So what do other languages call what C calls partition?

Conor 16:25

I think actually just part just C.

Bryce 16:28

Nobody else has partition?

Conor 16:29

Or actually, here, do you want to? Um oh man, damn, I'll post this as well.

Bryce 16:33

Because partition's like a fairly important algorithm. I would be surprised if other languages don't have it. Wait, isn't it like your job to know what this would be in all the other languages?

Conor 16:45

I mean, we're bringing up Google Translate. We're bringing it up. Uh we need to go just.

Bryce 17:03

I want to know what this algorithm in this particular programming language is called in other programming languages. Yes, Connor has a thing for this. Of course he does. Why wouldn't he?

Conor 17:11

Yeah, I mean it's supposed to be a website at some point. Um I just haven't had time to do that.

Bryce 17:16

My my my guess is that other languages call it some form of sort.

Conor 17:20

Well, so I know that Haskell actually they call it partition, but Haskell returns a pair of arrays, not just a single array. Um do you know what other? It's actually a library. It's not a language. We could, but we don't. So here we are. Google translate. So let's uh type in partition. Um so what this is here, this is color-coded by implementation. And actually that's interesting. Why does oh so yeah, all of the blue ones, C, CUDA, and D, um, have partition doing exactly what we do. And the purple ones, I believe, return. Well, actually, let's just go to should we go to the Rust docs? Let's see what partition does. Creating an iterator, uh, consumes an iterator, creating two collections from it. So yeah, I think purple here means that all of these languages return a pair of lists. So it is sort of the same algorithm, but then closure and APL, their partitions do completely different things. So if we go to the closure docs, um returns a lazy sequence of lists of n items each. So yeah, you it's basically chunks of. So if you give chunks of four, it'll take four elements at a time.

Bryce 18:34

Ah, okay, that makes sense.

Conor 18:36

And uh and there's overloaded versions where you can also create like where the chunk size is different than the step size, um, and then you got some padding and stuff.

Bryce 18:44

Alright, so Bryce But but but that that I mean like that algorithm, the the algorithm, the partition algorithm, like it must be it must be a like just a general algorithm in CS. Like there must be some term of art for it, right? Like it's some class of sorting algorithm.

Conor 19:05

I think it's actually talked about in uh programming pearls, but I don't actually I don't remember if it had a name on it.

Bryce 19:11

Hang on, hang on, hang on. I don't know if you've heard this story, but uh when I worked for uh for Hartmet uh Kaiser at LSU, um he gave me uh four books. Um for the first birthday that I worked there for him, he gave me his copy of Elements of Programming. Um and then when we moved out of the building, he gave me um a hard copy of um SICP, the structure and interpretation of computer programs, which when I told you that I had a hard copy of, you got very excited because they're very they're very expensive.

Conor 19:53

I mean, here let's go. While you tell this story, I'm gonna look up what the price of SICP is on Amazon. Um I guarantee you it's not.

Bryce 20:06

Um uh The Art of Computer Programming, the book that Donald Newth wrote. Um and I was like, well, what about volume one and four? And he was like, Yeah, I don't know what, I don't know how the s set got broke up got broken up, but you know, you only really need two and three. And so uh volume two is semi-numerical algorithms, and volume three is sorting and searching. Um and it's been a long time since I've opened this up. Um and so I'm gonna take a look and see if I can find if I can find partition in the index here.

Conor 20:45

I'm gonna give you uh twenty seconds to find that. And yes, the you can get it in paperback for not that expensive. I mean 73 bucks for a paperback text is is still up there. But hard.

Bryce 20:55

Let's see. We got partition exchange sort, partition in a file, partitions of a set, partitions of an integer. None of those particularly sound promising. But let's look at what a partition exchange sort is. I have I'm almost certain that's not what we're looking for.

Conor 21:15

And while Bryce skips to that page, the hardcover price used is 140, and if you want it new, it's $1,077.

Bryce 21:22

So I'm surprised you can even get it new. Yeah, mine's a little a little uh a little beating up. Which we can look at.

Conor 21:41

I mean, actually, isn't this now that I think about it, I mean I haven't really been thinking much. I've just been waiting for you to find the answer. Um Partition is the single step within Quick Sort, is it not?

Bryce 21:51

Right, right. And that's that's the this the section that I'm in in the book is the quick sort section. And it's talking about how you can use this to, you know, yeah, so this is definitely documented in Yeah, yeah, yeah. And so so I think that the origin the origin of the term partition for what C calls std partition is probably from this 1962 CS paper, which presumably is about, you know, how you write a quick sort.

Conor 22:22

Alright, well we're we're coming up on the hour mark here. We're gonna we're gonna punt this to a different episode, and uh stay tuned for a future episode where we look Your audio cut out.

Bryce 22:33

I can't hear you, your audio cut out. Nope, still can't hear you.

Conor 22:39

And that concludes part one of this two part episode due to the fact that my audio cut out. Stay tuned for the second part next week. Thanks for listening, we hope you enjoyed and have a great day.