-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathroad_map.go
268 lines (230 loc) · 7.56 KB
/
road_map.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
package main
import (
"fmt"
"regexp"
"sort"
"strings"
)
// We can use *CityRoads as an identifier for the city. We can compare pointers sometimes.
type CityName string
type CityRoads struct {
north *City
east *City
south *City
west *City
}
type City struct {
aliens CityAliens
roads CityRoads
}
type RoadMap map[CityName]*City
// Are roads automatically two-way? Suppose the map says Foo has north=Bar, but
// Bar doesn't have south=Foo. Should I assume:
//
// * Bar south=Foo implicitly
// * A one-way road north from Foo to Bar
// * An invalid file
//
// I don't want to assume the implicit two-way, because then I'd need to assume
// that the map is actually laid out on a nice grid, roads don't curve, etc. I
// don't want to assume one-way roads, that doesn't make as much sense. I will
// assume the file is invalid if there isn't a reference back, even if it's not
// coming from the opposite direction. I.e. a road north from Foo can come in
// from the east of Bar.
// Each city name should be alphanumeric or underscore
func parseMap(input string) (roadMap RoadMap, err error) {
roadMap = make(RoadMap)
// Loop over input once to just look at the cities being defined, to create
// the empty city stucts. Having this as a separate step makes it easier to
// check for duplicate cities or later check for references to nonexistent
// cities.
for _, line := range strings.Split(input, "\n") {
line = strings.TrimSpace(line)
segments := strings.Split(line, " ")
// Allow empty lines
if len(segments) == 1 && len(segments[0]) == 0 {
continue
}
subjectName := CityName(segments[0])
re := regexp.MustCompile(`^\w+$`)
if !re.Match([]byte(subjectName)) {
err = fmt.Errorf("Invalid line in initial map (invalid city name): " + line)
return
}
if _, ok := roadMap[subjectName]; ok {
err = fmt.Errorf("Invalid line in initial map (repeated city): " + line)
return
}
// Initialize a new city at this name in the roadMap
newCity := City{roads: CityRoads{}}
roadMap[subjectName] = &newCity
}
// Loop over input a second time to make the connections between cities
for _, line := range strings.Split(input, "\n") {
line = strings.TrimSpace(line)
segments := strings.Split(line, " ")
// Allow empty lines
if len(segments) < 1 {
continue
}
// The subject is the city we're making roads to and from
subjectName := CityName(segments[0])
subject := roadMap[subjectName]
for _, road := range segments[1:] {
// Each road is in the form of "direction=destinationName"
roadParts := strings.Split(road, "=")
if len(roadParts) != 2 {
err = fmt.Errorf("Invalid line in initial map (expecting one = in road description): " + line)
return
}
direction := roadParts[0]
destinationName := CityName(roadParts[1])
if _, ok := roadMap[destinationName]; !ok {
err = fmt.Errorf("Invalid line in initial map (road to undefined city): " + line)
return
}
destination := roadMap[destinationName]
if subject == destination {
err = fmt.Errorf("Invalid line in initial map (road from city to itself): " + line)
return
}
if subject.roads.north == destination ||
subject.roads.east == destination ||
subject.roads.south == destination ||
subject.roads.west == destination {
err = fmt.Errorf("Invalid line in initial map (two roads to the same town): " + line)
return
}
switch direction {
case "north":
if subject.roads.north != nil {
err = fmt.Errorf("Invalid line in initial map (road direction repeated): " + line)
return
}
subject.roads.north = destination
case "east":
if subject.roads.east != nil {
err = fmt.Errorf("Invalid line in initial map (road direction repeated): " + line)
return
}
subject.roads.east = destination
case "south":
if subject.roads.south != nil {
err = fmt.Errorf("Invalid line in initial map (road direction repeated): " + line)
return
}
subject.roads.south = destination
case "west":
if subject.roads.west != nil {
err = fmt.Errorf("Invalid line in initial map (road direction repeated): " + line)
return
}
subject.roads.west = destination
default:
err = fmt.Errorf("Invalid line in initial map (invalid direction): " + line)
return
}
}
}
// Loop over the results to make sure no one-way roads
// This function checks whether a given city is connected to another city
isHalfConnectedCity := func(subject *City, destination *City) bool {
// If the destination is nil in the first place, it's not a
// city, therefore not a half-connected city.
if destination == nil {
return false
}
// If none of the directions from destination go back to the
// subject, destination is half-connected
return !(destination.roads.north == subject ||
destination.roads.east == subject ||
destination.roads.south == subject ||
destination.roads.west == subject)
}
for _, city := range roadMap {
// Confirm that every connected city connects back
if isHalfConnectedCity(city, city.roads.north) ||
isHalfConnectedCity(city, city.roads.east) ||
isHalfConnectedCity(city, city.roads.south) ||
isHalfConnectedCity(city, city.roads.west) {
err = fmt.Errorf("Invalid initial map (some roads are not connected on both ends)")
return
}
}
if len(roadMap) == 0 {
err = fmt.Errorf("Invalid initial map (empty)")
return
}
return
}
func (rm RoadMap) outputMap() (output string) {
// Sort the city names so we get predictable output
var orderedCityNames sort.StringSlice
for cityName, _ := range rm {
// Cast it to string so that we can use the string sorting function
orderedCityNames = append(orderedCityNames, string(cityName))
}
sort.Sort(orderedCityNames)
// A rare case that we want a city name given a city
nameByCity := make(map[*City]string)
for cityName, city := range rm {
// We'll use it for output so let's just cast it to string now
nameByCity[city] = string(cityName)
}
for i, cn := range orderedCityNames {
output += cn
// Cast it back to CityName
cityName := CityName(cn)
roads := rm[cityName].roads
if roads.north != nil {
output += " north=" + nameByCity[roads.north]
}
if roads.east != nil {
output += " east=" + nameByCity[roads.east]
}
if roads.south != nil {
output += " south=" + nameByCity[roads.south]
}
if roads.west != nil {
output += " west=" + nameByCity[roads.west]
}
// Newline if it's not the last line
if i < len(orderedCityNames)-1 {
output += "\n"
}
}
return
}
func (rm RoadMap) destroyCity(cityName CityName) {
city := rm[cityName]
message := fmt.Sprintf("%s has been destroyed by %s!", cityName, city.aliens.englishList())
// This function deletes a connection from the given city to another city
deleteConnections := func(subject *City, destination *City) {
// If the destination is nil in the first place, it's not a
// city, therefore nothing to destroy.
if destination == nil {
return
}
// Find the road back to the subject and delete the connection
// in that direction
if destination.roads.north == subject {
destination.roads.north = nil
}
if destination.roads.east == subject {
destination.roads.east = nil
}
if destination.roads.south == subject {
destination.roads.south = nil
}
if destination.roads.west == subject {
destination.roads.west = nil
}
}
// Delete all roads back the city, then delete the city itself.
deleteConnections(city, city.roads.north)
deleteConnections(city, city.roads.east)
deleteConnections(city, city.roads.south)
deleteConnections(city, city.roads.west)
delete(rm, cityName)
fmt.Println(message)
}