Skip to content

Commit 5086f6f

Browse files
codeforkjeffcodeforkjeff
committed
day 15 part 1 and 2
1 parent 2ab319a commit 5086f6f

File tree

10 files changed

+407
-0
lines changed

10 files changed

+407
-0
lines changed

‎src/main/resources/day15/input.txt

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
################################
2+
##########################..####
3+
#########################...####
4+
#########################..#####
5+
########################G..#####
6+
#####################.#.....##.#
7+
#####################..........#
8+
##############.#####...........#
9+
########G...G#.####............#
10+
#######......G....#.....#......#
11+
#######...G....GG.#............#
12+
#######G.G.............####....#
13+
#######.#.....#####....E.....###
14+
#######......#######.G.......###
15+
#..####..G..#########.###..#####
16+
#........G..#########.##########
17+
#..#..#G....#########.##########
18+
#.###...E...#########.##########
19+
#####...G.G.#########.##########
20+
########G....#######..##########
21+
####..........#####...##########
22+
####......E........G..##########
23+
#.G..................###########
24+
#G...................###########
25+
###.....##E.......E..###########
26+
###....#............############
27+
###.................############
28+
##G.....#.............##########
29+
###########...#E..##..##########
30+
###########.E...###.E.EE.#######
31+
###########......#.......#######
32+
################################

‎src/main/resources/day15/testData1.txt

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
#######
2+
#.G...#
3+
#...EG#
4+
#.#.#G#
5+
#..G#E#
6+
#.....#
7+
#######

‎src/main/resources/day15/testData2.txt

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
#######
2+
#G..#E#
3+
#E#E.E#
4+
#G.##.#
5+
#...#E#
6+
#...E.#
7+
#######

‎src/main/resources/day15/testData3.txt

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
#######
2+
#E..EG#
3+
#.#G.E#
4+
#E.##E#
5+
#G..#.#
6+
#..E#.#
7+
#######

‎src/main/resources/day15/testData4.txt

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
#######
2+
#E.G#.#
3+
#.#G..#
4+
#G.#.G#
5+
#G..#.#
6+
#...E.#
7+
#######

‎src/main/resources/day15/testData5.txt

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
#######
2+
#.E...#
3+
#.#..G#
4+
#.###.#
5+
#E#G#G#
6+
#...#G#
7+
#######

‎src/main/resources/day15/testData6.txt

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
#########
2+
#G......#
3+
#.E.#...#
4+
#..##..G#
5+
#...##..#
6+
#...#...#
7+
#.G...G.#
8+
#.....G.#
9+
#########

‎src/main/scala/org/codefork/aoc2018/Day15.scala

