Transcript

Transcript prepared by

Adám Brudzewsky, Bob Therriault, Igor Kim and Sanjay Cherian

Show Notes

00:00:00 [John Earnest]

So a note to the implementers for next year, you should definitely incorporate some hexadecimal numbers in input. That'll really bust some chops.

00:00:10 [Marshall Lochbaum]

Don't do hexadecimal, do base 15.

00:00:13 [JE]

Ah, there we go. Now you're thinking.

00:00:15 [Music]

00:00:26 [Connor Hoekstra]

Welcome to episode 95 of ArrayCast. I'm your host, Connor. And today with us, we have two returning guests, not just one, but two. We'll get to introducing them in a moment, but first we're going to go around and do brief introductions. We'll start with Bob, go to Stephen, and then to Marshall, and we'll finish with Rich.

00:00:42 [Bob Therriault]

I'm Bob Therriault, and season's greetings to everyone. And I'm a J enthusiast.

00:00:48 [Stephen Taylor]

I'm Stephen Taylor. I work with APL and q.

00:00:52 [ML]

I'm Marshall Lochbaum. I made BQN. I'm a Singeli enthusiast.

00:00:56 [Rich Park]

I'm Rich Park. I do media training outreach for Dyalog, so APL for me.

00:01:02 [CH]

And as mentioned before, my name is Connor, host of ArrayCast, massive Array language enthusiast. And yes, happy holidays. I believe this will be the closest to the holiday season, at least if you celebrate this holiday season, depending on which one it is for you. It might be a month away, six months away. I don't know all the holiday seasons, but anyways, hope you are having some time off, spending some time with family, friends. And with that out of the way, I think we have one grand announcement that comes from Bob, and then I will segue into introducing our two returning guests, and then we'll hop into our conversation. So over to you, Bob.

00:01:37 [BT]

Yes. My grand announcement [01] is, well, it has to do with the topic of the day, which we're looking at Advent of Code and these kinds of games and all the whole stuff that goes around it, because everybody this time of year is, well, not everybody, I suppose most people are very interested if they're programming in Advent of Code problems for a variety of different reasons. In any case, my announcement is Rory Kemp, who has actually showed up on one of the Iverson College episodes. Rory has posted solutions in, interactive solutions, I should add, in q. And I became aware of that today. We'll have a link in our show notes. So if you're into this stuff, Rory actually is, well, we all found, I think, at Iverson College, he's quite brilliant and does actually pretty good, really good explanations of how to approach these things. Spoiler alert, these are massive spoilers. If you haven't solved the problem, you want to know how, take a look at this. He'll show you how in q, and quite often that gives you some real strong clues about how to do it in just about all the array languages. But that's the announcement, and that leads us into Advent of Code and the two guests we have on today.

00:02:47 [CH]

Yes, so we'll do that next. We have two returning guests, as I mentioned, not just one, but two today. First, we'll introduce the guest of episodes 41 and 43. I looked it up, folks, all the way back from 2022, John Earnest. I will, or I will, we will link in the show notes if you haven't listened to those episodes already. I believe one of them, if my memory serves correctly, the first one, we did a history of all the Ks, a fantastic resource because that information is hard to come by. And then the second one, we talked about John's work on LIL, Decker. I think we also talked about your k implementation, OK, and the multimedia stuff around that. Both awesome episodes. Welcome back, John. How are you doing?

00:03:29 [JE]

Great to be back.

00:03:49 [CH]

Awesome. And then we will also introduce our second guest, Kai, who has also been on twice in 2023 and 2024, I believe episode 63 and 77, where we were talking, obviously, about the Uiua language, the hottest, newest array language on the block. I actually don't, is that still true? There might be a newer, probably not hotter. I don't know how we measure the-- I don't remember anything that's come up since then, so. So I think it still has the title of at least newest, maybe hottest.

00:04:00 [ML]

Whatever newer array language is out there has yet to kind of make this scene.

00:04:04 [CH]

That's true. That's true. I mean, famously, Uiua was in the wings for a while, and we all didn't know about it. And boom, it blasted onto the scenes, partly in this ArrayCast forum when it was announced. Welcome back, Kai. How's it going?

00:04:16 [Kai Schmidt]

Good to be here.

00:04:17 [CH]

And with that, I guess we'll just hop right back into the topic that Bob mentioned, Advent of Code. It is today, December 17th. So we are 16 and a half, 17 days through our 25 days of Advent of Code. And for those that are living under a rock, but at also the same time listening to this podcast, Advent of Code, there are 25 daily challenges, part A, part B. They progressively get harder, although I think everyone would agree that it skips around in difficulty sometimes. Every once in a while, you'll have like day seven, and then day eight will be drastically easier for some definition of the word easier. Maybe there's a trick you need to know, and it's less programming. And it's super fun, a great way. A lot of people choose new languages to learn. And I'm this year, so I think maybe that's the first question we'll start with. We'll go around for folks that have been doing them, whether you did half a problem, or you've just been reading them and paying attention. I myself have been solving the problems in BQN. What is it? A spoiler? I guess a special announcement. I've decided next year, mainly because I was watching Tacit Sanctuary's videos, and I saw that Kai, you added subscripts.

00:05:30 [ML]

So this is not an Advent of Code spoiler to be.

00:05:32 [CH]

It's not an Advent of Code spoiler. It's a...

00:05:35 [KS]

Is this episode Advent of Code spoilers? I feel like it...

00:05:37 [ML]

I think we'll just... We won't spoil any particular problems, right?

00:05:42 [JE]

We can focus on historical problems.

00:05:44 [RP]

They've already happened if you're listening to this.

00:05:46 [CH]

I mean... I think it would be a shame not to talk about... Well, I mean, we'll see what the direction... We will put spoilers, skip ahead 10 minutes if we end up talking about specific problems.

00:05:55 [BT]

You're giving me a lot more work in editing. I'm going to have to have a fog horn or something. It's a spoiler alert.

00:06:01 [ML]

Connor just started off with spoilers, so anybody who wants to avoid Advent of Code spoilers is going to say, "Oh no, what do I do?"

00:06:05 [CH]

This is not an Advent of Code spoiler, but just if you're thinking about doing Advent of Code, you haven't started, or you're a few days behind, just hit pause on this episode. Come back in a couple of weeks, folks. It's no problem. No problem. You can come back. It'll still be here, unless Bob... I mean, we haven't deleted episodes in the past. So anyways, the non-Advent of Code spoilers that next year, I'm going to do it in Uiua, because I'm super excited. It's probably the most exciting feature to be added to Uiua recently, and it's the subscripts, folks. It's the subscripts.

00:06:32 [KS]

Really.

00:06:41 [CH]

Well, I'm not sure if you want to talk about it, Kai, or we should finish going around and mentioning if you've been solving them or not, but I just got to say...

00:06:43 [RP]

No, you've mentioned it now. I want to hear what's...

00:06:44 [CH]

Okay. Well, maybe we'll throw it over to Kai, and you can talk about what, like I said, it's obviously... Everyone's been talking about it.

00:06:51 [KS]

It's just a notation that's basically you put a little subscript number on a function or a modifier or something, and it changes its behavior. Usually, it's kind of analogous to APL's access operator thing in that what it does for each function is different, although groups of functions have similar behavior. And it looks nice. There's little numbers next to stuff.

00:07:14 [CH]

Ah, it looks beautiful. Looks beautiful, Kai. The reason I'm so excited about it is in the back of my programming language brain, I've always thought... Adam and I have talked about this. I think a few other folks have talked. What are the different strategies? We were talking about this at Iverson College back in August of the order of binding for modifiers. Sometimes you want the order that modifiers bind not to be the right to left order. In order to get around this, you now need to use parentheses. Are there alternatives? One of them that Adam suggested was you could add... This is pie in the sky stuff. You could add colored boxes similar to some esoteric languages where the boxing around... You would just use keyboard shortcuts to overlay these colored boxes, and that would define the order of evaluation. The other systems are like Pedmas where you have hierarchical rules. Another system could be subscripting some of these. Anyways, we're off in the weeds. The fact that Uiua now is the first language that I know of to introduce subscripts means that we're opening up the floodgates for possibilities. Marshall has another example, though.

00:08:21 [ML]

Oh, hold up. Back in 1962, the popular book by Ken Iverson titled A Programming Language featured the use of subscripts on functions to indicate the index origin. You'd have a subscript zero or one on various functions. Even the residue, the modulus function, you could do a one modulus. If the modulus... If the remainder on division is zero, it would actually return the divisor instead. Subscripts have been used.

00:08:59 [CH]

I mean, it was called A Programming Language, but that was not ever implemented.

00:09:03 [ML]

I guess what you can say is that it was not a linear text-based language because it had lots of these...

00:09:11 [CH]

Does it count?

00:09:12 [ML]

It had the thing where for inner products, you would put two functions on top of each other and stuff like that. It was a notation that was usable for programming. It was a programming language, but it wasn't text-based.

00:09:24 [CH]

Usable in what sense, though?

00:09:27 [ML]

There are sorting programs in that book and stuff. There's actual programming in it.

