Conor

If the listener is wondering, hmm, I wonder if his wife is going to let him do this when they have a two-week year old that is crying a lot. The answer is no. My hobby is going to be I would say very sadly, but not sadly, because we're starting a family, and that, to be honest, is much more exciting. Like, odds are I would never have this hobby if I didn't make it to the age of 35 with no children, no dependents, and no serious responsibilities. There was an Instagram reel one time that I saw like a few years ago that said, if you're born in 1990, you're doing one of the following three things. One, getting married, two, starting a family, or three, running a marathon. Welcome to ADSP the podcast, episode 295, recorded on July 13th, 2026. My name is Connor, and today with my co-host Bryce, we chat about city strides, graph algorithms, GPT 5.6 soul, and more.

Bryce

It's exciting times. Okay, okay, all right. So first thing, so listen, I I despite me being very AI forward, I'm still like an old man. And by that I mean like there's some places where I'm using AI everywhere, but there's a lot of other places where I feel like I see other people on the internet using AI to solve to solve parts of their life in ways that I just I've just been too stubborn or haven't been able to get the momentum to like adopt. Like I haven't been using like an AI personal assistant for anything. Like I don't have it like reading my emails or writing my emails. I don't have it like managing my to-do list, etc. And I I mostly have just been using it for coding in in kind of like a dumb way. Like I don't have I use all these like persistent, uh I use all these ephemeral agents that like run in VMs. I don't like build up like a deep skill library, I don't build up a deep memory library. Like I'm I feel like I'm using it in a very different way than other people. But I kind of I've kind of like recognize I've started to recognize that more and more of my time is being or AI has accelerated so much of parts of my you know work, you know, like it's accelerated my output in so many places, like the places where I used to not think about wasting time, I'm now like crap. Like I just spent three hours like going through my email inbox and think about all the stuff I could have done in that time. And uh the thing that I I started using last week was computer use and like browser use. And the reason I started using it is kind of interesting. So if you go to Chat GPT or Claude Code or uh Codecs, like the CLI, or you just go to Chat GPT and you tell it like, hey, go get me prices for this specific flight. Like I want to fly from New York to Toronto on this date. Go get me prices for it. But what I want it to do is I want it to like go to Google Flights or Expedia or any of the tools that like I use to go and price out flights. Or like maybe I'll ask it for hotels. And again, I have like you know, some set of tools I want it to go and use. But what I've found is because it doesn't have access to a lot of stuff. And I think what happens is if you ask it to go to like flight.google.com or like on some sites, some sites either need a login to get useful information. Another good example of this is if you ask it to look up a tweet. Sometimes if somebody posts into something, instead of me trying to figure out what they're like alluding to in their post, I'll just I'll just like send a link of chat GPT. But I don't I don't actually send a link anymore because if I give it a link to Twitter, it can't actually see the tweet in a lot of cases. I'll send it a screen chat. But um, it can't actually pull the data there. And I don't know if it's okay. When it goes to that site, like when I think automated system goes to a website, there's some protocol where it has to the website, like, hey, you know, I'm a robot and can I come look at your site? Like robots in a txt thing. And uh there's a bunch of sites that are like, no, go away. So it's either that or it's the login thing. And so there's this set of tags that I want it to be able to do that it just can't do because it doesn't have it doesn't have the access that it needs. And then sometimes there's like a website I want it to use where like it doesn't have an API, you know, like it's something where it's not easy to interact with, and that's specifically why I want the agent to deal with it, because like it would require a million clicks on this annoying website for me to go and do something. Like, oh, I want to go apply for some visa for some country or something where you know websites for visas are notoriously like awful to interact with. And so there's this thing called like computer use, where basically instead of like going through an API or even just like looking at the HTML of the website, it interacts with your browser or some app on your computer just like the way the same way you would with like point and click, you know, like it controls the mouse. And it really saddens me that this is like this has to be one of the most inefficient ways for an AI to interact with something. Like it goes to the website and I literally watch it going through and like entering stuff into form fields and like clicking buttons and whatnot. And it's just gotta be so like wildly inefficient, but it does kind of get the job done. Like I had it automate a lot of the like flight tracking and like flight search and award like redemption tracking stuff that I do. And I was like pretty happy with it. It was funny though to see like the AI complaining about how slow the website was and sort of like sort of validated for me. Like it took it like five hours to create like 20 flights worth of tracking on this one website. And I'm like, crap, did I used to spend five hours doing this myself? Anyway, I don't know if you've started using any of this, but for me at least it's been it's been very powerful.

Conor

I haven't done any computer use stuff, but like I'll give you an I'll give you an example.

Bryce

I bet you that there is something related to running that you do that involves using some website that has a not great UI that doesn't have like an easy API to access that you probably interact with semi-regularly, that you could probably automate with computer use.

Conor

