I feel like there's a really trivial solution lurking in here that I just can't put my finger on. ("weight" is the length of the segment in train cars.) My code for this right now looks like this: def can_afford(path, cards): But how does one write a generalized algorithm that solves this problem for less obvious cases involving more colors and more segments? The answer, of course, is to use the 3 blue cards between Paris and Zurich, and 2 red cards each for Venice to Zagrad and Zagrad to Vienna. Then it needs to decide how to use the remaining 4 red and 3 blue cards to cover the gray segments of lengths 3, 2, and 2. My algorithm for figuring this out starts with the green segment, and allocates the two green cards there. Looking at the board, it's pretty easy to see that the only possible route for this card combination involves going Paris -(3 gray)-> Zurich -(2 green)-> Venice -(2 gray)-> Zagrad -(2 gray)-> Vienna. With multiple gray segments, however, one can run into situations where the color chosen for the first segment makes completing the second or third segment impossible.Īs an example, suppose a player's card inventory is 4 red, 2 green, 3 blue, and we're trying to figure out if he can get from Paris to Vienna. With gray, because you can pick any color to use for each segment, it gets a bit more involved.įor paths with just one gray segment, it's still easy - either you have enough cards of any one color to fill it in or not. I do the non-gray segments first since they're more straightforward - either you have enough red/green/blue cards for each red/green/blue segment in the path or you don't. With the code as it stands now, I can find all paths between two given cities and get back how many train cards of each color are needed to take that particular path, unless the paths involve gray segments. (There are edge cases involving tunnels and ferries, but we'll leave those aside for now.) These colors correspond to the color of train lines on the game board ( shown here) except for the gray lines, where you can use any color, as long as all cars in the segment are the same color. I think it's more of a math problem than a programming problem per se, and I can probably piece together a brute force method for figuring things out, but thought there must be a more efficient way.įor those who don't know the game: at any given time, each player has a number of train cards in one of eight colors, plus a special "locomotive" category that serves as a wild card. The one part I'm having trouble with is analyzing whether a particular path through the board is possible given an inventory of train cards the player possesses. The game board is essentially a weighted multigraph, so replicating the basic structure of the game with NetworkX was a cinch. I enjoy playing Ticket to Ride, so I decided to play around with implementing parts of the game logic in Python as a side programming project.
0 Comments
Leave a Reply. |