Lines changed: 290 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,290 @@
1+
package org.codefork.aoc2018
2+
3+
import scala.annotation.tailrec
4+
import scala.io.Source
5+
6+
object Day15 {
7+
8+
case class XY(x: Int, y: Int)
9+
10+
sealed trait Thing {
11+
def xy: XY
12+
def isPerson: Boolean
13+
def isOpenSpace: Boolean
14+
}
15+
16+
// 'Unit' is a reserved word in scala so we use Person
17+
case class Person(xy: XY,
18+
personType: Char,
19+
id: String,
20+
hp: Int = 200)
21+
extends Thing {
22+
def isPerson = true
23+
def isOpenSpace = false
24+
25+
override def toString: String = personType.toString
26+
}
27+
28+
case class Wall(xy: XY) extends Thing {
29+
def isPerson = false
30+
def isOpenSpace = false
31+
override def toString: String = "#"
32+
}
33+
34+
case class Empty(xy: XY) extends Thing {
35+
def isPerson = false
36+
def isOpenSpace = true
37+
override def toString: String = "."
38+
}
39+
40+
// 'reading order' means we should store coordinates as Seq
41+
case class Battlefield(field: Map[XY, Thing] = Map.empty,
42+
roundsCompleted: Int = 0,
43+
finished: Boolean = false) {
44+
45+
val people: Seq[Person] = field.keys.toSeq
46+
.filter(
47+
xy =>
48+
field(xy) match {
49+
case Person(_, _, _, _) => true
50+
case _ => false
51+
}
52+
)
53+
.sortBy(xy => (xy.y, xy.x))
54+
.map(xy => field(xy))
55+
.collect {
56+
case p: Person => p
57+
}
58+
59+
val elves = people.filter(_.personType == 'E')
60+
61+
val goblins = people.filter(_.personType == 'G')
62+
63+
def display() = {
64+
println("Round " + roundsCompleted)
65+
val allY = field.keys.toSeq.groupBy(xy => xy.y)
66+
allY.keys.toSeq.sorted.foreach(y => {
67+
val allX = allY(y)
68+
val row = allX.sortBy(xy => xy.x).foldLeft(("", "")) { (acc, xy) =>
69+
{
70+
val hp = if (field(xy).isPerson) {
71+
field(xy).asInstanceOf[Person].personType + "(" + field(xy)
72+
.asInstanceOf[Person]
73+
.hp + ")"
74+
} else ""
75+
(acc._1 + field(xy).toString, acc._2 + hp)
76+
}
77+
}
78+
println(row._1 + " " + row._2)
79+
})
80+
}
81+
82+
def fightToTheDeath(elfAttackPower: Int = 3): Battlefield = {
83+
//display()
84+
if (finished) {
85+
this
86+
} else {
87+
doRound(people, elfAttackPower).fightToTheDeath(elfAttackPower)
88+
}
89+
}
90+
91+
def outcome = roundsCompleted * people.map(_.hp).sum
92+
93+
@tailrec
94+
final def doRound(queue: Seq[Person], elfAttackPower: Int): Battlefield = {
95+
if (queue.size == 0) {
96+
copy(roundsCompleted = roundsCompleted + 1)
97+
} else if (elves.isEmpty || goblins.isEmpty) {
98+
//println("finished mid round")
99+
copy(finished = true)
100+
} else {
101+
val nextPerson = queue.head
102+
val personOpt = people.find(_.id == nextPerson.id)
103+
if (personOpt.isDefined) {
104+
val person = personOpt.get
105+
val (battlefieldAfterMove, moved) = move(person)
106+
val newBattlefield = battlefieldAfterMove.attack(moved, elfAttackPower)
107+
newBattlefield.doRound(queue.tail, elfAttackPower)
108+
} else {
109+
// this happens when a person dies during a round before it's their turn
110+
doRound(queue.tail, elfAttackPower)
111+
}
112+
}
113+
}
114+
115+
def move(person: Person): (Battlefield, Person) = {
116+
val xyOpt =
117+
if (adjacentEnemies(person).isEmpty)
118+
findSquareToMoveTo(person)
119+
else None
120+
121+
val newPerson = if (xyOpt.isDefined) {
122+
//println("moving " + person.xy + " to " + xyOpt.get)
123+
person.copy(xy = xyOpt.get)
124+
} else person
125+
126+
if (xyOpt.isDefined) {
127+
val replace: Map[XY, Thing] =
128+
Map(xyOpt.get -> newPerson, person.xy -> Empty(person.xy))
129+
(copy(field ++ replace), newPerson)
130+
} else (this, person)
131+
}
132+
133+
def attack(person: Person, elfAttackPower: Int = 3): Battlefield = {
134+
val enemies = adjacentEnemies(person)
135+
if (enemies.nonEmpty) {
136+
val target = enemies.minBy(e => (e.hp, e.xy.y, e.xy.x))
137+
val attackPower = if(person.personType == 'E') elfAttackPower else 3
138+
val attacked = target.copy(hp = target.hp - attackPower)
139+
val replace = if (attacked.hp <= 0) Empty(attacked.xy) else attacked
140+
copy(field + (attacked.xy -> replace))
141+
} else this
142+
}
143+
144+
def findSquareToMoveTo(person: Person): Option[XY] = {
145+
146+
val destinations = openAdjacent(person.xy).toSet
147+
148+
val targets = if (person.personType == 'E') goblins else elves
149+
150+
// for each target, get squares "in range" and determine shortest paths from those squares
151+
// to person
152+
// TODO: this is super slow
153+
val shortestPaths =
154+
targets
155+
// 'in range' = open sq adjacent to targets
156+
.flatMap(target => openAdjacent(target.xy))
157+
.map(
158+
inRange => {
159+
//println("finding shortest path for " + inRange)
160+
ShortestPath(this,
161+
inRange,
162+
destinations,
163+
0,
164+
Map(0 -> Set(inRange))).find
165+
})
166+
.filter(_.isDefined)
167+
.map(_.get)
168+
169+
if (shortestPaths.nonEmpty)
170+
Some(
171+
shortestPaths
172+
.minBy(
173+
result =>
174+
(result.d,
175+
result.targetXy.y,
176+
result.targetXy.x,
177+
result.destXy.y,
178+
result.destXy.x))
179+
.destXy)
180+
else
181+
None
182+
}
183+
184+
def openAdjacent(xy: XY) = {
185+
Seq(XY(xy.x - 1, xy.y),
186+
XY(xy.x, xy.y - 1),
187+
XY(xy.x + 1, xy.y),
188+
XY(xy.x, xy.y + 1)).filter(xy => field(xy).isOpenSpace)
189+
}
190+
191+
def adjacentEnemies(person: Person): Seq[Person] = {
192+
val xy = person.xy
193+
val enemy = if (person.personType == 'E') 'G' else 'E'
194+
Seq(XY(xy.x - 1, xy.y),
195+
XY(xy.x, xy.y - 1),
196+
XY(xy.x + 1, xy.y),
197+
XY(xy.x, xy.y + 1))
198+
.map(field(_))
199+
.collect {
200+
case p: Person => p
201+
}
202+
.filter(p => p.personType == enemy)
203+
}
204+
}
205+
206+
case class PathResult(targetXy: XY, destXy: XY, d: Int)
207+
208+
// find the shortest path from inRange square to one of destination squares
209+
case class ShortestPath(battlefield: Battlefield,
210+
inRangeXy: XY,
211+
destinations: Set[XY],
212+
d: Int = 0,
213+
distances: Map[Int, Set[XY]] = Map.empty) {
214+
215+
@tailrec
216+
final def find: Option[PathResult] = {
217+
val intersect = destinations.intersect(distances.values.flatten.toSet)
218+
if (intersect.nonEmpty) {
219+
Some(PathResult(inRangeXy, intersect.minBy(xy => (xy.y, xy.x)), d))
220+
} else {
221+
val adjToLastD =
222+
distances(d).flatMap(xy => battlefield.openAdjacent(xy))
223+
val newDistances = adjToLastD.diff(distances.values.flatten.toSet)
224+
if (newDistances.nonEmpty)
225+
copy(d = d + 1, distances = distances + ((d + 1) -> newDistances)).find
226+
else
227+
None
228+
}
229+
}
230+
231+
}
232+
233+
def getInput = {
234+
val url = getClass.getResource("/day15/input.txt")
235+
Source.fromURL(url).getLines().toSeq
236+
}
237+
238+
def getTestData1 = {
239+
val url = getClass.getResource("/day15/testData1.txt")
240+
Source.fromURL(url).getLines().toSeq
241+
}
242+
243+
def getTestData2 = {
244+
val url = getClass.getResource("/day15/testData2.txt")
245+
Source.fromURL(url).getLines().toSeq
246+
}
247+
248+
def getTestData3 = {
249+
val url = getClass.getResource("/day15/testData3.txt")
250+
Source.fromURL(url).getLines().toSeq
251+
}
252+
253+
def getTestData4 = {
254+
val url = getClass.getResource("/day15/testData4.txt")
255+
Source.fromURL(url).getLines().toSeq
256+
}
257+
258+
def getTestData5 = {
259+
val url = getClass.getResource("/day15/testData5.txt")
260+
Source.fromURL(url).getLines().toSeq
261+
}
262+
263+
def getTestData6 = {
264+
val url = getClass.getResource("/day15/testData6.txt")
265+
Source.fromURL(url).getLines().toSeq
266+
}
267+
268+
def buildBattlefield(lines: Seq[String], elfAttackPower: Int = 3) = {
269+
val field = lines.zipWithIndex.foldLeft(Map[XY, Thing]()) {
270+
case (acc, (line, y)) => {
271+
line.zipWithIndex.filter(_._1 != ' ').foldLeft(acc) {
272+
case (acc, (ch, x)) => {
273+
val xy = XY(x, y)
274+
275+
val thing: Thing =
276+
if (ch == 'E' || ch == 'G')
277+
Person(xy, ch, xy.toString)
278+
else if (ch == '.')
279+
Empty(xy)
280+
else
281+
Wall(xy)
282+
283+
acc + (xy -> thing)
284+
}
285+
}
286+
}
287+
}
288+
Battlefield(field)
289+
}
290+
}

‎src/main/scala/org/codefork/aoc2018/Day15Part1.scala

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package org.codefork.aoc2018
2+
3+
object Day15Part1 extends Part {
4+
5+
override def answer: String = {
6+
assert(Day15.buildBattlefield(Day15.getTestData1).fightToTheDeath().outcome == 27730)
7+
assert(Day15.buildBattlefield(Day15.getTestData2).fightToTheDeath().outcome == 36334)
8+
assert(Day15.buildBattlefield(Day15.getTestData3).fightToTheDeath().outcome == 39514)
9+
assert(Day15.buildBattlefield(Day15.getTestData4).fightToTheDeath().outcome == 27755)
10+
assert(Day15.buildBattlefield(Day15.getTestData5).fightToTheDeath().outcome == 28944)
11+
assert(Day15.buildBattlefield(Day15.getTestData6).fightToTheDeath().outcome == 18740)
12+
Day15.buildBattlefield(Day15.getInput).fightToTheDeath().outcome.toString
13+
}
14+
15+
}

0 commit comments

Comments
 (0)