Grid Balancing Algo Help

[spudw2k]

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.

expandcollapse popup

#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

 

[UEZ]

Why is for 18 not:

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

?

[spudw2k]

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 January 21, 2016 by spudw2k

[UEZ]

Then what about this 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 January 21, 2016 by UEZ
Little update

[spudw2k]

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 January 24, 2016 by spudw2k