Well, it's funny that you guessed that because I was I was trying to figure out how to articulate what I've been doing with my running. But the problem is that like I have this like multi-headed hydra of different stuff that I mean we uh we've talked about this actually. I'm pretty sure we have. Let me check on the website ADSP, an episode that had the word uh did it have city stride? Yeah, it had episode 149, 2023, September 29th, CityStrides.com, graph algorithms, and more. And we never actually talked about in depth how to solve it. I just like threw the problem out there. And I wonder if you go to the GitHub discussion. I know that we got a couple comments, and remind me by at the end of this 30-minute discussion to talk about GitHub, GitHub discussion things again. Anyway, so we I I have mentioned that this very tricky problem that I tried to solve at one point. So I mean I can explain it a bit again, but let's take a step back. For those of you that recall, one of my biggest things that I spend time on is a website called CityStrides.com. It ranks or it tracks, you upload your Strava or you connect your Garmin or Strava, and it tracks all the routes, the GPX files that you run, and then it it figures out how many streets that you've completed. And the tricky thing about this is you don't actually need to run the full length of the street, you just need to run over the nodes that define the street. So some streets only have two nodes, a start and an end, because they're very short and they're straight. Other streets are very, very long and they're windy, so you need a bunch more nodes. And so my my hobby is going and doing this. I don't I'm in 2023. I don't know, you'd have to go back and listen to that episode. I was probably in the top a hundred, top, you know, a couple hundred. You do know this because you actually referred to it when we were walking in Venice and I was collecting the nodes, but I have become like uh obsessed. Like it to say what I can't remember who said it once that I don't have passions, I have obsessions. But like if I was, you know, focused on city strides and collecting nodes back in June, I am now like a full-blown like addict. I have gone and written two, well, technically I wrote one Python graph algorithm to generate like optimal routes, and I've become like an open street map. I wouldn't say expert, but there's like an equivalent, an open source equivalent of Python.

Bryce

We're gonna talk about that Python script in a little bit.

Conor

Yeah. Well, I wrote it initially in Python, and then I was like, this is too slow, I need to speed it up. Let's convert it to you know Rust, why not? And I just got ChatGPT to do it, and it worked amazing, man. Nice. And uh, anyways, my point is I've become uh very much obsessed, and I'm going to be I said this um did I say I said this on my other podcast as well, that I'm currently uh ranked, you know, I think at the time on my other podcast, I was ranked 116th, I'm now ranked 114th. I will be ranked number one in my lifetime, probably within the next few years. I'm now ranked 13th in the world, soon to be number one in like a decade, and I spend like, especially right now, because it's two months before Shima's due date, I'm trying to complete the entirety of Toronto before she gives birth. Because once my son is here, right now the hobby consists of me, it used to be just going for a run, you know, running some weird route and then getting some streets, but I have completed every single street within like a seven-kilometer radius of where I live. And so now what I have to do is hop in the car, you know, drive anywhere from 15 to 20 minutes, sometimes more if it's traffic's bad on like a weekend, and then I go park the car in some parking lot of a grocery store. I start my run from there, end my run, and then drive back home. And if the listener is wondering, hmm, I wonder if his wife is gonna let him do this when they have a two-week year old that is crying a lot. The answer is no. My hobby is gonna be I would say very sadly, but not sadly, because we're starting a family, and that, to be honest, is much more exciting. Like, odds are I would never have this hobby if I didn't make it to the age of 35 with no children, no dependents, and no serious responsibilities. There was an Instagram reel one time that I saw like a few years ago that said, if you're born in 1990, you're you're doing one of the following three things: one, getting married, two, starting a family, or three, running a marathon. And the the exact hobby that takes a lot of time, you know, it doesn't actually need to be a marathon, but I thought it like it nailed me so hard because at the time I wasn't getting married or having kids. Uh I was spending a lot of time running though. And anyways, the point being is that I'm trying to finish Toronto, which has like 10,318 streets, I think, and I'm at about eight and a half thousand. And one of the websites I actually have, it tracks the top 50 people and like has anybody else completed Toronto? Yes, three other people. In fact, very tragically, there was a man that was raising money for, I believe, a music foundation, and he was, I'm not sure if he was in his 70s or 80s, but he had cancer and he was doing it to like raise awareness, uh, which really puts like me doing it to shame because I'm not trying to raise awareness for anything. And he, I think, just passed away in the last month. And you know, on a happy happy note, he he completed Toronto just like a month or two before he passed away. And anyway, so he is one of three people. Carlo, let me actually just get his name because we should shout him out. And I'll leave a link if you want to go and leave a donation because he had a page for it. But you actually let me share my screen because I'm probably gonna But yeah, so this is City Strides, and the most the number one, or I guess the second person in Toronto right now, because every once in a while, how do they define Toronto here?

Bryce

I see a blue line around.

Conor

Yeah, so it is like the it's it's the municipality boundary defined by like different, you know, latitude and longitudes or whatever that are specified, I'm sure, in some legal document. And so, yeah, but actually the first City Strider so actually I lied, four people have finished it, and for some reason one of them is private. Carlo De Lorenzi was the individual that just passed away recently and was raising money. The other two are named Matthew and Richard. I'm good friends with Brian, who's ranked in seventh. I just passed him, I'm now ranked sixth, and probably in a week or two I'll pass Steve, who's ranked in fifth.

Bryce

But you have more total streets than all of these people. Interesting.

Conor

