-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathday11.nim
143 lines (109 loc) · 4.69 KB
/
day11.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
136
137
138
139
140
141
142
143
# Advent of Code 2020, Day 11
# (c) blu3r4y
import options
import sequtils
type TextGrid = object
arr: seq[seq[char]]
ncols: int
nrows: int
func newTextGrid(arr: seq[seq[char]]): TextGrid =
result.arr = arr
result.ncols = len(arr[0])
result.nrows = len(arr)
func orient(i: int): tuple[dc: int, dr: int] =
## returns the orientation offset by index.
## this just a static result for `product([-1, 0, +1], repeat=2)[i]`
const orients = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
return orients[i]
iterator coords(grid: TextGrid): tuple[c: int, r: int] =
## return all coordinate pairs `(c, r)` in the grid
for c in 0 ..< grid.ncols:
for r in 0 ..< grid.nrows:
yield (c, r)
func set(grid: var TextGrid, c: int, r: int, value: char) =
## set the character `value` at column `c` and row `r`
grid.arr[r][c] = value
func get(grid: TextGrid, c: int, r: int): char =
## retrieve the character at column `c` and row `r`
return grid.arr[r][c]
func count(grid: TextGrid, value: char): int =
## return the number of occurrences of the character `value` in the grid
let counts = grid.arr.mapIt(count(it, value))
return counts.foldl(a + b)
iterator trace(grid: TextGrid, c: int, r: int, o: int, limit: int = 1): char =
## retrieve all the field values in the grid, starting at position `(c, r)`
## going into direction `o` for all lengths `1 .. limit` (inclusive)
let (dc, dr) = orient(o)
for d in 1 .. limit:
let tc = c + dc * d
let tr = r + dr * d
if 0 <= tc and tc < grid.ncols and 0 <= tr and tr < grid.nrows:
yield grid.get(tc, tr)
iterator neighbors(grid: TextGrid, c: int, r: int, match: Option[string] = none(string)): char =
## retrieve the values of all neighbouring cells, and possibly
## filtered only on cell values that match the passed `match` character
for o in 0 ..< 8:
for tr in grid.trace(c, r, o):
if match.isNone or match.get().contains(tr):
yield tr
func tracesplit(grid: TextGrid, c: int, r: int, o: int, limit: int, match: string): tuple[a: seq[char], b: seq[char]] =
## like `trace(c, r, o, limit, match)` but splits the sequence into two parts.
## the split occurs once the first element matches the field values
var a = newSeq[char]()
var b = newSeq[char]()
var takewhile = true
for tr in grid.trace(c, r, o, limit):
# take everything into sequence a, as long as the cell values do not match
takewhile = takewhile and not match.contains(tr)
if takewhile:
a.add(tr)
else:
b.add(tr)
return (a, b)
iterator starsplit(grid: TextGrid, c: int, r: int, match: string): tuple[a: seq[char], b: seq[char]] =
## applies the tracesplit into all 8 directions
let limit = max(grid.ncols, grid.nrows)
for o in 0 ..< 8:
yield grid.tracesplit(c, r, o, limit, match)
###############################################################################
func part1(grid: var TextGrid): int =
var changeset = @[(0, 0, '0')]
while len(changeset) > 0:
changeset.setLen(0)
for (c, r) in grid.coords():
let val = grid.get(c, r)
# number of occupied neighbouring seats
let numNeighbors = len(toSeq(grid.neighbors(c, r, some("#"))))
if val == 'L' and numNeighbors == 0:
changeset.add((c, r, '#'))
elif val == '#' and numNeighbors >= 4:
changeset.add((c, r, 'L'))
for (c, r, val) in changeset:
grid.set(c, r, val)
return grid.count('#')
func part2(grid: var TextGrid): int =
var changeset = @[(0, 0, '0')]
while len(changeset) > 0:
changeset.setLen(0)
for (c, r) in grid.coords():
let val = grid.get(c, r)
if val == 'L' or val == '#':
# number of occupied seats in star-split-sight
var numOccupied = 0
for split in grid.starsplit(c, r, "L#"):
if len(split.b) > 0 and split.b[0] == '#':
numOccupied += 1
if val == 'L' and numOccupied == 0:
changeset.add((c, r, '#'))
elif val == '#' and numOccupied >= 5:
changeset.add((c, r, 'L'))
for (c, r, val) in changeset:
grid.set(c, r, val)
return grid.count('#')
###############################################################################
when is_main_module:
var text = toSeq(lines("./data/day11.txt")).mapIt(toSeq(it))
var grid1 = newTextGrid(text)
echo part1(grid1)
var grid2 = newTextGrid(text)
echo part2(grid2)