00:09:33 [CH]

This is like if a tree falls in the wood, does it make a noise? If a programming language exists on paper, is it actually a programming language? If it's only in a book.

00:09:43 [JE]

Like Plankalkül was written down in notebooks for many, many years. I think there's been some experiments in trying to implement it.

00:09:52 [CH]

Plankalkül? Could you give us... I've never even heard of this.

00:09:55 [JE]

This is Conrad Zuse's programming calculus. It was a notation that he developed with the intent of describing algorithms in... I don't know. I think he was working on it in the late '40s. But to my knowledge, it was never completely implemented with an interpreter, but it's widely regarded as one of the first stabs at a high-level programming language.

00:10:23 [CH]

And I guess it is true that there was some ALGOL version, I think, that only really existed in standardese. I can't remember if the committee just gave up on it because it was the VASA ship that sunk before it even set sail, basically.

00:10:39 [JE]

I mean, ALGOL 60 was at the forefront of compiler technology when it was described, and there was quite a bit of brow-knitting over how the heck to actually implement this.

00:10:52 [BT]

How different is this from things like J's, I think they're either overcoat functions or trench code functions, where you just use your left argument?

00:11:03 [KS]

I specifically don't. I don't use them to make trench coat functions. A lot of them are just...

00:11:10 [ML]

So it's more like an extra parameter is what you're saying?

00:11:13 [KS]

No, not usually. So some of the simpler ones are like... I wrote a blog post about this. I guess you can link it. It's basically, if you do like +1, that's just a function that does +1, but you don't need to put parentheses around it. Other things are like deshape. So deshape subscript 2 deshapes to a rank 2 array rather than a rank 1 array.

00:11:37 [ML]

I mean, that sounds like an extra argument or parameter to me. Definitely with +1...

00:11:43 [KS]

I suppose you could say that. You're right.

00:11:43 [CH]

Well, in +1, isn't it just like a different notation for partial application, where you would have to use an after, before, bind in BQN?

00:11:53 [KS]

For that, it's more about just having less noise in the code. But then there's other ones like the both modifier. It calls the same function on two sets of values. If you do both subscript 3, it calls the same function on three sets of values, or subscript 4, or whatever. Or if you do like couple, couple subscript 4 is going to couple four values together instead of just two.

00:12:20 [BT]

So that sounds to me closer to what the cut conjunction does in J, where you've got an operand that you're putting next to it that determines how you're going to cut, whether you're going to cut based on the first character, the last character, and whether you're going to eliminate them from frets.

00:12:34 [ML]

BSo in that case, it's completely qualitative, right? There's no way... I mean, I can't even remember what 1 versus 2 does in cut, because it's just an arbitrary assignment. And it doesn't sound like Uiua has anything like that.

00:12:48 [KS]

No, there's not like, oh, you pick 1 if you want this behavior, you pick 2 if you want this behavior. It's going to be the same behavior, just with a different... It is in many cases an argument. A lot of cases, it's stuff like with the both example. It's stuff that you couldn't do at a runtime. It's stuff that has to be processed at compile time. So it's well suited for this static number that's in your code there. And I think having them separate from actual numbers, like visually, being small and smaller, and lower down in a different color, is good for separating different kinds of numbers visually in your code.

00:13:24 [CH]

I mean, it is actually very exciting to me, not just because it's introducing subscripts and potentially superscripts in the future. It opens the doors to say, well, I wasn't the first language to do it. Kai did it, so I can go ahead and do it. But also too, I think that makes Uiua the language that you can spell the tersest like increment function. Like BQN or APL had it before.

00:13:48 [ML]

J has a dedicated function for it. [02] It's greater than colon.

00:13:52 [CH]

In the cases where you're actually trying to partially apply a 1 to a plus, BQN and APLs, it's typically 3. The plus, the number, and then some kind of binding operator. And...

00:14:04 [KS]

You know, just last night, I was doing Advent of code, and I needed an increment by 2 function. And it was real short.

00:14:09 [CH]

Exactly. It's the same thing.

00:14:10 [ML]

Plus 2, plus regular 2, still is the increment by 2 function. It's just that you may want to use it with some modifiers that bind more tightly than functions, right?

00:14:20 [CH]

Exactly. And then you can avoid the parens.

00:14:23 [ML]

So the subscript 2 is basically what binds tighter than modifiers?

00:14:27 [KS]

Yes. Yes, it does. And I tend to be of the opinion that getting rid of the need for parentheses is not just a code golf exercise. I think in many cases, it does improve the clarity of code when you have just less grouping symbols to parse as you look at it. So that's where some of that value comes from, I think.

00:14:45 [CH]

It's one of my biggest pet peeves that you end up, especially with over, the over modifier in BQN and just in general in APL as well. If you want to sum is your operation, you always have to parenthesize that. And it's like, no, we're so close to having the most elegant code. And then I have to add a couple of parens, which is like the non-array language fans who I guess they're probably zero of that are listening to this are like, what are you talking about? A couple of parens is the end of the world. And it's like, you don't understand. We got the equal with over and then plus reduced. And it's like, it's everything in that, oh, we need a couple of parens.

00:15:22 [ML]

We need some sort of vertical indentation notation where every, your source code is a string of characters plus their vertical positions. And so the lower down it is, the tighter it binds to other characters. And then you'd never need parentheses.

00:15:39 [KS]

Marshall, didn't you solve this with I?

00:15:42 [ML]

Yeah, but you need to write a lot of spaces. So I mean, this way you just have, your lines are just like the entire screen tall. And other than that, you have no problems.

00:15:51 [CH]

APL plus music notation. That's what we need folks is every symbol is on a different spot on the, and depending on how complicated your program is.

00:16:00 [ML]

Oh yeah, no, you just use, you just use slurs for, for association. You say, well, these are slurred together. So you, you apply them first and.

00:16:09 [RP]

Oh, OK.

00:16:10 [KS]

Oh, like, like in BQN.

00:16:11 [ML]

Oh well, I guess so.

00:16:12 [JE]

Are you going to have to specify like the timing for every stanza or something?

00:16:17 [ML]

Well, no, if you don't specify it's common time, of course.

00:16:19 [KS]

This function has this time signature.

00:16:23 [RP]

And chord is concurrent or it's like a way of different way of composing functions.

00:16:27 [ML]

Do we have a topic for this episode?

00:16:30 [BT]

I was going to say we're 20 minutes in and we've sort of told people to watch out for spoilers for Advent of Code. We haven't really talked about Advent of Code.

00:16:40 [CH]

I mean, I would have gotten us back on track, except from the moderator's point of view, we are entirely on track folks.

00:16:46 [RP]

On the topic of, of, of programming interfaces that people may or may not like, and this concept of a music notation programming language, has anyone had to use Sibelius back in school or something? People were not, were not a fan of that. So I'll just throw a little caution out there before someone goes and implements this tomorrow.

00:17:08 [ML]

No, I, I actually, I am seriously considering doing my own music notation program that, that wraps through Lily Pond. Cause I, there's all sorts of, I want it to be text-based, but there's all sorts of stuff. It doesn't do well.

00:17:21 [CH]

Well, links to both of those. Haven't heard of either of them. All right. Bob has asked us to get actually back on track. So I will do that. Anyways, link in the show notes to probably some documentation on the subscript. If you want to go look into Uiua. It is pretty cool. And with that out of the way, couple solid 10 minutes on that topic. As mentioned before, I've been doing it in BQN. I think I've done 14 problems. I made videos on, I don't know, seven or eight of them. Maybe hands up if you have solved at least one problem and then I'll point at you and you can say what language you're doing it in. So Kai has his hand up. I'm guessing you're doing it in Uiua and we've got, well, I'll just go Kai and then I'll store the rest of my order. So I'll, I'll throw it to folks after Kai says how many he's done and the languages or language he's been solving it in.

00:18:07 [KS]

Well, yeah, I've been doing all of it in Uiua. And we have a thing in the Uiua community discord where a bunch of people are doing it. I've done all of them except two part twos for day 15 and 17, which was last night. Last night I didn't finish because I needed to go to bed so I could get up for this.

00:18:24 [CH]

Yes, yes.

00:18:26 [KS]

But it's been, it's been a lot of fun. I think it's, for a new language, it's, it's a good exercise and like whatever its strengths, whatever its weaknesses. We found a few bugs in the interpreter by people doing this.

00:18:41 [CH]

That was good.

00:18:42 [KS]

And I am very rarely the first one to, to finish a Uiua solution, even though I start at, when it starts, I open the problem, do it. There's a few people that always get it before me, which is interesting.

00:18:56 [CH]

You, I mean, that is the good fortune of being on the West coast of North America is that you are in the Pacific standard time zone, which is 9pm when the problems get released. I was in the West coast for a couple days and it was very nice at 9pm. I'm not, it's not midnight. I mean, for the first couple of days, it doesn't take too long, but once you hit, you know, day 10, it's, it's usually, you know.

00:19:19 [JE]

Starting at the night is just brutal.

00:19:21 [KS]

Yeah.

00:19:23 [CH]

