From Newsgroup: comp.programming

[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'.-a 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-a-a-a-a-a solution
1. row <= col and col odd-a-a-a (col * col) - row + 1
2. row <= col and col even-a-a ((col-1) * (col-1)) + row
3. row >-a col and row odd-a-a-a ((row-1) * (row-1)) + col
4. row >-a col and row even-a-a (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

--- Synchronet 3.21d-Linux NewsLink 1.2