1
\$\begingroup\$

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[1] = 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?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.