-
Notifications
You must be signed in to change notification settings - Fork 0
/
Contents.swift
74 lines (56 loc) · 1.88 KB
/
Contents.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
69
70
71
72
73
74
//: [Previous](@previous)
import Foundation
//: ## Day 7 Part 1
//: ### Problem definition
typealias Graph = [String: [String]]
func buildGraph(contraints: [String]) -> Graph {
var graph: Graph = [:]
contraints.map ({ (contraint) -> (String, String) in
let tokens = contraint.components(separatedBy: [" "])
return (tokens[1], tokens[7])
}).forEach { (verts) in
let (from, to) = verts
graph[from, default: []].append(to)
}
return graph
}
let problem = Problem { (graph: Graph) -> String in
// topological sort
var incomming = graph.flatMap({ $0.value }).reduce(into: [:]) { (f: inout [String:Int], s: String) in
f[s, default: 0] += 1
}
var fringe = Array(graph.filter ({ !incomming.keys.contains($0.key) }).keys)
var sorted: [String] = []
while !fringe.isEmpty {
fringe.sort()
let current = fringe.removeFirst()
sorted.append(current)
guard let edges = graph[current] else {
continue
}
for next in edges {
incomming[next, default: 1] -= 1
if incomming[next, default: 0] == 0 {
fringe.append(next)
}
}
}
return sorted.joined()
}
//: ### Tests
let example = """
Step C must be finished before step A can begin.
Step C must be finished before step F can begin.
Step A must be finished before step B can begin.
Step A must be finished before step D can begin.
Step B must be finished before step E can begin.
Step D must be finished before step E can begin.
Step F must be finished before step E can begin.
"""
let exampleGraph = buildGraph(contraints: example.lines)
problem.test(input: exampleGraph, expected: "CABDFE")
//: ### Find Solution
let input = try getInputString().lines
let graph = buildGraph(contraints: input)
print(problem.run(input: graph))
//: [Next](@next)