Hexagonal adjacency

Question

The above image displays a hexagonal grid of hexagons. Each cell in the grid is assigned an index, starting from the center and spiraling counterclockwise around as shown. Note that the grid will continue indefinitely - the above picture is simply the first section. The next hexagon would be adjacent to 60 and 37.

Your task is to determine if two given cells on this grid are adjacent.

Write a program or function that, given two cell indices, prints/returns a truthy value if the two cells are adjacent, and a falsey value if not.

If not limited by practical reasons, your code should theoretically work for any size inputs.

Truthy test cases:

0, 1
7, 18
8, 22
24, 45
40, 64
64, 65

Falsey test cases:

6, 57
29, 90
21, 38
38, 60
40, 63
41, 39
40, 40

This is code-golf so the shortest answer in bytes wins. Explanations, even for non-esoteric languages, are encouraged.

Answer 1

Elixir, 263 257 264 223 214 218 214 bytes

a=fn x,y->i=&(&1*(&1-1)*3+1)
[x,y]=Enum.sort [x,y]
if x<1,do: y in 1..6,else: (y-x==1||fn->a=y-trunc i.((r=(:math.sqrt(12*x-3)+3)/6)+1)
t=trunc r
a in [0,1,rem(b=x-i.(t)+1, t)<1&&b-t*6!=0&&2]||b<2&&a==-1 end.())end

Try it online!

ungolfed version

def get_ring(x) do
    1/6*(:math.sqrt(12*x-3)+3)
end

def inv_get_ring(x), do: x*(x-1)*3+1

def ring_base(x), do: inv_get_ring(trunc(x))

def is_corner(x) do
    ring = trunc(get_ring(x))
    inv_ring = ring_base(ring)
    stuff = (x-inv_ring+1)
    rem(stuff, ring) == 0
end

def is_last(x),do: ring_base(get_ring(x)+1)-1 == x
def is_first(x),do: ring_base(get_ring(x)) == x

def hex_adj(x, y) do
    {x, y} = {min(x,y), max(x,y)}
    cond do 
        x == 0 ->y in 1..6      
        y-x==1 -> true
        true ->
            adj = trunc(inv_get_ring(get_ring(x)+1))
            number = if is_corner(x)&&!is_last(x), do: 2, else: 1
            if y-adj in 0..number do
                true
            else
                is_first(x) && y == adj-1
            end
    end
end

• trunc(number) Returns the integer part of number
• rem(a,b) Returns the remainder of a/b
• cond do end This is equivalent to else if or switch case clauses in many imperative languages

Explanation

get_ring(index)

Calculates the "ring" of the index.

Example: 1 for 1-6, 2 for 7-18, etc.

This only applies if the result is floored. Trailing digits represent how far that tile is around the ring.

inv_get_ring(ring)

Calculates the inverse of get_ring(index).

ring_base(ring)

Calculates the index of the first tile in the ring.

is_corner(index)

Corners are tiles that have three adajcent tiles in the outer ring. The innermost ring consists entirely of corners.

Examples: 21,24,27,30,33,36

is_last(index)

Is true if this index is the highest in its ring.

is_first(index)

Is true if this is the base-tile of the ring.

Answer 2

MATL, 47 45 44 43 41 bytes

s:"JH3/^6:^t5)w5:&)@qY"w@Y"]vYs0hG)d|Yo1=

Try it online! Or verify all test cases.

As a bonus, the code generates a hexagonal spiral that traces the positions of the cell centers, which can be seen graphically at MATL Online by modifying the last part of the code.

Explanation

General idea   The code first builds a sufficiently large hexagonal spiral with unit step. The spiral is defined as a vector of complex numbers representing positions of the cell centers. Indexing into that vector with the input numbers and computing the absolute difference gives the distance between the two indicated cells. Cells are adjacent if and only if the result is 1. However, due to floating point inaccuracies, rounding is necessary before comparing with 1.

Building the spiral   The spiral will have a number of "layers" equal to the sum of the two inputs. This is (much) larger than necessary, and ensures that the input cells will be present in the spiral.

To build the spiral, the complex number j ^2/3 (where j is the imaginary unit) is first computed. Raising this to exponents 1 through 6 gives a basic set of displacements, such that following those displacements in order would trace a hexagon. This hexagon would form the innermost layer of the spiral, except that it would be "closed". Actually, we want that hexagon to "grow" at the last step and then we trace a larger hexagon, with twice as many points (aligned in groups of two), to form the next layer of the spiral; see illustration here. The next layer will have thrice as many points as the first (in groups of three); see here.

To do this, the fifth displacement from the basic set (which points in the south-east direction) is chosen as the "growing" step. Layer k begins with that step, followed by the first five basic steps repeated k times, followed by the sixth step (east direction) repeated k−1 times. This hopefully becomes clearer by looking at the two figures linked above.

The resulting vector, including all layers, represents the complex displacements that would trace the spiral. Cumulative sum gives the actual coordinates of the cell centers.

