Algorithms + Data Structures = Programs - Episode 295: CityStrides vs Graph Algorithms vs GPT 5.6 Sol

Episode Date: July 17, 2026

In this episode, Conor and Bryce chat about CityStrides, graph algorithms, GPT 5.6 Solver, and more!Link to Episode 295 on WebsiteDiscuss this episode, leave a comment, or ask a question (on GitHub)SocialsADSP: The Podcast: TwitterConor Hoekstra: LinkTree / BioBryce Adelstein Lelbach: TwitterShow NotesDate Recorded: 2026-07-13Date Released: 2026-07-17ADSP Episode 149: CityStrides.com, Graph Algorithms and More!Carlo de Lorenzi: Toronto runner with terminal brain cancer runs every street in the cityCarlo's fundraiser for Community Music Schools of Toronto FoundationCityStrides.comOpen Street Mapscity-strides-hacking GitHub RepoHamiltonian PathEulerian PathEpisode 220: Graph Algorithms & 7 Bridges of KönigsbergNVIDIA cuoptIntro Song InfoMiss You by Sarah Jansen https://soundcloud.com/sarahjansenmusicCreative Commons — Attribution 3.0 Unported — CC BY 3.0Free Download / Stream: http://bit.ly/l-miss-youMusic promoted by Audio Library https://youtu.be/iYYxnasvfx8

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 dependence, 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 13, 2006. My name is Connor, and today with my co-host, Bryce, we chat about city strides, graph algorithms, GPT 5.6, soul, and more. It's exciting times. Okay, okay, all right, so first thing, so listen, 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 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 mostly have just been using it for coding. And in kind of like a dumb way, like I don't have, I use all these like persistent,

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 recognized 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, accelerated my output in so many places that 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 the thing that I started using last week was computer use and, like, browser use. And the reason I started using it is kind of. kind of interesting. So if you go to chat GPT or ClaudeCode or Codex, 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. 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 sort of tools I want it to go and use and what I've found is it just doesn't have access to a lot of stuff and I think what happens is if you ask it to go to like flights.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 vague posts 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 it to chat GPT. But 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 screenshot instead. But with the flights thing, if it goes to

flights.com, it can't actually pull up data there. And I don't know if it's because it needs a login or if it's that when it goes to that site, that's like when an agent or any sort of automated system goes to a website, there's some protocol where it asks the website like, hey, you know, I'm a robot, can I come look at your site, this like robots.txtee thing. And 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 tasks that I wanted 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 wanted 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 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 got to 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, like, sort of validated for me, 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?

Anyways, I don't know if you started using any of this, but for me at least it's been, it's been very powerful. I haven't done any computer use stuff, but. Like, I'll give you an, I'll give you an example. 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.

Well, it's funny that you guessed that, because 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've talked about this, actually. I'm pretty sure we have. Let me check on the website, ADESP,

An episode that had the word, did it have City Street? Yeah, it had episode 149, 2000, 23, September 29th, Citestrides.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 at the end of this 30-minute discussion

to talk about GitHub discussion things again. Anyway, so we, I have many. mentioned 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 city strides.com. It ranks or it tracks, you upload your Strava or you connect your Garmin or Strava, and it tracks all the roots, the GPS files that you run, and then 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 hobby is going and doing this. In 2023, I don't know, you'd have to go back and listen to that episode. I was probably in the top 100, 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 obsessed. Like it to say, 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 roots and I've become like an open street map. I wouldn't say expert, but there's like an equivalent, an open source equivalent to We're going to talk about that Python script in a little bit.

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 ChatGTP to do it. And it worked amazing, Matt. Nice. And anyways, my point is, I've become.

I'm very much obsessed, and I'm going to be, I said this on my other podcast as well, that I'm currently 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 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 and my run and then drive back home. And 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 dependence, and no serious responsibilities. There was an Instagram real 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. And 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, 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 8.5,000. 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,

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 on a happy, happy note 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 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 everyone's in a while. How do they define Toronto here? I see a blue line around. 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. But you have more total streets than all of these people. Interesting. 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've got to take a left hand turn here. It's probably I should try and do one at a time. Either go ahead. So I notice some streets here that look more like highways. Is there, like, do they exclude from city streets, streets that are, like, not safe for a pedestrian to go on?