Yeah, yeah. So I'm definitely like the number one Canadian city strider in the world. But that's because like I spend a lot of time, like it's basically every time, if I'm not training for like a race, and even if I am training for a race, like I ran a marathon when I was in Ireland, it did not go well. Arguably a part of that is that even when I'm trying to do like a workout, which involves like one kilometer repeats five times, I go in city stride while I do that. So like I'm in the middle of trying to run like a kilometer really fast, and I've got my phone in my hand and I'm looking, I gotta take a left-hand turn here. It's probably I should try and do one at a time. Either go ahead.

Bryce

So I notice some streets here that look more like highways. Is that is is there like do they exclude from city streets streets that are like not safe for a pedestrian to go on?

Conor

Yes. I won't go into the details, but yeah, highways and like high traffic, unsafe roads are always excluded.

Bryce

That being said, like when I was in the Kingston Road on the far right there that Oh, King Kingston Road is is not a highway, so this is a road. Okay, that's you just you just haven't gotten over there.

Conor

Yeah, yeah. That's the like part of Scarborough. I'm like 75% done Scarborough right now, which is a embedded like region within Toronto. So technically Toronto is composed of old Toronto, which is downtown, York, East York, North York, Etobicoke, and Scarborough. And so I'm done everything but Etobicoke and Scarborough. And so if you click on Kingston Road, because you can see here that it actually says like there's a Kingston Road for Scarborough and there's a Kingston Road for Toronto. And the one in Toronto has more nodes because it's a superset. And if you click on this, it'll show you if I get rid of this, all of the dark purple ones are the nodes that I've run, and the red ones aren't, and it says that I'm 38.22% done this road. And a very important trick that comes into the algorithm that I'll show in a little bit is that you only need to complete 90% of the nodes in order for it to be considered done. And and Kingston is a special road in that it's 33 kilometers long. You're never running that all at once, and so it just happens slowly over time. But most streets are anywhere from you know two nodes to 40 nodes. And so if you have a 40 node street and one of the nodes is like a couple hundred meters away because it's just at the end of a long, straight part of that road, you can actually skip that, you know, 40th node and you'll still get completion for it.

Bryce

Hang on, hang on. That's cheating. You gotta you have to get all of the actual nodes in Toronto before the basics.

Conor

So that is that is what City Stride purists say. And there's a there's a mode called hardcore mode that you can click that requires 100%. I am not hardcore. I am just trying to climb this leaderboard as fast as possible, which means that I'm not trying to run the full length of these streets, which was covered in episode 149. So yeah, I'm trying to finish Toronto before the baby comes. And I I did actually have like a route mapping. If we go to and so actually, well, I can show you what what do I want to show you first? This is the website that shows like, you know, the top 50. So there I am. And it's got a separate tab that shows like the completion of the sub-municipalities within Toronto, and then just some other random cities that I run in.

Bryce

You've done all you've you've completed New York?

Conor

North York, not New York.

Bryce

Oh, okay. I okay I understand.

Conor

Yeah, North York. It's like the northern part of Toronto. And you can see here, like I even have this little projection. So if I run five times a week, you know, one of the estimates say I'll finish September 3rd, the other one says October 1st. And you can see that like in the last little bit, I've really started to go crazy. Like when I got back from, if I zoom in a little bit here, when I got back from Ireland, yeah, basically I've been running every single day city striding. Uh and if I if I kick it up to you know six runs a week, then it says September 3rd versus September 18th. The due date is September 15th. So, you know, it it depends though. Uh, are we gonna make it? Maybe, maybe not. Stay tuned. And uh the thing that I was doing over the weekend was trying to basically create a better version of the so if we go to City Strides, except I don't have an old version of this because I did I did get rid of it. Anyways, it was uh it was a very bad route planner, but it wouldn't like start and end at the same spot, and it just had a bunch of issues. And anyways, so I just basically over the weekend was talking to AI and saying, you know, these are these are my criteria. There's two different routes you want, right? If you're visiting, you know, Italy, Rome, and you're only there for a couple days, you don't want to complete a whole section. You just want the maximum number of streets possible, which means targeting the shortest streets, skipping the long streets, etc. But if you're trying to complete 100% of the city, you want like a dense, you know, and and one of the biggest problems with these automatic route generations is like stranded streets. You don't want to create a route that strands one or two streets that are gonna require running an extra two or three kilometers because you left them behind. Anyways, I won't go into all the details because the the viewer or the listener can't can't see this.

Bryce

But now like the idea of- That stranded street thing is some sort of sort of graph property.

Conor