Lastly, the initial cell, located at 0, is attached to the end of this vector. This is because MATL uses modular 1-based indexing, and index 0 refers to that last entry of an array.

Testing for adjacency   The two cells given by the input numbers are selected, their coordinates are subtracted, and the absolute value is rounded and compared with 1.

Commented code

s         % Implicitly input array of two numbers. Push their sum, say S
:         % Range [1 2 ... S]
"         % For each k in [1 2 ... S]
  J       %   Push 1j
  H3/     %   Push 2, then 3, then divide: gives 2/3
  ^       %   Power
  6:      %   Push [1 2 ... 6]
  ^       %   Element-wise power. This is the array of 6 basic displacements
  t5)     %   Duplicate. Get 5th entry
  w5:&)   %   Swap. Push subarray with entries 1st to 5th, then push 6th
  @qY"    %   Repeat the 6th displacement k-1 times
  w@Y"    %   Swap. Repeat 1st to 5th displacements k times
]         % End
v         % Concatenate everything into a column vector
Ys        % Cumulative sum. This gives the cell center coordinates
0h        % Append a 0
G)        % Index by the input vector
d|        % Absolute difference
Yo        % Round to nearest integer
1=        % Does it equal 1? Implicitly display

Answer 3

05AB1E (legacy), 30 29 27 bytes

α2‹i1q}1ݹ+v12y*3-tîÌy+}Ÿ²å

Try it online!

Explanation of code:

α2‹i1q}                     : if the absolute diff of the two number is 1 or 0 return 1
                          ²å: return that the second number is in
                         Ÿ  : range of {
       1Ý                   :  create [0, 1]
         ¹+                 :  add the first number to the elements
           v            }   :  map that list
            12y*3-tîÌy+     :  calculate the corresponding value where it's an adjacency
                                }

Explanation of math:

I "wasted" around 5 hours making this golf. In short I started making a 2d graph of the inputs, and draw X where they were adjacency to each other. Then I found a pattern. I searched for it on OEIS and bingo! I found that sequence and I used the formula given on the website.

Answer 4

C (gcc), 175 173 bytes

Thanks to Peter Taylor for catching a bug.

Thanks to ceilingcat for -2 bytes. That ~ operator continues to be my main blindspot.

c,r,C,L;y(a){a=a<L*2?L-a:a<L*3?-L:a<5*L?a-L*4:L;}z(a){L=ceil(sqrt(a/3.+.25)-.5);C=y(a-=3*L*~-L);L?L=y((L+a)%(L*6)):0;}f(a,b){z(a);c=C,r=L;z(b);a=a-b&&(abs(c-C)|abs(r-L))<2;}

Try it online!

This approach is focused on finding the row and the column of the two cells and compare them; any neighbours cannot have their corresponding coordinates differ by more than 1. Moving from the center outwards, we observe that each layer has 6 more cells than the previous. This means that the highest "index" in each layer L is on the form 6 * (L * (L - 1) * (L - 2) ...), or C = 6 * (L² + L) / 2, where C is the "global" cell number. Shuffling things around, we get L² + L - C / 3 = 0, which gives high-school math flashbacks. From that, we get the formula ceil (sqrt (1 / 4 + C / 3) + 0.5). Plugging a global cell index into it, we receive which layer the cell is in.

Since the first cell in each layer is naturally one higher than the highest of the previous layer, we find L_start = (6 * (L - 1)² + (L - 1)) / 2, which simplifies to 3 * (L² - L). From that we get the layer index L_index = C - L_start.

Next up, we see that each layer is comprised of six sections, each of length L. Starting at north-east and going counter-clockwise, we see that for the first two sections (1 <= L_index <= 2 * L), we get the column from L - L_index. The next section L * 2 < L_index <= L * 3 have all cells sharing a single column -L. The two next sections are L * 3 < L_index <= L * 5 with their columns according to L_index - L * 4. And lastly the sixth section all have its cells on column L. We can shift the upper bounds one step along to save some bytes in the code.

So then what about the rows? To reuse code, we turn the grid so that cell 44 is straight up. Then we run the same logic as for columns but call the results "rows" this time around. Of course, instead of actually turning a grid, we just walk 1 / 6 of a lap around it.

Answer 5

Python 3, 150 bytes

def h(a,b):
 L=[];i=1
 while len(L)<a+b:r=sum((i*[1j**(k/3)]for k in range(4,16,2)),[]);r[0]+=1;L+=r;i+=1
 return.9<abs(sum(L[min(a,b):max(a,b)]))<1.1

My solution basically follows the same line of thought as Luis Mendo's above. If written more readable, the code is pretty self-explanatory:

def h(a,b):
    L=[]
    i=1
    while len(L)<a+b:
        l=sum((i*[1j**(k/3)]for k in range(4,16,2)),[])
        l[0]+=1
        L+=l
        i+=1
return .9<abs(sum(L[min(a,b):max(a,b)]))<1.1

