17
\$\begingroup\$

This challenge will have you computing OEIS sequence A300154.

Consider a spiral on an infinite hexagonal grid. a(n) is the number of cells in the part of the spiral from 1st to n-th cell that are on the same [row*] or diagonal (in any of three directions) as the n-th cell along the spiral, including that cell itself.

(*I have very slightly changed the definition to match the orientation of the GIF below.)

The sequence begins

1, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 7, 6, 7, 7, 8, 7, 8, 9, 8, 9, 8, 9, 10, 9, 10, 11, 9, 10, 11, 10, 11, 12, 10, 11, 12, 13, 11, 12, 13, 11, 12, 13, 14, 12, 13, 14, 15, 12, 13, 14, 15, 13, 14, 15, 16, 13, 14, 15, 16, 17, 14

Example

Below is an example of the first fifteen terms of the sequence. On a hexagonal tiling, go in a spiral, and after each step, count the number of cells that you can "see" from that position, including the cell itself.

Example of A300154

Challenge

The challenge is simple, write a program that takes a positive integer n and computes \$A300154(n)\$. Again, this is so shortest code wins.

(Note: I will also award an additional bounty of 200 rep to the first person who completes this challenge in Hexagony.)

\$\endgroup\$
  • \$\begingroup\$ The format of this challenge ought to make it easy in hexagony but I'm not experienced enough in it to do it. \$\endgroup\$ – S.S. Anne Mar 18 at 18:46
  • 6
    \$\begingroup\$ Hardly anything is easy in Hexagony... \$\endgroup\$ – Luis Mendo Mar 18 at 18:47
  • \$\begingroup\$ I love how the OEIS page links to this challenge \$\endgroup\$ – rkong Mar 20 at 15:13
9
\$\begingroup\$

JavaScript (ES6),  178 169  168 bytes

Returns the \$n\$ first terms as an array.

n=>(X=[1],Y=[L=1],d=5,j=x=y=0,g=a=>--n?g([...a,(X[x+=~-'210012'[d%=6]]=-~X[x])+(Y[y+=~-'1221'[j?d:d++]]=-~Y[y])+(Z[x+y]=-~Z[x+y])-2],++j%L?0:(j%=L*6)?d++:L++):a)(Z=[1])

Try it online!

How?

This is a rather naive approach that actually computes the spiral with cube coordinates \$(x,y,x+y)\$ and keeps track of the number of cells on each row \$Z[x+y]\$, each diagonal \$Y[y]\$ and each anti-diagonal \$X[x]\$.

Commented

n => (                            // n = input
  X = [1], Y = [L = 1],           // X[] = anti-diagonals, Y[] = diagonals, L = layer
  d = 5,                          // d = direction in [0..5]
  j =                             // j = cell index in the current layer
  x = y = 0,                      // (x, y) = coordinates
  g = a =>                        // g = main recursive function taking the output a[]
    --n ?                         // decrement n; if we haven't computed enough terms:
      g(                          //   recursive call:
        [ ...a,                   //     append the previous terms
          ( X[x +=                //     update x and increment X[x]
              ~-'210012'[d %= 6]  //       pick dx according to d
            ] = -~X[x]            //
          ) +                     //
          ( Y[y +=                //     update y and increment Y[y]
              ~-'1221'[j ? d      //       pick dy according to d
                         : d++]   //       increment d afterwards if j = 0
            ] = -~Y[y]            //       (i.e. this is the 1st cell of the layer)
          ) +                     //
          (Z[x + y] = -~Z[x + y]) //     increment Z[x + y]
          - 2                     //     subtract 2 from X[x] + Y[y] + Z[z] because
        ],                        //     the current cell is counted three times
        ++j                       //     increment j
        % L ?                     //     if it's not the last cell of this side:
          0                       //       do nothing
        :                         //     else:
          (j %= L * 6) ?          //       if it's not the last cell of the layer:
            d++                   //         increment d
          :                       //       else:
            L++                   //         increment L
      )                           //   end of recursive call
    :                             // else:
      a                           //   we're done: return a[]
)(Z = [1])                        // initial call to g with a[] = Z[] = [1]
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I'm always delighted to see when you attempt a challenge of mine! \$\endgroup\$ – Peter Kagey Mar 18 at 16:39
3
\$\begingroup\$

APL (Dyalog Unicode), 23 bytesSBCS

⊢↑∘(∊⊢+∘(⍳¨⌊,⌈)¨÷∘3)⍳,⊢

Try it online!

A tacit function that returns the first n terms of the sequence.

Observation

