Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: DFS <nospam@dfs.com>
Newsgroups: comp.lang.c
Subject: Re: OT: CSES Number Spiral algorithm
Date: Sun, 23 Mar 2025 12:30:15 -0400
Organization: A noiseless patient Spider
Lines: 96
Message-ID: <vrpcun$2o6k4$2@dont-email.me>
References: <vrhgqd$3ku1m$2@dont-email.me> <vrhl8b$3njm0$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 23 Mar 2025 17:30:16 +0100 (CET)
Injection-Info: dont-email.me; posting-host="1416cee1c6e1e50fee3ae9def3ab8477";
	logging-data="2890372"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18Q3pChlzm+RKCOSKKJfc1I"
User-Agent: Betterbird (Windows)
Cancel-Lock: sha1:4rxlXHQrZEURCkXwBnu14MkC2d4=
Content-Language: en-US
In-Reply-To: <vrhl8b$3njm0$1@dont-email.me>
Bytes: 3824

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?



> 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:

- Odd rows increase at all times
- Even rows decrease until they hit the matching # column, then start
   increasing

- Odd columns decrease until they hit the matching # row, then start
   increasing
- Even columns increase at all times


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

https://ramandeepsingh.hashnode.dev/number-spiral