8000 Solve 2020 day 19 part 2 · sim642/adventofcode@13cb78d · GitHub
[go: up one dir, main page]
Skip to content

Commit 13cb78d

Browse files
sim642sim642
committed
Solve 2020 day 19 part 2
1 parent dcc07df commit 13cb78d

File tree

2 files changed

+199
-14
lines changed

2 files changed

+199
-14
lines changed

‎src/main/scala/eu/sim642/adventofcode2020/Day19.scala

Lines changed: 139 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@ package eu.sim642.adventofcode2020
22

33
import scala.collection.mutable
44
import scala.util.matching.Regex
5+
import scala.util.parsing.combinator.RegexParsers
56

67
object Day19 {
78

@@ -15,22 +16,147 @@ object Day19 {
1516

1617
case class Input(rules: Rules, messages: Seq[String])
1718

18-
def rules2Regex(rules: Rules): Regex = {
19+
// TODO: keep solution with regex for part 1
20+
// TODO: figure out why parser combinators didn't work right
1921

20-
val memo = mutable.Map.empty[Int, String]
21-
def helper(rule: Rule): String = rule match {
22-
case Literal(char) => char.toString
23-
case Sub(i) => memo.getOrElseUpdate(i, helper(rules(i)))
24-
case Concat(left, right) => helper(left) + helper(right)
25-
case Choice(left, right) => "(" + helper(left) + "|" + helper(right) + ")"
22+
// copied & modified from 2015 Day 19
23+
// TODO: move earley parser to library
24+
// https://en.wikipedia.org/wiki/Earley_parser
25+
// https://old.reddit.com/r/adventofcode/comments/3xflz8/day_19_solutions/cy6gv3z/
26+
type Production[N, T] = (N, Seq[Either[N, T]])
27+
def earley[N, T](grammar: Seq[Production[N, T]], initial: N, input: Seq[T]): Boolean = {
28+
29+
def nProductions(n: N): Seq[Production[N, T]] = grammar.filter(_._1 == n)
30+
31+
case class State(production: Production[N, T], dot: Int, j: Int, count: Int) {
32+
def isComplete: Boolean = dot >= production._2.length
33+
def current: Either[N, T] = production._2(dot)
34+
}
35+
36+
val S = IndexedSeq.fill(input.length + 1)(mutable.LinkedHashSet.empty[State])
37+
val initialProductions = nProductions(initial)
38+
for (production <- initialProductions)
39+
S(0).add(State(production, 0, 0, 0))
40+
41+
for (k <- 0 to input.length) {
42+
val SkQueue = S(k).to(mutable.Queue)
43+
44+
def addSk(state: State): Unit = {
45+
if (S(k).add(state))
46+
SkQueue.enqueue(state)
47+
}
48+
49+
while (SkQueue.nonEmpty) {
50+
val state@State((n, _), _, j, count) = SkQueue.dequeue()
51+
if (!state.isComplete) {
52+
state.current match {
53+
case Left(n) =>
54+
// prediction
55+
for (production <- nProductions(n))
56+
addSk(State(production, 0, k, 0))
57+
case Right(t) =>
58+
// scanning
59+
if (k < input.length && t == input(k))
60+
S(k + 1).add(state.copy(dot = state.dot + 1))
61+
}
62+
}
63+
else {
64+
// completion
65+
for {
66+
jState <- S(j)
67+
if !jState.isComplete && jState.current == Left(n)
68+
} addSk(jState.copy(dot = jState.dot + 1, count = jState.count + 1 + count))
69+
}
70+
}
2671
}
2772

28-
helper(Sub(0)).r
73+
S.last.exists(s => s.isComplete && initialProductions.contains(s.production))
2974
}
3075

31-
def countMatchingMessages(input: Input): Int = {
32-
val regex = rules2Regex(input.rules)
33-
input.messages.count(regex.matches)
76+
sealed trait Part {
77+
//sealed trait Part extends RegexParsers {
78+
79+
/*def rules2Regex(rules: Rules): Regex = {
80+
81+
val memo = mutable.Map.empty[Int, String]
82+
def helper(rule: Rule): String = rule match {
83+
case Literal(char) => char.toString
84+
case Sub(i) => memo.getOrElseUpdate(i, helper(rules(i)))
85+
case Concat(left, right) => helper(left) + helper(right)
86+
case Choice(left, right) => "(" + helper(left) + "|" + helper(right) + ")"
87+
}
88+
89+
//println(s"42: ${helper(Sub(42))}")
90+
//println(s"31: ${helper(Sub(31))}")
91+
92+
helper(Sub(0)).r
93+
}
94+
95+
def countMatchingMessages(input: Input): Int = {
96+
val regex = rules2Regex(input.rules)
97+
input.messages.count(regex.matches)
98+
}*/
99+
100+
/*def rules2Parser(rules: Rules): Parser[Unit] = {
101+
102+
val memo = mutable.Map.empty[Int, Parser[Unit]]
103+
def helper(rule: Rule): Parser[Unit] = rule match {
104+
case Literal(char) => literal(char.toString) ^^^ ()
105+
case Sub(i) => memo.getOrElseUpdate(i, helper(rules(i)))
106+
case Concat(left, right) => helper(left) ~ helper(right) ^^^ ()
107+
case Choice(left, right) => helper(left) | helper(right)
108+
}
109+
110+
//println(s"42: ${helper(Sub(42))}")
111+
//println(s"31: ${helper(Sub(31))}")
112+
113+
helper(Sub(0))
114+
}
115+
116+
def countMatchingMessages(input: Day19.Input): Int = {
117+
val parser = rules2Parser(input.rules)
118+
input.messages.count(message => {
119+
parseAll(parser, message) match {
120+
case Success(_, _) => true
121+
case _ => false
122+
}
123+
})
124+
}*/
125+
126+
def rules2Grammar(rules: Rules): Seq[Production[Int, Char]] = {
127+
128+
def helper(rule: Rule): Seq[Seq[Either[Int, Char]]] = rule match {
129+
case Literal(char) => Seq(Seq(Right(char)))
130+
case Sub(i) => Seq(Seq(Left(i)))
131+
case Concat(left, right) =>
132+
for {
133+
l <- helper(left)
134+
r <- helper(right)
135+
} yield l ++ r
136+
case Choice(left, right) => helper(left) ++ helper(right)
137+
}
138+
139+
def helper2(i: Int, rule: Rule): Seq[Production[Int, Char]] = helper(rule).map(i -> _)
140+
141+
//println(s"42: ${helper(Sub(42))}")
142+
//println(s"31: ${helper(Sub(31))}")
143+
144+
rules.toSeq.flatMap({ case (i, rule) => helper2(i, rule) })
145+
}
146+
147+
def countMatchingMessages(input: Day19.Input): Int = {
148+
val grammar = rules2Grammar(input.rules)
149+
input.messages.count(earley(grammar, 0, _))
150+
}
151+
}
152+
153+
object Part1 extends Part
154+
155+
object Part2 extends Part {
156+
override def rules2Grammar(rules: Rules) = {
157+
val newRules = rules + (8 -> Choice(Sub(42), Concat(Sub(42), Sub(8)))) + (11 -> Choice(Concat(Sub(42), Sub(31)), Concat(Concat(Sub(42), Sub(11)), Sub(31))))
158+
super.rules2Grammar(newRules)
159+
}
34160
}
35161

36162

@@ -69,6 +195,7 @@ object Day19 {
69195
lazy val input: String = io.Source.fromInputStream(getClass.getResourceAsStream("day19.txt")).mkString.trim
70196

71197
def main(args: Array[String]): Unit = {
72-
println(countMatchingMessages(parseInput(input)))
198+
println(Part1.countMatchingMessages(parseInput(input)))
199+
println(Part2.countMatchingMessages(parseInput(input)))
73200
}
74201
}

‎src/test/scala/eu/sim642/adventofcode2020/Day19Test.scala

Lines changed: 60 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,55 @@ class Day19Test extends AnyFunSuite {
3333
|aaabbb
3434
|aaaabbb""".stripMargin
3535

36+
val exampleInput2 =
37+
"""42: 9 14 | 10 1
38+
|9: 14 27 | 1 26
39+
|10: 23 14 | 28 1
40+
|1: "a"
41+
|11: 42 31
42+
|5: 1 14 | 15 1
43+
|19: 14 1 | 14 14
44+
|12: 24 14 | 19 1
45+
|16: 15 1 | 14 14
46+
|31: 14 17 | 1 13
47+
|6: 14 14 | 1 14
48+
|2: 1 24 | 14 4
49+
|0: 8 11
50+
|13: 14 3 | 1 12
51+
|15: 1 | 14
52+
|17: 14 2 | 1 7
53+
|23: 25 1 | 22 14
54+
|28: 16 1
55+
|4: 1 1
56+
|20: 14 14 | 1 15
57+
|3: 5 14 | 16 1
58+
|27: 1 6 | 14 18
59+
|14: "b"
60+
|21: 14 1 | 1 14
61+
|25: 1 1 | 1 14
62+
|22: 14 14
63+
|8: 42
64+
|26: 14 22 | 1 20
65+
|18: 15 15
66+
|7: 14 5 | 1 21
67+
|24: 14 1
68+
|
69+
|abbbbbabbbaaaababbaabbbbabababbbabbbbbbabaaaa
70+
|bbabbbbaabaabba
71+
|babbbbaabbbbbabbbbbbaabaaabaaa
72+
|aaabbbbbbaaaabaababaabababbabaaabbababababaaa
73+
|bbbbbbbaaaabbbbaaabbabaaa
74+
|bbbababbbbaaaaaaaabbababaaababaabab
75+
|ababaaaaaabaaab
76+
|ababaaaaabbbaba
77+
|baabbaaaabbaaaababbaababb
78+
|abbbbabbbbaaaababbbbbbaaaababb
79+
|aaaaabbaabaaaaababaa
80+
|aaaabbaaaabbaaa
81+
|aaaabbaabbaaaaaaabbbabbbaaabbaabaaa
82+
|babaaabbbaaabaababbaabababaaab
83+
|aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba""".stripMargin
84+
3685
test("parseRules") {
3786
println(parseRules(exampleRules))
3887
println(parseRules(exampleRules2))
@@ -44,10 +93,19 @@ class Day19Test extends AnyFunSuite {
4493
}
4594

4695
test("Part 1 examples") {
47-
assert(countMatchingMessages(parseInput(exampleInput)) == 2)
96+
assert(Part1.countMatchingMessages(parseInput(exampleInput)) == 2)
4897
}
4998

5099
test("Part 1 input answer") {
51-
assert(countMatchingMessages(parseInput(input)) == 226)
100+
assert(Part1.countMatchingMessages(parseInput(input)) == 226)
101+
}
102+
103+
test("Part 2 examples") {
104+
assert(Part1.countMatchingMessages(parseInput(exampleInput2)) == 3)
105+
assert(Part2.countMatchingMessages(parseInput(exampleInput2)) == 12)
106+
}
107+
108+
test("Part 2 input answer") {
109+
assert(Part2.countMatchingMessages(parseInput(input)) == 355)
52110
}
53111
}

0 commit comments

Comments
 (0)
0