# Spiralling Advent, Get To The Point

### Advent of Code Day 3 Challenge

Part 1:

Each square on the grid is allocated in a spiral pattern starting at a location marked 1 and then counting up while spiraling outward. For example, the first few squares are allocated like this:

17  16  15  14  13

18   5   4   3  12

19   6   1   2  11

20   7   8   9  10

21  22  23---> ...


While this is very space-efficient (no squares are skipped), requested data must be carried back to square 1 (the location of the only access port for this memory system) by programs that can only move up, down, left, or right. They always take the shortest path: the Manhattan Distance between the location of the data and square 1.

Given a number, find the number of steps required to carry the data from there back to the access port 1.

Part 2:

As a stress test on the system, the programs here clear the grid and then store the value 1 in square 1. Then, in the same allocation order as shown above, they store the sum of the values in all adjacent squares, including diagonals.

Once a square is written, its value does not change. Therefore, the first few squares would receive the following values:

147  142  133  122   59

304    5    4    2   57

330   10    1    1   54

351   11   23   25   26

362  747  806--->   ...


Given a number, find the next larger number that will be written in the grid.

### Solution

final class Day3 {

private Day3() {
// empty
}

static int stepsTo(int n) {
int layer = getLayer(n);
int end = getLayerMax(layer) - layer;
int chosen = IntStream.rangeClosed(0, 3)
.map(i -> end - 2 * layer * i)
.filter(i -> n >= i || n > i - layer)
.findFirst()
.orElseThrow(() -> new RuntimeException("Expecting a result"));
return layer + Math.abs(n - chosen);
}

static int getFirstAfter(int min) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 1; ; i++) {
if (find(map, i) > min) {
return map.get(i);
}
}
}

private static int find(Map<Integer, Integer> map, int n) {
return map.computeIfAbsent(n, k -> Math.max(1, Place.around(k)
.map(i -> find(map, i))
.sum()));
}

private static int getLayer(int n) {
int result = 0;
while (getLayerMax(result) < n) {
result++;
}
return result;
}

private static int getLayerMax(int layer) {
return (int) Math.pow(1 + (double) 2 * layer, 2);
}

private enum Place {
BOTTOM_RIGHT, BOTTOM, BOTTOM_LEFT, LEFT, TOP_LEFT, TOP, TOP_RIGHT, RIGHT;

static IntStream around(int n) {
return n == 1 ? IntStream.empty() : get(n).with(n);
}

static Place get(int n) {
for (int i = 1, t = getLayer(n), diff = 2 * t, max = getLayerMax(t);
i < values().length;
i += 2, max -= diff) {
if (max == n) {
return values()[i - 1];
} else if (max - diff < n) {
return values()[i];
}
}
throw new UnexpectedException("Expecting a result");
}

boolean isCorner() {
return ordinal() % 2 == 0;
}

private IntStream with(int n) {
int layer = getLayer(n);
int innerLayerMax = getLayerMax(layer - 1);
if (isCorner()) {
int inner = innerLayerMax - (layer - 1) * ordinal();
return this == BOTTOM_RIGHT
? IntStream.of(n - 1, inner, inner + 1)
: IntStream.of(n - 1, inner);
}
int inner = n - (4 * 2 * layer - ordinal());
int[] result = new int[]{n - 1, inner - 1, inner, inner + 1};
if (n - 1 == innerLayerMax) {
result = new int[]{n - 1, inner + 1};
} else if (n - 2 == innerLayerMax || get(n - 1).isCorner()) {
result = n - 2;
}
if (this != BOTTOM && get(n + 1).isCorner()) {
result = Arrays.copyOf(result, result.length - 1);
}
return Arrays.stream(result);
}
}
}


### Notes and Questions

1. Part 1 solution is in the method stepsTo(int), and part 2 solution is getFirstAfter(int).

2. Any optimizations that I have missed out for my solution to part 2, specifically in Place.with(int)? I feel like I keep having to compute the current layer and the maximum of the current layer every time I call Place.get(int) to derive what is the Place value for the neighbours.

3. How can I make my strategic (ahem) use of the Place.ordinal() values in the computation easier to understand, or it is fine as it-is?