The Path Of The Wildebeest












23












$begingroup$


Golf a program or function which gives the $n^{text{th}}$ location of the wildebeest who starts at square $1$ on an infinite chessboard which is numbered in an anti-clockwise square spiral, where the wildebeest always visits the lowest numbered square she can reach that she has not yet visited.



Inspiration: The Trapped Knight and OEIS A316667.



Edit: This sequence is now on the OEIS as A323763.



The code may produce the $n^{text{th}}$ location, the first $n$ locations, or generate the sequence taking no input.



Feel free to give her location after (or up to) $n$ leaps instead, but if so please state this clearly in your answer and make sure that an input of $n=0$ yields 1 (or [1] if appropriate).



This is code-golf, so the aim is to produce working code in as few bytes as possible in your chosen language.



Note: the wildebeest becomes trapped (much like the knight does at his $2016^{text{th}}$ location, square $2084$, and the camel does at his $3723^{text{rd}}$, square $7081$) at her $12899744968^{text{th}}$ location on square $12851850258$. The behaviour of your code may be undefined for $n$ larger than this. (Thanks to Deadcode for the C++ code that found this!)



Detail



The board looks like the below, and continues indefinitely:



101 100  99  98  97  96  95  94  93  92  91

102  65  64  63  62  61  60  59  58  57  90

103  66  37  36  35  34  33  32  31  56  89

104  67  38  17  16  15  14  13  30  55  88

105  68  39  18   5   4   3  12  29  54  87

106  69  40  19   6   1   2  11  28  53  86

107  70  41  20   7   8   9  10  27  52  85

108  71  42  21  22  23  24  25  26  51  84

109  72  43  44  45  46  47  48  49  50  83

110  73  74  75  76  77  78  79  80  81  82

111 112 113 114 115 116 117 118 119 120 121


A wildebeest is a "gnu" fairy chess piece - a non-standard chess piece which may move both as a knight (a $(1,2)$-leaper) and as a camel (a $(1,3)$-leaper).

As such she could move to any of these locations from her starting location of $1$:



  .   .   .   .   .   .   .   .   .   .   .

  .   .   .   .  35   .  33   .   .   .   .

  .   .   .   .  16   .  14   .   .   .   .

  .   .  39  18   .   .   .  12  29   .   .

  .   .   .   .   .  (1)  .   .   .   .   .

  .   .  41  20   .   .   .  10  27   .   .

  .   .   .   .  22   .  24   .   .   .   .

  .   .   .   .  45   .  47   .   .   .   .

  .   .   .   .   .   .   .   .   .   .   .


The lowest of these is $10$ and she has not yet visited that square, so $10$ is the second term in the sequence.



Next she could move from $10$ to any of these locations:



  .   .   .   .   .   .   .   .   .   .   .

  .   .   .   .   .   .  14   .  30   .   .

  .   .   .   .   .   .   3   .  29   .   .

  .   .   .   .   6   1   .   .   .  53  86

  .   .   .   .   .   .   . (10)  .   .   .

  .   .   .   .  22  23   .   .   .  51  84

  .   .   .   .   .   .  47   .  49   .   .

  .   .   .   .   .   .  78   .  80   .   .

  .   .   .   .   .   .   .   .   .   .   .


However, she has already visited square $1$ so her third location is square $3$, the lowest she has not yet visited.




The first $100$ terms of the path of the wildebeest are:



1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 18, 15, 12, 16, 19, 22, 41, 17, 33, 30, 34, 13, 27, 23, 20, 24, 44, 40, 21, 39, 36, 60, 31, 53, 26, 46, 25, 28, 32, 29, 51, 47, 75, 42, 45, 71, 74, 70, 38, 35, 59, 56, 86, 50, 78, 49, 52, 80, 83, 79, 115, 73, 107, 67, 64, 68, 37, 61, 93, 55, 58, 54, 84, 48, 76, 43, 69, 103, 63, 66, 62, 94, 57, 87, 125, 82, 118, 77, 113, 72, 106, 148, 65, 97, 137, 91, 129, 85


The first $11$ leaps are knight moves so the first $12$ terms coincide with A316667.






code-golf sequence integer chess







share|improve this question











$endgroup$












  • $begingroup$
    Comments are not for extended discussion; this conversation has been moved to chat.
    $endgroup$
    – Mego♦
    Jan 29 at 14:05
















23












$begingroup$


Golf a program or function which gives the $n^{text{th}}$ location of the wildebeest who starts at square $1$ on an infinite chessboard which is numbered in an anti-clockwise square spiral, where the wildebeest always visits the lowest numbered square she can reach that she has not yet visited.



Inspiration: The Trapped Knight and OEIS A316667.



Edit: This sequence is now on the OEIS as A323763.



The code may produce the $n^{text{th}}$ location, the first $n$ locations, or generate the sequence taking no input.



Feel free to give her location after (or up to) $n$ leaps instead, but if so please state this clearly in your answer and make sure that an input of $n=0$ yields 1 (or [1] if appropriate).



This is code-golf, so the aim is to produce working code in as few bytes as possible in your chosen language.



Note: the wildebeest becomes trapped (much like the knight does at his $2016^{text{th}}$ location, square $2084$, and the camel does at his $3723^{text{rd}}$, square $7081$) at her $12899744968^{text{th}}$ location on square $12851850258$. The behaviour of your code may be undefined for $n$ larger than this. (Thanks to Deadcode for the C++ code that found this!)



Detail



The board looks like the below, and continues indefinitely:



101 100  99  98  97  96  95  94  93  92  91

102  65  64  63  62  61  60  59  58  57  90

103  66  37  36  35  34  33  32  31  56  89

104  67  38  17  16  15  14  13  30  55  88

105  68  39  18   5   4   3  12  29  54  87

106  69  40  19   6   1   2  11  28  53  86

107  70  41  20   7   8   9  10  27  52  85

108  71  42  21  22  23  24  25  26  51  84

109  72  43  44  45  46  47  48  49  50  83

110  73  74  75  76  77  78  79  80  81  82

111 112 113 114 115 116 117 118 119 120 121


A wildebeest is a "gnu" fairy chess piece - a non-standard chess piece which may move both as a knight (a $(1,2)$-leaper) and as a camel (a $(1,3)$-leaper).

As such she could move to any of these locations from her starting location of $1$:



  .   .   .   .   .   .   .   .   .   .   .

  .   .   .   .  35   .  33   .   .   .   .

  .   .   .   .  16   .  14   .   .   .   .

  .   .  39  18   .   .   .  12  29   .   .

  .   .   .   .   .  (1)  .   .   .   .   .

  .   .  41  20   .   .   .  10  27   .   .

  .   .   .   .  22   .  24   .   .   .   .

  .   .   .   .  45   .  47   .   .   .   .

  .   .   .   .   .   .   .   .   .   .   .


The lowest of these is $10$ and she has not yet visited that square, so $10$ is the second term in the sequence.



Next she could move from $10$ to any of these locations:



  .   .   .   .   .   .   .   .   .   .   .

  .   .   .   .   .   .  14   .  30   .   .

  .   .   .   .   .   .   3   .  29   .   .

  .   .   .   .   6   1   .   .   .  53  86

  .   .   .   .   .   .   . (10)  .   .   .

  .   .   .   .  22  23   .   .   .  51  84

  .   .   .   .   .   .  47   .  49   .   .

  .   .   .   .   .   .  78   .  80   .   .

  .   .   .   .   .   .   .   .   .   .   .


However, she has already visited square $1$ so her third location is square $3$, the lowest she has not yet visited.




The first $100$ terms of the path of the wildebeest are:



1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 18, 15, 12, 16, 19, 22, 41, 17, 33, 30, 34, 13, 27, 23, 20, 24, 44, 40, 21, 39, 36, 60, 31, 53, 26, 46, 25, 28, 32, 29, 51, 47, 75, 42, 45, 71, 74, 70, 38, 35, 59, 56, 86, 50, 78, 49, 52, 80, 83, 79, 115, 73, 107, 67, 64, 68, 37, 61, 93, 55, 58, 54, 84, 48, 76, 43, 69, 103, 63, 66, 62, 94, 57, 87, 125, 82, 118, 77, 113, 72, 106, 148, 65, 97, 137, 91, 129, 85


The first $11$ leaps are knight moves so the first $12$ terms coincide with A316667.






code-golf sequence integer chess







share|improve this question











$endgroup$












  • $begingroup$
    Comments are not for extended discussion; this conversation has been moved to chat.
    $endgroup$
    – Mego♦
    Jan 29 at 14:05














23












23








23





$begingroup$


Golf a program or function which gives the $n^{text{th}}$ location of the wildebeest who starts at square $1$ on an infinite chessboard which is numbered in an anti-clockwise square spiral, where the wildebeest always visits the lowest numbered square she can reach that she has not yet visited.



Inspiration: The Trapped Knight and OEIS A316667.



Edit: This sequence is now on the OEIS as A323763.



The code may produce the $n^{text{th}}$ location, the first $n$ locations, or generate the sequence taking no input.



Feel free to give her location after (or up to) $n$ leaps instead, but if so please state this clearly in your answer and make sure that an input of $n=0$ yields 1 (or [1] if appropriate).



This is code-golf, so the aim is to produce working code in as few bytes as possible in your chosen language.



Note: the wildebeest becomes trapped (much like the knight does at his $2016^{text{th}}$ location, square $2084$, and the camel does at his $3723^{text{rd}}$, square $7081$) at her $12899744968^{text{th}}$ location on square $12851850258$. The behaviour of your code may be undefined for $n$ larger than this. (Thanks to Deadcode for the C++ code that found this!)



Detail



The board looks like the below, and continues indefinitely:



101 100  99  98  97  96  95  94  93  92  91

102  65  64  63  62  61  60  59  58  57  90

103  66  37  36  35  34  33  32  31  56  89

104  67  38  17  16  15  14  13  30  55  88

105  68  39  18   5   4   3  12  29  54  87

106  69  40  19   6   1   2  11  28  53  86

107  70  41  20   7   8   9  10  27  52  85

108  71  42  21  22  23  24  25  26  51  84

109  72  43  44  45  46  47  48  49  50  83

110  73  74  75  76  77  78  79  80  81  82

111 112 113 114 115 116 117 118 119 120 121


A wildebeest is a "gnu" fairy chess piece - a non-standard chess piece which may move both as a knight (a $(1,2)$-leaper) and as a camel (a $(1,3)$-leaper).

As such she could move to any of these locations from her starting location of $1$:



  .   .   .   .   .   .   .   .   .   .   .

  .   .   .   .  35   .  33   .   .   .   .

  .   .   .   .  16   .  14   .   .   .   .

  .   .  39  18   .   .   .  12  29   .   .

  .   .   .   .   .  (1)  .   .   .   .   .

  .   .  41  20   .   .   .  10  27   .   .

  .   .   .   .  22   .  24   .   .   .   .

  .   .   .   .  45   .  47   .   .   .   .

  .   .   .   .   .   .   .   .   .   .   .


The lowest of these is $10$ and she has not yet visited that square, so $10$ is the second term in the sequence.



Next she could move from $10$ to any of these locations:



  .   .   .   .   .   .   .   .   .   .   .

  .   .   .   .   .   .  14   .  30   .   .

  .   .   .   .   .   .   3   .  29   .   .

  .   .   .   .   6   1   .   .   .  53  86

  .   .   .   .   .   .   . (10)  .   .   .

  .   .   .   .  22  23   .   .   .  51  84

  .   .   .   .   .   .  47   .  49   .   .

  .   .   .   .   .   .  78   .  80   .   .

  .   .   .   .   .   .   .   .   .   .   .


However, she has already visited square $1$ so her third location is square $3$, the lowest she has not yet visited.




The first $100$ terms of the path of the wildebeest are:



1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 18, 15, 12, 16, 19, 22, 41, 17, 33, 30, 34, 13, 27, 23, 20, 24, 44, 40, 21, 39, 36, 60, 31, 53, 26, 46, 25, 28, 32, 29, 51, 47, 75, 42, 45, 71, 74, 70, 38, 35, 59, 56, 86, 50, 78, 49, 52, 80, 83, 79, 115, 73, 107, 67, 64, 68, 37, 61, 93, 55, 58, 54, 84, 48, 76, 43, 69, 103, 63, 66, 62, 94, 57, 87, 125, 82, 118, 77, 113, 72, 106, 148, 65, 97, 137, 91, 129, 85


The first $11$ leaps are knight moves so the first $12$ terms coincide with A316667.






code-golf sequence integer chess







share|improve this question











$endgroup$




Golf a program or function which gives the $n^{text{th}}$ location of the wildebeest who starts at square $1$ on an infinite chessboard which is numbered in an anti-clockwise square spiral, where the wildebeest always visits the lowest numbered square she can reach that she has not yet visited.



Inspiration: The Trapped Knight and OEIS A316667.



Edit: This sequence is now on the OEIS as A323763.



The code may produce the $n^{text{th}}$ location, the first $n$ locations, or generate the sequence taking no input.



Feel free to give her location after (or up to) $n$ leaps instead, but if so please state this clearly in your answer and make sure that an input of $n=0$ yields 1 (or [1] if appropriate).



This is code-golf, so the aim is to produce working code in as few bytes as possible in your chosen language.



Note: the wildebeest becomes trapped (much like the knight does at his $2016^{text{th}}$ location, square $2084$, and the camel does at his $3723^{text{rd}}$, square $7081$) at her $12899744968^{text{th}}$ location on square $12851850258$. The behaviour of your code may be undefined for $n$ larger than this. (Thanks to Deadcode for the C++ code that found this!)



Detail



The board looks like the below, and continues indefinitely:



101 100  99  98  97  96  95  94  93  92  91

102  65  64  63  62  61  60  59  58  57  90

103  66  37  36  35  34  33  32  31  56  89

104  67  38  17  16  15  14  13  30  55  88

105  68  39  18   5   4   3  12  29  54  87

106  69  40  19   6   1   2  11  28  53  86

107  70  41  20   7   8   9  10  27  52  85

108  71  42  21  22  23  24  25  26  51  84

109  72  43  44  45  46  47  48  49  50  83

110  73  74  75  76  77  78  79  80  81  82

111 112 113 114 115 116 117 118 119 120 121


A wildebeest is a "gnu" fairy chess piece - a non-standard chess piece which may move both as a knight (a $(1,2)$-leaper) and as a camel (a $(1,3)$-leaper).

As such she could move to any of these locations from her starting location of $1$:



  .   .   .   .   .   .   .   .   .   .   .

  .   .   .   .  35   .  33   .   .   .   .

  .   .   .   .  16   .  14   .   .   .   .

  .   .  39  18   .   .   .  12  29   .   .

  .   .   .   .   .  (1)  .   .   .   .   .

  .   .  41  20   .   .   .  10  27   .   .

  .   .   .   .  22   .  24   .   .   .   .

  .   .   .   .  45   .  47   .   .   .   .

  .   .   .   .   .   .   .   .   .   .   .


The lowest of these is $10$ and she has not yet visited that square, so $10$ is the second term in the sequence.



Next she could move from $10$ to any of these locations:



  .   .   .   .   .   .   .   .   .   .   .

  .   .   .   .   .   .  14   .  30   .   .

  .   .   .   .   .   .   3   .  29   .   .

  .   .   .   .   6   1   .   .   .  53  86

  .   .   .   .   .   .   . (10)  .   .   .

  .   .   .   .  22  23   .   .   .  51  84

  .   .   .   .   .   .  47   .  49   .   .

  .   .   .   .   .   .  78   .  80   .   .

  .   .   .   .   .   .   .   .   .   .   .


However, she has already visited square $1$ so her third location is square $3$, the lowest she has not yet visited.




The first $100$ terms of the path of the wildebeest are:



1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 18, 15, 12, 16, 19, 22, 41, 17, 33, 30, 34, 13, 27, 23, 20, 24, 44, 40, 21, 39, 36, 60, 31, 53, 26, 46, 25, 28, 32, 29, 51, 47, 75, 42, 45, 71, 74, 70, 38, 35, 59, 56, 86, 50, 78, 49, 52, 80, 83, 79, 115, 73, 107, 67, 64, 68, 37, 61, 93, 55, 58, 54, 84, 48, 76, 43, 69, 103, 63, 66, 62, 94, 57, 87, 125, 82, 118, 77, 113, 72, 106, 148, 65, 97, 137, 91, 129, 85


The first $11$ leaps are knight moves so the first $12$ terms coincide with A316667.






code-golf sequence integer chess




code-golf sequence integer chess






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Feb 9 at 13:50







Jonathan Allan

















asked Jan 27 at 16:21









Jonathan AllanJonathan Allan

53.4k535172




53.4k535172












  • $begingroup$
    Comments are not for extended discussion; this conversation has been moved to chat.
    $endgroup$
    – Mego♦
    Jan 29 at 14:05


















  • $begingroup$
    Comments are not for extended discussion; this conversation has been moved to chat.
    $endgroup$
    – Mego♦
    Jan 29 at 14:05
















$begingroup$
Comments are not for extended discussion; this conversation has been moved to chat.
$endgroup$
– Mego♦
Jan 29 at 14:05




$begingroup$
Comments are not for extended discussion; this conversation has been moved to chat.
$endgroup$
– Mego♦
Jan 29 at 14:05










3 Answers
3






active

oldest

votes


















20












$begingroup$


JavaScript (Node.js),  191 ... 166  164 bytes



Saved 2 bytes thanks to @grimy.



Returns the $N$th term.



n=>(g=(x,y)=>n--?g(Buffer('QPNP1O?O@242Q3C3').map(m=c=>g[i=4*((x+=c%6-2)*x>(y+=c%7-2)*y?x:y)**2,i-=(x>y||-1)*(i**.5+x+y)]|i>m||(H=x,V=y,m=i))&&H,V,g[m]=1):m+1)(1,2)


Try it online! or See a formatted version



How?



Spiral indices



In order to convert the coordinates $(x,y)$ into the spiral index $I$, we first compute the layer $L$ with:



$$L=max(|x|,|y|)$$



Which gives:



$$begin{array}{c|ccccccc}
&-3&-2&-1&0&+1&+2&+3\
hline
-3&3&3&3&3&3&3&3\
-2&3&2&2&2&2&2&3\
-1&3&2&1&1&1&2&3\
0&3&2&1&0&1&2&3\
+1&3&2&1&1&1&2&3\
+2&3&2&2&2&2&2&3\
+3&3&3&3&3&3&3&3
end{array}$$



We then compute the position $P$ in the layer with:



$$P=begin{cases}
2L+x+y&text{if }x>y\
-(2L+x+y)&text{if }xle y
end{cases}$$



Which gives:



$$begin{array}{c|ccccccc}
&-3&-2&-1&0&+1&+2&+3\
hline
-3&0&1&2&3&4&5&6\
-2&-1&0&1&2&3&4&7\
-1&-2&-1&0&1&2&5&8\
0&-3&-2&-1&0&3&6&9\
+1&-4&-3&-2&-3&-4&7&10\
+2&-5&-4&-5&-6&-7&-8&11\
+3&-6&-7&-8&-9&-10&-11&-12
end{array}$$



The final index $I$ is given by:



$$I=4L^2-P$$



NB: The above formula gives a 0-indexed spiral.



In the JS code, we actually compute $4L^2$ right away with:



i = 4 * (x * x > y * y ? x : y) ** 2


And then subtract $P$ with:



i -= (x > y || -1) * (i ** 0.5 + x + y)


Moves of the wildebeest



Given the current position $(x,y)$, the 16 possible target squares of the wildebeest are tested in the following order:



$$begin{array}{c|cccccccc}
&-3&-2&-1&x&+1&+2&+3\
hline
-3&cdot&cdot&9&cdot&11&cdot&cdot\
-2&cdot&cdot&8&cdot&10&cdot&cdot\
-1&7&6&cdot&cdot&cdot&12&13\
y&cdot&cdot&cdot&bullet&cdot&cdot&cdot\
+1&5&4&cdot&cdot&cdot&14&15\
+2&cdot&cdot&2&cdot&0&cdot&cdot\
+3&cdot&cdot&3&cdot&1&cdot&cdot
end{array}$$



We walk through them by applying 16 pairs of signed values $(dx,dy)$. Each pair is encoded as a single ASCII character.



 ID | char. | ASCII code | c%6-2 | c%7-2 | cumulated

----+-------+------------+-------+-------+-----------

  0 |  'Q'  |     81     |   +1  |   +2  |  (+1,+2)

  1 |  'P'  |     80     |    0  |   +1  |  (+1,+3)

  2 |  'N'  |     78     |   -2  |   -1  |  (-1,+2)

  3 |  'P'  |     80     |    0  |   +1  |  (-1,+3)

  4 |  '1'  |     49     |   -1  |   -2  |  (-2,+1)

  5 |  'O'  |     79     |   -1  |    0  |  (-3,+1)

  6 |  '?'  |     63     |   +1  |   -2  |  (-2,-1)

  7 |  'O'  |     79     |   -1  |    0  |  (-3,-1)

  8 |  '@'  |     64     |   +2  |   -1  |  (-1,-2)

  9 |  '2'  |     50     |    0  |   -1  |  (-1,-3)

 10 |  '4'  |     52     |   +2  |   +1  |  (+1,-2)

 11 |  '2'  |     50     |    0  |   -1  |  (+1,-3)

 12 |  'Q'  |     81     |   +1  |   +2  |  (+2,-1)

 13 |  '3'  |     51     |   +1  |    0  |  (+3,-1)

 14 |  'C'  |     67     |   -1  |   +2  |  (+2,+1)

 15 |  '3'  |     51     |   +1  |    0  |  (+3,+1)


We keep track of the minimum encountered value in $m$ and of the coordinates of the corresponding cell in $(H,V)$.



Once the best candidate has been found, we mark it as visited by setting a flag in the object $g$, which is also our main recursive function.



On the first iteration, we start with $x=1$ and $y=2$. This ensures that the first selected cell is $(0,0)$ and that it's the first cell to be marked as visited.






share|improve this answer











$endgroup$









  • 3




    $begingroup$
    So much golfing, can't wait for the rundown of how all the magic works!
    $endgroup$
    – Jonathan Allan
    Jan 27 at 23:25










  • $begingroup$
    did you have to use Buffer to force each character to be interpreted as a single byte?
    $endgroup$
    – Jonah
    Jan 28 at 1:49






  • 1




    $begingroup$
    @Jonah Although it's been deprecated, the Buffer constructor still accepts a string. So, yes, this is a rather cheap way to convert it to a list of bytes -- as opposed to [..."string"].map(c=>do_something_with(c.charCodeAt())).
    $endgroup$
    – Arnauld
    Jan 28 at 10:39






  • 1




    $begingroup$
    -2 bytes on the coordinate encoding: TIO
    $endgroup$
    – Grimy
    Jan 28 at 10:45










  • $begingroup$
    @Grimy Nicely done!
    $endgroup$
    – Arnauld
    Jan 28 at 11:03



















8












$begingroup$


Coconut, 337 276 bytes



import math

def g((x,y))=

 A=abs(abs(x)-abs(y))+abs(x)+abs(y)

 int(A**2+math.copysign(A+x-y,.5-x-y)+1)

def f():

 p=x,y=0,0;s={p};z=[2,3,1,1]*2

 while 1:yield g(p);p=x,y=min(((a+x,b+y)for a,b in zip((1,1,2,-2,-1,-1,3,-3)*2,z+[-v for v in z])if(a+x,b+y)not in s),key=g);s.add(p)


Returns a generator of values. Could probably be golfed more. (Especially the sequence of difference tuples.) Spiral algorithm taken from this math.se answer.



Try it online!






share|improve this answer











$endgroup$









  • 1




    $begingroup$
    for a,b in ( -> for a,b in( (maybe you can golf the delta tuple of tuples itself too)
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:21






  • 1




    $begingroup$
    No need for q and a zip is shorter for the tuples: 306 bytes may still be golfable of course
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:36






  • 1




    $begingroup$
    ...how about this for 284? EDIT... this for 278
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:45








  • 1




    $begingroup$
    FWIW, that math.se answer has x and y swapped and both negative relative to the coordinate system in this challenge (where positive x is right and y is up). Not that it'd make any difference due to the symmetries, but still.
    $endgroup$
    – Deadcode
    Jan 27 at 22:47






  • 1




    $begingroup$
    0.5->.5 for another byte save; A**2->A*A for one more.
    $endgroup$
    – Jonathan Allan
    Jan 27 at 23:18





















7












$begingroup$


05AB1E, 77 65 58 57 52 bytes



Xˆ0UF3D(Ÿ0KãʒÄ1¢}εX+}Dε·nàDtyÆ+yO·<.±*->}D¯KßDˆkèU}¯


-6 bytes thanks to @Arnauld by using a port of his formula.



Outputs the first $n+1$ values as a list (of decimals).



Try it online (the ï in the footer removes the .0 to make the output more compact, but feel free to remove it to see the actual result).



Code explanation:





Xˆ             # Put integer 1 in the global_array (global_array is empty by default)

0U             # Set variable `X` to 0 (`X` is 1 by default)

F              # Loop the (implicit) input amount of times:

 3D(Ÿ          #  Push the list in the range [-3,3]: [-3,-2,-1,0,1,2,3]

     0K        #  Remove the 0: [-3,-2,-1,1,2,3]

       ã       #  Cartesian product with itself, creating each possible pair: [[3,3],[3,2],[3,1],[3,-1],[3,-2],[3,-3],[2,3],[2,2],[2,1],[2,-1],[2,-2],[2,-3],[1,3],[1,2],[1,1],[1,-1],[1,-2],[1,-3],[-1,3],[-1,2],[-1,1],[-1,-1],[-1,-2],[-1,-3],[-2,3],[-2,2],[-2,1],[-2,-1],[-2,-2],[-2,-3],[-3,3],[-3,2],[-3,1],[-3,-1],[-3,-2],[-3,-3]]

        ʒ   }  #  Filter this list of pairs by:

         Ä     #   Where the absolute values of the pair

          1¢   #   Contains exactly one 1

               #  (We now have the following pairs left: [[3,1],[3,-1],[2,1],[2,-1],[1,3],[1,2],[1,-2],[1,-3],[-1,3],[-1,2],[-1,-2],[-1,-3],[-2,1],[-2,-1],[-3,1],[-3,-1]])

 εX+}          #  Add the variable `X` (previous coordinate) to each item in the list

 D             #  Duplicate this list of coordinates

  ε            #  Map each `x,y`-coordinate to:

   ·           #   Double both the `x` and `y` in the coordinate

    n          #   Then take the square of each

     à         #   And then pop and push the maximum of the two

   Dt          #   Duplicate this maximum, and take its square-root

     yÆ        #   Calculate `x-y`

       +       #   And add it to the square-root

   yO          #   Calculate `x+y`

     ·         #   Double it

      <        #   Decrease it by 1

       .±      #   And pop and push its signum (-1 if < 0; 0 if 0; 1 if > 0)

   *           #   Multiply these two together

    -          #   And subtract it from the duplicated maximum

   >           #   And finally increase it by 1 to make it 1-based instead of 0-based

  }D           #  After the map: Duplicate that list with values

    ¯K         #  Remove all values that are already present in the global_array

      ß        #  Pop the list of (remaining) values and push the minimum

       Dˆ      #  Duplicate this minimum, and pop and add the copy to the global_array

         k     #  Then get its index in the complete list of values

          è    #  And use that index to get the corresponding coordinate

           U   #  Pop and store this coordinate in variable `X` for the next iteration

}¯             # After the outer loop: push the global_array (which is output implicitly)


General explanation:



We hold all results (and therefore values we've already encountered) in the global_array, which is initially started as [1].

We hold the current $x,y$-coordinate in variable X, which is initially [0,0].



The list of coordinates we can reach based on the current $x,y$-coordinate are:



[[x+3,y+1], [x+3,y-1], [x+2,y+1], [x+2,y-1], [x+1,y+3], [x+1,y+2], [x+1,y-2], [x+1,y-3], [x-1,y+3], [x-1,y+2], [x-1,y-2], [x-1,y-3], [x-2,y+1], [x-2,y-1], [x-3,y+1], [x-3,y-1]]


The list I mention in the code explanation above holds these values we can jump to, after which the current $x,y$ (stored in variable X) is added.



Then it will calculate the spiral values based on these $x,y$-coordinates. It does this by using the following formula for a given $x,y$-coordinate:



$${T = max((2 * x) ^ 2, (2 * y) ^ 2)}$$
$${R = T - (x - y + √T) * signum((x + y) * 2 - 1) + 1}$$



Which is the same formula @Arnauld is using in his answer, but written differently to make use of 05AB1E's builtins for double, square, -1, +1, etc.



(If you want to see just this spiral part of the code in action: Try it online.)



After we've got all the values we can reach for the given $x,y$-coordinate, we remove all values that are already present in the global_array, and we then get the minimum of the (remaining) values.

This minimum is then added to the global_array, and variable X is replaced with the $x,y$-coordinate of this minimum.



After we've looped the input amount of times, the program will output this global_array as result.






share|improve this answer











$endgroup$









  • 1




    $begingroup$
    FWIW, here is a port of my own formula to convert the coordinates into spiral indices. It's 5 bytes shorter but yields floats. (I don't know if this is a problem or not.)
    $endgroup$
    – Arnauld
    Jan 28 at 16:58










  • $begingroup$
    (Note that $y$ in your code is $-y$ in mine.)
    $endgroup$
    – Arnauld
    Jan 28 at 17:07










  • $begingroup$
    @Arnauld Thanks, that saves 5 additional bytes. :) EDIT: Which you already mentioned in your first comment. ;p
    $endgroup$
    – Kevin Cruijssen
    Jan 28 at 17:36













Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f179157%2fthe-path-of-the-wildebeest%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























3 Answers
3






active

oldest

votes








3 Answers
3






active

oldest

votes









active

oldest

votes






active

oldest

votes









20












$begingroup$


JavaScript (Node.js),  191 ... 166  164 bytes



Saved 2 bytes thanks to @grimy.



Returns the $N$th term.



n=>(g=(x,y)=>n--?g(Buffer('QPNP1O?O@242Q3C3').map(m=c=>g[i=4*((x+=c%6-2)*x>(y+=c%7-2)*y?x:y)**2,i-=(x>y||-1)*(i**.5+x+y)]|i>m||(H=x,V=y,m=i))&&H,V,g[m]=1):m+1)(1,2)


Try it online! or See a formatted version



How?



Spiral indices



In order to convert the coordinates $(x,y)$ into the spiral index $I$, we first compute the layer $L$ with:



$$L=max(|x|,|y|)$$



Which gives:



$$begin{array}{c|ccccccc}
&-3&-2&-1&0&+1&+2&+3\
hline
-3&3&3&3&3&3&3&3\
-2&3&2&2&2&2&2&3\
-1&3&2&1&1&1&2&3\
0&3&2&1&0&1&2&3\
+1&3&2&1&1&1&2&3\
+2&3&2&2&2&2&2&3\
+3&3&3&3&3&3&3&3
end{array}$$



We then compute the position $P$ in the layer with:



$$P=begin{cases}
2L+x+y&text{if }x>y\
-(2L+x+y)&text{if }xle y
end{cases}$$



Which gives:



$$begin{array}{c|ccccccc}
&-3&-2&-1&0&+1&+2&+3\
hline
-3&0&1&2&3&4&5&6\
-2&-1&0&1&2&3&4&7\
-1&-2&-1&0&1&2&5&8\
0&-3&-2&-1&0&3&6&9\
+1&-4&-3&-2&-3&-4&7&10\
+2&-5&-4&-5&-6&-7&-8&11\
+3&-6&-7&-8&-9&-10&-11&-12
end{array}$$



The final index $I$ is given by:



$$I=4L^2-P$$



NB: The above formula gives a 0-indexed spiral.



In the JS code, we actually compute $4L^2$ right away with:



i = 4 * (x * x > y * y ? x : y) ** 2


And then subtract $P$ with:



i -= (x > y || -1) * (i ** 0.5 + x + y)


Moves of the wildebeest



Given the current position $(x,y)$, the 16 possible target squares of the wildebeest are tested in the following order:



$$begin{array}{c|cccccccc}
&-3&-2&-1&x&+1&+2&+3\
hline
-3&cdot&cdot&9&cdot&11&cdot&cdot\
-2&cdot&cdot&8&cdot&10&cdot&cdot\
-1&7&6&cdot&cdot&cdot&12&13\
y&cdot&cdot&cdot&bullet&cdot&cdot&cdot\
+1&5&4&cdot&cdot&cdot&14&15\
+2&cdot&cdot&2&cdot&0&cdot&cdot\
+3&cdot&cdot&3&cdot&1&cdot&cdot
end{array}$$



We walk through them by applying 16 pairs of signed values $(dx,dy)$. Each pair is encoded as a single ASCII character.



 ID | char. | ASCII code | c%6-2 | c%7-2 | cumulated

----+-------+------------+-------+-------+-----------

  0 |  'Q'  |     81     |   +1  |   +2  |  (+1,+2)

  1 |  'P'  |     80     |    0  |   +1  |  (+1,+3)

  2 |  'N'  |     78     |   -2  |   -1  |  (-1,+2)

  3 |  'P'  |     80     |    0  |   +1  |  (-1,+3)

  4 |  '1'  |     49     |   -1  |   -2  |  (-2,+1)

  5 |  'O'  |     79     |   -1  |    0  |  (-3,+1)

  6 |  '?'  |     63     |   +1  |   -2  |  (-2,-1)

  7 |  'O'  |     79     |   -1  |    0  |  (-3,-1)

  8 |  '@'  |     64     |   +2  |   -1  |  (-1,-2)

  9 |  '2'  |     50     |    0  |   -1  |  (-1,-3)

 10 |  '4'  |     52     |   +2  |   +1  |  (+1,-2)

 11 |  '2'  |     50     |    0  |   -1  |  (+1,-3)

 12 |  'Q'  |     81     |   +1  |   +2  |  (+2,-1)

 13 |  '3'  |     51     |   +1  |    0  |  (+3,-1)

 14 |  'C'  |     67     |   -1  |   +2  |  (+2,+1)

 15 |  '3'  |     51     |   +1  |    0  |  (+3,+1)


We keep track of the minimum encountered value in $m$ and of the coordinates of the corresponding cell in $(H,V)$.



Once the best candidate has been found, we mark it as visited by setting a flag in the object $g$, which is also our main recursive function.



On the first iteration, we start with $x=1$ and $y=2$. This ensures that the first selected cell is $(0,0)$ and that it's the first cell to be marked as visited.






share|improve this answer











$endgroup$









  • 3




    $begingroup$
    So much golfing, can't wait for the rundown of how all the magic works!
    $endgroup$
    – Jonathan Allan
    Jan 27 at 23:25










  • $begingroup$
    did you have to use Buffer to force each character to be interpreted as a single byte?
    $endgroup$
    – Jonah
    Jan 28 at 1:49






  • 1




    $begingroup$
    @Jonah Although it's been deprecated, the Buffer constructor still accepts a string. So, yes, this is a rather cheap way to convert it to a list of bytes -- as opposed to [..."string"].map(c=>do_something_with(c.charCodeAt())).
    $endgroup$
    – Arnauld
    Jan 28 at 10:39






  • 1




    $begingroup$
    -2 bytes on the coordinate encoding: TIO
    $endgroup$
    – Grimy
    Jan 28 at 10:45










  • $begingroup$
    @Grimy Nicely done!
    $endgroup$
    – Arnauld
    Jan 28 at 11:03
















20












$begingroup$


JavaScript (Node.js),  191 ... 166  164 bytes



Saved 2 bytes thanks to @grimy.



Returns the $N$th term.



n=>(g=(x,y)=>n--?g(Buffer('QPNP1O?O@242Q3C3').map(m=c=>g[i=4*((x+=c%6-2)*x>(y+=c%7-2)*y?x:y)**2,i-=(x>y||-1)*(i**.5+x+y)]|i>m||(H=x,V=y,m=i))&&H,V,g[m]=1):m+1)(1,2)


Try it online! or See a formatted version



How?



Spiral indices



In order to convert the coordinates $(x,y)$ into the spiral index $I$, we first compute the layer $L$ with:



$$L=max(|x|,|y|)$$



Which gives:



$$begin{array}{c|ccccccc}
&-3&-2&-1&0&+1&+2&+3\
hline
-3&3&3&3&3&3&3&3\
-2&3&2&2&2&2&2&3\
-1&3&2&1&1&1&2&3\
0&3&2&1&0&1&2&3\
+1&3&2&1&1&1&2&3\
+2&3&2&2&2&2&2&3\
+3&3&3&3&3&3&3&3
end{array}$$



We then compute the position $P$ in the layer with:



$$P=begin{cases}
2L+x+y&text{if }x>y\
-(2L+x+y)&text{if }xle y
end{cases}$$



Which gives:



$$begin{array}{c|ccccccc}
&-3&-2&-1&0&+1&+2&+3\
hline
-3&0&1&2&3&4&5&6\
-2&-1&0&1&2&3&4&7\
-1&-2&-1&0&1&2&5&8\
0&-3&-2&-1&0&3&6&9\
+1&-4&-3&-2&-3&-4&7&10\
+2&-5&-4&-5&-6&-7&-8&11\
+3&-6&-7&-8&-9&-10&-11&-12
end{array}$$



The final index $I$ is given by:



$$I=4L^2-P$$



NB: The above formula gives a 0-indexed spiral.



In the JS code, we actually compute $4L^2$ right away with:



i = 4 * (x * x > y * y ? x : y) ** 2


And then subtract $P$ with:



i -= (x > y || -1) * (i ** 0.5 + x + y)


Moves of the wildebeest



Given the current position $(x,y)$, the 16 possible target squares of the wildebeest are tested in the following order:



$$begin{array}{c|cccccccc}
&-3&-2&-1&x&+1&+2&+3\
hline
-3&cdot&cdot&9&cdot&11&cdot&cdot\
-2&cdot&cdot&8&cdot&10&cdot&cdot\
-1&7&6&cdot&cdot&cdot&12&13\
y&cdot&cdot&cdot&bullet&cdot&cdot&cdot\
+1&5&4&cdot&cdot&cdot&14&15\
+2&cdot&cdot&2&cdot&0&cdot&cdot\
+3&cdot&cdot&3&cdot&1&cdot&cdot
end{array}$$



We walk through them by applying 16 pairs of signed values $(dx,dy)$. Each pair is encoded as a single ASCII character.



 ID | char. | ASCII code | c%6-2 | c%7-2 | cumulated

----+-------+------------+-------+-------+-----------

  0 |  'Q'  |     81     |   +1  |   +2  |  (+1,+2)

  1 |  'P'  |     80     |    0  |   +1  |  (+1,+3)

  2 |  'N'  |     78     |   -2  |   -1  |  (-1,+2)

  3 |  'P'  |     80     |    0  |   +1  |  (-1,+3)

  4 |  '1'  |     49     |   -1  |   -2  |  (-2,+1)

  5 |  'O'  |     79     |   -1  |    0  |  (-3,+1)

  6 |  '?'  |     63     |   +1  |   -2  |  (-2,-1)

  7 |  'O'  |     79     |   -1  |    0  |  (-3,-1)

  8 |  '@'  |     64     |   +2  |   -1  |  (-1,-2)

  9 |  '2'  |     50     |    0  |   -1  |  (-1,-3)

 10 |  '4'  |     52     |   +2  |   +1  |  (+1,-2)

 11 |  '2'  |     50     |    0  |   -1  |  (+1,-3)

 12 |  'Q'  |     81     |   +1  |   +2  |  (+2,-1)

 13 |  '3'  |     51     |   +1  |    0  |  (+3,-1)

 14 |  'C'  |     67     |   -1  |   +2  |  (+2,+1)

 15 |  '3'  |     51     |   +1  |    0  |  (+3,+1)


We keep track of the minimum encountered value in $m$ and of the coordinates of the corresponding cell in $(H,V)$.



Once the best candidate has been found, we mark it as visited by setting a flag in the object $g$, which is also our main recursive function.



On the first iteration, we start with $x=1$ and $y=2$. This ensures that the first selected cell is $(0,0)$ and that it's the first cell to be marked as visited.






share|improve this answer











$endgroup$









  • 3




    $begingroup$
    So much golfing, can't wait for the rundown of how all the magic works!
    $endgroup$
    – Jonathan Allan
    Jan 27 at 23:25










  • $begingroup$
    did you have to use Buffer to force each character to be interpreted as a single byte?
    $endgroup$
    – Jonah
    Jan 28 at 1:49






  • 1




    $begingroup$
    @Jonah Although it's been deprecated, the Buffer constructor still accepts a string. So, yes, this is a rather cheap way to convert it to a list of bytes -- as opposed to [..."string"].map(c=>do_something_with(c.charCodeAt())).
    $endgroup$
    – Arnauld
    Jan 28 at 10:39






  • 1




    $begingroup$
    -2 bytes on the coordinate encoding: TIO
    $endgroup$
    – Grimy
    Jan 28 at 10:45










  • $begingroup$
    @Grimy Nicely done!
    $endgroup$
    – Arnauld
    Jan 28 at 11:03














20












20








20





$begingroup$


JavaScript (Node.js),  191 ... 166  164 bytes



Saved 2 bytes thanks to @grimy.



Returns the $N$th term.



n=>(g=(x,y)=>n--?g(Buffer('QPNP1O?O@242Q3C3').map(m=c=>g[i=4*((x+=c%6-2)*x>(y+=c%7-2)*y?x:y)**2,i-=(x>y||-1)*(i**.5+x+y)]|i>m||(H=x,V=y,m=i))&&H,V,g[m]=1):m+1)(1,2)


Try it online! or See a formatted version



How?



Spiral indices



In order to convert the coordinates $(x,y)$ into the spiral index $I$, we first compute the layer $L$ with:



$$L=max(|x|,|y|)$$



Which gives:



$$begin{array}{c|ccccccc}
&-3&-2&-1&0&+1&+2&+3\
hline
-3&3&3&3&3&3&3&3\
-2&3&2&2&2&2&2&3\
-1&3&2&1&1&1&2&3\
0&3&2&1&0&1&2&3\
+1&3&2&1&1&1&2&3\
+2&3&2&2&2&2&2&3\
+3&3&3&3&3&3&3&3
end{array}$$



We then compute the position $P$ in the layer with:



$$P=begin{cases}
2L+x+y&text{if }x>y\
-(2L+x+y)&text{if }xle y
end{cases}$$



Which gives:



$$begin{array}{c|ccccccc}
&-3&-2&-1&0&+1&+2&+3\
hline
-3&0&1&2&3&4&5&6\
-2&-1&0&1&2&3&4&7\
-1&-2&-1&0&1&2&5&8\
0&-3&-2&-1&0&3&6&9\
+1&-4&-3&-2&-3&-4&7&10\
+2&-5&-4&-5&-6&-7&-8&11\
+3&-6&-7&-8&-9&-10&-11&-12
end{array}$$



The final index $I$ is given by:



$$I=4L^2-P$$



NB: The above formula gives a 0-indexed spiral.



In the JS code, we actually compute $4L^2$ right away with:



i = 4 * (x * x > y * y ? x : y) ** 2


And then subtract $P$ with:



i -= (x > y || -1) * (i ** 0.5 + x + y)


Moves of the wildebeest



Given the current position $(x,y)$, the 16 possible target squares of the wildebeest are tested in the following order:



