-
Notifications
You must be signed in to change notification settings - Fork 0
/
Solution_2021_12.swift
68 lines (58 loc) · 1.82 KB
/
Solution_2021_12.swift
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
//
// Solution_2021_12.swift
//
//
// Created by Ivan Chalov on 12.12.21.
//
import Foundation
struct Solution_2021_12: Solution {
var input: Input
func run() throws {
let input = try self.input.get()
.split(whereSeparator: \.isNewline)
.map { $0.split(separator: "-") }
.map { (String($0[0]), String($0[1])) }
// ------- Part 1 -------
let map: [String: [String]] = input.reduce(into: [:]) { acc, x in
acc[x.0, default: []].append(x.1)
acc[x.1, default: []].append(x.0)
}
let part1 = walk("start", map).count
print(part1)
// ------- Part 2 -------
let part2 = map.keys
.filter { $0 != "start" && $0 != "end" && $0.first!.isLowercase }
.map { walk("start", map, $0) }
.reduce(into: Set()) { $0.formUnion($1) }
.count
print(part2)
// ------- Test -------
assert(part1 == 5212, "WA")
assert(part2 == 134862, "WA")
}
}
private func walk(
_ cave: String,
_ map: [String: [String]],
_ possibleTwice: String? = nil,
_ visited: Set<String> = [],
_ path: [String] = []
) -> Set<[String]> {
guard cave != "end" else { return Set([path]) }
guard possibleTwice == cave || !cave.first!.isLowercase || !visited.contains(cave) else { return Set() }
let newPossibleTwice = possibleTwice == cave ? nil : possibleTwice
let newVisited = possibleTwice == cave
? visited
: (cave.first!.isLowercase ? visited.union([cave]) : visited)
return map[cave]!
.map { nextCave in
walk(
nextCave,
map,
newPossibleTwice,
newVisited,
path + [cave]
)
}
.reduce(into: Set()) { $0.formUnion($1) }
}