Yeah, like that, and that's the thing, is as I was having conversations over the weekend, like I basically just kept on verbally explaining like heuristics it needed to add, where like, you know, you'll see here when I I've zoomed into a road called Wonderland Drive, and like at one point it was generating this route that not only would run the full length of Wonderland Drive once, but it would double back. And the point being is there's no nodes in between basically like the start and the end of the street. And so, like, not only do you not want to run it twice, you don't even want to run it once. You want to just get over the start and the end and like add that to your route. And so I would explain this heuristic and it would be like, oh yeah, that makes sense, that makes sense. And uh and then there's a bunch of other heuristics like the you know, minimizing the stranded streets because it completely defeats the purpose if you isolate two or three streets. Like it's basically like that's a non-starter, like it's it's it's uh a thing it has to get right. Anyway, so now basically these show you all like the nodes that I have to, you know, collect so far. I choose the distance, I go build closed loop, and it just starts doing it. And that's the thing. I don't fully understand what it's doing right now. And you can see whenever there's yellow nodes, those are ones that'll be completed basically by by hitting 90% of the nodes. And it's not perfect yet. You can see here that it it kind of missed this cul-de-sac. Like, if you're running by a cul-de-sac that has no other, like that's the definition of a cul-de-sac, it just has one entrance, it should definitely get this. So it's not perfect yet, but honestly, it's pretty good. And so, anyways, this is a long-winded response to your like, there's probably something you spend a lot of time every single day. Basically, I go for a run, I get back from my run, I run a bunch of scripts that like update my websites and rankings and whatnot, and then I'll spend, you know, 20 to 30 minutes basically designing my run for the next day based on you know a start and end location, and just basically manually creating, like on the City Strides website, they have a button for creating a route. And so you can just go here manually and start like uh once you see the nodes, you just manually click around, and this will give you uh basically a GPX file. Some people load it into their garments, but I basically just like have the website open on my phone while I'm running around. And now I'm gonna save myself like uh 30 minutes a day. And to be honest, I'm pretty sure I can get this to the point that it is not just saving me time, but like 25% better than any manual route that I can just kind of eyeball, right? Because I can't constantly be clicking on streets checking how many nodes does this have, like what's my current completion, yada yada yada. But like this doesn't involve any computer use. This is still, and the funny thing is, is I was using cursor at first because I still, when I'm building like software like this and I'm not doing auto research, I still prefer cursor, but I found and we're we're allowed to talk about 5.6 soul now, right?

SPEAKER_02

Yeah, yeah, we can, yeah.

Conor

Yeah, yeah. So 5.6 soul is so much better than Opus 4.8, in my opinion. Like, I I basically had both Opus 4.8 and 5.6 soul like working on this problem, and Opus 4.8 just kept on like making really silly I shouldn't say silly mistakes. It was doing okay, but then the insights that I saw GPT 5.6 soul making, just by working and iterating it on itself, it'd be like, oh, actually, you know, really I should like do this kind of heuristic, and it set up some like test engine like based on a couple roots, and it made sure that like every single time it added another heuristic, it wasn't regressing on some other heuristic that it had set up earlier. Like it did some sophisticated stuff, and uh I kind of just gave up on Opus 4.8 at some point. And also, too, like I just asked for a visualization from both of them, and the one that Opus 4.8 came up with was like a plotly refreshing, super, super slow thing. I don't even know what this is from GPT 5.6. It's using leaflet, like I think they were using the same stuff, but this one was just so much better from like a design point of view. I asked it to change the colors and stuff, but anyways, I've been kind of rambling nonstop. I will I will stop talking so. So we're doing the same thing, just not computer use on my part.

Bryce

So this problem of like visiting all the nodes, you know, once without without backtracking. I actually think it well, so for okay. Going back to my days in college the second time around and in you know getting a math degree, I recall there being something called a Hamiltonian path, which is where you visit every node once, or maybe it's a path that goes over Yeah, like over every vertex once, I think. I I wonder though whether that's I think that's not exactly your problem, because I think that your problem you you care you care less about like visiting the same node twice is fine. You care more about the edges. You don't want to go down an edge multiple times, because that would be wasted time. Like if you if you happen to come back to a node again, like that's fine. But that's the thing.

Conor

Yeah, you can eat you can even see here that like on this road, Mountland Drive, like it is identified that like the gap to these remaining five nodes, which it doesn't need because it's got enough nodes, like like at one point it was always completing this and like making a loop, but it's made like it at after having enough conversations about it, about the heuristic that it needed, it's finally figured out that at certain times doing a 180-degree turn and backtracking is the optimal thing you want to do, but like you always need to be assessing like is this the time? And like even over here, technically, if I was doing this, I would never like backtrack here because the trade-off, like you're only saving a little bit of running by backtracking here, but because it's just like it's down done some optimal calculation where it says, actually, I should do a 180-degree turn here and backtrack instead of like completing this loop because it is gonna save me, even if it's a small amount of distance, it's still a saving, right? But like this is not like a simple thing to like program, especially when you think about how many nodes you're looking at, and uh and yeah, anyways, I interrupted you.

Bryce

I think that I I know that the Hamilton path problem is an NP. Yeah, the Hamiltonian path problem, although there is a Hamilton near Toronto, so maybe you have a Hamiltonian path problem in Hamilton. But I believe the Hamiltonian path problem is an NP complete problem, and I think it's in the same family of problems as like traveling salesmen. But I I'm I I looked it up. The visiting all the edges of a graft exactly once is is called an Eulerian path or an Eulerian circuit. And I think there's a formulation of this problem called the China or I think it's sometimes also known as the Chinese postman problem, according to this. And I I wonder what have you when you were looking at it over the weekend, did you come across that or any of the graph theory behind this?

Conor

I I mean I did no research on my own. It's just been talking with the models and nobody.

Bryce

Didn't we once talk about the Seven Bridges of Coinsberg problem?

Conor

Yeah, yeah, that might have let's actually check.

Bryce

