Click here to Skip to main content
13,793,288 members
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

3.9K views
82 downloads
4 bookmarked
Posted 19 Nov 2018
Licenced CPOL

Array-less Numerical Spiral Pattern

, 19 Nov 2018
Rate this:
Please Sign up or sign in to vote.
How to generate a spiral numerical pattern without using arrays

The spiral numeric pattern

Picture 0 - The dimension 10 spiral pattern on the console screen

Introduction

The program comes from this question in the QA: Make pattern program in C#.

While the straightforward (and intuitive) solution uses an array to keep track of filled positions, the one presented here is array-less, achieving O(1), instead of O(N^2) space complexity.

The program source is already available on the linked page, here I am going to show the 'train of thought' leading to the algorithm.

The Idea

In order to provide an array-less solution, it is necessary to relate every number to its position on the screen, that is to find the mapping:

(x,y) -> n

where:

  • (x,y) is the coordinate, in a 'suitable' coordinate system, of the number in the pattern.
  • n is the number itself.

Let's goto the details...

The Problem

Given a dimension (for instance 5), produce a spiral pattern, like the one shown in the following picture, on the console.

Dimension 5 spiral pattern

Picture 1 - Dimension 5 spiral pattern

The Backward Problem

Consider now the following 'backward' problem:

Dimension 5 backward spiral pattern

Picture 2 - Dimension 5 backward spiral pattern

It is, of course, pretty equivalent: solving the backward problem effectively solves the original one.

The Coordinate System

A 'suitable' (i.e., convenient) coordinate system is shown in pictures 3 and 4.

The coordinate system

Picture 3 - The suitable coordinate system

The coordinate system applied to odd and even dimensions

Picture 4 - The coordinate system applied to odd (on the left) and even (on the right) pattern dimensions

Such system is convenient because it highlights the symmetry of the system and applies nicely to both odd and even pattern dimensions.

It is worth noting the positions (blocks) of the numbers have:

  • Even coordinates .., -2, 0, 2, .. in odd-dimensions patterns (see the left part of picture 4)
  • Odd coordinates .., -3, -1, 1, 3, .. in even-dimensions patterns (see the right part of picture 4)

The distance

In such a coordinate, a useful quantity is the distance, defined this way:

d(x,y) = max(abs(x), abs(y))

So that, for instance:

  • d(-3, 5) = 5
  • d( 2, 2) = 2
  • d( 2,-5) = 5

The Algorithm

Now, back to the backward algorithm (pardon the pun), let's try, for example, to find out how to assign the number 18 to position (4,-2).

The solution is counting the blocks up to the chosen coordinate, starting from the center, following the backward pattern.

Picture 5 shows clearly that there are two contributions:

  • The inner square (yellow blocks)
  • The partial ring (orange blocks)

Computing the inner square contribution is trivial: (D-1)^2 blocks (where D = d(4,-2) = 4 is the distance).

Contributions to position (4,-2)

Picture 5 - Contributions to the number at positions (4,-2)

Contributions to position, odd and even dimension cases

Picture 6 - Inner square and partial ring contributions, both in odd and even dimension patterns

The partial ring contribution is more difficult. There can be four cases, depending on the position (see pictures 7,8):

  • Case A: 'somewhere at the bottom'
  • Case B: 'somewhere at the top'
  • Case C: 'somewhere on the left'
  • Case D: 'somewhere on the right'

Cases A,B

Picture 7 - Partial ring contributions, cases A, B

Cases C,D

Picture 7 - Partial ring contributions, cases C, D

The formula for such cases are shown in the following snippet:

public static int ring_contribution(int d, int x, int y)
{
  if (y == -d)
    return (d - 1) + (d + x) / 2; // Case A, somewhere in the bottom
  else if (y == d)
    return (d - 1) + 2 * d + (d - x) / 2; // Case B, somewhere in the top
  else if (x == -d)
    return (d - y) / 2 - 1; // Case C, somewhere in the left
  else
    return 2 * d + (d + y) / 2 - 1; // Case D, somewhere in the right
}

Adding the inner square and the partial ring contributions gives the expected result for the backward problem and, in turn, for the original one.

Points of Interest

Not useful a bit, I believe. Beating (again) the dead horse was some fun for me, though.

History

  • 19th November, 2018 - First release

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

CPallini
Software Developer (Senior) AEM S.p.A.
Italy Italy




Debugging? Klingons do not debug. Our software does not coddle the weak. Bugs are good for building character in the user.
-- The Klingon programmer



Beelzebub for his friends [^].





You may also be interested in...

Comments and Discussions

 
QuestionI completed this pattern successfully 1 month back Pin
Member 1352451820-Nov-18 19:23
memberMember 1352451820-Nov-18 19:23 
QuestionIronic, I was just looking up an algorithm for this a couple weeks ago Pin
Marc Clifton20-Nov-18 5:43
protectorMarc Clifton20-Nov-18 5:43 
AnswerRe: Ironic, I was just looking up an algorithm for this a couple weeks ago Pin
CPallini20-Nov-18 6:18
mvpCPallini20-Nov-18 6:18 
GeneralMy vote of 5 Pin
Сергій Ярошко19-Nov-18 21:38
professionalСергій Ярошко19-Nov-18 21:38 
GeneralRe: My vote of 5 Pin
CPallini20-Nov-18 4:28
mvpCPallini20-Nov-18 4:28 
GeneralRe: My vote of 5 Pin
Сергій Ярошко20-Nov-18 5:52
professionalСергій Ярошко20-Nov-18 5:52 
QuestionImages not seen Pin
Amarnath S19-Nov-18 21:03
professionalAmarnath S19-Nov-18 21:03 
AnswerRe: Images not seen Pin
Сергій Ярошко19-Nov-18 21:34
professionalСергій Ярошко19-Nov-18 21:34 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web01 | 2.8.181207.3 | Last Updated 19 Nov 2018
Article Copyright 2018 by CPallini
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid