-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.go
202 lines (169 loc) · 4.17 KB
/
main.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
package main
import (
"bufio"
"flag"
"fmt"
"os"
"strconv"
"strings"
)
type Point struct {
x int
y int
}
func main() {
// Use Flags to run a part
methodP := flag.String("method", "p1", "The method/part that should be run, valid are p1,p2 and test")
flag.Parse()
switch *methodP {
case "p1":
PartOne()
break
case "p2":
PartTwo()
break
case "test":
break
}
}
func PartOne() {
input := readInput()
largestArea := FindLargestArea(input)
fmt.Printf("The largest area is %v\n", largestArea)
}
func PartTwo() {
//input := readInput()
}
func FindLargestArea(points []Point) int {
largestArea := 0
checkPoints := FindInfinitePoints(points)
// Find number of closest neighbours for point
sizeMap := make(map[Point]int)
for _, point := range checkPoints {
areaSize := FindNumClosestNeighbours(point, points)
sizeMap[point] = areaSize
if areaSize > largestArea {
largestArea = areaSize
}
}
fmt.Println(sizeMap)
return largestArea
}
// Remove any points that have an "infinite area", check if they are closest to one of the edge points of the grid
func FindInfinitePoints(points []Point) []Point {
checkPoints := make([]Point, len(points))
copy(checkPoints, points)
// First find out the area we are dealing with, dont want to consider any points that have infinite area
// Figure out max X and Y, then do closest neighbours on all edge points, and remove the points that are associated with them
xmax := FindMax(1, points)
ymax := FindMax(2, points)
edgePoints := make([]Point, 0)
for i := 0; i <= xmax; i++ {
for j := 0; j <= ymax; j++ {
if i == 0 || j == 0 || i == xmax || j == ymax {
//Add this point to check points list
edgePoints = append(edgePoints, Point{i, j})
}
}
}
// Now that we have all the edge points
// Find the list of nearest neighbours for each of those points, then remove them
for _, point := range edgePoints {
closest := FindClosestNeighbour(point, points)
// Remove this from our checkPoints list
for i, checkPoint := range checkPoints {
if checkPoint == closest {
checkPoints = append(checkPoints[:i], checkPoints[i+1:]...)
}
}
}
return checkPoints
}
// FindMax for x and y
func FindMax(field int, points []Point) int {
highest := 0
switch field {
case 1:
for _, point := range points {
if point.x > highest {
highest = point.x
}
}
case 2:
for _, point := range points {
if point.y > highest {
highest = point.y
}
}
}
return highest
}
// Find number of Closest neighbours for a point
func FindNumClosestNeighbours(neighbour Point, points []Point) int {
xmax := FindMax(1, points)
ymax := FindMax(2, points)
areaSize := 0
for i := 0; i < xmax; i++ {
for j := 0; j < ymax; j++ {
if (FindClosestNeighbour(Point{i, j}, points) == neighbour) {
areaSize++
}
}
}
return areaSize
}
// Find out which is the closest neighbour to the gridpoint
func FindClosestNeighbour(gridPoint Point, neighbours []Point) Point {
closestPoint := neighbours[0]
closestDelta := ManhattenDistance(closestPoint, gridPoint)
var deltaList []int
for _, point := range neighbours {
delta := ManhattenDistance(point, gridPoint)
if delta < closestDelta {
closestPoint = point
closestDelta = delta
}
deltaList = append(deltaList, delta)
}
// Only check if we have two of the closest distances already
found := 0
for deltaL := range deltaList {
if closestDelta == deltaL {
found++
}
}
if found > 1 {
return Point{-1, -1}
}
return closestPoint
}
// Figure out the Manhatten Distance between two points
func ManhattenDistance(firstPoint Point, secondPoint Point) int {
x := abs(firstPoint.x - secondPoint.x)
y := abs(firstPoint.y - secondPoint.y)
return x + y
}
// Absoulute value of Int
func abs(x int) int {
if x < 0 {
return -x
} else {
return x
}
}
// Read data from input.txt
// Load it into points array
func readInput() []Point {
var input []Point
f, _ := os.Open("input.txt")
scanner := bufio.NewScanner(f)
for scanner.Scan() {
if scanner.Text() != "" {
values := strings.Split(scanner.Text(), ",")
x, _ := strconv.Atoi(values[0])
y, _ := strconv.Atoi(strings.Trim(values[1], " "))
input = append(input, Point{x, y})
}
}
return input
}