Description

We start our season off with something that often pops up in technical interviews: the Traveling Salesman Problem (TSP). In this problem, a salesperson has to travel to every single city in an area, visiting each city only once. Additionally, they need to end up in the same city where they starts their journey from. Find out how to make our salesperson do this in the most efficient way possible!

Show Notes

This episode of the Basecs podcast is based on Vaidehi's blog post, The Trials And Tribulations Of The Traveling Salesman from her basecs blog series.

Transcript

[00:00:02] SY: Welcome to the Base.cs Podcast where we explore the basics of computer science concepts. I’m your host Saron, Founder of CodeNewbie.

[00:00:09] VJ: And I’m Vaidehi Joshi, Author and Developer.

[00:00:12] SY: And she is the brilliant mind behind the Base.cs Blog Series. Today, we’re talking about…

[00:00:16] VJ: The Traveling Salesman Problem.

[00:00:19] SY: This season of the Base.cs Podcast is brought to you by DigitalOcean and Heroku. DigitalOcean’s cloud infrastructure is optimized to make it super intuitive and easy to build faster and scale easier. The pricing is predictable. They have flexible configurations and excellent customer support. Get started on DigitalOcean for free with the free $100 credit at DO.co/basecs. That’s DO.co/basecs.

[00:00:47] Did you know you can build, run, and operate applications entirely from the cloud? With Heroku’s intuitive platform, you can streamline development using the most popular open source languages, so you don’t have to worry about backend logistics. Also, you’re not walk-in to the service. So why not start building your apps today with Heroku?

[00:01:12] So I have heard of this problem before. I feel like it’s one of those really famous things that I never actually learned and don’t really know what it is. What is the traveling salesman problem?

[00:01:24] VJ: This is a problem that comes up frequently I feel like in like technical interviews or like computer science courses and it’s got this reputation like you just mentioned, but really all it is, is a graph problem, a glorified graph problem, if you will.

[00:01:41] SY: Okay.

[00:01:41] VJ: And the traveling salesman problem is basically trying to solve a problem where you have a salesman who travels as his job or her job or their job, and this salesman basically wants to travel to every single city and they want to visit each city only once and end up back where they started. So the traveling salesman problem is figuring out what’s the most efficient way for the salesman to do this. And if we think about it in the context of a graph problem, the cities are the nodes in the graph and the distance to get from one node to the other, those are basically the edges, the links that connect them together. So it’s like a word problem for computer science sort of.

[00:02:30] SY: Well, it seems like a very relevant one because I feel like we’re always trying to do exactly that, right? We’re always trying to get from one thing to another, like maps is the thing that really comes to mind. Are there other examples besides maps that we might be familiar with?

[00:02:45] VJ: If you thought about it in the context of like how you find the fastest way to get from one piece of data to another. So like if you think about a graph can be like a social network. It can be a map. It can be any kind of representation of data that is loosely connected, anytime you’re trying to find the most efficient way to touch all those pieces of data to go to all of those different nodes in the graph but finding like the fastest way to do it, like trying to be efficient about it, you’re basically solving the same problem. Like the example that I think about a lot is like when I’m trying to find a flight from one location to the next, I’m often thinking about like, “Okay, how do I get from one place to the other in the most efficient way?” And like maybe that’s a layover or maybe like one flight is more expensive than the other. You don’t want to take the expensive route. You want to take like the cheaper one. So there’s lots of ways that you can transpose that traveling salesman problem onto literally any other kind of dataset.

[00:03:41] SY: Oh, okay, okay, okay. I was trying to think of why it sounds so familiar. It reminds me of that other problem that we did with Euler and the City of…

[00:03:52] VJ: Konigsberg.

[00:03:53] SY: Konigsberg?

[00:03:56] VJ: Konigsberg, I think.

[00:03:57] SY: Konigsberg. Okay. Cool.

[00:03:58] VJ: It’s how I’ve been saying it.

[00:04:02] SY: I’m trying to remember what the setup was. We were trying to go to different parts of the island, but we could only cross a bridge once. What was the setup for that?

[00:04:11] VJ: So. The story you’re thinking about is Euler and Konigsberg, and that’s the origins of graph theory story. And yeah, you’ve got most of it right, like this story was basically that in this town, everybody was trying to cross these seven bridges, but only cross them once.

[00:04:29] SY: Right.