It's, it only lasted, I don't know, a few days. And then my partner was like, are we, are we doing this for all the whole month? And I was like, no, no, no. It's, we're going to hit a threshold and we're just going to start sleeping like a normal person.

00:19:33 [JE]

I mean, like, especially, especially if you want to like, you know, tidy up your solution and post it on the subreddit or something, you can easily be up to like 2am. And if you do that and you also have a day job, that, that's really rough.

00:19:46 [CH]

All right. So Kai and community has been solving them. We will, I think Rich, you had your hand up next. My guess is APL, but I don't want to speak for you.

00:19:52 [RP]

No, no, I'm doing APL, keeping it easy. I mean, I sort of didn't realize it was December until maybe about the 4th or 5th. And then I was like, oh, and then sort of rattled a few out. And then I've been busy again. So I think I did seven and skipped a bunch of days and then I turned up on day 13. Just my luck. It was, did not take that long at all. Won't spoil that yet. Maybe we'll talk about it later, but that was a stroke of luck for me, but then that's all I've done. I have been following Isaac Wooden on YouTube. I think he's put three videos out, solving them in Dyalog APL and yeah, really nice linear algebra solutions or stuff that I didn't even realize you could, I didn't realize you could do it that way.

00:20:39 [CH]

Nice. I will link to their YouTube videos in the show notes as well. And I will add it to, on the read me of my GitHub repo, I have three different YouTube channels, two that are doing BQN, one that's doing Uiua and now it sounds like there's another one doing Dyalog APL. So I'll make sure to add that to that list of video people. I think Marshall, you had your hand up. You've done, at one point I had talked to you and you said you hadn't done any, but now it sounds like you've had a change of heart.

00:21:07 [ML]

This is not too different from past years. So I think it was day six, part two. Yeah, yeah, I didn't do part one. Part two, no one found a fast solution for it.

00:21:16 [CH]

How'd you get to part two if you didn't do part one?

00:21:18 [ML]

Well, I didn't even, so I took Dzaima's solution because it was so that I didn't have to redo some stuff and he had all the input parsing and everything, which for this problem was not very hard. So nobody found a fast solution for part two. So I wrote one that got it down to, it was like 20 to 30 milliseconds, whereas Dzaima's was 200 or so, which was not that great. So I've done at least the hard part of one of the problems.

00:21:48 [CH]

You've done half a problem purely to show that you could squeeze some speed out of the CBQN interpreter.

00:21:54 [ML]

Well, it took a few hours.

00:21:57 [KS]

Oh, wow. I was going to say, we have very different definitions of fast for some of these.

00:22:01 [ML]

So that one was, I mean it's kind of a very sequential problem. So it was, it was hard for anyone to do in the right language.

00:22:10 [RP]

This was like the maze-y, like- Yeah, it was following- It's like sliding along and then hitting some rocks. I don't remember how they, obstructions.

00:22:13 [ML]

Yeah, following a path around, yeah, with obstructions and then you have to modify the-

00:22:24 [RP]

I think I did that all with Boolean scans and reversing stuff.

00:22:29 [ML]

Yeah, but it was, it took like a significant fraction of a second to do it that way, right?

00:22:34 [RP]

I'm not sure, but I'll have to take a look.

00:22:38 [ML]

And yeah, so regarding BQN, I keep a list of people who are publishing their solutions in BQN. So I have a nice chart that I did and the code for that just pulls from everybody's repository and then generates it. So that didn't take a lot of work to update for this year. So I keep running it.

00:22:58 [CH]

And I think the last hand that I saw up was Bob's, if I'm not mistaken.

00:23:02 [BT]

Yeah, well, I spent six weeks in Italy. I was not doing any programming. And so Advent of Code has been an opportunity for me to reacquaint myself with the J language. Because as soon as I go in and try and solve problems, I realize how much I've forgotten and things and how big a language it is. There's something that did something like this. So I'm abysmal at it. And I think I've completed two complete problems, days one and two. I've skipped around a bit. Whenever I hear one that might be suited to the array languages, I'll go try it. And I haven't since.

00:23:46 [CH]

What do you mean? They're all suited to it. BQN's great for everything.

00:23:50 [ML]

Not problem part two day six.

00:23:54 [BT]

Thank you, Marshall, for bailing me out. I just felt even worse. So that's been my limit. But it's been humbling. And one of the things I wonder about is these people who get on the top of the leaderboard, how is it possible to solve this in like a minute? It takes me a minute to read the thing. How is this done? It must be done automatically.

00:24:18 [CH]

Nah, you just skip the first four paragraphs. There's nothing useful in there. It's just a story about an elf going up a mountain, riding on a train. I've never -- honestly, I used to in past years, I would explain a bit of the problem. But then I realized, I don't care. Some people really enjoy the story. But I have zero interest. I go straight for the numbers. And then if I have missed some piece of information, I just do like an up scan to see what I missed. And it is -- some of the times I spent like an extra 20 minutes because I realized I did miss some key piece of information. But probably an aggregate. I have saved time by not reading that story.

00:24:55 [RP]

They highlight the keywords for you.

00:24:57 [CH]

Yes, that's true. That is true. But sometimes they give you -- now they give you three sets of tests. A mini test, the sample input, and then the full input. And that's where I got tripped up one day is that I realized that I think there was some Xs and Os or something. And I had looked at the third graph and didn't realize that like, oh, I was trying to identify all of the word search or something. Like in the already identified word search. So there was no letters I was looking through. I was just looking through the found words. And anyway, so

00:25:29 [JE]

Was it last year where the first problem stumped a whole bunch of people because the sample input did not disambiguate a significant case? And it ended up making like the very first problem significantly harder than you would think. Unless you happen to just, you know, leap to the interpretation that solves it correctly.

00:25:49 [CH]

Usually if you -- here's a pro tip. Not that I'm a pro. But it works for me every time, basically. If you end up having a correct solution for the sample input but an incorrect solution for the full input, either on part A or part B, just go to the subreddit for Advent of Code. The top post will be a meme being like day one when -- it literally happened this time. It was for one of the problems where you had to like -- it was the compression one where you were swapping things around. And it's like when you solve part A thinking that, you know, the number can only be one digit only to realize that it could be two digits. And then I was like, oh, yeah, that's exactly -- that meme was the direct thing that I had done.

00:26:37 [JE]

So -- It was just particularly mean because it was the very first day. And so, you know, usually the first day is a softball. Historically it's always been, you know, something that most people could do in 10 or 15 minutes.

00:26:48 [ML]

Yeah. And I should disclose day six. I still haven't read the problem. I've only read the solutions and figured out what the problem might be sort of like.

00:26:55 [JE]

Very declarative programming of you.

00:26:57 [BT]

So how is it that people can solve the problems so quickly? Like top of the leaderboard, they're solving them like under five minutes, right?

00:27:07 [KS]

I mean the pessimistic answer is is AI right?

00:27:11 [ML]

Yeah, I'm pretty sure the first few days are, yeah.

00:27:13 [JE]

Yeah.

00:27:14 [KS]

That's right. I mean, the optimistic answer is purpose-built languages for Advent of Code, which I've heard of before.

00:27:21 [RP]

I assume they make a little DSL in whatever language that they're -- like at the very least they've got something that brings the -- brings their input into their environment.

00:27:31 [JE]

Yeah, you always -- you always pre-stage boilerplate for stuff.

00:27:36 [ML]

No, but like in previous years, there were not a lot of like sub-30-second solves. And this year there are, and there's an obvious reason. So the very fastest people for the easy problems are not solving it themselves, I don't think.

00:27:53 [CH]

It should be noted there is a past guest, at least one, that is on the top 100 for this year so far. Does anybody know who?

00:28:01 [ML]

Kamilla? [03]

00:28:02 [CH]

Kamilla. She's ranked 98th right now.

00:28:06 [ML]

Oh, hanging on.

00:28:07 [CH]

And I think I've seen -- I've seen Dzaima once or twice. He made the leaderboard.

00:28:09 [BT]

Yeah.

00:28:11 [ML]

And Rory did -- Rory made it for day one. I don't know if he's made it since then.

00:28:17 [CH]

Yeah. So honestly, like if you have a -- like as you go through it and you build up these helper functions, like the single most useful -- and this has been like the most pleasant year of Advent of Code for me is because of a function that just pulls out all the integers from a string. At least up until day 14, there hasn't been a single problem that's required more parsing than just like ignoring all non-numeric, aka like negative sign and digits, and then just like converting those into a list of numbers, and then usually you have to like take the first one and then use the rest or take the first two and the last two. In years past, like I've never -- I've always tried to like parse it like, oh, first split on the commas, then split on the whatever, and even in Python, that's like a pain. So like if you have these -- a couple helper functions to like basically make the parsing invisible or at least just like a single liner, that can like save you like, you know, 30 minutes a day for some of the problems.

00:29:20 [JE]

So a note to the implementers for next year, you should definitely incorporate some hexadecimal numbers in input. That'll really bust some chops.

00:29:32 [ML]

Dude. Don't do hexadecimal, do base 15.

00:29:34 [JE]

Ah, there we go. Now you're thinking.

