#board-game #max-score #ticket-to-ride

bin+lib ticket2ride

A small program to compute the theoretically largest score in ticket to ride Europe

6 releases

0.3.1 Nov 7, 2021
0.3.0 Nov 3, 2021
0.2.8 Nov 1, 2021
0.2.7 Oct 31, 2021

#37 in #board-game

Apache-2.0

45KB
899 lines

Ticket2ride project

Purpose

This project started as a mind exercise, when I asked myself what the largest theoretical score in this game could be. Before I started this, I read in a few places opinions about high score routes, but there was no evidence if these where the optimum solutions. So I told myself, this is a nice project to work on my programming skills in rust and in exploring algorithms for solving this.

Architecture

This is the first attempt and no specific algorithmic logic is used, only brute force, basically.

The user, when executing the cli program, can provide the starting city for the algorithm with the -c or --city option. If no city if provided or if the city provided is non existent, then Edinburgh is used by default.

The program execution consists of two steps. In the first step, all possible routes are explored, starting from the initial city. In the second step, all these possible routes are scored, and then the route with the highest score is found.

The correctness of the program is not certain. It seems to create valid routes and after fixing a logic bug, the score is correct, taking into account:

  • one of the big tickets
  • all small tickets that are covered
  • the score of the trains used to connect the route
  • the score of 10 for the express bonus
  • the score of 12 for three unused stations

Also, I guess because of the use of HashMaps, the maximum number of routes computed each time differs. My reasoning is that because HashMaps are not ordered and each time the way that are stored in memory is kind of arbitrary, the computed routes differ also. Maybe there is some bug in my logic there that I need to check.

One final consideration is that all routes start from the initial city and no route is created where the initial city is in the middle of a route.

Future considerations

This that I could do in the future:

  • Add color of routes
  • Experiment with different algorithms for traversing the network
  • Use stations for fulfilling more tickets

Dependencies

~3.5MB
~55K SLoC