[00:04:30] VJ: And so the challenge there was how do we cross each bridge only once without repeating ourselves. So it’s interesting that you see a similarity between the problem that Euler faced and this traveling salesman problem because the problem that Euler face was basically finding Eulerian circuit. And that’s what we sort of learned about when we were learning about graph theory. And as a quick reminder, in Eulerian circuit, we visit every single edge in a graph once, but that does not apply to the vertices in the graph. So the goal with an Eulerian circuit is visit each edge once, but you can visit vertices more than once if you need to. And so in the Konigsberg example, we were trying to cross each bridge once and only once, and those were the edges.

[00:05:19] SY: Right.

[00:05:20] VJ: However, even though that example is very similar, there’s a slight difference with this traveling salesman problem, which is that we’re trying to get to each city once without repeating ourselves and end up in the same place, but the cities in a graph are really the nodes. So what we care about is not visiting each edge once, we care about visiting each vertex or node in the graph once, and we want to end up at the exact same vertex that we began with. So it’s not quite an Eulerian circuit. This is a different kind of circuit.

[00:05:57] SY: Okay. What’s this one called?

[00:05:59] VJ: This is called a Hamiltonian circuit.

[00:06:04] SY: Is it by someone named Hamilton?

[00:06:06] VJ: Yup. You got it. It’s named after another mathematician, just like the Eulerian one, and actually we can use a Hamiltonian circuit for solving this graph problem, and it’s named after a mathematician William Rowan Hamilton, and basically he came up with the idea of like, “You can create a path where you touch each of vertex exactly once and you end up at the same vertex you began with, and that’s a Hamiltonian path, but we are looking for this traveling salesman to end up at the same place that they started at. So it’s not just a path we’re looking for. We’re looking for a Hamiltonian circuit where every edge doesn’t need to be visited, but every vertex does, and you’ve got to end up the same place you started.

[00:06:50] SY: Right. Okay. So we have the traveling salesman problem and we are going to use a Hamiltonian circuit to solve it. Okay. That’s not too bad. That’s not too bad. I think it really helps that we have that Euler example that we did earlier.

[00:07:05] VJ: I know. Yeah. We’ve dealt with like mathematicians and their little circuits before. We can do this.

[00:07:10] SY: That’s right. Okay. So maybe we can walk through an example to see how this might work.

[00:07:14] VJ: Yeah, that sounds great. What should our graph look like? What should we work with for our salesman?

[00:07:20] SY: Okay, let’s do some letters. Let’s do W, X, Y, Z. I feel like we do A, B, C, D a lot. Let’s do W, X, Y, Z and switch it up and let’s assume that they are all connected like a square. So W to X to Z to Y, and then let’s also assume that they are connected across from each other. So that W is connected to Z, Y is connected to X so that it looks like a kite. So everything is connected to everything else.

[00:07:48] VJ: I like that.

[00:07:48] SY: Okay. So I remember when we’re talking about graphs. I don’t remember how many episodes ago we talked about weights, right? Because the edges had different weights on them, which would help us determine what the shortest and the longest paths were. So let’s give this one some weight. So we have W, X, Y, Z. And the way we are going to map this out is if you think about a house, right? We’ve got the walls, we’ve got the foundation, and then we’ve got the roof. So we have two corners for our foundation. One is Y, one is Z. Y is connected to the corner W which is at the top. So that’s the beginning of our ceiling. And then Z is connected to the corner X to make up a wall. And then W and X are connected to make the ceiling.

[00:08:36] VJ: Yeah, I can imagine what you’re saying. We have these two nodes on the bottom, Y and Z, and then we have two nodes above them, W and X, and all four of them are connected. So we have like a floor and then two walls and then a ceiling. So we basically have four edges right now and four notes. Is that it?

[00:08:55] SY: Yes. That’s it. But twist, we have two cross beams to make sure this house is really strong and structurally sound.

[00:09:07] VJ: I have no idea, by the way, if that’s how crossbeams work.

[00:09:09] SY: Yeah. I have no idea if this is true. I had no clue.

[00:09:11] VJ: But I like to imagine.

[00:09:12] SY: It sounds right. It sounds very architectural. Okay. So we’ve got our opposing corner units. We have our Y and our X, and they’re sitting at opposite sides of each other, and we’re going to connect them so we have our first crossbeam there, and then we have our W and our Z, which are diagonal from each other, and then we’re going to connect those. So we have two new edges, Y to X and then W to Z.