00:29:37 [CH]

So I mean, a couple problems were mentioned, day six, part two, day 13. There was some worry about spoiling it for folks. Do we want to talk about any of the problems specifically, or do we want to talk generically about, you know, array languages, why you might want to consider them? Bob's got a suggestion.

00:29:54 [BT]

My suggestion, I've got one more generic thing that had popped up, and again, it's Rory mentioned it, is sometimes a solution, the solutions people are coming up with are not general purpose solutions. They're fit to the data that you're given. And since people are given different data sets, it's, I suppose, randomized. So you might not get the same data set to work with as somebody else. But he's stated, and I don't know, because I haven't gone to this level yet, but he said there are times when he's solved the problem for his data set, and they're not general. They wouldn't work on somebody else's data set, but he's looked at his data set and said, ah, this works for mine. So in this case, I can solve the problem. But it's not, it wouldn't solve generally all data sets that would be presented.

00:30:43 [ML]

Yeah, well, there are two kinds of, you might have it where there's an assumption that the author's made sure is true for all the inputs, but that just isn't stated in the problem, and he does that intentionally. You might also have an assumption that happens to be true for just your input, and isn't true for other inputs. But if you only have your input, you don't know which is which. So, if, I mean, the goal of Advent of Code is just to solve whatever problem you're given, specifically. But if you're writing up your solution, that's kind of a challenge. I don't know what you, what you should do to address that.

00:31:20 [JE]

Well, I mean, there's definitely historically been problems where there's like a nasty edge case that only applies to some subset of the inputs that people are given. And I mean, that's why you read the Reddit discussion, and you find out whether or not you won the lottery on that particular problem.

00:31:36 [KS]

That's actually, it's actually how I found two different bugs in the Uiua interpreter, is that people came up with equally good solutions, and then it worked, their solutions worked for some people's inputs, but not others. And so, then you have to figure out like --

00:31:54 [ML]

This is like their solution should have worked on all inputs, but the bug was.

00:31:58 [KS]

Yes, the bug made it only work on some inputs. And it's really, it's a weird thing to track down. Yeah. Because it like, there's one of them that was like one of the maze problems, and the maze had to be configured just so for the bug to trigger. And it happened with some people's, not others.

00:32:15 [ML]

Yeah, that's pretty scary.

00:32:17 [CH]

This is like a form of fuzz testing, but it's Advent of Code testing or something like that.

00:32:23 [KS]

It is. And I've actually put a reduced Advent of Code input into like my test suite now to make sure that bug doesn't happen again.

00:32:29 [BT]

And Uiua's put in a path primitive, right? The Dijkstra?

00:32:33 [KS]

There is a path primitive, yeah. It's Dijkstra/A*, which is basically all you need. That makes some of the problems much easier.

00:32:42 [BT]

Now, was that put in for Advent of Code?

00:32:45 [KS]

No, no, it was in there long before.

00:32:47 [JE]

Because implementing that sort of thing in an array language from scratch is really awkward because of all of the bookkeeping that you have to do for a priority queue or something like that.

00:32:57 [KS]

Yeah. And I find, I don't know, there's lots of problems you wouldn't normally think of. There's a lot of problems that don't immediately come to mind that are good, that can be graph based problems, right? Because the primitive doesn't just work on a grid, it works with functions. And so you could be working on a grid, a graph of nodes, you could just be working on like a string and finding adjacent things. So it helps lots of stuff.

00:33:18 [CH]

Do we want to dive into a select problem and then talk about the, not necessarily the exact solution, but the advantages or disadvantages of solving with an array language? Yes, no? Do we want to vote for a problem?

00:33:33 [KS]

I think that would be fine. What's the best array problem?

00:33:36 [RP]

Day 13. No. Only in Dyalog APL.

00:33:40 [ML]

Well, I can tell you which one has the highest ratio. So, yeah, days 13 and 14 have fewer than have more than one in 3000 solutions done in BQN.

00:33:54 [KS]

So. I found day 13 really easy, well, part two specifically, I found it really easy to solve once I knew what the solution was, like the trick that you're supposed to know. I was actually kind of mad that you needed to both recognize it as a linear algebra problem and then do that, because I don't know that much linear algebra. And so the idea that this would be required for this problem, I don't think it's possible to do without some linear algebra.

00:34:26 [ML]

A lot of that is also just because the solutions in any language are kind of dropping off faster. So day seven is the one that sticks out the most as more people have solved it in BQN relatively. I don't remember what day seven was.

00:34:40 [CH]

Day seven was the construction of an algebraic expression that evaluates from left to right using plus multiplies. And then for part two, the concatenation of integers to figure out if it could equal a given value.

00:34:58 [KS]

I brute forced this one.

00:34:59 [ML]

Does that actually end up being arrays at all?

00:35:01 [RP]

Yeah, the only difference is some people literally catenate and build executable expressions out of the things. And then some people were doing stuff with logarithms.

00:35:13 [ML]

Yeah.

00:35:16 [RP]

Yeah. That's the other way you can join digits together.

00:35:18 [KS]

Like the first person who solved it in Uiua found a very nice sort of non-exponential, is it exponential? I don't know. A very well time-bounded solution that doesn't require you to build up the expressions. That is benefited by having pervasive operations that array languages have. Yeah. Although that one, for part two, I still had to brute force it, which Uiua has multithreading, so I took advantage of that.

00:35:45 [CH]

Uiua has multithreading now. Is there a multithreading primitive?

00:35:48 [KS]

It's had it for a very long time, yeah.

00:35:51 [JE]

Is it like Peach in q?

00:35:54 [KS]

No, no. There's a modifier pool which spawns a function in a thread pool and one just called spawn which just spawns it normally.

00:36:04 [ML]

Yeah, so it's a lot like the Dyalog thing.

00:36:06 [KS]

Yeah, so instead of doing like rows function, you do-

00:36:09 [ML]

Which I guess isn't actually, it's a Dyalog utility. It's not really in Dyalog.

00:36:14 [RP]

No, it hasn't gone in. There are symbols thought about for it.

00:36:18 [KS]

But basically, instead of writing like rows function, you just write wait rows pool and it'll spawn for each row in your inputs. It'll just spawn a thread and thread pool and then wait for all them all to finish. It only speeds it up by a factor of how many CPU cores you have, but it's useful for this brute force kind of problem.

00:36:40 [CH]

Interesting. So this is not in the form of a symbol. This is-

00:36:43 [KS]

It doesn't have a glyph, no. There are two functions, well, three functions that just have names. It's pretty easy to use. I actually didn't use it with rows. I used it with a partition, so you end up doing a parallel partition.

00:36:55 [RP]

Is this a sort of search you want that benefits from memoization? Does anyone bother with that?

00:37:01 [KS]

I don't think this one was. Others were. There is a memo function modifier in Uiua too that helped with some stuff.

00:37:07 [RP]

Oh, you've got it baked in?

00:37:09 [ML]

Well, so a lot of the time, instead of memoization, [04] you can use bottom-up dynamic programming where you build a list of all solutions and then you generate a bigger list from that and so on.

00:37:22 [JE]

Poses the challenges for parallelizing though?

00:37:37 [ML]

It depends on how that list is built, I guess. But also, if you're parallelizing the memoization, you have to have a- I guess you just share the hash table across threads or the lookup, whatever argument lookup structure you have.

00:37:40 [CH]

That's what I was going to say, is that that's one of the things I learned from reading other people's solutions after having solved it myself was that- I think it was day 11, which was the one that was like growing a list by a number of rules. If it's zero, if it's one, or if it's got an even number of digits, et cetera, one of your first thoughts is, yeah, just set up a cache that you can memoize stuff with. And a bunch of people that had solved it in BQN used the system hash map, which I did not know existed. Or maybe I did, and I've just never used it, so it's not top of mind.

00:38:20 [ML]

Yeah, so we implemented that. I wanted to have it ready for the 2023 advent of code, which it was. It was done a few months before. But then a lot of people had older BQNs and didn't end up using- didn't have it installed. So this year, pretty much everyone has it.

00:38:35 [CH]

Yeah. Anyways, it's a bunch of things that I learned from looking at other- I also had never used the system while function. And now that I know how to use it, probably for worse, I was going to say for better or for worse, but probably for worse, I reach for it way more often now. Because there are some times where you could use a scan or a reduction and twist a solution to use one of those, but you can just throw it in a while loop. And there was one where you had to find a Christmas tree or something, and that's just classically- you had to iterate a bunch of times until one showed up. And I was like, okay, well.

00:39:10 [ML]

You don't have to.

00:39:12 [KS]

I also found that one kind of annoying, because it's a very underspecified problem.

00:39:17 [CH]

Yeah, yeah. My first thought was like, what? They ask you to find something and then they don't give you any details about it other than that it's a Christmas tree. And I'm like, okay, what does that mean? What does that mean?

00:39:26 [KS]

Yeah, I saw one solution that was just the person wrote code to output every iteration as an image file and then just opened their Windows Explorer and just scrolled until they saw the Christmas tree in the thumbnails for the images.

00:39:41 [JE]