Yes. I won't go into the details, but yeah, highways and, like, high traffic, unsafe roads are always excluded. That being said, like, when I was in... Like, I noticed this, like, Kingston Road on the far right there that... Oh, Kingston Road is not a highway, so this is a road. Okay, that's, you just haven't gotten over there. 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, Atobico and Scarborough. And so I've done everything but Atobico 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 super set. 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 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 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. Hang on, hang on. That's cheating. You have to get all of the actual nodes in Toronto before the baby. So that is what city stride purists say. And 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 did actually have like a route mapping if we go to. And so actually, well, I can show you. 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-minicipality. within Toronto and then just some other random cities that I run in often. You've completed New York? North York, not New York. Oh, okay. Okay, all right, I understand. 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, And basically I've been running every single day, city striding. And 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 depends, though. Are we going to make it? Maybe, maybe not. Stay tuned. And 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 that I don't have an old version of this because I did get rid of it.

Anyways, 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 anyway, so I just basically over the weekend was talking to AI and saying, you know, 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, et cetera. But if you're trying to complete 100% of the city, you want like a dense, you know, and one of the biggest problems with these automatic root generations is like stranded streets. You don't want to create a route that strands one or two streets that are going to require running an extra two or three kilometers because you left them behind. Anyways, I won't go into all the details because the viewer or the listener can't see this.

But now, like, the idea is. That stranded street thing is some sort of, there's some sort of grass. property. Yeah, like, 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'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 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, basically like that's a non-starter. Like it's 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 hitting 90% of the nodes. And it's not perfect yet. You can see here that 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 for 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 once you see the nodes you just manually click around and this will give you a basically a GPS file some people loaded into their garbans but I basically

just like have the website open on my phone while I'm running around and now I'm going to save myself like 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 allowed to talk about 5.6 soul now, right? Yeah, yeah, we can, yeah. Yeah, so 5.6 soul is so much better than Opus 4.8 in my opinion. like 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 the insights that I saw GPT 5.6 soul making just by working and iterating it on itself, it'd be like, ah, 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 routes. And it made sure that like every single time it added a another heuristic. It wasn't regressing on some other heuristic that it had set up earlier. Like, it did some sophisticated stuff. And 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 stop talking. So we're doing the same thing, just not computer use on my part. So this problem of like visiting all the nodes, you know, once without backtracking.

I actually think, well, so for, okay, going back to my days in college the second time around and, 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 wonder, though, whether that's, I think that's not exactly your problem, because I think that your problem, 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, you can, 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, after having enough conversations about it, about the heuristic that it needed, it's finally figured out that at certain times, doing 180 degree turn and backtracking, is the optimal thing you want to do,

but 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 done some optimal calculation where it says, actually, I should do 180-degree turn here and backtrack instead of, like, completing this loop, because it is going to save me, even if it's a small amount of distance,

it's still a saving, right? But, like, this is not like a, a simple thing to like program, especially when you think about how many nodes you're looking at. And yeah, anyways, I interrupt you. I think that 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 looked it up. Visiting all the edges of a graph exactly once is called an Eulerian path or an Eulerian circuit. And I think there's a formulation of this problem called the China. I think it's sometimes also known as the Chinese postman problem according to this. And I wonder, when you were looking at it over the weekend, did you come across that or any of the graph theory behind this? I mean, I did no research on my own. It's just been talking with the models.

and at no points from... Didn't we once talk about the seven bridges of Coensburg problem? Yeah, yeah, that might have... Let's actually check the... So if we go back here... When I go to the Eulerian Path Wikipedia page, 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. Yeah, I was going to say, the graph algorithms and seven bridges, I'm not sure if this came up because of cities. So City Stride doesn't mention. I think you were just traveling in Europe and you had come across some algorithm book. And in the algorithm book, it was talking about graph algorithms. So definitely, like, these have come up.

