-
Notifications
You must be signed in to change notification settings - Fork 10
/
Day15.cs
136 lines (112 loc) · 4.57 KB
/
Day15.cs
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
using AdventOfCode.CSharp.Common;
using System;
namespace AdventOfCode.CSharp.Y2021.Solvers;
public class Day15 : ISolver
{
public static void Solve(ReadOnlySpan<byte> input, Solution solution)
{
var width = input.IndexOf((byte)'\n');
var height = input.Length / (width + 1);
// The risk level for (x, y) is stored at riskLevels[y * width + x].
// The risk levels are subtracted by 1 so that they are from the range 0 - 8 instead of 1 - 9
Span<byte> riskLevels = stackalloc byte[width * height];
ParseRiskLevels(input, width, height, riskLevels);
int part1 = FindShortestPath(riskLevels, width, height);
// Expand the risk levels span to repeat 5 times over.
int part2Width = 5 * width;
int part2Height = 5 * height;
Span<byte> riskLevelsPart2 = stackalloc byte[part2Width * part2Height];
for (int yRepeat = 0; yRepeat < 5; yRepeat++)
{
int yOffset = yRepeat * height;
for (int xRepeat = 0; xRepeat < 5; xRepeat++)
{
int xOffset = xRepeat * width;
int increase = yRepeat + xRepeat;
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
int origRiskLevel = riskLevels[y * width + x];
int riskAfterIncrease = origRiskLevel + increase;
int riskAfterWrapping = riskAfterIncrease % 9;
riskLevelsPart2[(yOffset + y) * part2Width + xOffset + x] = (byte)riskAfterWrapping;
}
}
}
}
int part2 = FindShortestPath(riskLevelsPart2, part2Width, part2Height);
solution.SubmitPart1(part1);
solution.SubmitPart2(part2);
}
private static int FindShortestPath(Span<byte> riskLevels, int width, int height)
{
const int maxBucketSize = 4096;
Span<byte> seenCells = stackalloc byte[width * height];
int startBucketPtr = 0;
int minBucketDistance = 0;
Span<int> pq = stackalloc int[maxBucketSize * 11];
Span<int> bucketPtrs = stackalloc int[11];
for (int i = 0; i < 11; i++)
bucketPtrs[i] = i * maxBucketSize;
pq[bucketPtrs[0]++] = 0;
minBucketDistance = width + height - 2; // heuristic distance to end
int bottomRightPos = (width * height) - 1;
while (true)
{
for (int i = startBucketPtr; i < bucketPtrs[0]; i++)
{
int packedPos = pq[i];
if (packedPos == bottomRightPos)
return minBucketDistance;
ref byte seenCell = ref seenCells[packedPos];
if (seenCell != 0)
continue;
seenCell = 1;
int x = packedPos % width;
if (x > 0)
{
int riskLevel = riskLevels[packedPos - 1];
int bucketPtr = bucketPtrs[riskLevel + 2]++;
pq[bucketPtr] = packedPos - 1;
}
if (x < width - 1)
{
int riskLevel = riskLevels[packedPos + 1];
int bucketPtr = bucketPtrs[riskLevel]++;
pq[bucketPtr] = packedPos + 1;
}
if (packedPos >= width)
{
int riskLevel = riskLevels[packedPos - width];
int bucketPtr = bucketPtrs[riskLevel + 2]++;
pq[bucketPtr] = packedPos - width;
}
if (packedPos <= bottomRightPos - width)
{
int riskLevel = riskLevels[packedPos + width];
int bucketPtr = bucketPtrs[riskLevel]++;
pq[bucketPtr] = packedPos + width;
}
}
for (int i = 0; i < 10; i++)
bucketPtrs[i] = bucketPtrs[i + 1];
bucketPtrs[10] = startBucketPtr;
startBucketPtr = (startBucketPtr + maxBucketSize) % (11 * maxBucketSize);
minBucketDistance++;
}
}
private static void ParseRiskLevels(ReadOnlySpan<byte> input, int width, int height, Span<byte> riskLevels)
{
int riskLevelIndex = 0;
int inputIndex = 0;
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
riskLevels[riskLevelIndex++] = (byte)(input[inputIndex++] - '1');
}
inputIndex++;
}
}
}