Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #391422 > unrolled thread

OT: CSES Number Spiral algorithm

Back to article view | Back to comp.lang.c

Contents

  OT: CSES Number Spiral algorithm DFS <nospam@dfs.com> - 2025-03-20 12:47 -0400
    Re: OT: CSES Number Spiral algorithm Richard Heathfield <rjh@cpax.org.uk> - 2025-03-20 18:02 +0000
      Re: OT: CSES Number Spiral algorithm DFS <nospam@dfs.com> - 2025-03-23 12:30 -0400
        Re: OT: CSES Number Spiral algorithm Richard Heathfield <rjh@cpax.org.uk> - 2025-03-24 04:15 +0000
    Re: OT: CSES Number Spiral algorithm Kaz Kylheku <643-408-1753@kylheku.com> - 2025-03-20 18:32 +0000
      Re: OT: CSES Number Spiral algorithm DFS <nospam@dfs.com> - 2025-03-21 16:54 -0400
        Re: OT: CSES Number Spiral algorithm Kaz Kylheku <643-408-1753@kylheku.com> - 2025-03-22 01:55 +0000
    Re: OT: CSES Number Spiral algorithm Tim Rentsch <tr.17687@z991.linuxsc.com> - 2025-03-20 11:38 -0700
      Re: OT: CSES Number Spiral algorithm Richard Heathfield <rjh@cpax.org.uk> - 2025-03-20 20:07 +0000
        Re: OT: CSES Number Spiral algorithm Tim Rentsch <tr.17687@z991.linuxsc.com> - 2025-03-20 13:10 -0700
          Re: OT: CSES Number Spiral algorithm Richard Heathfield <rjh@cpax.org.uk> - 2025-03-21 03:40 +0000
            Re: OT: CSES Number Spiral algorithm Tim Rentsch <tr.17687@z991.linuxsc.com> - 2025-03-20 23:52 -0700
      Re: OT: CSES Number Spiral algorithm DFS <nospam@dfs.com> - 2025-03-20 16:54 -0400
        Re: OT: CSES Number Spiral algorithm Tim Rentsch <tr.17687@z991.linuxsc.com> - 2025-03-20 16:52 -0700
          Re: OT: CSES Number Spiral algorithm DFS <nospam@dfs.com> - 2025-03-20 20:26 -0400
            Re: OT: CSES Number Spiral algorithm Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-03-20 18:49 -0700
              Re: OT: CSES Number Spiral algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-03-21 14:18 -0700
          Re: OT: CSES Number Spiral algorithm DFS <nospam@dfs.com> - 2025-03-20 20:45 -0400

#391422 — OT: CSES Number Spiral algorithm

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?

[toc] | [next] | [standalone]

#391424

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).

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).

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

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

[toc] | [prev] | [next] | [standalone]

#391544

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

[toc] | [prev] | [next] | [standalone]

#391550

