# Grid Balancing Algo Help

Go to solution Solved by UEZ,

## Recommended Posts

Anyone looking for an algorithm challenge?  I have a function I am building to convert an Integer into a grid/array.  What the function does is create an array sized to the nearest square/rectangle of the input Integer.  What I am trying to do is "balance" the rows as much as possible.  I think by analyzing the

My demo script iterates from 0 to 100.  You can see the normal Top-Left to Bottom-Right ordering that is occurring.  Instead of a "linear" fill (for lack of a better term/desc), I'm looking to "balance/evenly distribute entities" amongst  each row as much as possible.  See the attached images for an example of what I'm essentially looking to achieve.

```#include <Array.au3>

For \$iX = 0 to 100
_IntToGrid(\$iX)
Next

Func _IntToGrid(\$iInput)
;Ensure Input is Number
Local \$iNumber = Number(\$iInput)
If \$iNumber <= 0 Then Return 0
;Vars
Local \$iCols = 0
Local \$iRows = 0
Local \$bPerfect = False
;Collect Square Root of Input
\$iSqrt = Sqrt(\$iNumber)
\$iSqrtFloor = Floor(\$iSqrt)
Select
Case \$iNumber <= 2  ;If Input <=2 Then make 1 Row, X Col
\$iRows = 1
\$iCols = \$iNumber
Case \$iSqrt == \$iSqrtFloor  ;If Input is Square Then make "square" Grid
\$iRows = \$iSqrt
\$iCols = \$iRows
EndSelect

If Not \$iRows Then  ;If Not easy grid Then work it out
Local \$iNextSquare = 0
Local \$iNextRect = 0
Local \$iSquareCounter = 1
Do
;Calculate Next Square and/or Next Rect >= Input
\$iSquareCounter += 1
\$iNextSquare = \$iSquareCounter ^ 2
\$iNextRect = \$iNextSquare + \$iSquareCounter
\$iSqrt = Sqrt(\$iNextSquare)
Until (\$iNextSquare >= \$iNumber) Or (\$iNextRect >= \$iNumber)
If \$iNumber < \$iNextSquare Then
\$iCols = \$iSqrt
\$iRows = \$iSqrt
ElseIf \$iNumber <= \$iNextRect Then
\$iCols = (\$iNextRect/\$iSqrt)
\$iRows = \$iSqrt
If \$iNumber == \$iNextRect Then \$bPerfect = True
EndIf
Else
\$bPerfect = True
;ConsoleWrite("Easy Square" & @CRLF)
EndIf

Local \$aGrid[\$iRows][\$iCols]
Local \$iIdx = 0
Local \$bInputIsEven = (Mod(\$iNumber,2) ? False : True)
Local \$bRowsAreEven = (Mod(\$iRows,2) ? False : True)

For \$iY = 0 to \$iRows-1
For \$iX = 0 to \$iCols-1
;Select
;   Case \$bPerfect = True
\$iIdx += 1
If \$iIdx > \$iNumber Then ExitLoop

\$aGrid[\$iY][\$iX] = \$iIdx

;Case \$bI

;EndSelect
Next
If \$iIdx > \$iNumber Then ExitLoop
Next

_ArrayDisplay(\$aGrid, \$iNumber, "", 32 + 4)
EndFunc```

Spoiler

Misc Code Snippets:
Projects: SubnetCalc
Cool Stuff:

##### Share on other sites

Why is for 18 not:

```1  2  3  4
5  6  7  8  9
10 11 12 13 14
15 16 17 18```

?

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

##### Share on other sites

23 minutes ago, UEZ said:

Why is for 18 not:

```1  2  3  4
5  6  7  8  9
10 11 12 13 14
15 16 17 18```

?

No reason...why should it be?

edit: I see.  My examples for 7 and 10 have the "heavy" row(s) in the center, so I guess you assumed that was the pattern I was looking for.  I just showed it that way to show the nice "balanced" look I am looking for.

Really I guess I don't care in what fashion the rows are spread, as long as I can produce a predictable pattern.

18 could be

```1   2   3   4   5
6   7   8   9   10
11  12  13  14
15  16  17  18```

or even.

```1   2   3   4
5   6   7   8   9
10  11  12  13
14  15  16  17  18```

I'd prefer a more "balanced look" (like your example or my two with the alternating row length), but some numbers just won't "look pretty"...for example 17 or 19

```1   2   3   4   5
6   7   8   9
10  11  12  13
14  15  16  17

1   2   3   4
5   6   7   8   9
10  11  12  13
14  15  16  17

1   2   3   4   5
6   7   8   9   10
11  12  13  14  15
16  17  18  19

1   2   3   4   5
6   7   8   9
10  11  12  13  14
15  16  17  18  19

etc..```

Edited by spudw2k
Spoiler

Misc Code Snippets:
Projects: SubnetCalc
Cool Stuff:

##### Share on other sites

• Solution

