ticket2ride/
lib.rs

1#![warn(missing_docs)]
2//! This project contains data structures for representing the ticket
3//! to ride Europe edition game and some functions for computing
4//! possible routes and their respective scores.
5//!
6//! Here I provide some enumerations and hash maps that are required
7//! for representing the ticket to ride Europe game in my code. The
8//! functions for computing routes and scores are included in the
9//! respective modules.
10
11use std::collections::HashMap;
12use std::str::FromStr;
13use strum_macros::EnumIter;
14
15pub mod routing;
16pub mod scoring;
17/// All available cities of the game are included into this handy
18/// enumeration, so that my code is more clear. The cities are not
19/// entered with any particular order, I just started from Edinburgh
20/// and traversed the map gradually most of the times randomly.
21#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy, EnumIter)]
22pub enum City {
23    /// These are all cities included in the board game of Ticket to
24    /// Ride, Europe edition. They don't have a specific meaning to be
25    /// documented, other than that they are a nice way to keep track
26    /// for me.
27    Edinburgh,
28    ///
29    London,
30    ///
31    Dieppe,
32    ///
33    Amsterdam,
34    ///
35    Brest,
36    ///
37    Paris,
38    ///
39    Bruxelles,
40    ///
41    Essen,
42    ///
43    Frankfurt,
44    ///
45    Pamplona,
46    ///
47    Zuerich,
48    ///
49    Marseille,
50    ///
51    Kobenhavn,
52    ///
53    Berlin,
54    ///
55    Muenchen,
56    ///
57    Madrid,
58    ///
59    Barcelona,
60    ///
61    Venezia,
62    ///
63    Roma,
64    ///
65    Stockholm,
66    ///
67    Danzig,
68    ///
69    Warszawa,
70    ///
71    Wien,
72    ///
73    Lisboa,
74    ///
75    Cadiz,
76    ///
77    Zagrab,
78    ///
79    Brindisi,
80    ///
81    Palermo,
82    ///
83    Petrograd,
84    ///
85    Riga,
86    ///
87    Wilno,
88    ///
89    Kyiv,
90    ///
91    Budapest,
92    ///
93    Sarajevo,
94    ///
95    Athina,
96    ///
97    Smyrna,
98    ///
99    Moskva,
100    ///
101    Smolensk,
102    ///
103    Kharkov,
104    ///
105    Bucuresti,
106    ///
107    Sofia,
108    ///
109    Constantinople,
110    ///
111    Angora,
112    ///
113    Rostov,
114    ///
115    Sevastopol,
116    ///
117    Erzurum,
118    ///
119    Sochi,
120}
121
122/// The FromStr trait gives to the enumeration the handy from_str
123/// function that is used to convert a string (provided by command
124/// line arguments) to a City. I had to map each string to the
125/// specific city.
126/// # Example
127///
128/// ```
129/// # use ticket2ride::City;
130/// # use std::str::FromStr;
131/// let start_city = "Athina"; // This could come from clap
132/// let begin = City::from_str(start_city).unwrap();
133/// ```
134impl FromStr for City {
135    type Err = ();
136
137    fn from_str(input: &str) -> Result<City, Self::Err> {
138        match input {
139            "Edinburgh" => Ok(City::Edinburgh),
140            "London" => Ok(City::London),
141            "Dieppe" => Ok(City::Dieppe),
142            "Amsterdam" => Ok(City::Amsterdam),
143            "Brest" => Ok(City::Brest),
144            "Paris" => Ok(City::Paris),
145            "Bruxelles" => Ok(City::Bruxelles),
146            "Essen" => Ok(City::Essen),
147            "Frankfurt" => Ok(City::Frankfurt),
148            "Pamplona" => Ok(City::Pamplona),
149            "Zuerich" => Ok(City::Zuerich),
150            "Marseille" => Ok(City::Marseille),
151            "Kobenhavn" => Ok(City::Kobenhavn),
152            "Berlin" => Ok(City::Berlin),
153            "Muenchen" => Ok(City::Muenchen),
154            "Madrid" => Ok(City::Madrid),
155            "Barcelona" => Ok(City::Barcelona),
156            "Venezia" => Ok(City::Venezia),
157            "Roma" => Ok(City::Roma),
158            "Stockholm" => Ok(City::Stockholm),
159            "Danzig" => Ok(City::Danzig),
160            "Warszawa" => Ok(City::Warszawa),
161            "Wien" => Ok(City::Wien),
162            "Lisboa" => Ok(City::Lisboa),
163            "Cadiz" => Ok(City::Cadiz),
164            "Zagrab" => Ok(City::Zagrab),
165            "Brindisi" => Ok(City::Brindisi),
166            "Palermo" => Ok(City::Palermo),
167            "Petrograd" => Ok(City::Petrograd),
168            "Riga" => Ok(City::Riga),
169            "Wilno" => Ok(City::Wilno),
170            "Kyiv" => Ok(City::Kyiv),
171            "Budapest" => Ok(City::Budapest),
172            "Sarajevo" => Ok(City::Sarajevo),
173            "Athina" => Ok(City::Athina),
174            "Smyrna" => Ok(City::Smyrna),
175            "Moskva" => Ok(City::Moskva),
176            "Smolensk" => Ok(City::Smolensk),
177            "Kharkov" => Ok(City::Kharkov),
178            "Bucuresti" => Ok(City::Bucuresti),
179            "Sofia" => Ok(City::Sofia),
180            "Constantinople" => Ok(City::Constantinople),
181            "Angora" => Ok(City::Angora),
182            "Rostov" => Ok(City::Rostov),
183            "Sevastopol" => Ok(City::Sevastopol),
184            "Erzurum" => Ok(City::Erzurum),
185            "Sochi" => Ok(City::Sochi),
186            _ => Err(()),
187        }
188    }
189}
190
191/// The struct for representing a game ticket which includes the
192/// departure city, the arrival city and the value of the ticket when
193/// it is satisfied. This struct is used for both regular tickets and
194/// the six big tickets.
195#[derive(Debug)]
196pub struct Ticket {
197    /// The departing city of the ticket
198    pub depart: City,
199    /// The arriving city of the ticket
200    pub arrive: City,
201    /// The value of the ticket that counts towards the total score
202    /// for the game (provided that the ticket is served in a normal
203    /// game)
204    pub value: u8,
205}
206
207impl Ticket {
208    /// The constructor of a Ticket struct
209    /// # Example
210    ///
211    /// ```
212    /// # use ticket2ride::{City, Ticket};
213    /// let small_ticket = Ticket::new(City::Edinburgh, City::Athina, 20);
214    /// ```
215    pub fn new(depart: City, arrive: City, value: u8) -> Ticket {
216        return Ticket {
217            depart,
218            arrive,
219            value,
220        };
221    }
222}
223
224/// This function creates the game network. This is a Hash map of
225/// which the keys are the cities of the game and the value of each
226/// key is a Hash map of the cities that the key city can connect with
227/// and the number of trains that are needed to connect to that city.
228///
229/// destination HashMap is used to fill it in with all the relevant
230/// destinations of a city each time, and when it is cloned in the
231/// network HashMap as the value of the key, it is cleared and reused
232/// for the next city's destinations.
233pub fn create_network() -> HashMap<City, HashMap<City, u8>> {
234    let mut network = HashMap::<City, HashMap<City, u8>>::new();
235
236    let mut destination = HashMap::<City, u8>::new();
237
238    destination.insert(City::London, 4);
239    network.insert(City::Edinburgh, destination.clone());
240    destination.clear();
241
242    destination.insert(City::Edinburgh, 4);
243    destination.insert(City::Dieppe, 2);
244    destination.insert(City::Amsterdam, 2);
245    network.insert(City::London, destination.clone());
246    destination.clear();
247
248    destination.insert(City::Paris, 1);
249    destination.insert(City::London, 2);
250    destination.insert(City::Brest, 2);
251    destination.insert(City::Bruxelles, 2);
252    network.insert(City::Dieppe, destination.clone());
253    destination.clear();
254
255    destination.insert(City::Essen, 3);
256    destination.insert(City::Frankfurt, 2);
257    destination.insert(City::London, 2);
258    destination.insert(City::Bruxelles, 1);
259    network.insert(City::Amsterdam, destination.clone());
260    destination.clear();
261
262    destination.insert(City::Dieppe, 2);
263    destination.insert(City::Paris, 3);
264    destination.insert(City::Pamplona, 4);
265    network.insert(City::Brest, destination.clone());
266    destination.clear();
267
268    destination.insert(City::Brest, 3);
269    destination.insert(City::Dieppe, 1);
270    destination.insert(City::Bruxelles, 2);
271    destination.insert(City::Frankfurt, 3);
272    destination.insert(City::Zuerich, 3);
273    destination.insert(City::Marseille, 4);
274    destination.insert(City::Pamplona, 4);
275    network.insert(City::Paris, destination.clone());
276    destination.clear();
277
278    destination.insert(City::Paris, 2);
279    destination.insert(City::Dieppe, 2);
280    destination.insert(City::Amsterdam, 1);
281    destination.insert(City::Frankfurt, 2);
282    network.insert(City::Bruxelles, destination.clone());
283    destination.clear();
284
285    destination.insert(City::Amsterdam, 3);
286    destination.insert(City::Kobenhavn, 3);
287    destination.insert(City::Berlin, 2);
288    destination.insert(City::Frankfurt, 2);
289    network.insert(City::Essen, destination.clone());
290    destination.clear();
291
292    destination.insert(City::Paris, 3);
293    destination.insert(City::Bruxelles, 2);
294    destination.insert(City::Amsterdam, 2);
295    destination.insert(City::Berlin, 3);
296    destination.insert(City::Muenchen, 2);
297    destination.insert(City::Essen, 2);
298    network.insert(City::Frankfurt, destination.clone());
299    destination.clear();
300
301    destination.insert(City::Madrid, 3);
302    destination.insert(City::Brest, 4);
303    destination.insert(City::Paris, 4);
304    destination.insert(City::Marseille, 4);
305    destination.insert(City::Barcelona, 2);
306    network.insert(City::Pamplona, destination.clone());
307    destination.clear();
308
309    destination.insert(City::Paris, 3);
310    destination.insert(City::Muenchen, 2);
311    destination.insert(City::Venezia, 2);
312    destination.insert(City::Marseille, 2);
313    network.insert(City::Zuerich, destination.clone());
314    destination.clear();
315
316    destination.insert(City::Barcelona, 4);
317    destination.insert(City::Pamplona, 4);
318    destination.insert(City::Paris, 4);
319    destination.insert(City::Zuerich, 2);
320    destination.insert(City::Roma, 4);
321    network.insert(City::Marseille, destination.clone());
322    destination.clear();
323
324    destination.insert(City::Essen, 3);
325    destination.insert(City::Stockholm, 3);
326    network.insert(City::Kobenhavn, destination.clone());
327    destination.clear();
328
329    destination.insert(City::Essen, 2);
330    destination.insert(City::Danzig, 4);
331    destination.insert(City::Warszawa, 4);
332    destination.insert(City::Wien, 3);
333    destination.insert(City::Frankfurt, 3);
334    network.insert(City::Berlin, destination.clone());
335    destination.clear();
336
337    destination.insert(City::Zuerich, 2);
338    destination.insert(City::Frankfurt, 2);
339    destination.insert(City::Wien, 3);
340    destination.insert(City::Venezia, 2);
341    network.insert(City::Muenchen, destination.clone());
342    destination.clear();
343
344    destination.insert(City::Lisboa, 3);
345    destination.insert(City::Pamplona, 3);
346    destination.insert(City::Barcelona, 2);
347    destination.insert(City::Cadiz, 3);
348    network.insert(City::Madrid, destination.clone());
349    destination.clear();
350
351    destination.insert(City::Madrid, 2);
352    destination.insert(City::Pamplona, 2);
353    destination.insert(City::Marseille, 4);
354    network.insert(City::Barcelona, destination.clone());
355    destination.clear();
356
357    destination.insert(City::Zuerich, 2);
358    destination.insert(City::Muenchen, 2);
359    destination.insert(City::Zagrab, 2);
360    destination.insert(City::Roma, 2);
361    network.insert(City::Venezia, destination.clone());
362    destination.clear();
363
364    destination.insert(City::Marseille, 4);
365    destination.insert(City::Venezia, 2);
366    destination.insert(City::Brindisi, 2);
367    destination.insert(City::Palermo, 4);
368    network.insert(City::Roma, destination.clone());
369    destination.clear();
370
371    destination.insert(City::Kobenhavn, 3);
372    destination.insert(City::Petrograd, 8);
373    network.insert(City::Stockholm, destination.clone());
374    destination.clear();
375
376    destination.insert(City::Berlin, 4);
377    destination.insert(City::Riga, 3);
378    destination.insert(City::Warszawa, 2);
379    network.insert(City::Danzig, destination.clone());
380    destination.clear();
381
382    destination.insert(City::Berlin, 4);
383    destination.insert(City::Danzig, 2);
384    destination.insert(City::Wilno, 3);
385    destination.insert(City::Kyiv, 4);
386    destination.insert(City::Wien, 4);
387    network.insert(City::Warszawa, destination.clone());
388    destination.clear();
389
390    destination.insert(City::Muenchen, 3);
391    destination.insert(City::Berlin, 3);
392    destination.insert(City::Warszawa, 4);
393    destination.insert(City::Budapest, 1);
394    destination.insert(City::Zagrab, 2);
395    network.insert(City::Wien, destination.clone());
396    destination.clear();
397
398    destination.insert(City::Madrid, 3);
399    destination.insert(City::Cadiz, 2);
400    network.insert(City::Lisboa, destination.clone());
401    destination.clear();
402
403    destination.insert(City::Madrid, 3);
404    destination.insert(City::Lisboa, 2);
405    network.insert(City::Cadiz, destination.clone());
406    destination.clear();
407
408    destination.insert(City::Venezia, 2);
409    destination.insert(City::Wien, 2);
410    destination.insert(City::Budapest, 2);
411    destination.insert(City::Sarajevo, 3);
412    network.insert(City::Zagrab, destination.clone());
413    destination.clear();
414
415    destination.insert(City::Roma, 2);
416    destination.insert(City::Athina, 4);
417    destination.insert(City::Palermo, 3);
418    network.insert(City::Brindisi, destination.clone());
419    destination.clear();
420
421    destination.insert(City::Roma, 4);
422    destination.insert(City::Brindisi, 3);
423    destination.insert(City::Smyrna, 6);
424    network.insert(City::Palermo, destination.clone());
425    destination.clear();
426
427    destination.insert(City::Stockholm, 8);
428    destination.insert(City::Riga, 4);
429    destination.insert(City::Wilno, 4);
430    destination.insert(City::Moskva, 4);
431    network.insert(City::Petrograd, destination.clone());
432    destination.clear();
433
434    destination.insert(City::Danzig, 3);
435    destination.insert(City::Petrograd, 4);
436    destination.insert(City::Wilno, 4);
437    network.insert(City::Riga, destination.clone());
438    destination.clear();
439
440    destination.insert(City::Warszawa, 3);
441    destination.insert(City::Riga, 4);
442    destination.insert(City::Petrograd, 4);
443    destination.insert(City::Smolensk, 3);
444    destination.insert(City::Kyiv, 2);
445    network.insert(City::Wilno, destination.clone());
446    destination.clear();
447
448    destination.insert(City::Warszawa, 4);
449    destination.insert(City::Wilno, 2);
450    destination.insert(City::Smolensk, 3);
451    destination.insert(City::Kharkov, 4);
452    destination.insert(City::Bucuresti, 4);
453    destination.insert(City::Budapest, 6);
454    network.insert(City::Kyiv, destination.clone());
455    destination.clear();
456
457    destination.insert(City::Wien, 1);
458    destination.insert(City::Kyiv, 6);
459    destination.insert(City::Bucuresti, 4);
460    destination.insert(City::Sarajevo, 3);
461    destination.insert(City::Zagrab, 2);
462    network.insert(City::Budapest, destination.clone());
463    destination.clear();
464
465    destination.insert(City::Zagrab, 3);
466    destination.insert(City::Budapest, 3);
467    destination.insert(City::Sofia, 2);
468    destination.insert(City::Athina, 4);
469    network.insert(City::Sarajevo, destination.clone());
470    destination.clear();
471
472    destination.insert(City::Brindisi, 4);
473    destination.insert(City::Sarajevo, 4);
474    destination.insert(City::Sofia, 3);
475    destination.insert(City::Smyrna, 2);
476    network.insert(City::Athina, destination.clone());
477    destination.clear();
478
479    destination.insert(City::Palermo, 6);
480    destination.insert(City::Athina, 2);
481    destination.insert(City::Constantinople, 2);
482    destination.insert(City::Angora, 3);
483    network.insert(City::Smyrna, destination.clone());
484    destination.clear();
485
486    destination.insert(City::Smolensk, 2);
487    destination.insert(City::Petrograd, 4);
488    destination.insert(City::Kharkov, 4);
489    network.insert(City::Moskva, destination.clone());
490    destination.clear();
491
492    destination.insert(City::Wilno, 3);
493    destination.insert(City::Moskva, 2);
494    destination.insert(City::Kyiv, 3);
495    network.insert(City::Smolensk, destination.clone());
496    destination.clear();
497
498    destination.insert(City::Kyiv, 4);
499    destination.insert(City::Moskva, 4);
500    destination.insert(City::Rostov, 2);
501    network.insert(City::Kharkov, destination.clone());
502    destination.clear();
503
504    destination.insert(City::Budapest, 4);
505    destination.insert(City::Kyiv, 4);
506    destination.insert(City::Sevastopol, 4);
507    destination.insert(City::Constantinople, 3);
508    destination.insert(City::Sofia, 2);
509    network.insert(City::Bucuresti, destination.clone());
510    destination.clear();
511
512    destination.insert(City::Sarajevo, 2);
513    destination.insert(City::Bucuresti, 2);
514    destination.insert(City::Constantinople, 3);
515    destination.insert(City::Athina, 3);
516    network.insert(City::Sofia, destination.clone());
517    destination.clear();
518
519    destination.insert(City::Sofia, 3);
520    destination.insert(City::Bucuresti, 3);
521    destination.insert(City::Sevastopol, 4);
522    destination.insert(City::Angora, 2);
523    destination.insert(City::Smyrna, 2);
524    network.insert(City::Constantinople, destination.clone());
525    destination.clear();
526
527    destination.insert(City::Smyrna, 3);
528    destination.insert(City::Constantinople, 2);
529    destination.insert(City::Erzurum, 3);
530    network.insert(City::Angora, destination.clone());
531    destination.clear();
532
533    destination.insert(City::Kharkov, 2);
534    destination.insert(City::Sevastopol, 4);
535    destination.insert(City::Sochi, 2);
536    network.insert(City::Rostov, destination.clone());
537    destination.clear();
538
539    destination.insert(City::Bucuresti, 4);
540    destination.insert(City::Rostov, 4);
541    destination.insert(City::Sochi, 2);
542    destination.insert(City::Erzurum, 4);
543    destination.insert(City::Constantinople, 4);
544    network.insert(City::Sevastopol, destination.clone());
545    destination.clear();
546
547    destination.insert(City::Sevastopol, 4);
548    destination.insert(City::Sochi, 3);
549    destination.insert(City::Angora, 3);
550    network.insert(City::Erzurum, destination.clone());
551    destination.clear();
552
553    destination.insert(City::Sevastopol, 2);
554    destination.insert(City::Rostov, 2);
555    destination.insert(City::Erzurum, 3);
556    network.insert(City::Sochi, destination.clone());
557    destination.clear();
558
559    network
560}
561
562/// This function returns a vector with the 6 big tickets of the
563/// game. Differentiating between big tickets and small tickets is not
564/// relevant for computing the max theoretical score but still it's
565/// nice to have it separately, for future stuff to come.
566pub fn get_big_tickets() -> Vec<Ticket> {
567    let big_tickets = vec![
568        Ticket::new(City::Brest, City::Petrograd, 20),
569        Ticket::new(City::Cadiz, City::Stockholm, 21),
570        Ticket::new(City::Edinburgh, City::Athina, 21),
571        Ticket::new(City::Kobenhavn, City::Erzurum, 21),
572        Ticket::new(City::Lisboa, City::Danzig, 20),
573        Ticket::new(City::Palermo, City::Moskva, 20),
574    ];
575
576    big_tickets
577}
578
579/// This returns a vector with the regular tickets of the game.
580pub fn get_tickets() -> Vec<Ticket> {
581    let tickets = vec![
582        Ticket::new(City::Amsterdam, City::Pamplona, 7),
583        Ticket::new(City::Amsterdam, City::Wilno, 12),
584        Ticket::new(City::Angora, City::Kharkov, 10),
585        Ticket::new(City::Athina, City::Angora, 5),
586        Ticket::new(City::Athina, City::Wilno, 11),
587        Ticket::new(City::Barcelona, City::Bruxelles, 8),
588        Ticket::new(City::Barcelona, City::Muenchen, 8),
589        Ticket::new(City::Berlin, City::Bucuresti, 8),
590        Ticket::new(City::Berlin, City::Moskva, 12),
591        Ticket::new(City::Berlin, City::Roma, 9),
592        Ticket::new(City::Brest, City::Marseille, 7),
593        Ticket::new(City::Brest, City::Venezia, 8),
594        Ticket::new(City::Bruxelles, City::Danzig, 9),
595        Ticket::new(City::Budapest, City::Sofia, 5),
596        Ticket::new(City::Edinburgh, City::Paris, 7),
597        Ticket::new(City::Essen, City::Kyiv, 10),
598        Ticket::new(City::Frankfurt, City::Kobenhavn, 5),
599        Ticket::new(City::Frankfurt, City::Smolensk, 13),
600        Ticket::new(City::Kyiv, City::Petrograd, 6),
601        Ticket::new(City::Kyiv, City::Sochi, 8),
602        Ticket::new(City::London, City::Berlin, 7),
603        Ticket::new(City::London, City::Wien, 10),
604        Ticket::new(City::Madrid, City::Dieppe, 8),
605        Ticket::new(City::Madrid, City::Zuerich, 8),
606        Ticket::new(City::Marseille, City::Essen, 8),
607        Ticket::new(City::Palermo, City::Constantinople, 8),
608        Ticket::new(City::Paris, City::Wien, 8),
609        Ticket::new(City::Paris, City::Zagrab, 7),
610        Ticket::new(City::Riga, City::Bucuresti, 10),
611        Ticket::new(City::Roma, City::Smyrna, 8),
612        Ticket::new(City::Rostov, City::Erzurum, 5),
613        Ticket::new(City::Sarajevo, City::Sevastopol, 8),
614        Ticket::new(City::Smolensk, City::Rostov, 8),
615        Ticket::new(City::Sofia, City::Smyrna, 5),
616        Ticket::new(City::Stockholm, City::Wien, 11),
617        Ticket::new(City::Venezia, City::Constantinople, 10),
618        Ticket::new(City::Warszawa, City::Smolensk, 6),
619        Ticket::new(City::Zagrab, City::Brindisi, 6),
620        Ticket::new(City::Zuerich, City::Brindisi, 6),
621        Ticket::new(City::Zuerich, City::Budapest, 6),
622    ];
623
624    tickets
625}
626
627/// This is a helper function the finds the maximum value in a HashMap
628/// and returns the key of that maximum value. This is basically used
629/// to find the path with the largest score in the possible paths
630/// computed from a specific starting city.
631pub fn max_key<K, V>(hash: &HashMap<K, V>) -> Option<&K>
632where
633    V: Ord,
634{
635    hash.iter().max_by(|a, b| a.1.cmp(&b.1)).map(|(k, _v)| k)
636}
637
638#[test]
639fn test_max_key() {
640    let mut some_routes = HashMap::<City, u16>::new();
641    some_routes.insert(City::London, 30);
642    some_routes.insert(City::Athina, 70);
643    some_routes.insert(City::Lisboa, 7);
644    some_routes.insert(City::Moskva, 69);
645
646    let largest_city = max_key(&some_routes).unwrap();
647    assert_eq!(*largest_city, City::Athina);
648}
ticket2ride/lib.rs

ticket2ride/
lib.rs
