-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day12.scala
131 lines (120 loc) · 3.94 KB
/
Day12.scala
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
package com.kensai.aoc.aoc2021
object Day12 {
case class Cave(name: String) {
def isSmall: Boolean =
name.head.isLower
def isStart: Boolean =
name == "start"
def isEnd: Boolean =
name == "end"
}
case class Path(from: Cave, to: Cave)
private val pathRegex = """([a-zA-Z]*)-([a-zA-Z]*)""".r
private def parseInputs(lines: Seq[String]): Seq[Path] =
lines.filterNot(_.isEmpty).flatMap {
case pathRegex(left, right) =>
Seq(Path(Cave(left), Cave(right)), Path(Cave(right), Cave(left)))
case _ => throw new IllegalArgumentException(s"Invalid line: [$lines]")
}
/** Count number of different path from "start" to "end" where every small cave can only be accessed once.
*/
def countUniqPaths(lines: Seq[String]): Int = {
val paths = parseInputs(lines)
val pathByFirstCave = paths.groupBy(_.from)
val solutions =
doComputePathsToEnd(Cave("start"), pathByFirstCave, Seq(), Set())
solutions.size
}
/** @param currentCave
* : The cave at this step
* @param paths
* : all the available paths grouped by cave
* @param currentPath
* : sequence of caves visited
* @param smallCaveVisited
* : set of small cave visited
* @return
* all the sequences of caves from "start" to "end"
*/
private def doComputePathsToEnd(
currentCave: Cave,
paths: Map[Cave, Seq[Path]],
currentPath: Seq[Cave],
smallCaveVisited: Set[Cave]
): Seq[Seq[Cave]] =
if (currentCave.isEnd)
Seq(currentPath :+ currentCave)
else {
val possiblePaths = paths(currentCave)
possiblePaths.foldLeft(Seq.empty[Seq[Cave]]) { case (acc, path) =>
if (smallCaveVisited.contains(path.to))
acc
else
acc ++ doComputePathsToEnd(
path.to,
paths,
currentPath :+ path.to,
if (currentCave.isSmall) smallCaveVisited + currentCave
else smallCaveVisited
)
}
}
/** Start cave can only be access once. Each small cave can only be accessed once except one.
* @return
* the number of different path from "start" to "end"
*/
def countUniqPaths2(lines: Seq[String]): Int = {
val paths = parseInputs(lines)
val pathByFirstCave = paths.groupBy(_.from)
doComputePathsToEnd2(Cave("start"), pathByFirstCave, Seq(), Set(), None).size
}
/** @param currentCave
* : The cave at this step
* @param paths
* : all the available paths grouped by cave
* @param currentPath
* : sequence of caves visited
* @param smallCaveVisited
* : set of small cave visited
* @param caveVisitedTwice
* : the only one small cave visited twice
* @return
* all the sequences of caves from "start" to "end"
*/
private def doComputePathsToEnd2(
currentCave: Cave,
paths: Map[Cave, Seq[Path]],
currentPath: Seq[Cave],
smallCaveVisited: Set[Cave],
caveVisitedTwice: Option[Cave]
): Seq[Seq[Cave]] =
if (currentCave.isEnd)
Seq(currentPath :+ currentCave)
else {
val possiblePaths = paths(currentCave)
possiblePaths.foldLeft(Seq.empty[Seq[Cave]]) { case (acc, path) =>
if (currentPath.nonEmpty && currentCave.isStart)
acc
else if (smallCaveVisited.contains(path.to) && caveVisitedTwice.isDefined)
acc
else if (smallCaveVisited.contains(path.to))
acc ++ doComputePathsToEnd2(
path.to,
paths,
currentPath :+ path.to,
if (currentCave.isSmall) smallCaveVisited + currentCave
else smallCaveVisited,
Some(currentCave)
)
else
acc ++ doComputePathsToEnd2(
path.to,
paths,
currentPath :+ path.to,
if (currentCave.isSmall) smallCaveVisited + currentCave
else smallCaveVisited,
caveVisitedTwice
)
}
}
}