Well, I mean, like really, some of these really fast solutions to things are augmenting a human's abilities with a program rather than fully automating the thing. I mean, like in Project Euler problems, it's very much the same thing. They'll be like, oh, well, I can partially simplify this in math. I can write a program that brute forces some aspect of it, and then I just have to look at a few results.

00:40:06 [ML]

Yeah, Project Euler is a little different, I think, because you can almost never solve a Project Euler problem just like purely by programming. You have to do some math. In Advent of Code, if you just write the program fast enough, like the Christmas tree thing, you can go through all the frames. There is, in fact, a much faster way. So, like, if the author had wanted to force you to use the faster way, they could have picked some bigger numbers, made the size bigger.

00:40:35 [JE]

Well, but to Connor's point, if it's an underspecified problem, then you -- I suspect that a lot of people on Reddit who are trying to aim for beautiful solutions to things do kind of a parallel construction approach. Oh, yeah. Where they totally wing it, and then, well, now that I understand what the shape of the answer needs to be, now I can go back and write a very elegant program that's fully automated.

00:40:50 [ML]

I think the case with this problem was pretty much that, like, if you guessed a criterion that, like, at least sort of seemed like it would work, then it would actually work, because, like, a Christmas tree is very different from random noise.

00:41:15 [KS]

Yeah, I mean, the idea was to create a heuristic that you could run on each frame, right, to say, "Could this be it?"

00:41:21 [ML]

Well, again, not necessarily on each frame.

00:41:24 [KS]

Sure, sure. I mean, that's what I ended up doing, though.

00:41:28 [CH]

That was the thing, though, is you don't -- like, my idea ended up working, but, like, I could immediately think of, like, a couple different cases that, like, my heuristic wouldn't have worked for, and, like, how many iterations is it going to be? Like, do I let it run for a million iterations? Like, I basically just, like, had the while loop output the count, and then I think it hit it within 10,000 or something like that, but, like, if I had a wrong heuristic, how long do I let it run for to be able to conclude that, like, that was incorrect, right? Because my guess is there's not some cycle, and how --

00:42:02 [ML]

No, it cycles. Oh, it doesn't?

00:42:03 [KS]

It has to.

00:42:04 [ML]

Yeah, yeah, you can compute the cycle length without too much trouble. Oh, okay. And using some math.

00:42:09 [KS]

The scariest problems to me, all the way, was the ones where it's, like, oh, here's this part one, and you say, oh, I came up with this cool solution for part one, and you get a part two, and it's just, like, oh, do the same thing, except, like, triple the size of the input. And it's, like, oh, my part one solution is definitely not going to work for this, because it's some exponential problem, and so you have to totally change the way you solve it. It's happened a couple times so far this year.

00:42:34 [JE]

Yeah, when I was doing the ACM ICPC in college, you know, you always look at the N at the top of the sheet of paper, and you immediately know what complexity class your solution has to be in. If N is, like, 12, it's bad.

00:42:51 [ML]

It's exponential, yeah.

00:42:52 [CH]

Yeah, that's the trick with LeetCode problems, too, is, like, you can immediately look at the length of a list, and if it's 10,000, when you, oh, okay, they specifically chose the number that quadratic won't work for, so.

00:43:01 [ML]

Doesn't LeetCode usually, like, tell you the complexity that they want you, or is it just memory complexity?

00:43:07 [CH]

Sometimes they'll say, you know, try to solve this.

00:43:10 [ML]

I feel like most of the ones I've seen have, like, some specified complexity, which is just, which I think is a very bad way to do the problems, because, like, actually, a lot of the practical solutions, like, theoretical complexity, the theoretical model that is commonly in use is very bad, and its only advantage is that it's easy to calculate with. And so, when you specify, you know, something needs to run in O of N theoretical complexity, if you use a hash table for that, that might be a lot slower than sorting on large inputs, because your theoretical model is wrong. So, I don't like it when you specify, oh, solve this in big O of N, assuming random accesses, which are fake. Yeah, like, LeetCode sometimes will say, you know, solve it with this time complexity, but it enforces that with the input that it gives you. And so, technically, you can use a worst case thing, but if you do some pruning or whatever that, like, you know, short circuits a lot of the cases, like, you'll end up being able to pass the problem without getting a TLE, just because you did, like, some cute trick or something like that. So, like, there's definitely been examples where it's asked for, like, some log N thing, and I just had a linear thing, but I short circuited enough, or I had some trick, which is what they would call not in the spirit of whatever the LeetCode thing, but I'm, like, I'm just trying to get a green checkmark, you know?

00:44:38 [ML]

Yeah. Well, I mean, it's all spirit only, too, right? Because your pointers don't go past 64 bits, so it's, like, big O cannot apply.

00:44:48 [JE]

Well, in the ACM competitions where you're using a fixed set of languages and writing everything from scratch and having that included in your timing, there are, like, certain algorithms that are really good to use specifically for that kind of problem, because the implementation is very simple and elegant, but the complexity class is bad. The best example of this would be the Floyd-Warshall all-pairs shortest path algorithm, [05] which is cubic, but it's three simple nested for loops that you can just bang out. And you can solve a remarkable number of graph problems with just that building block, as long as you don't care how long it takes to run.

00:45:24 [ML]

That runs pretty fast in BQN, I have to say. So if your graph isn't that big, don't rule it out.

00:45:30 [CH]

I think it's what Python gets 10 seconds, and then the other languages get, like, one or two seconds in those contests. Yeah, when I used to compete in those, never very well, but there were some tricks where, like, you would actually just create some program that would generate an array of answers that would take, like, a long time, and you'd have one computer, but you'd just, like, launch a terminal, let it run, and then an hour later, like, you'd get the, you know, capture it, paste it to a file, and just then index into that array, and that was, like, a solution if you, you know, if you didn't know how to solve it the efficient way, getting, you know, a solution an hour later was better than getting no solution at all.

00:46:12 [JE]

But usually, you only get one computer, so you got to really commit if you're going to be grinding away at something like that, and hopefully not bogging it down to the point you can't work on other problems.

00:46:21 [ML]

Well, so, yeah, you have one computer and one brain. If you're not otherwise using the computer, may as well say it works.

00:46:27 [JE]

Well, most of the time, it's one computer and two or three brains, so.

00:46:33 [ML]

Oh, they give you an extra brain to work with. Wow. How much did that cost them?

00:46:37 [JE]

Maybe even a chalkboard, too, and, you know, that counts for something.

00:46:42 [ML]

So I'll set up the chalkboard to work on to evacuate this brute force method.

00:46:48 [CH]

What were you going to mention, Kai?

00:46:49 [KS]

I was just going to say, I think one thing we can say about, like, array languages with some of these problems is that there's some of the problems that, if I hadn't been doing the problem in an array language, I would have had a totally different approach. So, like, for example, there's one where, like, I mean, I'm not going to spoil the solution, but it's the problem. It's you have to figure out the area and perimeter of basically these, like, fenced areas, and then the second part is don't give me the perimeter of the fenced area, give me the number of sides on the possibly not square area. And if I had been doing this in, like, normal, like, C, or, well, I would have done it in Rust, right? But my solution would have been very, like, straightforward, like, walk along the fence count, right? And there'd be a bunch of stuff figuring out, like, what are the boundaries of this thing? How do you turn as you go around it? But because I knew that would be a real pain to do in array language, I found what I thought was a much more elegant solution that involves, like, windowing over the space and using, there's, like, some scans in there. And it's, I don't know. All that good array stuff.

00:48:06 [ML]

Yeah, all that good array stuff.

00:48:08 [KS]

And I don't know. I think that that's very cool that --

00:48:13 [ML]

I think this was also the one that, yeah, yeah, it was the one after day one that Dzaima got on the leaderboard for. So, he actually put up a video of him.

00:48:24 [KS]

Oh, no, I'm talking about day 12.

00:48:25 [ML]

I don't remember what number it is. It's the one with the fences and the perimeters and --

00:48:30 [KS]

The gardens, yeah.

00:48:31 [ML]

Yeah. So, he has a video of him solving it in eight minutes or something.

00:48:35 [KS]

That's crazy. It took me a while.

00:48:38 [ML]

You can definitely see how, you know, from the beginning, he's thinking about arrays.

00:48:43 [BT]

So, this video, he actually starts from scratch, records himself solving, and he solves it in eight minutes.

00:48:48 [ML]

Yeah. So, I guess he's recording every day, and if he makes it on the leaderboard, he posts it as the --

00:48:53 [RP]

That's how they do it Bob.

00:48:54 [KS]

I figured out, I mean, area, something like area is, like, trivial because, I don't know, Uiua has multi-dimensional partitions, so that was easy. Perimeter is slightly harder, but you figure out an algorithm for it, like, just an equation. But counting the --

00:49:11 [ML]

Yeah, well, I mean, it's all just going to come down to a sum of something.

00:49:14 [KS]

Yeah, but counting the number of sides, not, like, unit perimeter, but just the number of, like, contiguous fence segments was not, like, it was not apparent to me how you would do that in an array way, but I messed with it long enough that you figured out, and, I don't know, I was pretty happy with it.