But like 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 node.

And like you don't like really a kind of, I'm sure a heuristic that's built in is that any time you're traversing a road and the distance since the last node that you've 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 going to 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 seen, it needs to run a bit of distance where there are no nodes. Yeah. So if I recall correctly, or not all graphs have an all therein path.

and I believe that there's a relationship between whether the graph, like whether all of the vertices and the graph belong to a single connected component or slash strongly connected component. I think that it might be the case that it's only graphs in which all the vertices belong to a sync to like to one connected component have an o'larian path, by which I mean a path where you only have to visit. every vertex once. And so, yeah, like, you're right. 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 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, it's certainly, it's some class of optimization problem for sure. Microphone in use. All right. 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 path 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 see what Chachy. 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 going to say? I think it's going to say one of your Eulerian or Hamiltonian things? Actually, I think that... Chinese postman problem. It sounds like a variant of the Chinese pose. Why is he Chinese?

So the Eulerian Path problem is specifically wants 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 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 care about, you care about a shortest, like, distance. So the number of times that you repeat something maybe isn't as important. 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 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 retracing your steps when it's not down like a corridor or a cul-de-sac like that's cause for concern so 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 some of the nodes are not reachable from other nodes,

then obviously no such path where you visit all of them uniquely once exists. But I think there's also some other property. 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 going to be very hard to uniquely visit. Like you can't uniquely visit that node without taking that edge twice. Right.

Yeah. I mean, 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. Right. And, yeah, when I, when I... You care about... 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. Yeah. Like, it's a, it's an undirected, you know, weighted, weighted graph. Interesting. Yeah, I mean, it's probably, like, 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 solve. But you know what? GPU is very good at craft problems. Have you like looked at coopt? You should you probably coopt probably has like algorithms for this. Maybe. Actually,

should we just ask, should we ask? Can you explain roughly your route planning? Isn't this just traveling salesman? Well, so yeah, yeah, I mean at one point I asked, chat chabit, and 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, and I'm sure there are like graph theory experts out there that work for Google and on Google Maps like rooting 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. Because you only need 90%. Well, no, it's not that I, yes, I, I, yes, I, 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, so when you hit a cul-de-sac, like, you know you have to do it. That sounds like a call. 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 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, like each street you kind of want to model. And I recall when we talked about this last time that you you talked about like modeling each street separately.

But like 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. Yeah, I mean, I don't really know. Like, 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 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, 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 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 going to completely do something that's not, like, doing the snake pattern. You know, like, it's, 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 anyways, I asked Codex to explain what it's been doing. And he said, roughly, it's a greedy graph search optimizer. So it's not actually doing anything fancy. It builds a walkable graph from all the relevant open street map, road, 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 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. which it's still pretty good result, even with that, like, glaring flaw, which maybe we can talk about in a sec because... There's the question of what, like, what is the graph theory and the optimal... 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 you're just that your agents describing here, you know, is probably in the class of things that are like most reasonable. Because like maybe the optimal way to solve this problem is like some ridiculously computationally intensive thing, you know, like some way to estimate some solution to some NP, you know, hard problem.

And you don't need, you don't need the option. solution, you need, like, a reasonably good solution, you know, within 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 way to solve this, like, to actually find the optimal route existed, but, like, required you to run on, like, 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'm searching, 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 like the quota constrained 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 means relative to the traveling salesman problem, but maybe it's the generalized part is just that it generalizes the cost function. Generalized traveling salesman. Generalized traveling salesman problem. Generalized traveling salesman problem where the graph's 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 and some class of traveling salesman-like problem. Though the specific formulation that you need sounds like it's a little bit unique. Yeah, 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? So if we chose, if we choose some new location, so let's go, let's go all the way over, all the way over here.

