AoCG2021 Day 9: Spiral memory stress test

Question

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2017 Day 3, Part 2.

---

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:

17  16  15  14  13
18   5   4   3  12
19   6   1   2  11
20   7   8   9  10
21  22  23---> ...

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, not including diagonals.

So, the first few squares' values are chosen as follows:

• Square 1 starts with the value 1.
• Square 2 has only one adjacent filled square (with value 1), so it also stores 1.
• Square 3 is the same (diagonal neighbors don't count), so it also stores 1.
• Square 4 has squares 1 and 3 as neighbors and stores the sum of their values, 2.
• Square 5 has square 4 as its only neighbor, so it gets the value 2.

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

 12   12   10    8    7
 14    2    2    1    7
 17    3    1    1    6
 20    3    4    5    5
 20   23   27--->   ...

What is the first value written that is at least as large as the input (a positive integer)?

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

1 -> 1
2 -> 2
9 -> 10
18 -> 20
50 -> 55
100 -> 111
200 -> 214
500 -> 552
1000 -> 1070
1070 -> 1070

Answer 1

Charcoal, 49 bytes

Ｎθ≔⟦¹⟧ηＷ‹⌈ηθ«⊞υη≔ＥηＥ⮌υ§μλυ≔Ｅ§υ⁰Σ…§υ±¹⊕λη»Ｉ⌊Φ笋ιθ

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input the target.

≔⟦¹⟧η

Start with the middle cell.

Ｗ‹⌈ηθ«

Repeat until the target is reached.

⊞υη

Add the latest row to the grid.

≔ＥηＥ⮌υ§μλυ

Rotate the grid.

≔Ｅ§υ⁰Σ…§υ±¹⊕λη

Take the cumulative sum of the new last row.

»Ｉ⌊Φ笋ιθ

Output the smallest value not lower than the target.

Answer 2

J, ³⁹ 37 bytes

{{y(<:<./@#]),|:@|.@(,+/\@{:)^:y,.1}}

-2 thanks to Olius's idea of using direct definition {{ }} instead of a tacit verb

YAPONA - Yet Another Port of Neil's Answer.

To save bytes, we repeat the iteration <input> times -- which is always enough, and usually returns much more than we need -- then find the first valid number within that result.

No TIO for this one because the TIO J version is too old and doesn't have {{ }} yet. I tested locally though and it works. TIO'd tacit version below.

J, 39 bytes tacit solution with TIO

(<:<./@#&,])]1&(](,~+/\.@{.)@|:@|.),.@1

Try it online!

Answer 3

Ruby, 80 78 75 66 bytes

->n,*r{(n+a=1).times{|x|r<<a;(1..x/2).map{a<n&&r<<a+=r[1-x-x]}};a}

Try it online!

Explanation (if it still matters):

• We need at most (n+1) segments to find the number (n=2,3,4 can't be found on the 2nd 3rd and 4th segment).

• Length of segments (removing corners) is 0, 0, 1, 1, 2, 2, 3, 3 ...

• In the corners we can reuse the previous value: x[n]=x[n-1]

• For the other cells: x[n]=x[n-1]+x[n-m] where m is increased by 2 for every side.

Maybe there is a way to skip the corners? we don't need the repeated values to find the final result, only to calculate the other intermediate values.

Answer 4

Python 3.8 (pre-release), 96, 94, 92 (@dingledooper), 90 bytes (@xnor)

def f(i):
 *T,s=1,;t=T,[1],[1]
 while i>s:T,*t=*t,[s:=s+x*(i>s)for x in[0,*T,0]]
 return s

Try it online!

Older versions

Try it online!

Try it online!

Try it online!

This keeps a running sum s and the four sides of the growing rectangle/spiral double accounting for corners. T holds the "active" side, t the three others.

Answer 5

JavaScript (ES6), 73 bytes

n=>eval("for(j=k=0,a=[t=q=1];q<n;)a.push(q+=j--?a[++t-k]:![j=++k>>1]);q")

Try it online!

Commented

This is a version without eval() for easier formatting.

n => {               // n = input
  for(               // main loop:
    j =              //   j is the length of the current segment minus 1
    k = 0,           //   k is incremented after each segment
                     //   (which means that it holds the number of turns)
                     //   the length of the next segment is floor((k+1)/2)
    a = [            //   a[] is used to store the sequence
      t =            //   t+1-k is the index of the neighbor cell in the
                     //   previous layer of the spiral
      q = 1          //   q is the current value of the sequence
    ];               //
    q < n;           //   we keep going until q >= n
  )                  //
    a.push(          //   append to a[]:
      q +=           //     the updated value of q
        j--          //     decrement j
        ?            //     if we haven't reached the end of the segment:
          a[++t - k] //       increment t and add the value of the
                     //       neighbor cell in the previous layer
        :            //     else (this is a corner):
          ![         //       leave q unchanged
            j =      //       increment k and update j to
            ++k >> 1 //       floor(k/2)
          ]          //
    );               //   end of push()
  return q           // end of for(); return q
}                    //

Answer 6

JavaScript (Node.js), 91 bytes

f=(n,o=p=[X=x=y=0,Y=v=1])=>n>(o[[x+=o[p]?X:X+=Y+(Y=-X),y+=Y]]=v+=o[p=[x+Y,y-X]]|0)?f(n,o):v

Try it online!

Answer 7

Pari/GP, 87 bytes

n->a=Mat(1);until(d=[b|b<-c,b>=n],s=0;a=Mat(Vecrev(concat(c=[s+=b|b<-a[,1]],a~))));d[1]

Try it online!

A port of @Neil's answer.

Answer 8

05AB1E, 18 bytes

1¸¸IFøí¤ηOª}˜ʒI@}ß

Port of @Neil's Charcoal answer.

Try it online or verify all test cases (the test suite loops until the result is found (IF replaced with [ZI@#), since looping \$n\$ times will time out for the larger test cases).

Explanation:

1¸¸         # Start matrix at center [[1]]
   IF       # Loop the input amount of times:
     øí     #  Rotate the matrix once clockwise:
     ø      #   Zip/transpose; swapping rows/columns
      í     #   Reverse each row
       ¤    #  Get the last row (without popping the matrix)
        ηO  #  Get the cumulative sum:
        η   #   Pop and push a list of its prefixes
         O  #   Sum each inner list
          ª #  Add this row to the matrix
    }˜      # After the loop: flatten the matrix to a list
      ʒ     # Filter this list of integers by:
       I@   #  Keep those larger than or equal to the input
      }ß    # After the filter: pop and push the minimum
            # (which is output implicitly as result)

ʒI@}ß could alternatively be I<LKß (push list \$[1,input)\$, remove those values, minimum) or {.Δ>‹ (sort, find first \$n\$ which is \$input\lt n+1\$) for the same byte-count.

Answer 9

Rust, 155 151 bytes

|a|{let(mut s,mut v)=(1,vec![0,1,1]);for i in(0..).flat_map(|i|{s+=i/2;(0..1).chain(s-i/2..=s)}){let r=v[i]+v[v.len()-1];v.push(r);if r>=a{return r}}0}

Try it online!

This works by generating A334742 (the actual numbers in the spiral) using A265400 (indices of adjacent squares), which is generated using A004526 (length of each corner, which increases every two rotations).

• -4 bytes by replacing the outer iterator with for

Answer 10

BQN, 31 bytes ^SBCS

{⊑≥⟜𝕩⊸/∧⥊{⌽˘⍉𝕩∾+`⊏⌽𝕩}⍟𝕩≍≍1}

Run online!

Similar idea to Neil's answer. Some combinators come in really handy here.

Answer 11

TypeScript Types, 389 bytes

//@ts-ignore
type a<T,K=keyof T>=T extends T?keyof T extends K?T:never:0;type b<T,N=[],U=[]>=T extends[infer A,...infer T]?b<T,[...N,...A],[...U,[...N,...A]]>:U;type c<N,A=[[0]],B=A,C=A,D=A,E=b<A>,F=E[number]>=1 extends(F extends N?1:0)?a<Extract<F,N>>:E extends[...{}[],infer L]?c<N,[L,...B],C,[...D,A[0]],E>:0;type M<N,m=[]>=N extends m["length"]?c<[...m,...0[]]>["length"]:M<N,[...m,0]>

Try It Online!

Ungolfed / Explanation

// Filters a union of tuples for those with the shortest length
type Shortest<T, K = keyof T> = T extends T ? keyof T extends K ? T : never : 0

// Turns [a, b, c, d] into [a, a+b, a+b+c, a+b+c+d]
type CumSum<T, N=[], U=[]> = T extends [infer A,...infer T] ? CumSum<T, [...N, ...A], [...U, [...N, ...A]]> : U

// Extends the spiral one side at a time until one of the numbers is matches N
// If the spiral is
//   a b c d
//   e f g h
//   i j k l
//   '->
// (where g was the start)
// It will be represented as A=[i,j,k,l] ; B=[l,h,d] ; C=[d,c,b,a] ; D=[a,e,i]
// The next iteration will be
//   a b c d
//   e f g h
//   i j k l ^
//   m n o p-'
// Where m=i ; n=m+j ; o=n+k ; p=o+l
// And is represented as A=[p,l,h,d] ; B=[d,c,b,a] ; C=[a,e,i,m] ; D=[m,n,o,p]
// The spiral starts as A=B=C=D=[1] ([[0]] in tuple form)
type Iterate<Cond, A=[[0]], B=A, C=A, D=A, New=CumSum<A>, NewNums=New[number]> =
  1 extends (NewNums extends Cond ? 1 : 0)
    // If any of NewNums match Cond, return the shortest of those that do
    ? Shortest<Extract<NewNums, Cond>>
    : New extends [...{}[],infer L]
      // Get the last element of New, and update the spiral sides
      ? Iterate<Cond, [L,...B], C, [...D, A[0]], New>
      // Unreachable
      : 0

type Main<N,M=[]> =
  N extends M["length"]
    // If M's length is N, return Iterate where Cond is >= M
    ? Iterate<[...M,...0[]]>["length"]
    // Increment M and repeat
    : Main<N, [...M, 0]>

Answer 12

Wolfram Language (Mathematica), 76 bytes

Min@Cases[Nest[Reverse@Append[#,Accumulate@Last@#]&,{{1}},#],b_/;b>=#,2]&

Try it online!

A port of @Neil's answer.

Answer 13

Python3, 261 bytes

f=lambda n,c=[[1],[1],[1]]:c[-1][-1]if c[-1][-1]>=n else(f(n,c[:-1]+[(c[-1]+[c[-1][-1]+k[len(c[-1])-1]if len(k:=c[len(c)>4 and -5]+([]if len(c)<4 else[c[-4][0]]))>=len(c[-1])else c[-1][0]])])if all(len(c[-1])<= len(i)for i in c[-3:-1])else f(n,c+[[c[-1][-1]]]))

Not a very fancy solution, at each recursive call, builds a side of the spiral square.

Try it online!

Answer 14

R, 91 bytes

function(x,m=t(1)){while(x>max(m))m=rbind(cumsum((m=t(m[,ncol(m):1]))[1,]),m);min(m[m>=x])}

Try it online!