[00:09:35] VJ: Right. So we basically have four nodes all connected to form a square and then a big X in the center of them.

[00:09:41] SY: Exactly. And each of these have different weights. So we’ve got weights of six, we’ve got a couple of threes, four, two, one. So each of these edges has its own weight associated with it, which we’re going to use a little bit later. And remind us again what a weight is.

[00:09:56] VJ: Yes, it’s important for us to know this before we go any further. A weight is just a cost or like a distance associated with an edge. So in this scenario, we have these one, two, three, four, five, six edges, and each of them has a weight, which means that whenever we look at one of these edges, if we want to know the cost or the distance to get from the two nodes that that edge is between, we can look at the weight, and the reason that this graph has weights is because for the traveling salesman problem, we’re trying to find the most efficient route for the salesman to get through all of our nodes, W, X, Y, and Z. So we’re going to have to take the weights into account.

[00:10:37] SY: Okay. So to start the traveling salesman or salesperson, I should say, problem.

[00:10:42] VJ: Yeah, I like that.

[00:10:44] SY: I like that, right? Yeah. Include everybody, all the people. We need to start with the vertex, right? We have to start at one node and then we’re going to travel around then get back to that node. So let’s start with our Vertex W.

[00:10:56] VJ: Great. So that is the top left vertex.

[00:11:00] SY: Okay. So now that we’ve picked our vertex, what do we do now?

[00:11:04] VJ: Just because this is kind of like a new problem for us, let’s sort of approach it with the naïve approach as people would say, but I don’t even think that’s naïve. I just think it’s like brute force. So in order to figure out the most efficient route between W and then all the other nodes ending back at W, we can just sort of brute force our way through this and what we really want to do is we want to look at all of the potential paths through this graph, all the different routes we can take because if we look at all of them, then it’ll be hopefully pretty easy for us to figure out the most efficient one of all of these. We can do this by using recursion and if we use recursion, we can keep track of the nodes that we can go to next. Eventually what we can do is list out all the possible permutations, all of the different routes we can take using recursion, and then once we have them all listed out, we will look at what’s the fastest and what’s the most efficient, or rather which one costs the least in terms of the weight of the edges.

[00:12:04] SY: Okay. So we’re going to do this recursively?

[00:12:07] VJ: Exactly, because we’re using recursion, we know that we’re going to want to repeat the same steps again and again and recursively apply this till we finish doing this whole graph problem. So really what we care about is whether we’re starting with the first node or any other node in this graph traversal problem, we want to know what node am I looking at and what are the remaining nodes that I can potentially visit. So like who are these nodes’ neighbors? So we’re starting initially with W, right? So there’s two things we want to pay attention to for this. We want to look at what is the node, the node is W, and who are the remaining nodes that I can potentially visit and what that really is answering is what are the potential paths that I can take from this particular vertex. So we can say we have Node W and the potential paths that we can take, the remaining nodes to look at are the Nodes X, Y, and Z, which is really just all of the nodes because we haven’t done anything yet.

[00:13:08] SY: Right.

[00:13:09] VJ: But now we’ve established these two basic steps. We can sort of apply this to every other node because we’re using recursion, right? So we’ll basically have one single node and then a list of its neighbors and for each of those nodes we’ll do the same thing. And so what we can do is we can go to each of the other nodes and say, “Okay, what is the node I’m looking at and who are the remaining nodes that I have left to visit?” So we can go to Node X and we can say, “Oh, what are the remaining nodes?” Well, just Y and Z because we’ve already looked at W, and then we can do the same thing again with the Node Y. We can say, “Who are your remaining nodes to visit?” Well, X and Z, because we’ve already looked at W and this is Node Y. And if we do this with Z, we can do that again and we can see that the remaining nodes are X and Y. Those are the ones left to visit, if we start with W and then we look at Z. And if you sort of visually imagine us listing out these nodes, you can think of it like a tree structure where W is the root and then the nodes that we’re visiting, the places that we can go from there are X, Y, and Z, and those are sort of the three children nodes.

[00:14:22] SY: Okay. That makes total sense to me. So we start with our W and we had one list and then we went to members of that list and we made some more lists and then I assume we’re going to go to those lists and make more lists?

