A number spiral is an infinite grid whose upper-left square has number 1. Here are the first five layers of the spiral:

enter image description here

Your task is to find out the number in row y and column x.


Example:

Input: 2 3
Out  : 8
Input: 1 1
Out  : 1
Input: 4 2
Out  : 15

Note:

  1. Any programming language is allowed.
  2. This is a challenge so shortest code wins.
  3. Best of Luck!

Source: https://cses.fi/problemset/task/1071

  • 1
    It looks like your inputs are 1 indexed (coordinates start at 1,1) (although this has to be intuited from the test cases) can we use 0 indexing (coordinates start at 0,0)? – W W Aug 17 at 16:26
  • 4
    What is the reasoning for this? – W W Aug 17 at 16:30
  • 3
    Nice challenge, but I don't really like that you force it to be 1-indexed... +1 anyway... – Stewie Griffin Aug 18 at 8:30
  • 7
    I think it's absolutely fine for the coordinates to start at (1, 1), especially if the program is posted that way on CSES, and the OP doesn't need to justify this. I think golfers here are getting a little too used to somewhat arbitrary freedoms. – Lynn Aug 18 at 12:57
  • 2
    @Lynn I second that – Agile_Eagle Aug 18 at 12:58

14 Answers 14

C (gcc),  44  43 bytes

f(x,y,z){z=x>y?x:y;z=z*z-~(z%2?y-x:x-y)-z;}

Try it online!

The spiral has several "arms":

12345
22345
33345
44445
55555

The position \$(x, y)\$ is located on arm \$\max(x, y)\$ (assigned to variable z). Then, the largest number on arm \$n\$ is \$n^2\$, which alternates between being in the bottom left and top right position on the arm. Subtracting \$x\$ from \$y\$ gives the sequence \$-n+1, -n+2, \ldots, -1, 0, 1, \ldots, n-1, n-2\$ moving along arm \$n\$, so we choose the appropriate sign based on the parity of \$n\$, adjust by \$n-1\$ to get a sequence starting at 0, and subtract this value from \$n^2\$.

Thanks to Mr. Xcoder for saving a byte.

  • f(x,y,z){z=x>y?x:y;z=z*z-~(z%2?x-y:y-x)-z;} saves 1 byte. – Mr. Xcoder Aug 17 at 15:52
  • @Mr.Xcoder Neat trick, thanks! – Doorknob Aug 17 at 15:55
  • 3
    @RobertS. Yes, that is what the function I defined does (in the Code section on TIO). For instance, f(1, 1) returns the value 1. The Footer section loops through x=1 through 5 and y=1 through 5, calls the function for all such values, and prints its output in a grid, to demonstrate that the function is correct for all inputs shown in the question. – Doorknob Aug 17 at 19:38
  • 1
    @Agile_Eagle The function does return the number (it couldn't output the spiral - it doesn't even have any loops!). – Doorknob Aug 17 at 19:40

Python,  54   50  49 bytes

def f(a,b):M=max(a,b);return(a-b)*(-1)**M+M*M-M+1

-4 bytes thanks to @ChasBrown

-1 bytes thanks to @Shaggy

Try it Online!

First time golfing! I'm more than aware this is not optimal, but whatever.

Essentially runs on the same principle as @Doorknob C code.

  • 2
    Welcome to PPCG! In this case you can save 4 bytes using the def f(a,b): approach, see here. – Chas Brown Aug 17 at 21:21
  • @ChasBrown Very interesting, thank you! – Rushabh Mehta Aug 17 at 21:21
  • @Shaggy Thank you! I've posted a few challenges, but never been good enough to golf – Rushabh Mehta Aug 17 at 22:32
  • In that case, then, welcome to Golf! :) I'm not a Python guy but I'm pretty sure M**2 can be replaced with M*M. – Shaggy Aug 17 at 22:36
  • @Shaggy Thank you! Will fix right now – Rushabh Mehta Aug 17 at 22:37

MATL, 15 bytes

X>ttq*QwoEqGd*+

Try it online!
Collect and print as a matrix

How?

Edit: Same technique as @Doorknob's answer, just arrived at differently.

The difference between the diagonal elements of the spiral is the arithmetic sequence \$ 0, 2, 4, 6, 8, \ldots \$. Sum of \$ n \$ terms of this is \$ n(n - 1) \$ (by the usual AP formula). This sum, incremented by 1, gives the diagonal element at position \$ (n, n) \$.

Given \$ (x, y) \$, we find the maximum of these two, which is the "layer" of the spiral that this point belongs to. Then, we find the diagonal value of that layer as \$ v = n(n-1) + 1 \$. For even layers, the value at \$ (x, y) \$ is then \$ v + x - y \$, for odd layers \$ v - x + y \$.

X>        % Get the maximum of the input coordinates, say n
ttq*      % Duplicate that and multiply by n-1
Q         % Add 1 to that. This is the diagonal value v at layer n
wo        % Bring the original n on top and check if it's odd (1 or 0)
Eq        % Change 1 or 0 to 1 or -1
Gd        % Push input (x, y) again, get y - x
*         % Multiply by 1 or -1
          % For odd layers, no change. For even layers, y-x becomes x-y
