This repository has been archived by the owner on Jan 2, 2023. It is now read-only.
-
-
Notifications
You must be signed in to change notification settings - Fork 0
/
day20.nim
135 lines (120 loc) · 4.93 KB
/
day20.nim
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
132
133
134
135
import deques, sequtils, sets, strutils, tables
type
Point = tuple[x,y: int]
Direction = enum
N, E, S, W
Sequence = ref object
forks: bool
nodes: seq[Sequence]
content: seq[Direction]
proc `+` (a, b: Point): Point =
result.x = a.x + b.x
result.y = a.y + b.y
# Parses the regular expression into a 'Sequence' data structure, by pushing
# sequences onto a stack each time a nested expression is encountered.
#
# Three types of sequences are found:
# 1) "Content-only", e.g. NNNEEE
# 2) "Forks", e.g. (subsequence|subsequence|subsequence)
# 3) "Concatenations", e.g. NN(subsequence)EE
#
func process(regex: string): Sequence =
var
stack = initDeque[Sequence]()
span: seq[Direction]
result = new(Sequence)
stack.addLast(result)
for c in regex:
if c == '^':
continue
if c in ['(', ')', '|', '$']:
if span.len > 0:
# If we've got bare directions, add them as a content element.
var newSeq = new(Sequence)
newSeq.content = span
stack.peekLast.nodes.add(newSeq)
span.setLen(0)
if c == '(':
# To start a new fork block we add two sequences: one that will
# contain all the forked elements, and the first child to hold
# the content of the first fork.
var forkSeq = new(Sequence)
forkSeq.forks = true
stack.addLast(forkSeq)
stack.addLast(new(Sequence))
elif c == '|':
# Pop the previous child off and add it to the parent fork block,
# then add a new one for the next branch.
var child = stack.popLast
stack.peekLast.nodes.add(child)
stack.addLast(new(Sequence))
elif c == ')':
# Pop both the child and the parent fork block off the stack.
var child = stack.popLast
stack.peekLast.nodes.add(child)
var forkSeq = stack.popLast
stack.peekLast.nodes.add(forkSeq)
else:
span.add(parseEnum[Direction]($c))
stack.popLast
let
directions = {
N: ( 0, 1),
E: ( 1, 0),
S: ( 0, -1),
W: (-1, 0),
}.toTable
opposites = { N: S, E: W, S: N, W: E, }.toTable
input = readFile("data/20.txt").strip
proc addDirection(table: var Table[Point, HashSet[Direction]], point: Point, direction: Direction) =
if not table.hasKey(point):
table[point] = initSet[Direction]()
table[point].incl(direction)
proc addDirections(table: var Table[Point, HashSet[Direction]], point: Point, direction: Direction): Point =
let otherPoint = point + directions[direction]
table.addDirection(point, direction)
table.addDirection(otherPoint, opposites[direction])
otherPoint
# Recurses through the given sequence and builds up a map of which points are
# traversable in which directions.
#
# The points parameter tracks which points could have been reached by the
# sequence thus far. The current sequence must be evaluated for all of those
# points. Initially this is just {(0,0)} but every time a fork is encountered
# the number of points will expand.
proc map(sequence: Sequence, grid: var Table[Point, HashSet[Direction]], points: HashSet[Point]): HashSet[Point] =
if sequence.content.len > 0:
result = initSet[Point]()
for point in points:
var newPoint = point
for d in sequence.content:
newPoint = grid.addDirections(newPoint, d)
result.incl(newPoint)
elif sequence.forks:
result = initSet[Point]()
for child in sequence.nodes:
result.incl(child.map(grid, points))
else:
result = points
for child in sequence.nodes:
result = child.map(grid, result)
# Performs a breadth-first search of the navigable area and assigns a
# distance to each point.
proc score(dirs: Table[Point, HashSet[Direction]]): Table[Point, int] =
result = initTable[Point, int]()
var stack = initDeque[tuple[pos: Point, length: int]]()
stack.addLast(((0, 0), 0))
while stack.len > 0:
let step = stack.popFirst
if not result.hasKey(step.pos) or result[step.pos] > step.length:
result[step.pos] = step.length
for direction in dirs[step.pos]:
stack.addLast((step.pos + directions[direction], step.length + 1))
proc distances(input: string): seq[int] =
var grid = initTable[Point, HashSet[Direction]]()
let points = toSet([(0, 0)])
discard input.process.map(grid, points)
toSeq(grid.score.values)
let distanceValues = input.distances
echo distanceValues.max
echo distanceValues.filter(proc(i: int): bool = i >= 1000).len