[00:14:35] VJ: Yeah, sort of. And you’re saying the word “list” and really what we’re doing is we are going through all the possible permutations of this graph. So we can think of it as lists. We can also think of it as a tree that we’re building out where W is the root and then it’s possible paths are X, Y, and Z. Those are the three children, and then X, Y, and Z have their own possible paths to take, and then those spawn their own children. So we’re basically growing out.

[00:15:04] SY: Kids on kids.

[00:15:06] VJ: It’s like the theme of the show.

[00:15:08] SY: It really is.

[00:15:11] VJ: Imagine then that we do the same exact thing recursively to each of the three children nodes, right? So we started with W, we know the remaining nodes that we can potentially visit are X, Y, and Z. So we spawned three children, X, Y, and Z, and then each of them, again, are going to have their own list of remaining nodes and we will need to create a child for each of those remaining nodes because those remaining nodes represent potential paths we can take. So now if we do that again, we’re basically creating another list or creating another permutation, or not creating another permutation, but rather extending the permutation we already have. And so Node X has two potential remaining nodes we can visit, Y and Z. So we can sort of imagine that there are two different routes we could take so we can create a left child of X that’s going to be Y and a right child of X that’s going to be Z. And for each of those, there’s only going to be one remaining place we can go. If we start with W and then go to X and then go to Y, the only other place we really need to go is Z. And if we start with w and then go to X and then go to Z, the only other place we can really go is Y. I won’t list all the other permutations, but eventually what will happen is we will see that there are six different paths that we can take to start at Node W and go through all three nodes and end up back at W. And really all we’re doing is we’re just like doing a slightly fancier version of brute forcing our way and writing down every single path. We’re just sort of doing it recursively or sort of creating this tree structure and we will end up with a tree that basically has six different paths and it will show us all the combinations of paths, and it will start with W as the root and all of them will end with W as a leaf child. Because again, we have to end back at where we started.

[00:17:05] SY: So we start at W and then let’s just go down one path. We go to X, we go to Y, we go to Z. But the traveling salesperson problem says that we have to end back at W, right? So how do we make that happen?

[00:17:19] VJ: So all we really need to do is eventually, once we get to the last node in all of these lists, for example, let’s say we start with W, then we go to X, then we go to Y, and then we go to Z. What are the remaining nodes to check? Well, the answer’s nothing. It’s an empty list.

[00:17:37] SY: Right. We’re done. Right? Okay.

[00:17:38] VJ: Yeah. Exactly.

[00:17:40] SY: I was like, “Oh, it was a trick question.” Okay. No. There’s nothing. We’re done.

[00:17:42] VJ: I’ve been doing those since day one. Yeah. Right. So you’re right, that there’s nothing left to check. So basically that is our recursive base case. So with recursion, you keep doing the same thing again and again until you hit your base case. So in our situation, we’re going to keep writing out the possible paths that we can take the permutation, all the permutations based on the number of remaining nodes until we have nothing left in our remaining nodes list. So if we start with W, then go to X, then go to Y, and go to Z, at that point we’ll say, “Okay, what are the remaining nodes? Oh, wait a second. This list is empty because there are no remaining nodes. We’ve checked them all.” When we get to that point, we basically say, “Okay, the last node to add here, the leaf node is going to be W because I know at the end of the day I have to end back where I started.” So really we’re going to have a bunch of like directed chains where W is the root, and then we can see that we can go through W, X, Y, Z and the last note is always going to be W because that’s how we get back to where we started from. That’s what makes it a Hamiltonian circuit.

[00:18:53] SY: Okay. So we’ve got all these paths. Now that we’ve expanded them, we have all these permutations, how do I know which one is the most efficient?

[00:19:03] VJ: Well, remember those weights? We got to pay attention to those now.

[00:19:08] SY: Okay.

[00:19:08] VJ: And there’s a convenient little way that we can represent these edges and the total cost of each of these paths and that is by using a handy dandy, adjacency matrix.

[00:19:20] SY: Oh, we talked about that before.

[00:19:22] VJ: We did. Yeah. Adjacency matrices are a matrix representation of exactly which nodes in a graph contain edges between them. And so what we talked about in probably like one or two seasons ago, whenever we learned about them, we talked about how it’s sort of like an Excel spreadsheet or a table where we have all the nodes on the X axis and the Y axis, and then match the two nodes and see if there’s a zero there. That means no edge exists. And if there’s a one there, that means an edge does exist. Now we don’t really care right now if the edge exists specifically, we care about what the weight is because like it doesn’t really help us to know that it exists. We want to know, “Okay, how much does it cost?” So we can use an adjacency matrix. But instead of putting zeros and ones in it, instead of putting a one, we’ll put the weight of the edge and obviously we’ll put a zero if the edge doesn’t exist, but what matters here is that we can use an adjacency matrix and record the weight of all of the edges inside that adjacency matrix. And the convenient thing about this is now we can look up the cost of every edge really fast. So now that we have this adjacency matrix, we can use it to sort of do a little bit of math.

[00:20:39] SY: Cool. How do we do that?

[00:20:40] VJ: So we have these like six different paths, right? This big tree structure of all the different nodes and all the different permutations. So really…

[00:20:50] SY: Six options.

[00:20:51] VJ: Right. Exactly. So really all we need to do now is once we know the cost, the distance between two vertices, we can just sum up the distance between them and work our way up the tree structure. We start from the bottom most level and we ask ourselves, “What is the distance, the cost to get from one node to the next?” And as we do that each time, we need to like add a little bit onto our tally because we’re trying to calculate the cost of the total path. So initially we say, “What is the cost to get from W to W?” It’s zero. So we just start with zero. That’s easy. But then we say, “Okay, what is the cost to get from Z to W?” And that costs three.

[00:21:32] SY: And we use our adjacency matrix to find that out.

[00:21:35] VJ: Exactly. And then we do the same thing again, but we don’t let go of that three where you’ll remember that we’re trying to cumulatively do some math here.

[00:21:43] SY: Yes.

[00:21:44] VJ: We hold on to that three and then we say, “Okay, well, we were going from Z to W, we already did that math, but what about going from Y to Z?”

[00:21:51] SY: Okay. So I’m going on my adjacency matrix, I’m going down to Y, I’m going across to Z, the answer is two.

[00:21:56] VJ: Exactly. So the cost to go from Y to Z is two, but we also calculated that the cost to go from Z to W is three, so really now that path costs five. Now we’re going to run into a little bit of a problem on the next level because now it’s not just like a chain of nodes, now we’re getting to the point where we have the number five and we go up to it’ parent and its parent actually has two possible paths, two nodes.

[00:22:27] SY: Oh, right.

[00:22:28] VJ: Because it can go like when we’re at this next level, we have the Node X and it has two children, which means there are two different paths to take. So we either have to decide, “Are we going to calculate the cost of X to Y or are we going to calculate the cost of X to Z?”

[00:22:43] SY: But in order to pick between taking the path Y or taking the path of Z, we know what Y is going to cost us, right? Because we just added the two plus three equals five, so we know that picking Y costs five, but we don’t know what Z costs. So how can we decide?

[00:22:58] VJ: Well, I think we’re going to have to figure out what that whole path would cost and then decide which one of these to pick and just to do some really quick math. The other chain, if you go from W to X first, then you have the choice of going through the Y path, which we’ve already calculated, and then there’s the Z path, and that path would be starting at W going to X, then going to Z, then going to Y and ending up at W, and the whole cost of that would be zero plus two plus one which is three.

[00:23:34] SY: Yeah. Oh, that’s cheaper.

[00:23:36] VJ: So we did all this math to figure out that going from W to X to Y down that chain is five. But as it turns out, if we do some quick math, we’ll see that going from W to X to Z, taking that route is actually faster, cheaper.

[00:23:51] SY: Just two points.

[00:23:52] VJ: Less costly. More efficient.

[00:23:54] SY: Okay. All right. So we basically like narrowed it down a little bit. We started with six permutations and we’ve canceled out one of them. So we’ve only got five left to go.

[00:24:03] VJ: Yeah. Yeah. And actually, if we look at the Y path and the Z path, Y costs five and Z costs three, but before we can really make a decision, we need to see what is the cost of X to Y and X to Z.

[00:24:21] SY: Oh, right. Yeah. Yeah.

[00:24:22] VJ: Because there is still one more chain. We don’t want to eliminate Y yet because what if the cost of X to Y is very cheap, but the cost of X to Z is really expensive? Well, that changes everything.

[00:24:33] SY: Right.

[00:24:34] VJ: So should we quickly check what the cost of X to Y and X to Z are?

[00:24:38] SY: Yeah, let’s do it. So if we do X to Y and we’d go down in my adjacency matrix, going down to my X, going across to my Y, that is four. So it costs us four to get from X to Y, and we know that going from Y all the way down to W costs us five. So the full path of going from X to Y to Z to W costs nine.