+         % Add that to the diagonal value v
          % Implicit output

Alternate 21 byte solution:

Pdt|Gs+ttqq*4/QJb^b*+

Try it online!
Collect and print as a matrix
From the above, we know that the function we want is

$$ f = m * (m - 1) + 1 + (-1)^m * (x - y) $$

where \$ m = max(x, y) \$.

Some basic calculation will show that one expression for max of two numbers is

$$ m = max(x, y) = \frac{x + y + abs(x - y)}{2} $$

Plugging one into another, we find that one alternate form for \$ f \$ is:

$$ f = (x-y)\cdot i^{k} + \frac{1}{4}((k-2)\cdot k) + 1 $$

where \$ k = abs(x-y) + x + y \$.

This is the function the solution implements.

Japt, 16 bytes

Adapted from Doorknob's solution over a few beers.

wV
nU²ÒNr"n-"gUv

Try it


Explanation

                  :Implicit input of integers U=x and V=y
wV                :Maximum of U & V
\n                :Reassign to U
 U²               :U squared
   Ò              :-~
      "n-"        :Literal string
           Uv     :Is U divisible by 2? Return 0 or 1
          g       :Get the character in the string at that index
    Nr            :Reduce the array of inputs by that, where n is inverse subtraction (XnY = Y-X)
n                 :Subtract U from the result of the above

Pyth, 20 bytes

A~Qh.MZQh-+*-GH^_1Q*

Test suite

An almost literal translation of Rushabh Mehta's answer.

Explanation:
A~Qh.MZQh-+*-GH^_1Q*    | Full code
A~Qh.MZQh-+*-GH^_1Q*QQQ | Code with implicit variables filled
                        | Assign Q as the evaluated input (implicit)
A                       | Assign [G,H] as
 ~Q                     |  Q, then assign Q as
   h.MZQ                |   Q's maximal value.
                        | Print (implicit)
        h-+*-GH^_1Q*QQQ |  (G-H)*(-1)^Q+Q*Q-Q+1

Jelly, 13 bytes

»Ḃ-*×_‘+»×’$¥

Try it online!

Uses Doorknob's method. Way too long.

  • Alternative: »Ḃ-*×_‘+»²_»ʋ – Mr. Xcoder Aug 17 at 16:41

Jelly, 13 12 bytes

ṀḂḤ’×I+²_’ṀƲ

Try it online!

Computes the diagonal term with ²_’Ṁ and adds/subtracts to the correct index value with ṀḂḤ’×I.

Brain-Flak, 76 bytes

((({}<>))<>[(({}))]<{({}[()])<>}>)<>{}((){({}[()])({})<><([{}])><>}{}<>{}<>)

Try it online!

05AB1E, 12 11 bytes

ZÐ<*>ŠGR}¥+

-1 byte thanks to @Emigna changing Èi to G.

Port of @sundar's MATL answer, so make sure to upvote him!

Try it online or verify all test cases.

Explanation:

Z              # Get the maximum of the (implicit) input-coordinate
               #  i.e. [4,5] → 5
 Ð             # Triplicate this maximum
  <            # Decrease it by 1
               #  i.e. 5 - 1 → 4
   *           # Multiply it
               #  i.e. 5 * 4 → 20
    >          # Increase it by 1
               #  i.e. 20 + 1 → 21
     Š         # Triple swap the top threes values on the stack (a,b,c to c,a,b)
               #  i.e. [4,5], 5, 21 → 21, [4,5], 5
      G }      # Loop n amount of times
       R       #  Reverse the input-coordinate each iteration
               #   i.e. 5 and [4,5] → [5,4]→[4,5]→[5,4]→[4,5] → [5,4]
         ¥     # Calculate the delta of the coordinate
               #  [5,4] → [1]
          +    # And add it to the earlier calculate value (output the result implicitly)
               #  21 + [1] → [22]
  • 1
    Èi could be G. – Emigna Aug 20 at 10:39
  • @Emigna Oh smart, thanks! :D – Kevin Cruijssen Aug 20 at 11:01

Pascal (FPC), 90 bytes

uses math;var x,y,z:word;begin read(x,y);z:=max(x,y);write(z*z-z+1+(1and z*2-1)*(y-x))end.

Try it online!

Port of Doorknob's answer, but sundar's answer gave me idea for z mod 2*2-1 which I transformed into 1and z*2-1 to remove space.

Mathematica 34 bytes

x = {5, 8};

so:

m = Max[x];
Subtract @@ x (-1)^m + m^2 - m + 1

(*

54

*)

Julia 1.0, 35 bytes

x\y=(m=max(x,y))*~-m+1+(-1)^m*(x-y)

Try it online!

JavaScript (ES6), 46 bytes

f=(r,c,x)=>r<c?f(c,r,1):r%2-!x?r*r-c+1:--r*r+c

Java (JDK 10), 39 bytes

x->y->(y-x)*((y=x>y?x:y)%2*2-1)+y*y-y+1

Try it online!

Credits

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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