The so the if we go back to When I go to the when I go to the Eulerian Path Wikipedia page, uh one of the first things it mentions is that they were they were first discussed by Euler while solving the famous Seven Bridges of Coinsberg problem.

Conor

Yeah, I was gonna say the graph algorithms and seven bridges, I'm not sure if this came up because of City Strides. So City Strides isn't mentioned. I think you were just traveling in Europe and you had come across some algorithm book. Yeah. And in the algorithm book, it was talking about graph algorithms. So definitely like these have come up, but I like in in studying the traces or studying, in reading the traces of these models, admittedly, they're not telling you everything they're thinking about. It hasn't come up because I think this is like substantially different. This isn't like visiting everything once. Like, it's totally fine to visit a node twice. It's totally fine to backtrack if that's the optimal thing. Like the real goal here is you're just trying to like complete a section without leaving any roads behind, doing it optimally in terms of like you don't need to run over everything, every single uh node, and like you don't like really a a kind of I'm sure a heuristic that's built in is that anytime you're traversing a road and the distance since the last node that you run over is like increasing, that's a bad sign because it means that like you're probably unnecessarily running like a path that you don't need to run. And sometimes it definitely is gonna happen, but like, you know, like when it's when it's over here, which the listener can't see, but like it's decided it wants to backtrack here, and then you know, in order to get to the next closest node that it hasn't uh seen, it needs to run a bit of distance where there are no nodes.

Bryce

But yeah, so so if I recall correctly, or l not all graphs have an Eulerian path, and I believe that there's a relationship between whether the graph, like whether all of the vertices in the graph belong to a single connected component or slash strongly connected component. I think that it might be the case that it it's only graphs in which all the vertices belong to a sing to like to one connected component have an Eulerian path, by which I mean a path where you only have to visit every vertex once. And so yeah, like you're right that the problem that you're trying to solve is not like define the Eulerian path because it may not exist. It's like some form of it of like, you know, find the the closest thing to the Eulerian path with like the least amount of it's some form of like shortest path problem, probably. It's some c it's certainly some class of optimization problem for sure.

Conor

Microphone in use. Alright, they both seem to be picking this up. What do you call a part of a graph that is represents like a street? So a street has nodes, and those nodes have edges, and then on a map, you've got a bunch of streets. So what do you call like a single street within a map that's made up of a bunch of streets? Because that's basically what we we want. It's called a path, an order of sequence of nodes connected by edges representing one street through the larger road network graph path, the graph theory term, polyline. So yeah, basically when you have a graph that consists of paths, we want an algorithm. Actually, so let's let's see what chat GPT. I'm on medium right now on just like the web thing. So is there a name for the type of algorithm that solves wanting to complete a certain percentage of every path within a graph? And it doesn't matter how many times you visit edges and nodes, but you want that path to be as short as possible. What do you think it's gonna say? You think it's gonna say one of your Eulerian or Hamiltonian things?

Bryce

Actually, I I think that Chinese postman problem.

Conor

It sounds like a variant of the Chinese post-why is he Chinese?

Bryce

So so so the Eulerian path problem it specifically uh wants like to not visit a vertex more than once, which I don't think you actually care about, because what you care about, like if you have to if it you would probably prefer to visit sorry, not vertex, I meant edge. You would prefer to repeat a short street multiple times if it was shorter than you know having to go on a really long street. Like you you you care about you care about a shortest like distance. So the number of times that you repeat something maybe isn't as important.

Conor

Yeah, I mean in general, when you see some street being double backed on or like triple backed on, which is something that like I've never I don't think ever in a manually created street am I like tripling back on a street. Doubling a lot of the times, whenever I'm spinning around and changing direction, like that happens multiple times a run. But uh so in general you're trying to avoid that when it's not necessary for the optimal or shortest path. But yeah, in general, it's like a good rule of thumb. Like if you find yourself constantly trick retracing your steps when it's not down like a corridor or a cul-de-sac, like that's cause for concern.

Bryce

So the the connected component things I think is just a property of whether all of the nodes in the graph are reachable from each other, which makes sense. If you if if some of the nodes are not reachable from other nodes, then obviously like no no such path where you visit all of them uniquely ones exists. But I think there's also some other property, prop like I think there's some properties related to how many, like the degree of each node, like how many points into and out of it there are. Like if you have one node that only has one edge out of it, then and it's like in the middle of your graph, then it's gonna be very hard to uniquely visit, like you can't uniquely visit that node without taking that edge twice.

Conor

Right, yeah. I mean the the interesting thing here too is that like you don't actually care about any edge. At the end of the day, all you care about is nodes. The edges are incidental. And uh yeah, it is.

Bryce

You do care, you care about so so the type of graph that you have here is actually it's a form of what I believe is called a weighted graph. And it's weighted because the cost of each edge is not the same, right? You know, some edges might be really long and some might be really short.

Conor

Yeah.

Bryce

Like it's a it's a it's an undirected, you know, weighted, uh, weighted graph. Interesting. Yeah, I mean it's probably like I I I suspect strongly this is one of those sorts of problems that like one of these classes of optimization problems that's like in the NP complete family is very computationally intensive to to solve. But you know what? GPU is very good at graph problems. Have you like looked at co-opt? You should you probably co-opt probably has like algorithms for this.

