Re: OT: CSES Number Spiral algorithm

[This discussion is not about the C language. Following my own advice, therefore, I have cross-posted to comp.programming and set follow-ups.]
On 23/03/2025 16:30, DFS wrote:

On 3/20/2025 2:02 PM, Richard Heathfield wrote:

On 20/03/2025 16:47, DFS wrote:

I don't have a C question, but rather I'd like input about algorithmic approaches.
>
https://cses.fi/problemset/task/1071
>
It's an 'infinite grid'.  You have to find the value at rows-columns from 1 to 10^9.
>
First thing you notice about the 5x5 grid is the values in odd-numbered columns begin with the square of the column number, and the values in even-numbered rows begin with the square of the row number.
>
I followed the number pattern and built a grid in Excel and expanded it to 10x10 for more testing.
>
https://imgur.com/x4VymmA
>
Then coded 4 conditions      solution
1. row <= col and col odd    (col * col) - row + 1
2. row <= col and col even   ((col-1) * (col-1)) + row
3. row >  col and row odd    ((row-1) * (row-1)) + col
4. row >  col and row even   (row * row) - col + 1
>
My full C code submission was accepted the first time.
>
How would you have done it?

>
>
I see that you've already solved it, so that's good.
>
My first observation was the main diagonal, which goes:
>
1 3 7 13 21...
>
Differences are 2 4 6 8... respectively
>
Consider the triangle numbers (n(n+1)/2):
>
0 1 3 6 10 15 21 28...
>
Double and add 1:
>
1 3 7 13 21 31...
>
So the main diagonal is readily calculable - either (row, row) or (col, col).

 Even easier when row=column is: r^2-(r-1), or if you prefer: (r^2-r)+1
 I just now noticed that.
 After my code was accepted I looked online at other solutions, and most were similar to mine: 4 conditions/formulas.
 But I wouldn't doubt it can be done shorter/more efficiently.
 

I'd then have picked the biggest out of (row, col) and calculated its triangle number: n(n+1)/2, doubled (so don't divide) and add 1, for (n(n+1))+1 and then either added the column or subtracted the row (whichever of them is smaller).

 Let's try that:
refer to https://imgur.com/x4VymmA
row 8, col 7
value at 8,7 is 58
 your method (as I understand it)
8(8+1) + 1 - 7 = 66
  Did I mess it up?

No, I did.

Reviewing your solution after the fact, I don't see the need to
distinguish between odd and even. What did I miss?

 The number patters are different:

Indeed they are, and I spotted one pattern but obviously not the other.

The pattern is called a spiral by CSES, but the numbers don't follow a spiral at all.

Yes, I thought that was rather sloppy.
In the absence of actual code to discuss, I'm not sure that there's much more to say, except that you were clearly paying much closer attention than I was to the specification.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within