1. function h does the following:
2. List L will contain the (complex) positions of each number.
3. i is the ring number.
4. In the while-loop, a new ring is added every iteration. Instead of figuring out how many rings we need, we just continue to build the list until it is long enough to contain a+b, then it is certainly long enough to contain either of them.
5. the 'ring-list' l is a concatenation of 6 lists of len(i) times the step-vector, where the step-vector is 1j**(2/3) to some power. The range does not start at 0 but at 4, which causes a rotation of the whole grid. This allows me to do:
6. l[0]+=1 in line 6, which is the step from one ring to the next.
7. L+=l concatenates the complete list and the ring-list.
8. List L contains only step vectors, which still must be summed (integrated) to get a position. A neat feature here is that we can just sum the slice from the lowest number to the highest to get their distance! Because of roundoff errors, the result won't be exactly 1, hence the .9<...<1.1. Interestingly, the zero case h(0,0) or h(0,1) is taken care of implicitly, because the sum of an empty list is zero. If I could be sure that a<b, ie the arguments would come in increasing order, I could shave off another 14 bytes by replacing L[min(a,b):max(a,b)] with L[a:b], but alas!

PS: I didn't know this was such an old challenge, it showed up on top a few days ago, and kept nagging on me since:)

Answer 6

Mathematica, 111 105 104 bytes

r=Floor[(1+Sqrt[(4#-1)/3])/2]&;t=Limit[Pi(#/(3x)+1-x),x->r@#]&;p=r@#*Exp[I*t@#]&;Round@Abs[p@#-p@#2]==1&

Explanation:

r=Floor[(1+Sqrt[(4#-1)/3])/2]& defines a function r which takes input # and calculates the distance (in number of cells) to cell 0. It does this by exploiting the pattern in the last cells of each distance/ring: 0=3(0^2+0), 6=3(1^2+1), 18=3(2^2+2), 36=3(3^2+3),... and inverting the formula for that pattern. Note that for cell 0, it actually takes the floor of (1/2)+i *(sqrt(3)/6), which it calculates component-wise to get 0+0 * i = 0.

With r defined, r@# is the ring for cell # (inside the definition of another function). #+3r@#-3(r@#)^2& does not appear in the code exactly, but it takes the number of a cell and subtracts the highest number of a cell in the next inner ring, so that it gives the answer to the question "which cell of the current ring is this?" For example, cell 9 is the 3rd cell of ring 2, so r[9] would output 2 and #+3r@#-3(r@#)^2&[9] would output 3.

What we can do with the function above is use it to find the polar angle, the counter-clockwise angle from the "cell 0, cell 17, cell 58" ray to the cell in question. The last cell of every ring is always at an angle Pi/6, and we go around a ring in increments of Pi/(3*ring_number). So, in theory, we need to calculate something like Pi/6+(which_cell_of_the_current_ring)*Pi/(3*ring_number). However, the rotation of the picture doesn't affect anything, so we can discard the Pi/6 part (to save 6 bytes). Combining this with the previous formula and simplifying, we get Pi(#/(3r@#)+1-r@#)&

Unfortunately, this is undefined for cell 0 since its ring number is 0, so we need to get around this. A natural solution would be something like t=If[#==0,0,Pi(#/(3r@#)+1-r@#)]&. But since we don't care about the angle for cell 0 and because r@# is repeated, we can actually save a byte here with t=Limit[Pi(#/(3x)+1-x),x->r@#]&

Now that we have the ring number and the angle, we can to find the position of a cell (center) so we can test for adjacency. Finding the actual position is annoying because the rings are hexagonal, but we can simply pretend the rings are perfect circles so that we treat ring number as the distance to the center of cell 0. This won't be a problem since the approximation is pretty close. Using the polar form of a complex number, we can represent this approximate position in the complex plane with a simple function: p = r@#*Exp[I*t@#] &;

The distance between two complex numbers on the complex plane is given by the absolute value of their difference, and then we can round the result to take care of any errors from the approximation, and check if this is equal to 1. The function that finally does this work doesn't have a name, but is Round@Abs[p@#-p@#2]==1&.

---

You can try it online in the Wolfram Cloud sandbox by pasting code like the following and clicking Gear->"Evaluate cell" or hitting Shift+Enter or the numpad Enter:

r=Floor[(1+Sqrt[(4#-1)/3])/2]&;t=Limit[Pi(#/(3x)+1-x),x->r@#]&;p=r@#*Exp[I*t@#]&;Round@Abs[p@#-p@#2]==1&[24,45]

Or for all test cases:

r=Floor[(1+Sqrt[(4#-1)/3])/2]&;t=Limit[Pi(#/(3x)+1-x),x->r@#]&;p=r@#*Exp[I*t@#]&;Round@Abs[p@#-p@#2]==1&//MapThread[#,Transpose[{{0,1},{7,18},{8,22},{24,45},{40,64},{64,65},{6,57},{29,90},{21,38},{38,60},{40,63},{41,39},{40,40}}]]&