Conor

Maybe. Actually, should we just ask? Should we ask? Can you explain roughly your route planning?

Bryce

Isn't this just traveling salesman?

Conor

Well, so yeah, I I mean at one point I asked ChatGPT and it it mentioned that the quota traveling salesman problem is finding the shortest route that visits at least a required number or percentage of nodes. But the thing is, is, and I I'm sure there are like graph theory experts out there that work for Google and on Google Maps like routing software, that they have a whole set of vocabulary, but like this is a very special graph in that it's not just like traveling salesman with a bunch of nodes and like some random edges, like because you only need 90%. Well, no, it's it's not that I I I yes I only need 90%, but it's I only need 90% of each path, which is typically falls into a set of types of roads. Like there's a cul-de-sac where there's only one entrance and exit, and then there's a corridor, like a street, which has like a start and an end. And like when so when you hit a cul-de-sac, like you know you have to do it.

Bryce

That sounds like a c so I remember from school that there was this idea of like graph coloring, and I wonder whether that's maybe applicable here, because you you you essentially you have different classes of nodes, or maybe the nodes are in different subgraphs is the way to think about it, right? Because like you have some property that you want to be true for each each street, you kind of want to model, and I I recall when we talked about this last time that you you talked about like modeling each street separately, but like each each street is like its own graph, or you want you want some property to hold across each street that you hit some some required number of nodes.

Conor

Yeah, I mean I yeah, I don't really know. Like it because that's the thing, is if each street is really its own graph, like it's actually quite a simple graph, right? It's just like a straight line. Or like even if it's not straight, it's curved, but for all tens and purposes, you've just got like a linked list. You know, very rarely do streets like fork and then like rejoin, or I guess if it's a cul-de-sac, it might look like a lasso, but like the graphs, like the paths that form up the larger graph are actually quite simple. The complicated thing is that like if you can complete a path by just completing four other paths that happen to like wind through, like if you think of you just have a a matrix, like you know, five streets by five streets, so you've got first through fifth avenue and first through fifth street, and they all are perpendicular to each other, like the the streets and the avenues, the best thing to do is to ignore either the streets or the avenues and just do like a zigzag back and forth. And then like you're you're technically running the length of the avenues and ignoring the streets, but by the time you've completed running the avenues, incidentally you've completed the streets. So, like, how do you represent that like from a graph theory point of view? Because if you only look at each path without respect to like the larger graph that it's a part of, you know, it's you're gonna completely do something that's not like doing the snake pattern. You know, like it's so that's the thing, is like you want to see the whole graph, or at least like a subsection that you're focused on at the moment. And so, uh, anyways, I asked I asked uh codex to explain what it what it's been doing, and he said roughly it's a greedy graph search optimizer. So it's not it's not actually doing anything fancy. It builds a walkable graph from all the relevant open street map, roads, sidewalks, path, bridges, and for every street, it calculates how many additional nodes are needed to reach the 90% threshold, accounting for nodes that have already been completed. Starting from your selected location, it repeatedly scores nearby streets. There's two different algorithms. Maximum looks for short, inexpensive streets, and uh the total completion favors partially open streets and compact groups while penalizing isolated leftovers and stranded pockets. Shortest path searches connect those targets with extra costs for reusing the same road corridor, traveling long distances without city stride nodes, edges that produce no new progress, and choices that risk leaving insufficient distance to return home. That's the weakest part of this algorithm right now, that basically once it hits like the 80% mark, it just like finds the shortest path home.

Bryce

Which it's still pretty good result, even with that like glaring flaw, which maybe we can talk about in a sec, because I Th there's the question of what of like what is the graph theory and the uh the optimal uh what is the graph theory problem that you're handling here, and then like what is the computationally most reasonable way to approach this? And the thing that that you're just that your agent's describing here, you know, is is probably in the class of things that are like most reasonable. Because like m maybe, maybe the optimal way to solve this problem is like some ridiculously computationally intensive thing, you know, like some some way to to estimate some solution to some NP, you know, hard problem. And you you don't need you don't need the optimal solution. You need like a reasonably good solution, you know, within the the bounds of how much compute you're willing to spend on this, right? Like you wouldn't let's say that like the the the way to solve this like like to actually find the optimal route existed, but like required you to run on like you know, you know, a cluster of GPUs for like you know eight days or something. Like that would not would obviously not be the correct answer. When I when I'm searching it, it's it's mentioning what I searched, what I asked was I have a graph consisting of many labeled subgraphs. I want the shortest path that goes through 90% of the vertices of each subgraph. What is this problem called? And it says it's uh like the quota constrained general generalized traveling salesman path problem, also described as the group Steiner path problem with per group quotas. I've never heard of the generalized traveling salesman problem. I don't know what that what that means relative to the tr the traveling salesman problem, but maybe it's the generalized part is just that it generalizes the uh the cost function.

SPEAKER_02

Generalized traveling salesman. Generalized traveling salesman problem.

Bryce

Generalized traveling salesman problem where the graph nodes are partitioned into discrete subsets or clusters. The objective is to find the shortest possible route that visits exactly one node from each cluster before returning to the start. Yeah, so it's something in some some some class of traveling salesman like problem. Though the specific formulation that you need sounds like it's a little bit unique.

