8000 Solve 2018 day 6 part 1 · sim642/adventofcode@23a3e1e · GitHub
[go: up one dir, main page]
Skip to content

Commit 23a3e1e

Browse files
sim642sim642
committed
Solve 2018 day 6 part 1
1 parent 4cb4289 commit 23a3e1e

File tree

3 files changed

+121
-0
lines changed

3 files changed

+121
-0
lines changed

‎src/main/resources/eu/sim642/adventofcode2018/day6.txt

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
260, 78
2+
42, 40
3+
87, 276
4+
219, 124
5+
166, 137
6+
341, 138
7+
82, 121
8+
114, 174
9+
218, 289
10+
61, 358
11+
328, 164
12+
279, 50
13+
218, 107
14+
273, 320
15+
192, 349
16+
354, 103
17+
214, 175
18+
128, 196
19+
237, 67
20+
333, 150
21+
98, 260
22+
166, 217
23+
92, 212
24+
55, 165
25+
205, 138
26+
321, 199
27+
285, 148
28+
217, 130
29+
357, 319
30+
160, 67
31+
63, 75
32+
345, 123
33+
316, 220
34+
41, 253
35+
240, 245
36+
201, 124
37+
336, 166
38+
95, 301
39+
55, 181
40+
219, 315
41+
209, 237
42+
317, 254
43+
314, 300
44+
242, 295
45+
295, 293
46+
285, 263
47+
330, 204
48+
112, 106
49+
348, 49
50+
81, 185

‎src/main/scala/eu/sim642/adventofcode2018/Day6.scala

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package eu.sim642.adventofcode2018
2+
3+
import eu.sim642.adventofcode2017.Day3.Pos
4+
5+
object Day6 {
6+
7+
def largestFiniteArea(coords: Set[Pos]): Int = {
8+
def closestCoord(pos: Pos): Option[Pos] = {
9+
val Seq((coord1, d1), (coord2, d2)) = coords.toSeq.map(coord => coord -> (coord manhattanDistance pos)).sortBy(_._2).take(2) // TODO: optimize taking only smallest 2
10+
if (d1 < d2)
11+
Some(coord1)
12+
else
13+
None
14+
}
15+
16+
val minX = coords.minBy(_.x).x
17+
val minY = coords.minBy(_.y).y
18+
val maxX = coords.maxBy(_.x).x
19+
val maxY = coords.maxBy(_.y).y
20+
21+
// TODO: optimize with BFS
22+
val grid = (for {
23+
x <- minX to maxX
24+
y <- minY to maxY
25+
pos = Pos(x, y)
26+
coord <- closestCoord(pos)
27+
} yield pos -> coord).toMap
28+
29+
val finiteGrid = grid.filterKeys(pos => pos.x != minX && pos.x != maxX && pos.y != minY && pos.y != maxY)
30+
val finiteSizes = finiteGrid.groupBy(_._2).mapValues(_.size)
31+
finiteSizes.values.max
32+
}
33+
34+
private val coordRegex = """(\d+), (\d+)""".r
35+
36+
def parseCoord(s: String): Pos = s match {
37+
case coordRegex(x, y) => Pos(x.toInt, y.toInt)
38+
}
39+
40+
def parseCoords(input: String): Set[Pos] = input.lines.map(parseCoord).toSet
41+
42+
43+
lazy val input: String = io.Source.fromInputStream(getClass.getResourceAsStream("day6.txt")).mkString.trim
44+
45+
def main(args: Array[String]): Unit = {
46+
println(largestFiniteArea(parseCoords(input)))
47+
}
48+
}

‎src/test/scala/eu/sim642/adventofcode2018/Day6Test.scala

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package eu.sim642.adventofcode2018
2+
3+
import org.scalatest.FunSuite
4+
import Day6._
5+
6+
class Day6Test extends FunSuite {
7+
8+
val exampleInput =
9+
"""1, 1
10+
|1, 6
11+
|8, 3
12+
|3, 4
13+
|5, 5
14+
|8, 9""".stripMargin
15+
16+
test("Part 1 examples") {
17+
assert(largestFiniteArea(parseCoords(exampleInput)) == 17)
18+
}
19+
20+
test("Part 1 input answer") {
21+
assert(largestFiniteArea(parseCoords(input)) == 4771)
22+
}
23+
}

0 commit comments

Comments
 (0)
0