```#include <Array.au3>

\$aResult = GridBalance(17)
_ArrayDisplay(\$aResult)

Func GridBalance(\$iNumber)
Local \$iSquare = Ceiling(Sqrt(\$iNumber))
Local \$aGrid[Ceiling(\$iNumber / \$iSquare)][\$iSquare], \$iX, \$iY, \$iCounter = 1
Local \$iRest = UBound(\$aGrid) * UBound(\$aGrid, 2) - \$iNumber, \$iZ = \$iRest * 2
Local \$iLow = Floor(UBound(\$aGrid) / 2) - Floor((UBound(\$aGrid) - \$iRest) / 2)
Local \$iHigh = Floor(UBound(\$aGrid) / 2) + Ceiling((UBound(\$aGrid) - \$iRest) / 2)
If (\$iNumber - \$iRest) + (\$iHigh - \$iLow) <> \$iNumber And \$iSquare^2 <> \$iNumber Then \$iLow += 1

For \$iY = 0 To UBound(\$aGrid) - 1
Switch \$iY
Case \$iLow To \$iHigh
For \$iX = 0 To UBound(\$aGrid, 2) - 1
\$aGrid[\$iY][\$iX] = \$iCounter
\$iCounter += 1
If \$iCounter = \$iNumber + 1 Then ExitLoop 2
Next
Case Else
For \$iX = 0 To UBound(\$aGrid, 2) - 2
\$aGrid[\$iY][\$iX] = \$iCounter
\$iCounter += 1
If \$iCounter = \$iNumber + 1 Then ExitLoop 2
Next
EndSwitch
Next
Return \$aGrid
EndFunc```

Edit: didn't work for 87, 111.  Made several test and it seems to be working now.

Edited by UEZ
Little update

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

##### Share on other sites

Well done.  That's pretty neat.  It produces a neat pattern and balanced look.  It seems to not work for most "full rectangular" arrays, (2, 6, 12,)

I tweaked the iLow and iHigh variables and resolved the missing numbers issue.  it also "centered" the distribution better I think.

```#include <Array.au3>

Func GridBalance(\$iNumber)
Local \$iSquare = Ceiling(Sqrt(\$iNumber))
Local \$aGrid[Ceiling(\$iNumber / \$iSquare)][\$iSquare], \$iX, \$iY, \$iCounter = 1
Local \$iRest = UBound(\$aGrid) * UBound(\$aGrid, 2) - \$iNumber
Local \$iLow = Floor(UBound(\$aGrid) / 2) - (Floor((UBound(\$aGrid) - \$iRest) / 2) + 1)
Local \$iHigh = Floor(UBound(\$aGrid) / 2) + (Ceiling((UBound(\$aGrid) - \$iRest) / 2) - 1)
If (\$iNumber - \$iRest) + (\$iHigh - \$iLow) <> \$iNumber Or \$iSquare ^ 2 <> \$iNumber Then \$iLow += 1

For \$iY = 0 To UBound(\$aGrid) - 1
Switch \$iY
Case \$iLow To \$iHigh
For \$iX = 0 To UBound(\$aGrid, 2) - 1
\$aGrid[\$iY][\$iX] = \$iCounter
\$iCounter += 1
If \$iCounter = \$iNumber + 1 Then ExitLoop 2
Next
Case Else
For \$iX = 0 To UBound(\$aGrid, 2) - 2
\$aGrid[\$iY][\$iX] = \$iCounter
\$iCounter += 1
If \$iCounter = \$iNumber + 1 Then ExitLoop 2
Next
EndSwitch
Next

Return \$aGrid
EndFunc   ;==>GridBalance```

There is an interesting behavior, I noticed though (with this ^ code).   Arrays with Even rows (starting at 4 rows) produce an unbalanced pattern every square or rect.    It seems to occur when the input number = NearestFullSquareOrRect - (EvenRowCount/2), i.e. 14 = 16 - ( 4 / 2 ), or 18 = 20 - ( 4 / 2 ), or 33 = 36 - ( 6 / 2 ).

It's a little hard for me to explain eloquently in text (or speech for that matter).  If you do a loop from 12 to >=20, you'll see what I mean.  Either way...this Is good stuff!

edit:  Changing from an And to an Or seemed to do the trick.

```If (\$iNumber - \$iRest) + (\$iHigh - \$iLow) <> \$iNumber And \$iSquare ^ 2 <> \$iNumber Then \$iLow += 1
If (\$iNumber - \$iRest) + (\$iHigh - \$iLow) <> \$iNumber Or \$iSquare ^ 2 <> \$iNumber Then \$iLow += 1```

Sorry for the delay in my response BTW.  I went out of town right after I responded the first time.

Edited by spudw2k
Spoiler

Misc Code Snippets:
Projects: SubnetCalc
Cool Stuff:

## Create an account

Register a new account

• ### Recently Browsing   0 members

×

• Wiki

• Back

• #### Beta

• Git
• FAQ
×
• Create New...