[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

[toc] | [prev] | [next] | [standalone]

#391426

On 2025-03-20, DFS <nospam@dfs.com> wrote:
> I don't have a C question, but rather I'd like input about algorithmic 
> approaches.
>
> https://cses.fi/problemset/task/1071

  > Time limit: 1.00 s Memory limit: 512 MB

Is that just for the solution itself?

If I deploy a Kubernetes cluster, with seven different versions of
Fedora and Debian sporting thousands of packages running in different
containers, does all that count toward these limits?

Or just the small end program I will end up runnig in the end?

In any case, I could put it into a Docker image that has been staged and
optimized to just contain that binary and its minimal dependencies ...

... haha! I looked years younger there for a second, didn't I!

-- 
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

[toc] | [prev] | [next] | [standalone]

#391482

On 3/20/2025 2:32 PM, Kaz Kylheku wrote:
> On 2025-03-20, DFS <nospam@dfs.com> wrote:
>> I don't have a C question, but rather I'd like input about algorithmic
>> approaches.
>>
>> https://cses.fi/problemset/task/1071
> 
>    > Time limit: 1.00 s Memory limit: 512 MB
> 
> Is that just for the solution itself?
> 
> If I deploy a Kubernetes cluster, with seven different versions of
> Fedora and Debian sporting thousands of packages running in different
> containers, does all that count toward these limits?
> 
> Or just the small end program I will end up runnig in the end?
> 
> In any case, I could put it into a Docker image that has been staged and
> optimized to just contain that binary and its minimal dependencies ...
> 
> ... haha! I looked years younger there for a second, didn't I!


heh!

Were you wearing skinny jeans when you wrote it?

[toc] | [prev] | [next] | [standalone]

#391487

On 2025-03-21, DFS <nospam@dfs.com> wrote:
> On 3/20/2025 2:32 PM, Kaz Kylheku wrote:
>> On 2025-03-20, DFS <nospam@dfs.com> wrote:
>>> I don't have a C question, but rather I'd like input about algorithmic
>>> approaches.
>>>
>>> https://cses.fi/problemset/task/1071
>> 
>>    > Time limit: 1.00 s Memory limit: 512 MB
>> 
>> Is that just for the solution itself?
>> 
>> If I deploy a Kubernetes cluster, with seven different versions of
>> Fedora and Debian sporting thousands of packages running in different
>> containers, does all that count toward these limits?
>> 
>> Or just the small end program I will end up runnig in the end?
>> 
>> In any case, I could put it into a Docker image that has been staged and
>> optimized to just contain that binary and its minimal dependencies ...
>> 
>> ... haha! I looked years younger there for a second, didn't I!
>
>
> heh!
>
> Were you wearing skinny jeans when you wrote it?

Close. Mom.

-- 
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

[toc] | [prev] | [next] | [standalone]

#391428

DFS <nospam@dfs.com> writes:

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

This posting is not appropriate for comp.lang.c.  Putting "OT" in
the subject line doesn't excuse its lack of suitability.

[toc] | [prev] | [next] | [standalone]

#391440

On 20/03/2025 18:38, Tim Rentsch wrote:
> DFS <nospam@dfs.com> writes:
> 

<snip>

>> My full C code submission was accepted the first time.
>>
>> How would you have done it?
> 
> This posting is not appropriate for comp.lang.c.  Putting "OT" in
> the subject line doesn't excuse its lack of suitability.

You're right, of course, but would it have hurt so very much to 
point the OP towards comp.programming?

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

[toc] | [prev] | [next] | [standalone]

#391441

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 20/03/2025 18:38, Tim Rentsch wrote:
>
>> DFS <nospam@dfs.com> writes:
>
> <snip>
>
>>> My full C code submission was accepted the first time.
>>>
>>> How would you have done it?
>>
>> This posting is not appropriate for comp.lang.c.  Putting "OT" in
>> the subject line doesn't excuse its lack of suitability.
>
> You're right, of course, but would it have hurt so very much to point
> the OP towards comp.programming?

An oversight on my part.  Thank you for chiming in.

[toc] | [prev] | [next] | [standalone]

#391463

On 20/03/2025 20:10, Tim Rentsch wrote:
> Richard Heathfield <rjh@cpax.org.uk> writes:
> 
>> On 20/03/2025 18:38, Tim Rentsch wrote:
>>
>>> DFS <nospam@dfs.com> writes:
>>
>> <snip>
>>
>>>> My full C code submission was accepted the first time.
>>>>
>>>> How would you have done it?
>>>
>>> This posting is not appropriate for comp.lang.c.  Putting "OT" in
>>> the subject line doesn't excuse its lack of suitability.
>>
>> You're right, of course, but would it have hurt so very much to point
>> the OP towards comp.programming?
> 
> An oversight on my part.  Thank you for chiming in.

His questions were tailor-made for comp.programming, but it turns 
out he's just another toy-thrower, so it matters not.

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

[toc] | [prev] | [next] | [standalone]

#391465

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 20/03/2025 20:10, Tim Rentsch wrote:
>
>> Richard Heathfield <rjh@cpax.org.uk> writes:
>>
>>> On 20/03/2025 18:38, Tim Rentsch wrote:
>>>
>>>> DFS <nospam@dfs.com> writes:
>>>
>>> <snip>
>>>
>>>>> My full C code submission was accepted the first time.
>>>>>
>>>>> How would you have done it?
>>>>
>>>> This posting is not appropriate for comp.lang.c.  Putting "OT" in
>>>> the subject line doesn't excuse its lack of suitability.
>>>
>>> You're right, of course, but would it have hurt so very much to point
>>> the OP towards comp.programming?
>>
>> An oversight on my part.  Thank you for chiming in.
>
> His questions were tailor-made for comp.programming, but it turns out
> he's just another toy-thrower, so it matters not.

Perhaps not, but even so it was an oversight on my part not
to suggest comp.programming, and I thank you for reminding
me of that.

[toc] | [prev] | [next] | [standalone]

#391442

On 3/20/2025 2:38 PM, Tim Rentsch wrote:


> This posting is not appropriate for comp.lang.c.  Putting "OT" in
> the subject line doesn't excuse its lack of suitability.


Aren't you too old to be a net-nanny?

[toc] | [prev] | [next] | [standalone]

#391452

DFS <nospam@dfs.com> writes:

> On 3/20/2025 2:38 PM, Tim Rentsch wrote:
>
>
>> This posting is not appropriate for comp.lang.c.  Putting "OT" in
>> the subject line doesn't excuse its lack of suitability.
>
> Aren't you too old to be a net-nanny?

I see now why you are having difficulties doing these
simple programming exercises.

[toc] | [prev] | [next] | [standalone]

#391455

On 3/20/2025 7:52 PM, Tim Rentsch wrote:
> DFS <nospam@dfs.com> writes:
> 
>> On 3/20/2025 2:38 PM, Tim Rentsch wrote:
>>
>>
>>> This posting is not appropriate for comp.lang.c.  Putting "OT" in
>>> the subject line doesn't excuse its lack of suitability.
>>
>> Aren't you too old to be a net-nanny?
> 
> I see now why you are having difficulties doing these
> simple programming exercises.

asshole

[toc] | [prev] | [next] | [standalone]

#391462

DFS <nospam@dfs.com> writes:
> On 3/20/2025 7:52 PM, Tim Rentsch wrote:
>> DFS <nospam@dfs.com> writes:
>>> On 3/20/2025 2:38 PM, Tim Rentsch wrote:
>>>> This posting is not appropriate for comp.lang.c.  Putting "OT" in
>>>> the subject line doesn't excuse its lack of suitability.
>>>
>>> Aren't you too old to be a net-nanny?
>> I see now why you are having difficulties doing these
>> simple programming exercises.
>
> asshole

Don't make me stop this car.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#391483

On 3/20/2025 6:49 PM, Keith Thompson wrote:
> DFS <nospam@dfs.com> writes:
>> On 3/20/2025 7:52 PM, Tim Rentsch wrote:
>>> DFS <nospam@dfs.com> writes:
>>>> On 3/20/2025 2:38 PM, Tim Rentsch wrote:
>>>>> This posting is not appropriate for comp.lang.c.  Putting "OT" in
>>>>> the subject line doesn't excuse its lack of suitability.
>>>>
>>>> Aren't you too old to be a net-nanny?
>>> I see now why you are having difficulties doing these
>>> simple programming exercises.
>>
>> asshole
> 
> Don't make me stop this car.
> 

Yikes!

[toc] | [prev] | [next] | [standalone]

#391457

On 3/20/2025 7:52 PM, Tim Rentsch wrote:
> DFS <nospam@dfs.com> writes:
> 
>> On 3/20/2025 2:38 PM, Tim Rentsch wrote:
>>
>>
>>> This posting is not appropriate for comp.lang.c.  Putting "OT" in
>>> the subject line doesn't excuse its lack of suitability.
>>
>> Aren't you too old to be a net-nanny?
> 
> I see now why you are having difficulties doing these
> simple programming exercises.


Also, net-nanny asshole, except for one exercise (Two Knights) I haven't 
had ANY difficulty whatsoever with logic or solving them.  Just a few 
niggles with the insane C language and datatypes/sizes.

https://imgur.com/AiRC4kX


GFIA

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web