$$begin{array}{c|cccccccc}
&-3&-2&-1&x&+1&+2&+3\
hline
-3&cdot&cdot&9&cdot&11&cdot&cdot\
-2&cdot&cdot&8&cdot&10&cdot&cdot\
-1&7&6&cdot&cdot&cdot&12&13\
y&cdot&cdot&cdot&bullet&cdot&cdot&cdot\
+1&5&4&cdot&cdot&cdot&14&15\
+2&cdot&cdot&2&cdot&0&cdot&cdot\
+3&cdot&cdot&3&cdot&1&cdot&cdot
end{array}$$



We walk through them by applying 16 pairs of signed values $(dx,dy)$. Each pair is encoded as a single ASCII character.



 ID | char. | ASCII code | c%6-2 | c%7-2 | cumulated

----+-------+------------+-------+-------+-----------

  0 |  'Q'  |     81     |   +1  |   +2  |  (+1,+2)

  1 |  'P'  |     80     |    0  |   +1  |  (+1,+3)

  2 |  'N'  |     78     |   -2  |   -1  |  (-1,+2)

  3 |  'P'  |     80     |    0  |   +1  |  (-1,+3)

  4 |  '1'  |     49     |   -1  |   -2  |  (-2,+1)

  5 |  'O'  |     79     |   -1  |    0  |  (-3,+1)

  6 |  '?'  |     63     |   +1  |   -2  |  (-2,-1)

  7 |  'O'  |     79     |   -1  |    0  |  (-3,-1)

  8 |  '@'  |     64     |   +2  |   -1  |  (-1,-2)

  9 |  '2'  |     50     |    0  |   -1  |  (-1,-3)

 10 |  '4'  |     52     |   +2  |   +1  |  (+1,-2)

 11 |  '2'  |     50     |    0  |   -1  |  (+1,-3)

 12 |  'Q'  |     81     |   +1  |   +2  |  (+2,-1)

 13 |  '3'  |     51     |   +1  |    0  |  (+3,-1)

 14 |  'C'  |     67     |   -1  |   +2  |  (+2,+1)

 15 |  '3'  |     51     |   +1  |    0  |  (+3,+1)


We keep track of the minimum encountered value in $m$ and of the coordinates of the corresponding cell in $(H,V)$.



Once the best candidate has been found, we mark it as visited by setting a flag in the object $g$, which is also our main recursive function.



On the first iteration, we start with $x=1$ and $y=2$. This ensures that the first selected cell is $(0,0)$ and that it's the first cell to be marked as visited.






share|improve this answer











$endgroup$




JavaScript (Node.js),  191 ... 166  164 bytes



Saved 2 bytes thanks to @grimy.



Returns the $N$th term.



n=>(g=(x,y)=>n--?g(Buffer('QPNP1O?O@242Q3C3').map(m=c=>g[i=4*((x+=c%6-2)*x>(y+=c%7-2)*y?x:y)**2,i-=(x>y||-1)*(i**.5+x+y)]|i>m||(H=x,V=y,m=i))&&H,V,g[m]=1):m+1)(1,2)


Try it online! or See a formatted version



How?



Spiral indices



In order to convert the coordinates $(x,y)$ into the spiral index $I$, we first compute the layer $L$ with:



$$L=max(|x|,|y|)$$



Which gives:



$$begin{array}{c|ccccccc}
&-3&-2&-1&0&+1&+2&+3\
hline
-3&3&3&3&3&3&3&3\
-2&3&2&2&2&2&2&3\
-1&3&2&1&1&1&2&3\
0&3&2&1&0&1&2&3\
+1&3&2&1&1&1&2&3\
+2&3&2&2&2&2&2&3\
+3&3&3&3&3&3&3&3
end{array}$$



We then compute the position $P$ in the layer with:



$$P=begin{cases}
2L+x+y&text{if }x>y\
-(2L+x+y)&text{if }xle y
end{cases}$$



Which gives:



$$begin{array}{c|ccccccc}
&-3&-2&-1&0&+1&+2&+3\
hline
-3&0&1&2&3&4&5&6\
-2&-1&0&1&2&3&4&7\
-1&-2&-1&0&1&2&5&8\
0&-3&-2&-1&0&3&6&9\
+1&-4&-3&-2&-3&-4&7&10\
+2&-5&-4&-5&-6&-7&-8&11\
+3&-6&-7&-8&-9&-10&-11&-12
end{array}$$



The final index $I$ is given by:



$$I=4L^2-P$$



NB: The above formula gives a 0-indexed spiral.



In the JS code, we actually compute $4L^2$ right away with:



i = 4 * (x * x > y * y ? x : y) ** 2


And then subtract $P$ with:



i -= (x > y || -1) * (i ** 0.5 + x + y)


Moves of the wildebeest



Given the current position $(x,y)$, the 16 possible target squares of the wildebeest are tested in the following order:



$$begin{array}{c|cccccccc}
&-3&-2&-1&x&+1&+2&+3\
hline
-3&cdot&cdot&9&cdot&11&cdot&cdot\
-2&cdot&cdot&8&cdot&10&cdot&cdot\
-1&7&6&cdot&cdot&cdot&12&13\
y&cdot&cdot&cdot&bullet&cdot&cdot&cdot\
+1&5&4&cdot&cdot&cdot&14&15\
+2&cdot&cdot&2&cdot&0&cdot&cdot\
+3&cdot&cdot&3&cdot&1&cdot&cdot
end{array}$$



We walk through them by applying 16 pairs of signed values $(dx,dy)$. Each pair is encoded as a single ASCII character.



 ID | char. | ASCII code | c%6-2 | c%7-2 | cumulated

----+-------+------------+-------+-------+-----------

  0 |  'Q'  |     81     |   +1  |   +2  |  (+1,+2)

  1 |  'P'  |     80     |    0  |   +1  |  (+1,+3)

  2 |  'N'  |     78     |   -2  |   -1  |  (-1,+2)

  3 |  'P'  |     80     |    0  |   +1  |  (-1,+3)

  4 |  '1'  |     49     |   -1  |   -2  |  (-2,+1)

  5 |  'O'  |     79     |   -1  |    0  |  (-3,+1)

  6 |  '?'  |     63     |   +1  |   -2  |  (-2,-1)

  7 |  'O'  |     79     |   -1  |    0  |  (-3,-1)

  8 |  '@'  |     64     |   +2  |   -1  |  (-1,-2)

  9 |  '2'  |     50     |    0  |   -1  |  (-1,-3)

 10 |  '4'  |     52     |   +2  |   +1  |  (+1,-2)

 11 |  '2'  |     50     |    0  |   -1  |  (+1,-3)

 12 |  'Q'  |     81     |   +1  |   +2  |  (+2,-1)

 13 |  '3'  |     51     |   +1  |    0  |  (+3,-1)

 14 |  'C'  |     67     |   -1  |   +2  |  (+2,+1)

 15 |  '3'  |     51     |   +1  |    0  |  (+3,+1)


We keep track of the minimum encountered value in $m$ and of the coordinates of the corresponding cell in $(H,V)$.



Once the best candidate has been found, we mark it as visited by setting a flag in the object $g$, which is also our main recursive function.



On the first iteration, we start with $x=1$ and $y=2$. This ensures that the first selected cell is $(0,0)$ and that it's the first cell to be marked as visited.







share|improve this answer














share|improve this answer



share|improve this answer








edited Jan 28 at 13:59

























answered Jan 27 at 18:24









ArnauldArnauld

79.8k797330




79.8k797330








  • 3




    $begingroup$
    So much golfing, can't wait for the rundown of how all the magic works!
    $endgroup$
    – Jonathan Allan
    Jan 27 at 23:25










  • $begingroup$
    did you have to use Buffer to force each character to be interpreted as a single byte?
    $endgroup$
    – Jonah
    Jan 28 at 1:49






  • 1




    $begingroup$
    @Jonah Although it's been deprecated, the Buffer constructor still accepts a string. So, yes, this is a rather cheap way to convert it to a list of bytes -- as opposed to [..."string"].map(c=>do_something_with(c.charCodeAt())).
    $endgroup$
    – Arnauld
    Jan 28 at 10:39






  • 1




    $begingroup$
    -2 bytes on the coordinate encoding: TIO
    $endgroup$
    – Grimy
    Jan 28 at 10:45










  • $begingroup$
    @Grimy Nicely done!
    $endgroup$
    – Arnauld
    Jan 28 at 11:03














  • 3




    $begingroup$
    So much golfing, can't wait for the rundown of how all the magic works!
    $endgroup$
    – Jonathan Allan
    Jan 27 at 23:25










  • $begingroup$
    did you have to use Buffer to force each character to be interpreted as a single byte?
    $endgroup$
    – Jonah
    Jan 28 at 1:49






  • 1




    $begingroup$
    @Jonah Although it's been deprecated, the Buffer constructor still accepts a string. So, yes, this is a rather cheap way to convert it to a list of bytes -- as opposed to [..."string"].map(c=>do_something_with(c.charCodeAt())).
    $endgroup$
    – Arnauld
    Jan 28 at 10:39






  • 1




    $begingroup$
    -2 bytes on the coordinate encoding: TIO
    $endgroup$
    – Grimy
    Jan 28 at 10:45










  • $begingroup$
    @Grimy Nicely done!
    $endgroup$
    – Arnauld
    Jan 28 at 11:03








3




3




$begingroup$
So much golfing, can't wait for the rundown of how all the magic works!
$endgroup$
– Jonathan Allan
Jan 27 at 23:25




$begingroup$
So much golfing, can't wait for the rundown of how all the magic works!
$endgroup$
– Jonathan Allan
Jan 27 at 23:25












$begingroup$
did you have to use Buffer to force each character to be interpreted as a single byte?
$endgroup$
– Jonah
Jan 28 at 1:49




$begingroup$
did you have to use Buffer to force each character to be interpreted as a single byte?
$endgroup$
– Jonah
Jan 28 at 1:49




1




1




$begingroup$
@Jonah Although it's been deprecated, the Buffer constructor still accepts a string. So, yes, this is a rather cheap way to convert it to a list of bytes -- as opposed to [..."string"].map(c=>do_something_with(c.charCodeAt())).
$endgroup$
– Arnauld
Jan 28 at 10:39




$begingroup$
@Jonah Although it's been deprecated, the Buffer constructor still accepts a string. So, yes, this is a rather cheap way to convert it to a list of bytes -- as opposed to [..."string"].map(c=>do_something_with(c.charCodeAt())).
$endgroup$
– Arnauld
Jan 28 at 10:39




1




1




$begingroup$
-2 bytes on the coordinate encoding: TIO
$endgroup$
– Grimy
Jan 28 at 10:45




$begingroup$
-2 bytes on the coordinate encoding: TIO
$endgroup$
– Grimy
Jan 28 at 10:45












$begingroup$
@Grimy Nicely done!
$endgroup$
– Arnauld
Jan 28 at 11:03




$begingroup$
@Grimy Nicely done!
$endgroup$
– Arnauld
Jan 28 at 11:03











8












$begingroup$


Coconut, 337 276 bytes



import math

def g((x,y))=

 A=abs(abs(x)-abs(y))+abs(x)+abs(y)

 int(A**2+math.copysign(A+x-y,.5-x-y)+1)