And so actually, I've tried this one a couple of times. So like, if you're going to start in this corner, it's clearly got like one entrance, it's got two entrances. What the algorithm's going to do is it's going to complete this little triangle first. But really what I would do is, you know, 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 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 does the incredibly harmful thing right here of leaving this Rouge Hills drive open, which means that like if I were to create a, 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, all right, 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. Yeah, so the, you're. algorithm doesn't do backtracking? It does not, no. Well, I mean, I shouldn't say. I don't think it does, because

clearly when we watch it animate, it doesn't like pause, think, and on draw anything. It just is always moving forward. Yeah, so, so like the triangle problem you just described, like, I think you can't catch that without either some form of look ahead or backtracking. Yeah, I don't, and that's the problem, right?

It's like, how far are you going to look ahead because really it needs to be like 16 kilometers later when I'm finishing the run, which if you're going to look that far ahead and whatnot 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 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 prevent it from, although it's still, if it's doing the greedy thing, I don't know. The literature that I'm looking at, like, it's talking a lot about the idea, like, this like group Steiner path or 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, 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 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 need may not be like a, 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. Yeah, I mean, if you think of most real world rooting problems, it's point A to point B, right? It's not optimally trying to complete. Or actually, I don't know. 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 was about to say how many ice cream

truck businesses are optimizing the routes? I'm pretty sure they're just hitting a couple of parks and calling it a day. Yeah. It's probably like one application of this algorithm that I could imagine would be, well, I was going to say something like you have a network of existing bus stops, but you feel like you have, like in New York, like you have a, 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 problem would not have the clustering aspect of yours where you have multiple different routes that you want to optimize across. Yeah.

If people know of graph algorithms that are like exactly what we're talking about, feel free to. You were supposed to look at the GitHub discussion because people may be. Oh, yeah, yeah, yeah. 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, 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 going to split it. I'm too lazy. Yeah. I will have to leave in a few minutes because I do have to go get on a plane. 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 we're turning to the origin. that sounds like what you need.

The family traveling salesman problem. Maybe. I was just thinking, though, that I had a, because, 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 longer you go from one point of some depth for a 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, it can be faster. And I was thinking, you know, 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 basically had like both of them start one go left, one go right, would that work? I don't know, maybe. Yeah. So like, yeah, 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. Here's some papers on it. It's NPR, of course. So solving it strictly using brute force becomes computationally impossible. Instead, researchers and systems use heuristics and approaches breaking the problem into two sub-problems, 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, you should talk to the co-op people. 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. But yeah, maybe we need to hook a GPU up to this problem. Yeah. Anyways, we should probably wrap it here.

I got to get, you know, get to the airport. I got to go to Poland for Euro Python and Eurocypi. Wait, though, wait. Are we looking at the GitHub discussion? Yeah, last thing that I mentioned. So I was wrong. And I owe Bryce an apology. I said it was one of our most boring episodes ever

and that episode 293 had a great get-up 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 were Bryce because 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? What? Auto research algorithms explained using... There is an interesting development, and the interesting development is, I may be wrong because I was chatting with some,

or I put this on an internal Slack channel at Vida, and somebody said it can't be L2 bank conflicts because the L2 on the GPU is, like, banked on based on physical addresses, not virtual addresses. So I got a, I got a, I got to look into it a little bit more to make sure, make sure I actually understand what the true problem is. Well, that's fantastic. So we will have a histocash revisited and all the folks.

The interesting thing, the interesting development with histocash is the original version that I've been playing around with was you have the cache in 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 cash 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 cash in global memory. So this has smoother performance overall. Like you give up some performance wins that you get. Like you don't have as, you know, instead of getting 4x on 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, 100x slower than 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 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, 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 cash 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 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 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 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 would then make me happy and be closer to being shipable.

All right. Well, stay tuned, listener. We will have updates for you. And 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.

I got to let you go. Be sure to check these show notes, either in your podcast app or at ADSP thepodcast.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.

Low quality, high quantity. That is the tagline of our podcast. It's not the tagline. Our tagline is chaos with sprinkles of information.