n m | f(n,m): m consecutive integers starting at n
---------------
1 0 | 
1 1 | 1
2 0 | 
2 1 | 2
3 1 | 3
3 1 | 3
4 1 | 4
4 2 | 4 5
5 1 | 5
5 2 | 5 6
6 2 | 6 7
6 2 | 6 7
7 2 | 7 8
7 3 | 7 8 9
8 2 | 8 9
8 3 | 8 9 10
9 3 | 9 10 11
9 3 | 9 10 11
---------------
Flattened: 1 2 3 3 4 4 5 5 5 6 6 7 6 7 7 8 7 8 9 8 9 8 9 10 9 10 11 9 10 11

Though I don't have a rigorous argument that the pattern is mathematically correct, the test cases show that the first 3000 terms agree with Arnauld's JS answer.

How it works: the code

Uses ⎕IO←0, so ⍳ n gives 0 1 2 .. n-1.

⊢↑∘(∊⊢+∘(⍳¨⌊,⌈)¨÷∘3)⍳,⊢  ⍝ Input: n
                    ⍳,⊢  ⍝ Generate 0..n
   (               )     ⍝ For each number k...
                ÷∘3      ⍝ Divide k by 3
        (     )¨  ⍝ For each item of above,
           ⌊,⌈    ⍝ Collect its floor and ceil;
                  ⍝ (0 0)(0 1)(0 1)(1 1)(1 2)(1 2)(2 2)...
         ⍳¨       ⍝ For each number i, generate 0..i-1
                  ⍝ (2 3) -> ((0 1)(0 1 2))
     ⊢+∘  ⍝ Add k to each pair of ranges (results of f(n,m))
    ∊     ⍝ Enlist; collect all numbers into a vector
⊢↑∘       ⍝ Take first n numbers
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

MATL, 48 bytes

0i:"J_Q@q:gJJq1_J_tQ5$h@Y"&h]YsG:)&Zjyy+vt0Z)=as

Try it online! Or verify all test cases.

Explanation

This uses coordinate axes 60 degrees apart, so that cell coordinates are integer values. In addition, coordinates (r,s) are stored as a complex number r+j*s, where j is the imaginary unit.

The code first creates n layers of the spiral, which is enough (for most inputs, it is much more than enough). This is done by a loop that adds one layer in each iteration. The first cell is at the origin. For each new layer, the displacements from one cell to the next are defined (in the chosen system of complex coordinates): a displacement "outward" (to create room for the layer) and then several displacements "around" to complete a turn. Once all displacements for all layers have been specified, a cumulative sum produces the cell positions.

To see what is meant by "layer" and how the spiral is built, you can graphically depict the spiral with n layers. Note that the spiral is deformed because the plot uses orthogonal axes (real and imaginary), instead of axes with 60-degree separation.

Once the spiral has been created, the first n cells are kept. From these, the last cell is the reference. To detect which cells are in the same row/diagonal as the reference cell, the condition is that the candidate cell should have either the same value of the first coordinate as the reference cell, or the same value of the second coordinate, or the same value of the sum of coordinates.

0        % Push 0. This is the initial cell
i:"      % Input n. For each k in [1 2 ... n]
  J_Q    %   Push 1-j
  @q:g   %   Push [1 1 1 ... 1] (k-1 entries)
  J      %   Push j
  Jq     %   Push -1+j
  1_     %   Push -1
  J_     %   Push -j
  tQ     %   Duplicate, add 1: pushes 1-j
  5$h    %   Concatenate 5 elements into a row vector: [j -1+j -1 -j 1-j]
  @Y"    %   Repeat each entry k times
  &h     %   Concatenate everything into a row vector
]        % End
Ys       % Cumulative sum
G:)      % Keep first n entries. Gives a row vector of size n
&Zj      % Push real and imaginary parts. Gives two row vectors
yy+      % Duplicate top two elements in the stack, add
v        % Concatenate the three row vectors into a 3-row matrix
t        % Duplicate
0Z)      % Keep last column
=        % Equal? Element-wise with broadcast. Gives a true-false matrix
a        % Any: true for columns that contain at least one true entry
s        % Sum. Implicit display
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Jelly, 14 bytes

A monadic link taking an integer as input; computes the first n terms of the sequence.

÷3Ḟ,ĊƊḶ+
ŻÇ€Fḣ

Try it online! This is a port of Bubbler's answer, so be sure to upvote him as well!

How it works:

ŻÇ€Fḣ      Main link: monad taking integer n as input
Ż          Create the range [0, ..., n]
 ǀ        Map the auxiliar link over the range.
   F       Flatten...
    ḣ      and take the first n elements of that.

÷3Ḟ,ĊƊḶ+   Auxiliar link: monad taking integer k as input
÷3         Divide by 3.
   , Ɗ     Create a pair (a, b)
  Ḟ Ċ      with the floor and ceiling of the division.
      Ḷ    Finally create the ranges [0, ..., a-1] and [0, ..., b-1]
       +   and add k to each number in each range.
|improve this answer|||||
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.