def f():

 p=x,y=0,0;s={p};z=[2,3,1,1]*2

 while 1:yield g(p);p=x,y=min(((a+x,b+y)for a,b in zip((1,1,2,-2,-1,-1,3,-3)*2,z+[-v for v in z])if(a+x,b+y)not in s),key=g);s.add(p)


Returns a generator of values. Could probably be golfed more. (Especially the sequence of difference tuples.) Spiral algorithm taken from this math.se answer.



Try it online!






share|improve this answer











$endgroup$









  • 1




    $begingroup$
    for a,b in ( -> for a,b in( (maybe you can golf the delta tuple of tuples itself too)
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:21






  • 1




    $begingroup$
    No need for q and a zip is shorter for the tuples: 306 bytes may still be golfable of course
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:36






  • 1




    $begingroup$
    ...how about this for 284? EDIT... this for 278
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:45








  • 1




    $begingroup$
    FWIW, that math.se answer has x and y swapped and both negative relative to the coordinate system in this challenge (where positive x is right and y is up). Not that it'd make any difference due to the symmetries, but still.
    $endgroup$
    – Deadcode
    Jan 27 at 22:47






  • 1




    $begingroup$
    0.5->.5 for another byte save; A**2->A*A for one more.
    $endgroup$
    – Jonathan Allan
    Jan 27 at 23:18


















8












$begingroup$


Coconut, 337 276 bytes



import math

def g((x,y))=

 A=abs(abs(x)-abs(y))+abs(x)+abs(y)

 int(A**2+math.copysign(A+x-y,.5-x-y)+1)

def f():

 p=x,y=0,0;s={p};z=[2,3,1,1]*2

 while 1:yield g(p);p=x,y=min(((a+x,b+y)for a,b in zip((1,1,2,-2,-1,-1,3,-3)*2,z+[-v for v in z])if(a+x,b+y)not in s),key=g);s.add(p)


Returns a generator of values. Could probably be golfed more. (Especially the sequence of difference tuples.) Spiral algorithm taken from this math.se answer.



Try it online!






share|improve this answer











$endgroup$









  • 1




    $begingroup$
    for a,b in ( -> for a,b in( (maybe you can golf the delta tuple of tuples itself too)
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:21






  • 1




    $begingroup$
    No need for q and a zip is shorter for the tuples: 306 bytes may still be golfable of course
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:36






  • 1




    $begingroup$
    ...how about this for 284? EDIT... this for 278
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:45








  • 1




    $begingroup$
    FWIW, that math.se answer has x and y swapped and both negative relative to the coordinate system in this challenge (where positive x is right and y is up). Not that it'd make any difference due to the symmetries, but still.
    $endgroup$
    – Deadcode
    Jan 27 at 22:47






  • 1




    $begingroup$
    0.5->.5 for another byte save; A**2->A*A for one more.
    $endgroup$
    – Jonathan Allan
    Jan 27 at 23:18
















8












8








8





$begingroup$


Coconut, 337 276 bytes



import math

def g((x,y))=

 A=abs(abs(x)-abs(y))+abs(x)+abs(y)

 int(A**2+math.copysign(A+x-y,.5-x-y)+1)

def f():

 p=x,y=0,0;s={p};z=[2,3,1,1]*2

 while 1:yield g(p);p=x,y=min(((a+x,b+y)for a,b in zip((1,1,2,-2,-1,-1,3,-3)*2,z+[-v for v in z])if(a+x,b+y)not in s),key=g);s.add(p)


Returns a generator of values. Could probably be golfed more. (Especially the sequence of difference tuples.) Spiral algorithm taken from this math.se answer.



Try it online!






share|improve this answer











$endgroup$




Coconut, 337 276 bytes



import math

def g((x,y))=

 A=abs(abs(x)-abs(y))+abs(x)+abs(y)

 int(A**2+math.copysign(A+x-y,.5-x-y)+1)

def f():

 p=x,y=0,0;s={p};z=[2,3,1,1]*2

 while 1:yield g(p);p=x,y=min(((a+x,b+y)for a,b in zip((1,1,2,-2,-1,-1,3,-3)*2,z+[-v for v in z])if(a+x,b+y)not in s),key=g);s.add(p)


Returns a generator of values. Could probably be golfed more. (Especially the sequence of difference tuples.) Spiral algorithm taken from this math.se answer.



Try it online!







share|improve this answer














share|improve this answer



share|improve this answer








edited Jan 27 at 23:32

























answered Jan 27 at 21:36









Solomon UckoSolomon Ucko

372212




372212








  • 1




    $begingroup$
    for a,b in ( -> for a,b in( (maybe you can golf the delta tuple of tuples itself too)
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:21






  • 1




    $begingroup$
    No need for q and a zip is shorter for the tuples: 306 bytes may still be golfable of course
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:36






  • 1




    $begingroup$
    ...how about this for 284? EDIT... this for 278
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:45








  • 1




    $begingroup$
    FWIW, that math.se answer has x and y swapped and both negative relative to the coordinate system in this challenge (where positive x is right and y is up). Not that it'd make any difference due to the symmetries, but still.
    $endgroup$
    – Deadcode
    Jan 27 at 22:47






  • 1




    $begingroup$
    0.5->.5 for another byte save; A**2->A*A for one more.
    $endgroup$
    – Jonathan Allan
    Jan 27 at 23:18
















  • 1




    $begingroup$
    for a,b in ( -> for a,b in( (maybe you can golf the delta tuple of tuples itself too)
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:21






  • 1




    $begingroup$
    No need for q and a zip is shorter for the tuples: 306 bytes may still be golfable of course
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:36






  • 1




    $begingroup$
    ...how about this for 284? EDIT... this for 278
    $endgroup$
    – Jonathan Allan
    Jan 27 at 22:45








  • 1




    $begingroup$
    FWIW, that math.se answer has x and y swapped and both negative relative to the coordinate system in this challenge (where positive x is right and y is up). Not that it'd make any difference due to the symmetries, but still.
    $endgroup$
    – Deadcode
    Jan 27 at 22:47






  • 1




    $begingroup$
    0.5->.5 for another byte save; A**2->A*A for one more.
    $endgroup$
    – Jonathan Allan
    Jan 27 at 23:18










1




1




$begingroup$
for a,b in ( -> for a,b in( (maybe you can golf the delta tuple of tuples itself too)
$endgroup$
– Jonathan Allan
Jan 27 at 22:21




$begingroup$
for a,b in ( -> for a,b in( (maybe you can golf the delta tuple of tuples itself too)
$endgroup$
– Jonathan Allan
Jan 27 at 22:21




1




1




$begingroup$
No need for q and a zip is shorter for the tuples: 306 bytes may still be golfable of course
$endgroup$
– Jonathan Allan
Jan 27 at 22:36




$begingroup$
No need for q and a zip is shorter for the tuples: 306 bytes may still be golfable of course
$endgroup$
– Jonathan Allan
Jan 27 at 22:36




1




1




$begingroup$
...how about this for 284? EDIT... this for 278
$endgroup$
– Jonathan Allan
Jan 27 at 22:45






$begingroup$
...how about this for 284? EDIT... this for 278
$endgroup$
– Jonathan Allan
Jan 27 at 22:45






1




1




$begingroup$
FWIW, that math.se answer has x and y swapped and both negative relative to the coordinate system in this challenge (where positive x is right and y is up). Not that it'd make any difference due to the symmetries, but still.
$endgroup$
– Deadcode
Jan 27 at 22:47




$begingroup$
FWIW, that math.se answer has x and y swapped and both negative relative to the coordinate system in this challenge (where positive x is right and y is up). Not that it'd make any difference due to the symmetries, but still.
$endgroup$
– Deadcode
Jan 27 at 22:47




1




1




$begingroup$
0.5->.5 for another byte save; A**2->A*A for one more.
$endgroup$
– Jonathan Allan
Jan 27 at 23:18






$begingroup$
0.5->.5 for another byte save; A**2->A*A for one more.
$endgroup$
– Jonathan Allan
Jan 27 at 23:18













7












$begingroup$


05AB1E, 77 65 58 57 52 bytes



Xˆ0UF3D(Ÿ0KãʒÄ1¢}εX+}Dε·nàDtyÆ+yO·<.±*->}D¯KßDˆkèU}¯


-6 bytes thanks to @Arnauld by using a port of his formula.



Outputs the first $n+1$ values as a list (of decimals).



Try it online (the ï in the footer removes the .0 to make the output more compact, but feel free to remove it to see the actual result).



Code explanation:





Xˆ             # Put integer 1 in the global_array (global_array is empty by default)

0U             # Set variable `X` to 0 (`X` is 1 by default)

F              # Loop the (implicit) input amount of times:

 3D(Ÿ          #  Push the list in the range [-3,3]: [-3,-2,-1,0,1,2,3]

     0K        #  Remove the 0: [-3,-2,-1,1,2,3]

       ã       #  Cartesian product with itself, creating each possible pair: [[3,3],[3,2],[3,1],[3,-1],[3,-2],[3,-3],[2,3],[2,2],[2,1],[2,-1],[2,-2],[2,-3],[1,3],[1,2],[1,1],[1,-1],[1,-2],[1,-3],[-1,3],[-1,2],[-1,1],[-1,-1],[-1,-2],[-1,-3],[-2,3],[-2,2],[-2,1],[-2,-1],[-2,-2],[-2,-3],[-3,3],[-3,2],[-3,1],[-3,-1],[-3,-2],[-3,-3]]

        ʒ   }  #  Filter this list of pairs by:

         Ä     #   Where the absolute values of the pair

          1¢   #   Contains exactly one 1

               #  (We now have the following pairs left: [[3,1],[3,-1],[2,1],[2,-1],[1,3],[1,2],[1,-2],[1,-3],[-1,3],[-1,2],[-1,-2],[-1,-3],[-2,1],[-2,-1],[-3,1],[-3,-1]])

 εX+}          #  Add the variable `X` (previous coordinate) to each item in the list

 D             #  Duplicate this list of coordinates

  ε            #  Map each `x,y`-coordinate to:

   ·           #   Double both the `x` and `y` in the coordinate

    n          #   Then take the square of each

     à         #   And then pop and push the maximum of the two

   Dt          #   Duplicate this maximum, and take its square-root

     yÆ        #   Calculate `x-y`

       +       #   And add it to the square-root

   yO          #   Calculate `x+y`

     ·         #   Double it

      <        #   Decrease it by 1

       .±      #   And pop and push its signum (-1 if < 0; 0 if 0; 1 if > 0)

   *           #   Multiply these two together

    -          #   And subtract it from the duplicated maximum

   >           #   And finally increase it by 1 to make it 1-based instead of 0-based

  }D           #  After the map: Duplicate that list with values

    ¯K         #  Remove all values that are already present in the global_array

      ß        #  Pop the list of (remaining) values and push the minimum

       Dˆ      #  Duplicate this minimum, and pop and add the copy to the global_array

         k     #  Then get its index in the complete list of values

          è    #  And use that index to get the corresponding coordinate

           U   #  Pop and store this coordinate in variable `X` for the next iteration

}¯             # After the outer loop: push the global_array (which is output implicitly)


General explanation:



We hold all results (and therefore values we've already encountered) in the global_array, which is initially started as [1].

We hold the current $x,y$-coordinate in variable X, which is initially [0,0].



The list of coordinates we can reach based on the current $x,y$-coordinate are:



[[x+3,y+1], [x+3,y-1], [x+2,y+1], [x+2,y-1], [x+1,y+3], [x+1,y+2], [x+1,y-2], [x+1,y-3], [x-1,y+3], [x-1,y+2], [x-1,y-2], [x-1,y-3], [x-2,y+1], [x-2,y-1], [x-3,y+1], [x-3,y-1]]


The list I mention in the code explanation above holds these values we can jump to, after which the current $x,y$ (stored in variable X) is added.



Then it will calculate the spiral values based on these $x,y$-coordinates. It does this by using the following formula for a given $x,y$-coordinate:



$${T = max((2 * x) ^ 2, (2 * y) ^ 2)}$$
$${R = T - (x - y + √T) * signum((x + y) * 2 - 1) + 1}$$



Which is the same formula @Arnauld is using in his answer, but written differently to make use of 05AB1E's builtins for double, square, -1, +1, etc.



(If you want to see just this spiral part of the code in action: Try it online.)



After we've got all the values we can reach for the given $x,y$-coordinate, we remove all values that are already present in the global_array, and we then get the minimum of the (remaining) values.

This minimum is then added to the global_array, and variable X is replaced with the $x,y$-coordinate of this minimum.



After we've looped the input amount of times, the program will output this global_array as result.






share|improve this answer











$endgroup$









  • 1




    $begingroup$
    FWIW, here is a port of my own formula to convert the coordinates into spiral indices. It's 5 bytes shorter but yields floats. (I don't know if this is a problem or not.)
    $endgroup$
    – Arnauld
    Jan 28 at 16:58










  • $begingroup$
    (Note that $y$ in your code is $-y$ in mine.)
    $endgroup$
    – Arnauld
    Jan 28 at 17:07










  • $begingroup$
    @Arnauld Thanks, that saves 5 additional bytes. :) EDIT: Which you already mentioned in your first comment. ;p
    $endgroup$
    – Kevin Cruijssen
    Jan 28 at 17:36


















7












$begingroup$


05AB1E, 77 65 58 57 52 bytes



Xˆ0UF3D(Ÿ0KãʒÄ1¢}εX+}Dε·nàDtyÆ+yO·<.±*->}D¯KßDˆkèU}¯


-6 bytes thanks to @Arnauld by using a port of his formula.



Outputs the first $n+1$ values as a list (of decimals).



Try it online (the ï in the footer removes the .0 to make the output more compact, but feel free to remove it to see the actual result).



Code explanation:





Xˆ             # Put integer 1 in the global_array (global_array is empty by default)

0U             # Set variable `X` to 0 (`X` is 1 by default)

F              # Loop the (implicit) input amount of times:

 3D(Ÿ          #  Push the list in the range [-3,3]: [-3,-2,-1,0,1,2,3]

     0K        #  Remove the 0: [-3,-2,-1,1,2,3]

       ã       #  Cartesian product with itself, creating each possible pair: [[3,3],[3,2],[3,1],[3,-1],[3,-2],[3,-3],[2,3],[2,2],[2,1],[2,-1],[2,-2],[2,-3],[1,3],[1,2],[1,1],[1,-1],[1,-2],[1,-3],[-1,3],[-1,2],[-1,1],[-1,-1],[-1,-2],[-1,-3],[-2,3],[-2,2],[-2,1],[-2,-1],[-2,-2],[-2,-3],[-3,3],[-3,2],[-3,1],[-3,-1],[-3,-2],[-3,-3]]

        ʒ   }  #  Filter this list of pairs by:

         Ä     #   Where the absolute values of the pair

          1¢   #   Contains exactly one 1

               #  (We now have the following pairs left: [[3,1],[3,-1],[2,1],[2,-1],[1,3],[1,2],[1,-2],[1,-3],[-1,3],[-1,2],[-1,-2],[-1,-3],[-2,1],[-2,-1],[-3,1],[-3,-1]])

 εX+}          #  Add the variable `X` (previous coordinate) to each item in the list

 D             #  Duplicate this list of coordinates

  ε            #  Map each `x,y`-coordinate to:

   ·           #   Double both the `x` and `y` in the coordinate

    n          #   Then take the square of each

     à         #   And then pop and push the maximum of the two

   Dt          #   Duplicate this maximum, and take its square-root

     yÆ        #   Calculate `x-y`

       +       #   And add it to the square-root

   yO          #   Calculate `x+y`

     ·         #   Double it

      <        #   Decrease it by 1

       .±      #   And pop and push its signum (-1 if < 0; 0 if 0; 1 if > 0)

   *           #   Multiply these two together

    -          #   And subtract it from the duplicated maximum

   >           #   And finally increase it by 1 to make it 1-based instead of 0-based

  }D           #  After the map: Duplicate that list with values

    ¯K         #  Remove all values that are already present in the global_array

      ß        #  Pop the list of (remaining) values and push the minimum

       Dˆ      #  Duplicate this minimum, and pop and add the copy to the global_array

         k     #  Then get its index in the complete list of values

          è    #  And use that index to get the corresponding coordinate

           U   #  Pop and store this coordinate in variable `X` for the next iteration

}¯             # After the outer loop: push the global_array (which is output implicitly)