[00:25:06] VJ: And on the flip side, the path to go from X to Z, just those two nodes, is three, and we already know that going from Z to Y to W costs three so the total amount to go from W to X to Z to Y to W is three plus three, which is six.

[00:25:25] SY: Which is less than nine.

[00:25:26] VJ: Exactly. So now we’re 100% sure that the path we probably want to choose between this pair is the one that’s shorter, the less costly one, and that’s going to be the X to Z path, not the X to Y path, because that one costs nine and we know that the X to Z path costs six. So we’re going to sort of just like eliminate the chance of us ever going down the W, X, Y, Z path and say, “Let’s just focus on W, X, Z,” which is six. And so the last thing we need to do then is calculate how much it costs to get from W to X because that’s the last step, which is funny that I’m saying it’s the last step because it’s actually the first step that we would because we’re working our way from the bottom of the tree up, right? So the second half of recursion and the cost to get from W to X, if you look at your adjacency matrix, we would see that it costs us six. So really the whole cost of this path, starting from W going to X to Z to Y to W costs six plus six, twelve.

[00:26:31] SY: Okay.

[00:26:32] VJ: Oh, man!

[00:26:33] SY: That was a lot.

[00:26:34] VJ: Yeah, that was a lot. And we didn’t even do the other one, two, three, four paths. We basically took two paths, figured out the cost of both of them, pick the shorter one and figured out that, “Oh, okay. This one is the shorter.” But we’d have to do the same thing again for the two other or rather four other paths, the one where we go from W to Y first and then there’s the other two options, which are involving going from W to Z first, and then eventually we would figure out that, well, spoiler alert, I’ve already done this math before, but as it turns out, going from W to Y or going from W to Z, both of those end up costing, the cheaper of those two paths costs 11 and they’re both equivalent. So it turns out there’s actually two most efficient ways.

[00:27:22] SY: So what do we do now?

[00:27:24] VJ: When you find the shortest path and it turns out there are two shortest paths, you can just choose either of them because it doesn’t make a difference because they’re going to cost the same.

[00:27:31] SY: Great. We’ve got some options.

[00:27:32] VJ: Exactly.

[00:27:33] SY: All right. So just to sum it up, to do a recap, we did all the permutations where all the possible paths, we can visualize this as a tree, and we have our parent node, our root node, and then we have all the different paths we could possibly take, and then we add up all the different weights for each individual paths. So in our case, we had six possible paths, and then we basically just compared them until we found the shortest one.

[00:28:01] VJ: Exactly. Yeah. And then when we came to a branch, we just always picked the shorter one all the way up to the top of the tree until we found that we have two shortest paths as it turns out. But even if we didn’t have two shortest paths, we’d pick the shortest one each time and find the least costly and the most efficient way to get from W through all of the nodes back to W, which is a Hamiltonian circuit.

[00:28:25] SY: Okay. So you mentioned before we started explaining and walking through the steps of this, you mentioned that this was the brute force way of doing it. So I assume that means there’s a more efficient way of making this happen.

[00:28:38] VJ: Yes, there is. And we will talk about that in the next episode. We’ll learn how to speed it up and we’ll talk about why our way is not fast.

[00:28:47] SY: I really like our way. It makes so much sense, but I’m excited to speed it up.

[00:28:52] VJ: Yeah, me too.

[00:28:53] SY: And that’s the end of today’s show. If you liked what you heard, please leave us a review and make sure to check out Vaidehi’s blog post. Link to that is in your show notes. I also want to give a huge shout-out to DigitalOcean and Heroku. DigitalOcean is a simple developer-friendly cloud platform, which makes managing and scaling apps easy with an intuitive API, multiple storage options, integrated firewalls, load balancers, and more. There’s also a robust community that provides over 2,000 tutorials to help you stay up to date with the latest open source software, languages, and frameworks. Get started on DigitalOcean for free with a free $100 credit at DO.co/basecs. That’s DO.co/basecs. There’s a reason over nine million apps have been created and run on Heroku’s cloud service. They not only manage over two million data stores, but they make over 175 add-on services available to you. So whether you’re creating a personal app, a free app, or an enterprise app, start building today with Heroku. This episode was edited and mixed by Levi Sharpe. Thanks for listening. See you next week.

[00:30:04] VJ: Bye everyone.