„Die Legenden von Andor“ ist schon seit einiger Zeit eines meiner Lieblingsspiele. Vor kurzem haben wir das Spiel jetzt auch einer Freundin zum Geburtstag geschenkt. Brettspiele sind ja dank Corona voll im Trend 🙂
Wie es sich seit einiger Zeit bei uns eingebürgert hatte, musste es natürlich auch ein passendes Rätsel dazu geben. Mit ein bisschen Überlegung sind mir ein paar spannende Rätsel mit steigender Schwierigkeit eingefallen. Das erste lässt sich noch im Kopf lösen, aber für die anderen kann ein bisschen Computer-Unterstützung nicht schaden.
Die Legenden von Andor spielt auf einer (von Michael Menzel wunderbar gestalteten!) Karte aus Feldern, die teilweise aneinander angrenzen. Im Spiel kann jeder Held sich pro „Stunde“ ein Feld weiter bewegen. Das erste Rätsel war also schnell erdacht: Wie lang ist der kürzeste Weg von der Burg (Feld 0) zum Baum der Lieder (Feld 57)?
Als Informatiker klingelt bei „kürzester Pfad“ natürlich etwas: Das geht „einfach“ in O(n*log(n)) mit dem Dijkstra-Algorithmus. Praktischerweise gibt es davon (mehr als) eine fertige Implementierung in Python. Dann basteln wir also mal ein bisschen Python-Code 🙂
Als erstes brauchen wir dafür ein Liste mit allen Feldern und ihren direkten Nachbarn. Mit ein bisschen Hilfe von meiner Freundin (Danke! ❤️) hatte ich dann recht bald ganz viele Zahlen abgetippt:
map = {
0: [7, 11, 6, 2, 1, 4, 5],
1: [0, 2, 3, 4],
2: [0, 6, 14, 3, 1],
3: [1, 2, 14, 10, 19, 20, 4],
4: [0, 1, 3, 20, 21, 5],
5: [0, 4, 21],
6: [0, 11, 13, 17, 14, 2],
7: [15, 9, 8, 11, 0],
8: [9, 11, 7],
9: [8, 7, 15],
10: [3, 14, 18, 19],
11: [8, 12, 13, 6, 0, 7],
12: [11, 13],
13: [12, 16, 17, 6, 11],
14: [6, 17, 18, 10, 3, 2],
15: [9, 7],
16: [13, 32, 38, 36, 17, 48],
17: [6, 13, 16, 36, 18, 14],
18: [14, 17, 36, 28, 72, 19, 10],
19: [3, 10, 18, 72, 23, 22, 20],
20: [4, 3, 19, 22, 21],
21: [5, 4, 20, 22, 24],
22: [20, 19, 23, 24, 21],
23: [19, 72, 34, 35, 31, 25, 24, 22],
24: [21, 22, 23, 25],
25: [24, 23, 31, 27, 26],
26: [27, 25],
27: [25, 31, 26],
28: [36, 38, 29, 72, 18],
29: [72, 28, 30, 34],
30: [29, 33, 35, 34],
31: [23, 35, 33, 27, 25],
32: [38, 16],
33: [35, 30, 31],
34: [72, 29, 30, 35, 23],
35: [23, 34, 30, 33, 31],
36: [17, 16, 38, 28, 18],
37: [41],
38: [32, 39, 28, 36, 16],
39: [42, 43, 40, 38],
40: [39, 41],
41: [40, 37],
42: [44, 43, 39],
43: [45, 71, 39, 42, 44],
44: [46, 45, 43, 42],
45: [64, 65, 43, 44, 46],
46: [47, 64, 45, 44],
47: [53, 54, 56, 46, 48],
48: [49, 50, 51, 53, 47, 16],
49: [50, 48],
50: [52, 51, 48, 49],
51: [55, 53, 48, 50, 52],
52: [55, 51, 50],
53: [55, 54, 47, 48, 51],
54: [55, 57, 56, 47, 53],
55: [57, 54, 53, 51, 52],
56: [57, 63, 47, 54],
57: [59, 58, 63, 56, 54, 55],
58: [59, 60, 62, 61, 63, 57],
59: [60, 58, 57],
60: [62, 58, 59],
61: [62, 64, 63, 58],
62: [60, 61, 58],
63: [58, 61, 64, 56, 57],
64: [63, 61, 65, 45, 46],
65: [64, 66, 45],
66: [65, 67],
67: [66, 68],
68: [67, 69],
69: [68, 70],
70: [69, 81],
71: [43],
72: [18, 28, 29, 34, 23, 19],
80: [],
81: [70, 82],
82: [81, 84],
83: [],
84: [82]
}
Aus diesen Informationen können wir nun den Graphen bauen, den die „Dijkstar“-Bibliothek braucht. Jede Kannte muss hier in beide Richtungen hinzugefügt werden, weil der Algorithmus grundsätzlich auf gerichteten Graphen arbeitet. Das Gewicht jeder Kante (der dritte Parameter von add_edge) wird auf 1 gesetzt, da ja jeder Schritt gleich teuer ist (nämlich eine Stunde dauert). Vorher bietet es sich noch mal an, zu überprüfen, dass alle Nachbarschaftsbeziehungen auch in beide Richtungen existieren (damit habe ich tatsächlich drei Fehler gefunden…)
import dijkstar
def check_map(map):
"""Check that every connection exists in both directions."""
for start, adj_list in map.items():
for dest in adj_list:
if not start in map[dest]:
raise(Exception("Error found for {}->{}".format(start, dest)))
def build_graph(map):
graph = dijkstar.Graph()
for start, adj_list in map.items():
for dest in adj_list:
graph.add_edge(start, dest, 1)
return graph
check_map(map)
graph = build_graph(map)
Nun ist es tatsächlich nicht mehr schwer, den Weg zu berechnen:
keep_field = 0
tree_field = 57
keep_to_tree = dijkstar.find_path(graph, keep_field, tree_field)
print("Way from keep to tree:")
print(keep_to_tree)
Die Funktion find_path gibt dabei ein PathInfo Objekt zurück, was man einfach mit print auf der Konsole ausgeben kann. Damit erfahren wir dann, dass der (bzw. ein) kürzester Weg 7 Felder lang ist, und über die Felder 0, 11, 13, 16, 48, 51, 55 und 57 führt.
Und schon ist das erste Rätsel gelöst!
2 Gedanken zu „Informatik mit den „Legenden von Andor“ und Python“