General explanation:



We hold all results (and therefore values we've already encountered) in the global_array, which is initially started as [1].

We hold the current $x,y$-coordinate in variable X, which is initially [0,0].



The list of coordinates we can reach based on the current $x,y$-coordinate are:



[[x+3,y+1], [x+3,y-1], [x+2,y+1], [x+2,y-1], [x+1,y+3], [x+1,y+2], [x+1,y-2], [x+1,y-3], [x-1,y+3], [x-1,y+2], [x-1,y-2], [x-1,y-3], [x-2,y+1], [x-2,y-1], [x-3,y+1], [x-3,y-1]]


The list I mention in the code explanation above holds these values we can jump to, after which the current $x,y$ (stored in variable X) is added.



Then it will calculate the spiral values based on these $x,y$-coordinates. It does this by using the following formula for a given $x,y$-coordinate:



$${T = max((2 * x) ^ 2, (2 * y) ^ 2)}$$
$${R = T - (x - y + √T) * signum((x + y) * 2 - 1) + 1}$$



Which is the same formula @Arnauld is using in his answer, but written differently to make use of 05AB1E's builtins for double, square, -1, +1, etc.



(If you want to see just this spiral part of the code in action: Try it online.)



After we've got all the values we can reach for the given $x,y$-coordinate, we remove all values that are already present in the global_array, and we then get the minimum of the (remaining) values.

This minimum is then added to the global_array, and variable X is replaced with the $x,y$-coordinate of this minimum.



After we've looped the input amount of times, the program will output this global_array as result.






share|improve this answer











$endgroup$









  • 1




    $begingroup$
    FWIW, here is a port of my own formula to convert the coordinates into spiral indices. It's 5 bytes shorter but yields floats. (I don't know if this is a problem or not.)
    $endgroup$
    – Arnauld
    Jan 28 at 16:58










  • $begingroup$
    (Note that $y$ in your code is $-y$ in mine.)
    $endgroup$
    – Arnauld
    Jan 28 at 17:07










  • $begingroup$
    @Arnauld Thanks, that saves 5 additional bytes. :) EDIT: Which you already mentioned in your first comment. ;p
    $endgroup$
    – Kevin Cruijssen
    Jan 28 at 17:36
















7












7








7





$begingroup$


05AB1E, 77 65 58 57 52 bytes



Xˆ0UF3D(Ÿ0KãʒÄ1¢}εX+}Dε·nàDtyÆ+yO·<.±*->}D¯KßDˆkèU}¯


-6 bytes thanks to @Arnauld by using a port of his formula.



Outputs the first $n+1$ values as a list (of decimals).



Try it online (the ï in the footer removes the .0 to make the output more compact, but feel free to remove it to see the actual result).



Code explanation:





Xˆ             # Put integer 1 in the global_array (global_array is empty by default)

0U             # Set variable `X` to 0 (`X` is 1 by default)

F              # Loop the (implicit) input amount of times:

 3D(Ÿ          #  Push the list in the range [-3,3]: [-3,-2,-1,0,1,2,3]

     0K        #  Remove the 0: [-3,-2,-1,1,2,3]

       ã       #  Cartesian product with itself, creating each possible pair: [[3,3],[3,2],[3,1],[3,-1],[3,-2],[3,-3],[2,3],[2,2],[2,1],[2,-1],[2,-2],[2,-3],[1,3],[1,2],[1,1],[1,-1],[1,-2],[1,-3],[-1,3],[-1,2],[-1,1],[-1,-1],[-1,-2],[-1,-3],[-2,3],[-2,2],[-2,1],[-2,-1],[-2,-2],[-2,-3],[-3,3],[-3,2],[-3,1],[-3,-1],[-3,-2],[-3,-3]]

        ʒ   }  #  Filter this list of pairs by:

         Ä     #   Where the absolute values of the pair

          1¢   #   Contains exactly one 1

               #  (We now have the following pairs left: [[3,1],[3,-1],[2,1],[2,-1],[1,3],[1,2],[1,-2],[1,-3],[-1,3],[-1,2],[-1,-2],[-1,-3],[-2,1],[-2,-1],[-3,1],[-3,-1]])

 εX+}          #  Add the variable `X` (previous coordinate) to each item in the list

 D             #  Duplicate this list of coordinates

  ε            #  Map each `x,y`-coordinate to:

   ·           #   Double both the `x` and `y` in the coordinate

    n          #   Then take the square of each

     à         #   And then pop and push the maximum of the two

   Dt          #   Duplicate this maximum, and take its square-root

     yÆ        #   Calculate `x-y`

       +       #   And add it to the square-root

   yO          #   Calculate `x+y`

     ·         #   Double it

      <        #   Decrease it by 1

       .±      #   And pop and push its signum (-1 if < 0; 0 if 0; 1 if > 0)

   *           #   Multiply these two together

    -          #   And subtract it from the duplicated maximum

   >           #   And finally increase it by 1 to make it 1-based instead of 0-based

  }D           #  After the map: Duplicate that list with values

    ¯K         #  Remove all values that are already present in the global_array

      ß        #  Pop the list of (remaining) values and push the minimum

       Dˆ      #  Duplicate this minimum, and pop and add the copy to the global_array

         k     #  Then get its index in the complete list of values

          è    #  And use that index to get the corresponding coordinate

           U   #  Pop and store this coordinate in variable `X` for the next iteration

}¯             # After the outer loop: push the global_array (which is output implicitly)


General explanation:



We hold all results (and therefore values we've already encountered) in the global_array, which is initially started as [1].

We hold the current $x,y$-coordinate in variable X, which is initially [0,0].



The list of coordinates we can reach based on the current $x,y$-coordinate are:



[[x+3,y+1], [x+3,y-1], [x+2,y+1], [x+2,y-1], [x+1,y+3], [x+1,y+2], [x+1,y-2], [x+1,y-3], [x-1,y+3], [x-1,y+2], [x-1,y-2], [x-1,y-3], [x-2,y+1], [x-2,y-1], [x-3,y+1], [x-3,y-1]]


The list I mention in the code explanation above holds these values we can jump to, after which the current $x,y$ (stored in variable X) is added.



Then it will calculate the spiral values based on these $x,y$-coordinates. It does this by using the following formula for a given $x,y$-coordinate:



$${T = max((2 * x) ^ 2, (2 * y) ^ 2)}$$
$${R = T - (x - y + √T) * signum((x + y) * 2 - 1) + 1}$$



Which is the same formula @Arnauld is using in his answer, but written differently to make use of 05AB1E's builtins for double, square, -1, +1, etc.



(If you want to see just this spiral part of the code in action: Try it online.)



After we've got all the values we can reach for the given $x,y$-coordinate, we remove all values that are already present in the global_array, and we then get the minimum of the (remaining) values.

This minimum is then added to the global_array, and variable X is replaced with the $x,y$-coordinate of this minimum.



After we've looped the input amount of times, the program will output this global_array as result.






share|improve this answer











$endgroup$




05AB1E, 77 65 58 57 52 bytes



Xˆ0UF3D(Ÿ0KãʒÄ1¢}εX+}Dε·nàDtyÆ+yO·<.±*->}D¯KßDˆkèU}¯


-6 bytes thanks to @Arnauld by using a port of his formula.



Outputs the first $n+1$ values as a list (of decimals).



Try it online (the ï in the footer removes the .0 to make the output more compact, but feel free to remove it to see the actual result).



Code explanation:





Xˆ             # Put integer 1 in the global_array (global_array is empty by default)

0U             # Set variable `X` to 0 (`X` is 1 by default)

F              # Loop the (implicit) input amount of times:

 3D(Ÿ          #  Push the list in the range [-3,3]: [-3,-2,-1,0,1,2,3]

     0K        #  Remove the 0: [-3,-2,-1,1,2,3]

       ã       #  Cartesian product with itself, creating each possible pair: [[3,3],[3,2],[3,1],[3,-1],[3,-2],[3,-3],[2,3],[2,2],[2,1],[2,-1],[2,-2],[2,-3],[1,3],[1,2],[1,1],[1,-1],[1,-2],[1,-3],[-1,3],[-1,2],[-1,1],[-1,-1],[-1,-2],[-1,-3],[-2,3],[-2,2],[-2,1],[-2,-1],[-2,-2],[-2,-3],[-3,3],[-3,2],[-3,1],[-3,-1],[-3,-2],[-3,-3]]

        ʒ   }  #  Filter this list of pairs by:

         Ä     #   Where the absolute values of the pair

          1¢   #   Contains exactly one 1

               #  (We now have the following pairs left: [[3,1],[3,-1],[2,1],[2,-1],[1,3],[1,2],[1,-2],[1,-3],[-1,3],[-1,2],[-1,-2],[-1,-3],[-2,1],[-2,-1],[-3,1],[-3,-1]])

 εX+}          #  Add the variable `X` (previous coordinate) to each item in the list

 D             #  Duplicate this list of coordinates

  ε            #  Map each `x,y`-coordinate to:

   ·           #   Double both the `x` and `y` in the coordinate

    n          #   Then take the square of each

     à         #   And then pop and push the maximum of the two

   Dt          #   Duplicate this maximum, and take its square-root

     yÆ        #   Calculate `x-y`

       +       #   And add it to the square-root

   yO          #   Calculate `x+y`

     ·         #   Double it

      <        #   Decrease it by 1

       .±      #   And pop and push its signum (-1 if < 0; 0 if 0; 1 if > 0)

   *           #   Multiply these two together

    -          #   And subtract it from the duplicated maximum

   >           #   And finally increase it by 1 to make it 1-based instead of 0-based

  }D           #  After the map: Duplicate that list with values

    ¯K         #  Remove all values that are already present in the global_array

      ß        #  Pop the list of (remaining) values and push the minimum

       Dˆ      #  Duplicate this minimum, and pop and add the copy to the global_array

         k     #  Then get its index in the complete list of values

          è    #  And use that index to get the corresponding coordinate

           U   #  Pop and store this coordinate in variable `X` for the next iteration

}¯             # After the outer loop: push the global_array (which is output implicitly)


General explanation:



We hold all results (and therefore values we've already encountered) in the global_array, which is initially started as [1].

We hold the current $x,y$-coordinate in variable X, which is initially [0,0].



The list of coordinates we can reach based on the current $x,y$-coordinate are:



[[x+3,y+1], [x+3,y-1], [x+2,y+1], [x+2,y-1], [x+1,y+3], [x+1,y+2], [x+1,y-2], [x+1,y-3], [x-1,y+3], [x-1,y+2], [x-1,y-2], [x-1,y-3], [x-2,y+1], [x-2,y-1], [x-3,y+1], [x-3,y-1]]


The list I mention in the code explanation above holds these values we can jump to, after which the current $x,y$ (stored in variable X) is added.



Then it will calculate the spiral values based on these $x,y$-coordinates. It does this by using the following formula for a given $x,y$-coordinate:



$${T = max((2 * x) ^ 2, (2 * y) ^ 2)}$$
$${R = T - (x - y + √T) * signum((x + y) * 2 - 1) + 1}$$



Which is the same formula @Arnauld is using in his answer, but written differently to make use of 05AB1E's builtins for double, square, -1, +1, etc.



(If you want to see just this spiral part of the code in action: Try it online.)



After we've got all the values we can reach for the given $x,y$-coordinate, we remove all values that are already present in the global_array, and we then get the minimum of the (remaining) values.

This minimum is then added to the global_array, and variable X is replaced with the $x,y$-coordinate of this minimum.



After we've looped the input amount of times, the program will output this global_array as result.







share|improve this answer














share|improve this answer



share|improve this answer








edited Jan 28 at 17:36

























answered Jan 28 at 13:27









Kevin CruijssenKevin Cruijssen

41.5k567215




41.5k567215








  • 1




    $begingroup$
    FWIW, here is a port of my own formula to convert the coordinates into spiral indices. It's 5 bytes shorter but yields floats. (I don't know if this is a problem or not.)
    $endgroup$
    – Arnauld
    Jan 28 at 16:58










  • $begingroup$
    (Note that $y$ in your code is $-y$ in mine.)
    $endgroup$
    – Arnauld
    Jan 28 at 17:07










  • $begingroup$
    @Arnauld Thanks, that saves 5 additional bytes. :) EDIT: Which you already mentioned in your first comment. ;p
    $endgroup$
    – Kevin Cruijssen
    Jan 28 at 17:36
















  • 1




    $begingroup$
    FWIW, here is a port of my own formula to convert the coordinates into spiral indices. It's 5 bytes shorter but yields floats. (I don't know if this is a problem or not.)
    $endgroup$
    – Arnauld
    Jan 28 at 16:58










  • $begingroup$
    (Note that $y$ in your code is $-y$ in mine.)
    $endgroup$
    – Arnauld
    Jan 28 at 17:07










  • $begingroup$
    @Arnauld Thanks, that saves 5 additional bytes. :) EDIT: Which you already mentioned in your first comment. ;p
    $endgroup$
    – Kevin Cruijssen
    Jan 28 at 17:36










1




1




$begingroup$
FWIW, here is a port of my own formula to convert the coordinates into spiral indices. It's 5 bytes shorter but yields floats. (I don't know if this is a problem or not.)
$endgroup$
– Arnauld
Jan 28 at 16:58




$begingroup$
FWIW, here is a port of my own formula to convert the coordinates into spiral indices. It's 5 bytes shorter but yields floats. (I don't know if this is a problem or not.)
$endgroup$
– Arnauld
Jan 28 at 16:58












$begingroup$
(Note that $y$ in your code is $-y$ in mine.)
$endgroup$
– Arnauld
Jan 28 at 17:07




$begingroup$
(Note that $y$ in your code is $-y$ in mine.)
$endgroup$
– Arnauld
Jan 28 at 17:07












$begingroup$
@Arnauld Thanks, that saves 5 additional bytes. :) EDIT: Which you already mentioned in your first comment. ;p
$endgroup$
– Kevin Cruijssen
Jan 28 at 17:36






$begingroup$
@Arnauld Thanks, that saves 5 additional bytes. :) EDIT: Which you already mentioned in your first comment. ;p
$endgroup$
– Kevin Cruijssen
Jan 28 at 17:36




















draft saved

draft discarded




















































If this is an answer to a challenge…




  • …Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.


  • …Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
    Explanations of your answer make it more interesting to read and are very much encouraged.


  • …Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.



More generally…




  • …Please make sure to answer the question and provide sufficient detail.


  • …Avoid asking for help, clarification or responding to other answers (use comments instead).





draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f179157%2fthe-path-of-the-wildebeest%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

MongoDB - Not Authorized To Execute Command

Image
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I have successfully enabled authorization on MongoDB and I have created an account on the admin database and then I created an account for my database called test. The following connection string to connect to my test database works successfully: mongo --host 192.168.17.52 --port 27017 -u user1 -p password --authenticationDatabase test Only problem I have now is, I cannot execute commands such as: show dbs. I get the following error when I try to do so: "errmsg" : "not authorized on admin to execute command { listDatabases: 1.0, lsid: { id: UUID("a1d5bc0d-bc58-485e-b232-270758a89455") }, $db: "admin...
Read more

Npm cannot find a required file even through it is in the searched directory

Image
up vote 0 down vote favorite I got that error: users-Air:pdfuploader user$ npm run start client@0.1.0 start /Users/user/Documents/pdfuploader react-scripts start Could not find a required file. Name: index.html Searched in: /Users/user/Documents/pdfuploader/public npm ERR! code ELIFECYCLE npm ERR! errno 1 npm ERR! client@0.1.0 start: `react-scripts start` npm ERR! Exit status 1 npm ERR! npm ERR! Failed at the client@0.1.0 start script. npm ERR! This is probably not a problem with npm. There is likely additional logging output above. npm ERR! A complete log of this run can be found in: npm ERR! /Users/user/.npm/_logs/2018-11-19T10_19_14_555Z-debug.log users-Air:pdfuploader user$ And the file is in /Users/user/Documents/pdfuploader/public as you can see in my github repository: https://github.c...
Read more

in spring boot 2.1 many test slices are not allowed anymore due to multiple @BootstrapWith

Image
1 I tried to upgrade a yummy sandwich made of two test slices (@JsonTest and @JdbcTest in my case, crunchy test code in between) adding spring boot 2.1 flavour to it. But it seems it was not much of a success. I cannot annotate my tests with many @...Test since they are now each bringing their own XxxTestContextBootstrapper. It used to work when they all used same SpringBootTestContextBootstrapper. @RunWith(SpringRunner.class) @JdbcTest @JsonTest public class Test { @Test public void test() { System.out.printn("Hello, World !"); } } The error I get from BootstrapUtils is illegalStateException : Configuration error: found multiple declarations of @BootstrapWith for test class I understand I might be doing something wrong here but is there an easy way I could load both Json and Jdbc contex...
Read more