Advent of Code Day 3 螺旋内存

解题语言不限Java

谜题还有第二部分，不过是留给大家的，能解出第一题的，才能写第二题

题目内容

You come across an experimental new kind of memory stored on an infinite two-dimensional grid.

你来到一个在无限大的二维矩阵上建立的实验性内存。

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:

在这个矩阵上，每一个方格都从一个标着1的原点格按螺旋状排列向外展开。比如说，前几个方格的位置如图。

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.

这是一个空间利用率非常高的内存，但是需要的数据必须能返回原点1的方格，数据只能前后左右的移动。内存移动总是取最近的路径：距离原点的曼哈顿距离。

For example:

Data from square 1 is carried 0 steps, since it's at the access port.
在1格的数据需要0步，因为他已经在原点了。
Data from square 12 is carried 3 steps, such as: down, left, left.
在12格的数据需要3步，下左左
Data from square 23 is carried only 2 steps: up twice.
在23格的数据需要移动2步，上上
Data from square 1024 must be carried 31 steps.
在1024格的数据要移动31步
How many steps are required to carry the data from the square identified in your puzzle input all the way to the access port?
那么从给定的位置移动到原点需要多少步

解题思路

终于有些有难度的题目了

读题可知，本题的主要难度在生成螺旋的序列。

例子

观察这个序列可以发现

从就方格到新方格的移动顺序总是左，上，右，下。
每次移动的距离是不断增加的，走一格两次，走两个两次，以此类推。

所以把这两个规律叠加在一起，我们就可以生成一个可以预测的序列：

左 | 上 | 右右 | 下下 | 左左左

然后通过读题，我们一个找到这个点到原点的曼哈顿距离。其实曼哈顿距离是指这个点X坐标的绝对值加上Y坐标的绝对值：
D=|x|+|y|

以下是本人的方法，解法不唯一

首先我创建了一个移动序列Point displacementList[]={new Point(1,0),new Point(0,1),new Point(-1,0),new Point(0,-1)}; 这个序列储存的4个移动的方向：左（1,0），上（0,1），右（-1,0），下（0,-1）。
接下来应该有一个值来记录步长int length=1，因为这个序列一开始就移动，所以步长应该从1开始。
原点我用Point pointer=new Point(0,0)表示.
我用了一个ArrayList<Point> points=new ArrayList<Point>()

设完变量就应该组合逻辑了。在主函数里：

应该有一个for循环来使pointer移动指定次数

  for(int l=0;l<length;l++)

2.应该有另一个for循环来循环读取displacementList里的移动点坐标

  for(int dis=0;dis<4;dis++)

在每次移位之后,points里应该增加新的数据，pointer应该指向最新的位置

  Point newPoint=new Point(pointer.x+displacementList[dis].x,pointer.y-displacementList[dis].y);
  points.add(newPoint);
  pointer=newPointer;

当length的动作读完了之后，length应该增加

剩下的就是调试了。

Github 的源代码会在Advent of Code 结束之后发布

Advent of Code Day 3 螺旋内存

题目内容

解题思路

推荐阅读更多精彩内容