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

Commit 5b2e80b

Browse files
sim642sim642
committed
Solve 2018 day 7 part 1
1 parent b5800b7 commit 5b2e80b

File tree

3 files changed

+165
-0
lines changed

3 files changed

+165
-0
lines changed

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

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,101 @@
1+
Step Y must be finished before step L can begin.
2+
Step N must be finished before step D can begin.
3+
Step Z must be finished before step A can begin.
4+
Step F must be finished before step L can begin.
5+
Step H must be finished before step G can begin.
6+
Step I must be finished before step S can begin.
7+
Step M must be finished before step U can begin.
8+
Step R must be finished before step J can begin.
9+
Step T must be finished before step D can begin.
10+
Step U must be finished before step D can begin.
11+
Step O must be finished before step X can begin.
12+
Step B must be finished before step D can begin.
13+
Step X must be finished before step V can begin.
14+
Step J must be finished before step V can begin.
15+
Step D must be finished before step A can begin.
16+
Step K must be finished before step P can begin.
17+
Step Q must be finished before step C can begin.
18+
Step S must be finished before step E can begin.
19+
Step A must be finished before step V can begin.
20+
Step G must be finished before step L can begin.
21+
Step C must be finished before step W can begin.
22+
Step P must be finished before step W can begin.
23+
Step V must be finished before step W can begin.
24+
Step E must be finished before step W can begin.
25+
Step W must be finished before step L can begin.
26+
Step P must be finished before step E can begin.
27+
Step T must be finished before step K can begin.
28+
Step A must be finished before step G can begin.
29+
Step G must be finished before step P can begin.
30+
Step N must be finished before step S can begin.
31+
Step R must be finished before step D can begin.
32+
Step M must be finished before step G can begin.
33+
Step Z must be finished before step L can begin.
34+
Step M must be finished before step T can begin.
35+
Step S must be finished before step L can begin.
36+
Step S must be finished before step W can begin.
37+
Step O must be finished before step J can begin.
38+
Step Z must be finished before step D can begin.
39+
Step A must be finished before step C can begin.
40+
Step P must be finished before step V can begin.
41+
Step A must be finished before step P can begin.
42+
Step B must be finished before step C can begin.
43+
Step R must be finished before step S can begin.
44+
Step X must be finished before step S can begin.
45+
Step T must be finished before step P can begin.
46+
Step Y must be finished before step E can begin.
47+
Step G must be finished before step E can begin.
48+
Step Y must be finished before step K can begin.
49+
Step J must be finished before step P can begin.
50+
Step I must be finished before step Q can begin.
51+
Step E must be finished before step L can begin.
52+
Step X must be finished before step J can begin.
53+
Step T must be finished before step X can begin.
54+
Step M must be finished before step O can begin.
55+
Step K must be finished before step A can begin.
56+
Step D must be finished before step W can begin.
57+
Step H must be finished before step C can begin.
58+
Step F must be finished before step R can begin.
59+
Step B must be finished before step Q can begin.
60+
Step M must be finished before step Q can begin.
61+
Step D must be finished before step S can begin.
62+
Step Y must be finished before step I can begin.
63+
Step M must be finished before step K can begin.
64+
Step S must be finished before step G can begin.
65+
Step X must be finished before step L can begin.
66+
Step D must be finished before step V can begin.
67+
Step B must be finished before step X can begin.
68+
Step C must be finished before step L can begin.
69+
Step V must be finished before step L can begin.
70+
Step Z must be finished before step Q can begin.
71+
Step Z must be finished before step H can begin.
72+
Step M must be finished before step S can begin.
73+
Step O must be finished before step C can begin.
74+
Step B must be finished before step A can begin.
75+
Step U must be finished before step V can begin.
76+
Step U must be finished before step A can begin.
77+
Step X must be finished before step G can begin.
78+
Step K must be finished before step C can begin.
79+
Step T must be finished before step S can begin.
80+
Step K must be finished before step G can begin.
81+
Step U must be finished before step B can begin.
82+
Step A must be finished before step E can begin.
83+
Step F must be finished before step V can begin.
84+
Step Q must be finished before step A can begin.
85+
Step F must be finished before step Q can begin.
86+
Step J must be finished before step L can begin.
87+
Step O must be finished before step E can begin.
88+
Step O must be finished before step Q can begin.
89+
Step I must be finished before step K can begin.
90+
Step I must be finished before step P can begin.
91+
Step J must be finished before step D can begin.
92+
Step Q must be finished before step P can begin.
93+
Step S must be finished before step C can begin.
94+
Step U must be finished before step P can begin.
95+
Step S must be finished before step P can begin.
96+
Step O must be finished before step B can begin.
97+
Step Z must be finished before step F can begin.
98+
Step R must be finished before step V can begin.
99+
Step D must be finished before step L can begin.
100+
Step Y must be finished before step T can begin.
101+
Step G must be finished before step C can begin.

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

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package eu.sim642.adventofcode2018
2+
3+
object Day7 {
4+
5+
type Step = Char
6+
type Requirements = Map[Step, Set[Step]]
7+
8+
def topologicalSort(reqs: Requirements): String = {
9+
reqs.values.reduceOption(_ ++ _) match {
10+
case None => ""
11+
case Some(haveReqStep) =>
12+
val step = (reqs.keySet -- haveReqStep).min
13+
val restReqs = reqs.filterKeys(_ != step)
14+
step + topologicalSort(restReqs)
15+
}
16+
}
17+
18+
19+
private val requirementRegex = """Step ([A-Z]) must be finished before step ([A-Z]) can begin.""".r
20+
21+
def parseRequirement(s: String): (Step, Step) = s match {
22+
case requirementRegex(reqStep, step) => reqStep.head -> step.head
23+
}
24+
25+
def parseRequirements(input: String): Requirements = {
26+
input.lines.map(parseRequirement).foldLeft(Map.empty[Step, Set[Step]])({
27+
case (reqs, (reqStep, step)) =>
28+
reqs +
29+
(reqStep -> (reqs.getOrElse(reqStep, Set()) + step)) +
30+
(step -> reqs.getOrElse(step, Set()))
31+
})
32+
}
33+
34+
35+
lazy val input: String = io.Source.fromInputStream(getClass.getResourceAsStream("day7.txt")).mkString.trim
36+
37+
def main(args: Array[String]): Unit = {
38+
println(topologicalSort(parseRequirements(input)))
39+
}
40+
}

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

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package eu.sim642.adventofcode2018
2+
3+
import org.scalatest.FunSuite
4+
import Day7._
5+
6+
class Day7Test extends FunSuite {
7+
8+
val exampleInput =
9+
"""Step C must be finished before step A can begin.
10+
|Step C must be finished before step F can begin.
11+
|Step A must be finished before step B can begin.
12+
|Step A must be finished before step D can begin.
13+
|Step B must be finished before step E can begin.
14+
|Step D must be finished before step E can begin.
15+
|Step F must be finished before step E can begin.""".stripMargin
16+
17+
test("Part 1 examples") {
18+
assert(topologicalSort(parseRequirements(exampleInput)) == "CABDFE")
19+
}
20+
21+
test("Part 1 input answer") {
22+
assert(topologicalSort(parseRequirements(input)) == "MNOUBYITKXZFHQRJDASGCPEVWL")
23+
}
24+
}

0 commit comments

Comments
 (0)
0