00:49:31 [RP]

I was pretty blown away by Isaac Wooden's Day 5, which is the one where you have some rules for which order some numbers should be in, in a list of numbers, and I, like, I imagine a lot of people went budging around, reversing pairs of numbers in a big ugly loop, but then I watched Isaac's, and he manages to -- I mean, you know, some of these things, at first glance, the array, or, you know, this array approach, he's doing an out-of-product concatenating all the numbers in the input with themselves, which you think is going to be absolutely horrendous, you get this big nested matrix of pairs, but then he just looks up the rules in that big matrix of pairs, gets this Boolean out where, you know, there's some way by which the ones and zeros should be in the correct order that matches exactly with the sort of lexicographical ordering, or the total array ordering in Dyalog, so you can literally -- he just does a grade on that matrix, and that's the correct sorting for his inputs.

00:50:38 [ML]

I think I saw a few solutions that were, that were -- at least the grade was pretty similar.

00:50:43 [KS]

I thought that one was an interesting one, because the input that they give you, the ordering rules are cyclical. There's no total ordering. With the rules that they give you, but for every section of the input, it only uses a subset of those rules which aren't cyclical. And it also is the problem that made me learn how to do a sort by comparison operation in a language that doesn't have that built in, with just, like, grades.

00:51:13 [KS]

Yeah. Because a grade, a grade innately is like a sort by key type primitive, but with very little additional code, you can turn that into a sort by comparison function.

00:51:24 [RP]

Whatever, yeah. You just convert the thing you're sorting into the scores, the ranks of whatever your rule is.

00:51:33 [ML]

Yeah, well, and what you can do if you've got a completely arbitrary function, which I think was actually the path a lot of people used, is you just compare every element to every other element. Yeah. And then you have a matrix there of comparison results. And if you set it up right, that matrix orders the same way as the elements are supposed to.

00:51:53 [KS]

I was very surprised to learn, I think that's what you just were talking about, Rich, is that when you have that matrix of booleans, that that, like, sorts correctly for some reason. And I was like, it was not clear to me why that was the case.

00:52:04 [JE]

It's a really nice feature, being able to grade a matrix or an equivalent and have it do a lexicographic comparison. Yeah. Comes up surprisingly, surprisingly handy.

00:52:12 [ML]

And this took a while to appear in APL. It was added in Sharp APL at some point. And then once they did that, every other APL vendor followed them, which is not the case with a lot of things that happen at Sharp.

00:52:28 [KS]

A while to add what?

00:52:31 [ML]

Grading of things other than just lists. Ah. So this is actually, I think this is one of the, this was like the leading axis thing that happened before the leading axis model was even developed. Because it only makes sense to grade the rows of a matrix, right? It doesn't, like, grading the columns would be really weird. So you end up having grade which has to work along the first axis and there's no last axis version of it. Even before they decided that it was better to have most functions work on the leading axis.

00:53:07 [CH]

Did Dzaima post his video to YouTube or did he post it somewhere else?

00:53:11 [ML]

It is posted on YouTube. He had a link in the chat.

00:53:16 [CH]

Okay. We'll dig it up and put it in the show notes. I did a quick search for it and was --

00:53:22 [ML]

Yeah, because nobody's going to have time to watch it during the podcast.

00:53:26 [CH]

I meant more just I was trying to find it, but I wasn't sure if he posted it on Discord as, like, MP4 or something.

00:53:33 [ML]

No, I think it was on YouTube. His YouTube username is just Dzaima. So you can go there and find it. And it's, yeah, it's day 12 and the whole video is 10 minutes.

00:53:45 [CH]

Yeah, I tried to take a look at most of Dzaima's solutions because a lot of the times they're extremely elegant compared to what I came up with. And his solution is way, way more concise than what I did [chuckles]. I think I iterated on three different solutions trying to identify doing windowing tricks and then checking a quality of the garden value. And then finally landed on something that I thought was kind of cute and nice. Then I looked at what he did and I was like: "oh, my God; do I have some work to do on my array-fu or whatever you want to call it?" because he's doing something magical. And I've seen that trick now more than once that he's used where he uses the (I guess this is a tiny spoiler; it's not saying the whole solution because I don't even fully understand what he's doing) ... but it uses the different shifts to do something that I imagine is Game-of-Life-esque where you do that kind of shifting to get counts of the neighbors. The only time I've ever programmed that is in Game of Life; I've never actually used that as a technique outside of that [laughs].

00:54:56 [ML]

Yeah, I guess you could say sort of the idea is instead of you [starting] at one point and you check its neighbors (and you change your index and go to the next index over), you just take your whole grid of values and you shift them over. The corresponding values now for each position are the neighbors of the value that was there.

00:55:17 [JE]

Yeah, it's a parallel DFS. Because instead of representing a fringe with ... [sentence left incomplete]

00:55:22 [ML]

Well, depending on how you use it.

00:55:24 [JE]

Well, sure, but instead of representing a fringe with a queue or something, every ply gets unfolded at the same time.

00:55:36 [KS]

It's a question I've noticed as I'm solving a lot of these grid-type problems. Is that because array languages make it so easy to convert a 2D mask into an array of indices, either with the BQN indices function or APL and Uiua's "where"?

00:55:53 [ML]

Yeah, BQN's "indices" doesn't do 2D.

00:55:56 [CH]

Yeah, I was going to say, we'll follow up on that to ask why.

00:55:59 [ML]

Connors run into that, I know [chuckles].

00:56:05 [CH]

Yeah, I've got my own function called "i" that I borrowed from J. At first it was called "idxs", I love when precedence there. They called it "i."; I might as well just call it i, which when other people were reading my code, they had ... [sentence left incomplete]. But we'll come back to the design choice for that, but we'll let Kai finish.

00:56:18 [KS]