Conor

Yeah, I honestly I feel like the greedy algorithm that it has now is like 90% of what I need. It just needs like actually, does this work right now? Is it uh so if we chose if we choose some news new location, so if let's go, let's go all the way over uh all the way over here. And so actually I I've tried this one a couple times. So like if if you're gonna start in this corner, it's clearly got like one entrance, it's got two entrances. What the algorithm's gonna do is it's gonna complete this little triangle first, but really what I would do is, you know, I would I would go north, do a bunch of stuff up here, and then finish from the southern part and then come up here. But if if I go total completion right now and I do this, you know, see how it immediately formed a triangle to like complete these two streets here? Like this is not optimal, right? Like, because the greedy part of it is like, well, let me complete these two streets that are close to the starting point, but then by the time I get back, I'm basically like doubling up on one of these where I could have totally avoided that. And then also, too, it it does the incredibly harmful thing right here of leaving this Rouge Hills Drive open, which means that like if I were to create another, you know, route, it would basically have to double, it would have to run this whole length, which looks like a kilometer or two, and then double back because there's nothing over here to finish. Which is why, like, if I'm starting in this corner, it should be able to like reason that, like, alright, I want to go north, do a bunch of stuff, and then finish from the south. But right now it's just it's just greedy, right? So if I choose some other place that's like not boxed into that corner, like if we just choose here, I'm sure it'll do a lot better. It's very fun to watch too.

Bryce

Yeah, so so the your algorithm doesn't do backtracking?

Conor

It does not, no. Uh well, yeah. I mean, I I shouldn't say I don't think it does, because clearly when we watch it animate, it doesn't like pause, think, and undraw anything. It just is always moving forward.

Bryce

Yeah, so so like the the triangle problem you just described, like I think you can't catch that without either some form of look ahead or backtracking.

Conor

Yeah, I don't and that's the problem, right? Is like how far are you gonna look ahead? Because really it needs to be like 16 kilometers later when I'm finishing the run. Which if you're gonna look that far ahead and and whatnot and and do like some kind of equivalent of like Monte Carlo tree searching, like it's you know, it's a very tricky thing to I've I've thought about too of like doing some kind of human-assisted version where basically like you choose a starting point and then you choose like like a series of points, you know, where you kind of you kind of know the direction you want the algorithm to go, and then you want it to just fill the rest in, and that would ideally prov like prevent it from although it's still if it's doing the greedy thing, I don't I don't know.

Bryce

The the literature that I'm looking at, like it's talking a lot about the idea, like this like group Steiner path or the the quota generalized traveling salesman problem. That is the goal there is to have the shortest path that visits at least one node in every cluster. And the idea is like you would you like let's say that you wanted to like connect a computer network, right? Like you want to have all the different you know subnets connected together. Like what's the what's the shortest way to connect all these different you know existing networks together, something like that. So that makes sense. It sounds like the thing that you you need may not be like a a I'm sure I'm sure people have thought about this problem before, but it's not like a widely, you know, known thing in the literature. At least if it was, the agent probably would have come up with it.

Conor

Yeah, I mean if you think of most real-world routing problems, it's point A to point B, right? It's not optimally trying to complete or actually, I don't know, maybe maybe it is some. Although how many I was just thinking, like, what if you're an ice cream truck? You want to hit like all the parks in the shortest distance at the right times or something. But I'm uh I was about to say how many ice cream truck businesses are uh optimizing the routes. I'm pretty sure they're just hitting a couple parks and calling it a day.

Bryce

Yeah. It's probably like like one application of this algorithm that I could imagine would be, well, I was gonna say something something like like you have a network of existing bus stops, but you feel like you have like in New York, like you have a f there's some bus routes where there's too many bus stops. And so it would be optimal to you know say, like, okay, maybe let's let's come up with a better route that only covers 80 of these bus stops. But that but that that problem would all would not have the clustering aspect of yours where you have multiple different routes that you want to optimize across.

Conor

Yeah. If people know of graph algorithms that are like exactly what we're talking about, feel free to.

Bryce

You were supposed to look at the GitHub discussion because people may be Oh, yeah, yeah, yeah.

Conor

I mean, not of the one. Are you telling me the thing that I asked you to remind me of? Yeah. Yeah, that's something different. But I mean we can uh we can we've already been talking for like an hour now, and this was once again supposed to be 30 minutes. Will I split it? I'm probably not gonna split it, I'm too lazy. Yeah.

Bryce

I I will have to leave in a few minutes because I do have to go get on a get on a uh on a plane. There so there's a thing called the family traveling salesman problem, is an NP hard optimization problem where graph nodes are grouped into categories, families. The goal is to find the shortest possible route that visits a specific. Predefined number of nodes within each family before returning to the origin. That sounds like what you need. The family traveling salesman problem.

Conor

Um maybe. I was just thinking though that I I had a I because uh the like I said, one of the biggest faults of this algorithm is that it kind of just hits the 80% mark or 90% mark and goes home. But I was thinking like there are I don't know if it's like an A star variant or whatever search where you start searching from both the start and the end of some route from point A to point B. And then like whenever they meet each other, whatever you call it, that's the shortest path instead of just searching from one direction. Or like that, or that's maybe not a different algorithm, but it's like an optimization on finding it faster. Because like the s the longer you go from one point of some depth first search or BFS or even if it's a priority queue, like the more expensive, like the bigger your horizon that you're exploring is, so the slower your algorithm goes. But if you do it from both directions, uh it can be faster. And I was thinking, you know, if if you started doing that but from the same point, and you had some kind of thing that said, you know, shoot two of these off, or maybe even four or six, and try to not have them collide or whatever, if you did that from here, initially my idea was that like they'd just be mostly independent of each other. But if you if you b if you basically had like both of them start, one go left, one go right, would that work? I don't know, maybe.

Bryce

Yeah, so like yeah, there's there's a variety of like parallel search techniques. This family traveling salesman problem sounds like it is the exact definition of what you need. I'm looking at some literature on it. There's some papers on it. It's in P Hard, of course. So uh solving it strictly using brute force becomes computationally impossible. Instead, researchers and systems use heuristics and approaches, breaking the problem into two subproblems, a macro level, planning which families to visit, and a micro level, calculating the optimal node order. Popular algorithmic methods to generate optimal or near optimal solutions include randomized heuristics, biased random key genetic algorithms, evolutionary algorithms, and math heuristics, hybrids combining exact solvers like C Plex with simulated annealing or greedy search procedures. Interesting. You should talk to the uh you should talk to the co-op co-opt people.

Conor

Maybe. I probably have spent enough of my own resources on solving this problem. Let alone now trying to get other people other than you now thinking about this. Uh but yeah, maybe we need to hook a GPU GPU up to this problem and Yeah.

Bryce

Anyways, we should probably wrap it here. I gotta I gotta get, you know, get to the airport, I gotta go to Poland for EuroPython and Euro SciPy.

Conor

Wait though, wait, so we'll have the GitHub discussion. Yeah, last thing that I mentioned, so I was wrong. And uh I owe Bryce an apology. I said it was one of our most boring episodes ever, and that episode 293 had a a great GitHub discussion, and then we switched to this. Well, episode 294 had an even better GitHub discussion, and they were saying the most interesting parts were the ones where Bryce because I I scrolled your voice a couple times. And the people are upset. The people have spoken and they want more content like this. Anyway, so I was wrong, Bryce. You were right. More, I don't know, what do you call it?

Bryce

Auto research algorithms explained using uh there is an interesting development, and the interesting development is I may be wrong because I I was chatting with some or I put this on an internal Slack channel at NVIDIA, and somebody said it can't be L2 bank conflicts because the the L2 on the GPU is like banked on based on physical addresses, not virtual addresses. So I gotta I gotta uh I gotta look into it a little bit more to make sure make sure I actually understand what the true problem is.

Conor

Well that's fantastic.

Bryce

So we will have a histocache revisited and all the folks The interesting thing, the interesting development with Histocache is the original version that I've been playing around with was you have the cache in the the the fast shared memory, and then when you miss in the cache, you go directly to global memory. But I've been playing around with more like adversarial inputs, and there are some adversarial inputs where it really, really tanks performance, like where you basically you fill up the cache, and then the rest of the accesses are contended in global memory. So the thing I'm trying now is when you spill, you spill to a privatized cache in global memory. So this has uh smoother performance overall. Like you give up some performance wins that you get. Like you don't have as uh, you know, instead of getting 4x on some some inputs, you only get 2x, but you have fewer inputs where you have really atrocious performance. And when I mean atrocious performance, I mean like, you know, uh 100x slower than the the existing algorithm. And they are like pretty like you know, odd adversarial cases, but I do want to try to minimize those as much as possible. And there now that I've added in this basically this second level of caching, there's a couple knobs I can play around with. In particular, one of the knobs is do should we if we're spilling into like if we miss in the cache and we're spilling into this privatized histogram, should we do something like combining before we go into this privatized histogram? And then if you have this privatized histogram, there's a couple different options for how you combine all the local histograms at the end. And there's the question of at the end, do you combine the cache into the privatized histogram and then the privatized histogram into the global histogram, or do you combine the cash directly into the global histogram? So there's a whole set of new options I need to try out here. So uh I'll probably be exploring those over the next couple of weeks. Basically, what I would like to get out of the algorithm is to have the you know 1.5 to 2x like average speed up with as few regressions as possible. There's a couple cases where it's more like 4x, but uh if I can get it to like not have the regressions, but like still have like a pretty big like you know, 1.5 to 2x faster everywhere, that that that would then make me happy and be closer to being uh shippable.

Conor

All right. Well, stay tuned, listener. We will uh have updates for you. And uh I promise next time I'll let Bryce talk about all the nitty-gritty, and then I shall just wait for the people to rejoice once again on GitHub discussions. Yeah. Anyways, I gotta let you go. Be sure to check these show notes either in your podcast app or at adsphepodcast.com for links to anything we mentioned in today's episode, as well as a link to a GitHub discussion where you can leave thoughts, comments, and questions. Thanks for listening. We hope you enjoyed and have a great day.

Bryce

Low quality, high quality. That is the tagline of our podcast.

Conor

That's not the tagline. Our tagline is chaos with sprinkles of information.