No, it's because Marshall's much more principled than I am [Conor and Kai laugh]. But if you have that right, you then have to ask yourself a question when you get a grid problem is: do I want to solve this on the grid itself? Do I just want to keep the grid and manipulate that in some way: rotate it, transpose it, [and such] things. Or do I want to get out the indices and do comparisons and filters and sorts and things with those indices? And there's been problems where I start one way and then I realize this isn't really working out and so I'll switch to another way. There's one, for example (it's not really a spoiler as soon as you see the problem) but there's one this year that's a soka bong type problem where you move the guy around and he pushes the boxes. I initially started doing that with indices and figuring out: "okay, if the guy's here and there's adjacent indices of where the boxes and the walls are, and then ... oh, this is too complicated". So then I just changed it to manipulations on the actual grid of: "okay, if he's here and he's here, then you just flip these this way". I don't know. It's an interesting question of how you can approach this sort of thing in an array language.

00:57:33 [JE]

Well, when it comes to the experience of trying to write a solution to one of these things quickly, consider the REPL experience. If you're working with grids as a matrix and you're using an array language that has a nice, pretty printing of matrices (which is not always the case for q and k [chuckles]) then I find it often makes it a lot easier to just visually see if I'm doing the right thing or if I'm off on a wild goose chase.

00:58:03 [ML]

Yeah. So I checked J's capital I dot, I think, just works with rank one, so it doesn't do multidimensional indices either. So I don't know where you got it from, Connor, but it wasn't J. It was probably APL.

00:58:18 [CH]

Really?

00:58:19 [RP]

Well, didn't used to be. What version did the high-rank "where" come in? Wasn't even that.

00:58:25 [ML]

It was probably there from the start.

00:58:28 [RP]

No, no.

00:58:30 [ML]

But "where" was only added in version 16, right?

00:58:33 [RP]

Oh, I see, right. From the time when we had the "where" primitive, we've had the 2D "where", but before then, everyone was using the replicate indices.

00:58:40 [ML]

So the issue with 1D versus 2D "where", for those who don't know, is [as follows]. So [in] the multidimensional case of "where", every result is an index, which is a list of numbers. But for the one-dimensional "where", you want each result to just be a single number. So the one-dimensional case of the multidimensional "where" would return a list of singleton lists. So they're not actually the same function, and when you put them together, you basically don't have a complete implementation of the multidimensional "where". I mean, it's not a problem that often in practice, but BQN is supposed to be as solid as possible, so that kind of edge case is something that for BQN I didn't think was right.

00:59:31 [RP]

Okay, this is to being consistent through different rank; applying to arrays of different rank.

00:59:37 [ML]

Yeah.

00:59:39 [RP]

And then technically, Dyalog's "where" isn't in that case.

00:59:42 [CH]

So you're saying it's because the return type on different ranks is different, and therefore that's not good?

00:59:49 [KS]

No, it's because in Uiua, at least, if you do "where" on a list, it gives you back a list, but if you do "where" on rank two ([or] rank three, anything higher) it's always going to give you back a 2D array. Always. And so there's, like, an inconsistency.

01:00:03 [ML]

Okay, so yours is that, but flattened.

01:00:06 [KS]

Yeah, but it's the same inconsistency, though. But I just decided that it's useful, so I don't really care if it's inconsistent.

01:00:15 [JE]

I can entirely see the practical argument for it, and also a deep "where" is just ... it's not that common in practical programming anyway.

01:00:24 [ML]

Yeah and also you might have a few different formats that you want it in, so [with] BQN's approach of, "implement it yourself", you know what format it's going to give you and you can implement it however makes sense for what you're doing. But, yeah, it's definitely less convenient not to have it.

01:00:42 [BT]

So is that what you did, Connor? You implemented what you thought J would be doing? [chuckles]

01:00:47 [CH]

Well, no, I was going to say: I think the reason I thought that J's had it is because I conflated the fact that "range" (I actually don't know; I think J still calls it iota). [06] Anyways, iota (range, whatever it's called) on a non-scalar gives you back the shaped ... [sentence left incomplete]. So if you give it (2 3), it's the equivalent of a (2 3) "reshape" on (iota 6) in APL. So I conflated the fact that J has more functionality, and then took that and brought it over to indices, which clearly I should not have done, and I was thinking of Dyalog APL's "where".

01:01:29 [RP]

The case study in the guy who learned all the array languages at once [Conor laughs].

01:01:34 [JE]

That's an interesting direction to generalize iota, because in k, that same type of overload becomes odometer.

01:01:43 [CH]

Odometer?

01:01:44 [KS]

The funny thing about that iota implementation is that I've only ever needed that for examples [everyone laughs].

01:01:50 [CH]

Yes

01:01:51 [ML]

Yeah, exactly. I think I brought that up on the ArrayCast before [chuckles].

01:01:56 [KS]

This is a very unprincipled decision: I put that on unshape [John agrees]. If you invert the shape of something, it gives you back your iota array of that shape.

01:02:05 [JE]

OK.

01:02:06 [CH]

Oh, That's neat. So it's still there.

01:02:10 [ML]

I just need a thing of that shape, whatever you can give me [Conor laughs].

01:02:14 [JE]

Array languages have a rich history of cheating with the design just a little bit in order to make a few cute examples work out very nicely. Like I'm pretty sure that J has a primitive that is specifically for solving Sudoku. It handles the box indices really neatly. Do you know what I'm talking about, Bob?

01:02:35 [BT]

I know Roger wrote one of the essays for Sudoku. He actually writes out how it works and it's not very long at all.

01:02:43 [JE]

Yeah, but the point is that there's a primitive that makes one of the fiddliest parts of a Sudoku solver much neater and I can't think of any other application for it [laughs].

01:02:54 [ML]

Yeah, I don't know which ... [sentence left incomplete]

01:02:56 [KS]

I mean, in language design, it can be very tempting.

01:02:59 [JE]

This is the code golf disease, right? You end up picking up primitives that are useful for exactly one problem.

01:03:05 [BT]

One of the things, when you're saying the integer (I think is actually what they call it in J): the multiple argument gives you the different shapes. One thing it's really useful for (and it's an example) but it really helps me when I'm trying to figure out what's happening within an array when I start to do transposes and different things like that. It's a really quick way to see [how] the ordering changes as I do those manipulations. So, if I'm kind of lost in the woods there, I can do a transpose, and then immediately I see: "oh, well, that's what it's doing". Because it gives me a physical look at something that I'm doing algebraically.

01:03:42 [CH]

I completely agree that the multidimensional range or iota, I have also never used except for demoing: "oh, look what this can do".

01:03:53 [RP]

I use it to check that boxing display is on when I start Dyalog [Conor and John laugh].

01:03:59 [CH]

That being said, the indices or "where" that works on two dimensions, I've now used, I don't know, six times, because of the 14 problems I've done in Advent of Code. More than half of them are these grid things and whether or not my solution is the correct or the best array approach, a lot of the times, the first thing I do is ... [sentence left incomplete]. Like there was one where it's identify the trails from zero to nine and you need to start at the trailheads that are zero. Okay, well, I'm going to go and find everything that's equal to zero, and that'll be my starting position so what do you need? You need the, quote, unquote x-y coordinates of every zero. If you have the 2D indices or 2D "where", it's where zero equals your grid.

01:04:46 [JE]

It's a pretty nice way of saying it, right?

01:04:48 [CH]

Yeah, it's very nice, minus the fact that mine is spelt "fun.i", because "fun" is the name of a library that contains the i. Although I guess maybe I should rename it now.

01:05:00 [ML]

That's a very fun way of spelling it.

01:05:02 [CH]

It's not very fun [laughs].

01:05:03 [BT]

I think one of the ways you can do that in Jay is using a sparse array.

I think one of the ways you can do that in J is using a sparse array. So you use it as a sparse array and then you can actually find out the non-sparse elements.

01:05:12 [ML]

Yeah, so you convert it to a sparse array and then you use the function that gives you the non-zero indices of a sparse array [chuckles].

01:05:20 [BT]

Yeah, I'm not saying it's ... [sentence left incomplete]

01:05:22 [KS]

Isn't that what a sparse array is? Just a hash map of indices?

01:05:26 [ML]

Yeah, indices to values but if you just want the indices, then you have the function that's designed for working [chuckles] with sparse arrays that gives you the indices. I think that's kind of roundabout to me.

01:05:39 [JE]

Well, this is where you get into the very interesting design space of languages where you have a dictionary as a primitive type. And in k-6, I remember Arthur Whitney talking a lot about trying to design the semantics of conforming so that dictionaries would just work in a sensible, arithmetic way for representing sparse vectors. And it leads to slightly different rules for addition and multiplication and so on. But if you only have atoms and arrays, then you don't even begin to explore that area.

01:06:20 [CH]

Yeah, the tools that you can reach for affect ... [sentence left incomplete]. Yeah, I've been thinking about that a lot.

01:06:24 [ML]

Yeah, well J does have this: a sparse array has like a zero value, so it's not necessarily zero.

01:06:36 [BT]

You can set it, yeah.

01:06:37 [ML]

Which I think makes ...

01:06:40 [JE]

It's a fill.

01:06:52 [ML]

... makes your representing a sparse vector with a dictionary thing easier because if you're going to multiply two sparse arrays, you know that you would have to check the sparse element. And if the sparse element is zero, then you know that times any actual value is zero. But if the sparse element is one, say, it doesn't change anything. And if the sparse element is two, then you actually have to multiply values by two.

01:07:08 [JE]

Yeah, the alternatives involve deciding on a per operator basis whether you should be taking the intersection of keys or the union of keys with a fill.

01:07:20 [ML]

Yeah, well, and this way you would still do that decision. You would just decide based on the operator and the sparse value.

01:07:29 [JE]

Well, it's analogous to doing a reduce with an explicit seed every time versus languages where we just define the behavior for the one array or zero array case in a favorable way.

01:07:45 [ML]

It's only the zero array that you have to do anything special for. Because [for] one array, just take that single element and ... [sentence left incomplete]

01:07:52 [KS]

I would like to say that for Advent of Code, anyway, Uiua does have hash maps, but I haven't reached for one yet.

01:08:03 [ML]

But so you have immutable hash maps, right?

01:08:06 [KS]

Depends what you mean by immutable. I mean, you can insert and remove.

01:08:09 [ML]

In the same sense that the arrays are immutable [chuckles].

01:08:12 [KS]

Yes, although you pop one off the stack, mutate it, and then push it back onto the stack, sort of.

01:08:17 [JE]

It's copy on write or not is the question, really.

01:08:22 [ML]

Yeah.

01:08:22 [KS]

Sure, sure.

01:08:23 [ML]

Yeah, so can you save the copy and have it change along with the changes that you're making?

01:08:30 [KS]

No

01:08:30 [ML]

So, yeah, in that sense it's kind of an important distinction, particularly because a lot of algorithms are going to work a lot better with mutable hash maps. It's like you want something that you're able to save. It's kind of hard to describe.

01:08:47 [KS]

I mean, what do you mean "save"?

01:08:48 [ML]

Yeah, if you just got one of them, maybe it doesn't matter. The thing that BQN does is actually really completely different and has different uses from the thing that k and Uiua do where a hash map is more like an array. So, BQN says: "no, it's not at all like an array; it's a kind of object that maintains this state along with it".

01:09:11 [KS]

Yeah, but there's a lot of these problems where if I were doing this in Rust, which is my main other language, I would have used hash maps so many times by now. But I found that just with things like deduplicate and classify and group and partition and just normal "index of" and select, and then finally Uiua's run length encoding separate into deduplications and contiguous counts. Using these tools together has replaced every single time I've needed a hash map in these problems, which I thought was interesting because when I was originally doing early design for the language, I wasn't sure what problems you could and couldn't solve if you did or didn't have hash maps as an easy thing to reach for.

01:10:08 [ML]

Yeah, I think the big thing about all these array primitives is obviously you can consider them to be kind of wrapping a hash map underneath. I don't think that's really the best way to think about it. You should think of them as optimizing a whole bunch of comparisons instead. The big difference between that and a persistent hash map is that they do all their lookups at once. So all the data you have is known at one point. The things that you really need a hash map for are where you want to do one lookup in the hash map and based on the result of that, you want to look up some other thing in the hash map.

01:10:51 [KS]

Yeah, yeah.

01:10:52 [ML]

So some stuff like, you know, memoized functions ... if you're walking along your graph and you want to remember the values you've seen before and things like that are well suited to hash maps. Although walking along a graph can often be replaced with ...

01:11:08 [JE]

Having graph traversal.

01:11:10 [ML]

... instead considering the graph as a whole.

01:11:11 [KS]

I mean, yeah, the path primitive has at least three hash maps in there [chuckles].

01:11:15 [ML]

Oh, yeah, yeah. So you have another primitive that does sequential stuff for you.

01:11:20 [KS]

Yeah.

01:11:20 [ML]

Yeah, the other thing about that is that passing all your data in at once to a primitive that sees all this data can look at it as a whole is much faster, because then this primitive can observe cases about the data. It can say: "oh, you've given me all small integers and therefore I don't even have to hash them". I can use a quick lookup method. It can also just use faster hash tables. Another thing in BQN that we do is our resizing policy. If you do have to use a hash table, it's based on how many elements you have left. So it won't resize if it's going to finish up very soon. Or if there are a ton of elements left, it thinks: "well I probably better resize now and not have to deal with the slowing down as my occupancy increases". So I think it's interesting that actually moving to a higher level of view there lets you communicate to your programming language much better what's actually needed. And so the language implementation can take advantage of that.

01:12:27 [KS]

It's kind of the story of array languages, right? I think you guys talked about it a few episodes ago.

01:12:31 [ML]

Yeah. It's like array languages are a better way of saying what you actually want instead of how to do it.

01:12:38 [KS]

Letting it choose the actual underlying algorithm. Yeah.

01:12:41 [JE]

The dream of fifth generation languages [07] was actually achieved in the late '60s. Who knew?

01:12:47 [ML]

How long is a language generation?

01:12:50 [KS]

I only even learned about the concept of a generation not that long ago.

01:12:55 [JE]

I mean, what's important is just that the fifth generation was the dream of Prolog.

01:13:01 [ML]

And so Prolog was maybe not the right way to do that.

01:13:04 [JE]

Death by a million cuts. Who knows what generation we'll be applying to the ... [sentence left incomplete]. Well, maybe we can just replace everything with LLM's epoch.

01:13:17 [ML]

They're kind of more like species than generations, anyway [everyone laughs].

01:13:24 [RP]

Have you got LLMs to write any Uiua code yet?

01:13:27 [KS]

No, I haven't.

01:13:28 [ML]

Well, we've successfully bludgeoned the hour mark.

01:13:31 [CH]

As per usual. Not even a special occurrence anymore. It's just the norm.

01:13:35 [KS]

Oh, one more thing I could say is that the Uiua community has had a lot of fun with certain problems because you can make GIFs really easily as output. They've been having a lot of fun animating some of the solutions. Especially like anything that involves a robot moving around the grid or the pathfinding or the garden plots ones. People make animations that color all the garden plots. That's been fun.

01:14:02 [RP]

I love that.

01:14:03 [KS]

That's actually how I tried looking for the Christmas tree thing at first. I turned it into, like, every thousand frames into a GIF. And I just showed a bunch of GIFs on my screen and tried to find the one that looked like a Christmas tree as it went by. They didn't work out.

01:14:19 [ML]

It was too fast?

01:14:20 [KS]

Yeah, the frame rate was too high.

01:14:23 [CH]

Well, this has been fun. I mean, the problem is ... well, what's the problem? There's no problem [Bob laughs].

01:14:31 [ML]

There's 25 of them [Conor laughs].

01:14:34 [BT]

50 if you count parts one and two.

01:14:38 [CH]

I was going to recommend to the listener to go try an Advent of Code problem out. But odds are there's not too many folks that haven't already.

01:14:49 [RP]

This audience, yeah.

01:14:50 [CH]

Yeah, like, in the past or this year already done that.

01:14:53 [ML]

Also we've spoiled you on a few of them [chuckles].

01:14:53 [CH]

I think we did a pretty good job not actually going into the full-blown solutions.

01:15:01 [RP]

I would struggle to listen to this episode and code it from purely the descriptions given [everyone laughs].

01:15:07 [CH]

And how many times have we been in a lecture or something where someone's describing how to do something and then you go back to your whatever dorm room in university or wherever you live, and then you're like: "oh, I know how to do this". And then you try to do it and you're like: "well, at the time I thought I understood the explanation of how to solve this and clearly I did not understand, comprehensively at least, in full, what was supposed to be done".

01:15:30 [JE]

The feeling of having the solution fades when met with reality.

01:15:36 [CH]

I don't know how many times (I can't even count on both hands) where I was like: "oh, yeah, I know how to do this". And then you go and try and do it in practice, and then you're like: "oh, I clearly did not know how to do this fully". I thought I did, but I did not. So you might have gotten some tips or some inspiration.

01:15:54 [RP]

Listener that's you [Rich and Conor laughs].

01:15:55 [CH]

Yeah, you might have gotten some tips or inspiration. And I know that we've mentioned them over the last two episodes (this one and the last one), if you are solving these and you would like them to be highlighted. I know all the different languages, whether it's Marshall's leaderboard versus the APL wiki has some resources that point to GitHub repos and YouTube videos. If you make YouTube videos, let us know. We're happy to share them. I discovered that Dzaima has not just one. I found his channel, finally, and he has two. He has one for day one as well that only took two minutes. And I think I did know of ... [sentence left incomplete]. Was it Isaac Wooden was his name, Rich, that you mentioned?

01:16:39 [RP]

Yeah, he's Yernab on the social medias.

01:16:42 [CH]

Yeah, I just didn't recognize the name, but when I found the YouTube channel, I did recognize the handle, Yernab. So, I will link those, but if you're listening and you have solutions or content you'd like to share, even a blog post. Whatever it is, feel free to let us know, and we're happy to disseminate that. Any final thoughts before we throw this over to Bob from the esteemed guests?

01:17:07 [RP]

We've got eight days.

01:17:10 [CH]

Well, by the time folks are listening to this, it'll be only four or five days left.

01:17:16 [RP]

So hurry up!

01:17:18 [BT]

[laughs] Get to work!

01:17:22 [CH]

[Everyone laughs] Very authoritative there.

01:17:23 [RP]

Is that one on the 25th or only the 24th?

01:17:26 [KS]

There's a 25th one.

01:17:29 [ML]

It's only one part, right?

01:17:31 [KS]

Oh, is it? I never got that far.

01:17:33 [RP]

The kids presents can wait. You need to solve the problems! You must!

01:17:38 [JE]

I think, historically, it's usually something that's trivially easy if you've solved all the other problems.

01:17:44 [CH]

Mm. I see.

01:17:45 [RP]

And if you've been a naughty boy or girl, it's very hard [everyone laughs].

01:17:47 [CH]

All right. Well, with that, we'll throw it over to Bob, and he can tell us where you can reach us at.

01:17:55 [BT]

You can reach us at contact@arraycast.com [08] for your comments or your questions or anything you'd like to contribute to us and directions we should go or things we should talk about. And I guess I'll use this as a preview of coming attractions. We're actually going to have John on the next episode as well. We'll be talking about Decker, which is his HyperCard version and game machine combination of all the amazing things that Decker can do. And I guess I should preface that with the same way we ended up talking about something completely different than Advent of Code for the first 20 minutes of this episode [chuckles]: you never know where we're going to end up, but the idea is we're going to talk to John about Decker.

01:18:40 [CH]

Yeah. And speaking of our esteemed guests, thank you both for coming on. I guess we can't invite John back on for a third time without saying that we're also going to have Kai back on for a third time. But I think that goes without saying. We have him on (I can't remember what the cadence is) but there's always new Uiua stuff coming out. And so I think we'll have both of these. Only one of them is scheduled at this point in time.

01:19:01 [BT]

And to be fair, we probably should give John and Kai a chance right now to promo whatever they would like so people can keep up with what they're doing.

01:19:08 [CH]

Oh, yeah. Well, first we'll go to John and then we'll go to Kai. Stuff you want to plug, if anything, now's your opportunity.

01:19:16 [JE]

Well, sure. I think by the time this episode comes out, there will be a limited time left for it. But in the month of December, there is a thing jam for Decker. Not exactly a game jam, because you can make whatever you want, whether it's a tool or a toy or a zine. So if you search for "Deck-Month 2" on https://itch.io, you can find it. And we'll also have a link in the show notes.

01:19:45 [CH]

And Kai?

01:19:47 [KS]

Yeah, just check out Uiua. We've been having a lot of fun doing Advent of Code. By the time this episode comes out, version 0.14 should be released.

01:19:55 [BT]

And I can attest, Uiua is an amazingly active community. I lurk there but I can barely keep up with all the posts. It's really fascinating to see the way that community has evolved and the things people are doing. And it's actually not a bad place to hang out at all. Really nice people there.

01:20:15 [CH]

Yeah. All right. Once again, thank you both for coming on. We're looking forward to speaking to both of you in the future. And with that, we will say: happy array programming!

01:20:22 [everyone]

Happy Array Programming!

01:20:24 [CH]

Maybe we should have said something ... holiday.

[music]