Programming contest: Distributing N items into a 3D bar with size constraints ;)

[Skybuck Flying]

The objective: Distribute N items into a 3D bar with size constraints.

N is given.
MaxWidth is given. (constraint)
MaxHeight is given. (constraint)
MaxDepth is given. (constraint)
Width is the question.
Height is the question.
Depth is the question.

Items are 1x1x1=1 in size.

Objective is to calculate the optimal constrained width, constrained height
and constrained depth so that all N items fit into the 3D bar with the least
ammount of space wasted.

For the competition the value's are: N can range from 1 to 100 million.

MaxWidth can range from 1 to 4096.
MaxHeight can range from 1 to 4096.
MaxDepth can range from 1 to 4096.

Entries will be juried as follows:

1. All entries will be examined for "overall least ammount of space wasted
for all N is 1 to 100 million". (If possible by time/processing
constraint... a few hours of cpu time might be available for full N test ;))
(If processing time becomes to large all entries will be examined the same
for example N is 1 to 100000.)

2. Speed/number of operations is important too... In case multiple entries
produce optimal answers then the entrie which executes the least ammount of
loops/instructions wins ! ;)

All in all quite an interesting challenge/competition I think ! ;)

Bye,
Skybuck.

[Skybuck Flying]

"Skybuck Flying" <IntoTh...@hotmail.com> wrote in message
news:bf71b$4b513bac$d53371df$19...@cache4.tilbu1.nb.home.nl...

Hello People,

Here is my first contribution and entry to the contest ;) :)

It's the naive/brute force algorithm.

However I am going to "expand" the contest with further requirements:

"Find the 3D bar with the least ammount of wasted space which looks the most
like a CUBE".

(Since multiple solutions could contain wasted space zero, but not all might
look like a cube).

So a ratio is necessary as well. I am not yet sure how to calculate a "cube
ratio".

It's probably something like: width/height/depth ? or maybe: width/cube
with, height/cube height, depth /cube depth.

Where cube height=width=depth is the max(width,height,depth).

For now here is the brute force algorithm and code in Delphi, which does not
yet contain the searching for "cube ratio".

I like to provide the naive/brute force algorithm/pseudo code now to give
you an idea what it's all about ;) and to show you that it can indeed be a
"computational expensive task" for now until better algorithms are
given/found ! ;) :)

// *** BEGIN OF PROGRAM 0.01 ***
program TestProgram;

{$APPTYPE CONSOLE}

{

Distributing N items into a 3D bar with size constraints.

version 0.01 created on 16 january 2010 by Skybuck Flying.

To investigate if it's truely a computational intensive problem I decided
to first implement the "naive/brute force" algorithm.

And indeed it does cost some seconds before it finds a good solution for the
current settings.

However there is a new little problem which I am not yet sure how to solve

Take this solution for example:

vSolution: 8
vBestSpaceWasted: 0
vBestWidth: 43
vBestHeight: 565
vBestDepth: 3683

The algorithm could stop when SpaceWasted becomes zero.

However the solution doesn't really look that good...

The width is kinda small... the height is kinda small too... and the depth
is insanely large compared to the rest ! ;)

Maybe the competition needs to be extended with a "ratio"...

The 3D bar which fits/resembles a CUBE the best... with the least ammount of
waste space... let's assume zero for now... is the winner.

So new algorithm requirements:

Find the minimum ammount of wasted space, for example zero.

Then find the best fitting 3D bar which looks the most like a cube ! ;)

}

uses
SysUtils;

var
mItems : integer;

mMaxWidth : integer;
mMaxHeight : integer;
mMaxDepth : integer;

procedure Main;
var
mWidth : integer;
mHeight : integer;
mDepth : integer;

vArea : int64;
vSpaceWasted : int64;

vBestSpaceWasted : int64;
vBestWidth : integer;
vBestDepth : integer;
vBestHeight : integer;

vSolution : int64;
begin
writeln('program started');

mItems := (512 * 1024 * 1024) div 6;
mMaxWidth := 4096;
mMaxHeight := 4096;
mMaxDepth := 4096;

// start with the worst values
vBestSpaceWasted := mMaxWidth;
vBestSpaceWasted := vBestSpaceWasted * mMaxHeight;
vBestSpaceWasted := vBestSpaceWasted * mMaxDepth;
vBestSpaceWasted := vBestSpaceWasted - mItems;
// vBestWidth := mMaxWidth;
// vBestHeight := mMaxHeight;
// vBestDepth := mMaxDepth;

vSolution := 0;

// start searching for better 3D bars with naive/brute force algorithm:
for mWidth := 0 to mMaxWidth-1 do
begin
for mHeight := 0 to mMaxHeight-1 do
begin
for mDepth := 0 to mMaxDepth-1 do
begin
vArea := mWidth;
vArea := vArea * mHeight;
vArea := vArea * mDepth;

// only examine valid 3d bars which can hold all items.
if vArea >= mItems then
begin
vSpaceWasted := vArea - mItems;

if vSpaceWasted < vBestSpaceWasted then
begin
vBestWidth := mWidth;
vBestHeight := mHeight;
vBestDepth := mDepth;
vBestSpaceWasted := vSpaceWasted;

vSolution := vSolution + 1;

writeln( 'vSolution: ', vSolution );
writeln( 'vBestSpaceWasted: ', vBestSpaceWasted );
writeln( 'vBestWidth: ', vBestWidth );
writeln( 'vBestHeight: ', vBestHeight );
writeln( 'vBestDepth: ', vBestDepth );
end;
end;
end;
end;
end;

writeln('program finished');
end;

{

Results after a few seconds of running:

vSolution: 8
vBestSpaceWasted: 0
vBestWidth: 43
vBestHeight: 565
vBestDepth: 3683

}

begin
try
Main;
except
on E:Exception do
Writeln(E.Classname, ': ', E.Message);
end;
ReadLn;
end.

// *** END OF PROGRAM 0.01 ***

Bye,
Skybuck.

[A.L.]

On Sat, 16 Jan 2010 05:33:11 +0100, "Skybuck Flying"
<IntoTh...@hotmail.com> wrote:

>"Skybuck Flying" <IntoTh...@hotmail.com> wrote in message
>news:bf71b$4b513bac$d53371df$19...@cache4.tilbu1.nb.home.nl...
>> The objective: Distribute N items into a 3D bar with size constraints.
>>

>alt.comp.lang.borland-delphi,alt.math,comp.graphics.algorithms,comp.graphics.api.opengl,sci.op-research

You forgot to post to alt.sex also

A.L.

[Skybuck Flying]

Al has been banned for "usenet abuse".

So please don't bother replieing anymore Al ;)

Bye,
Skybuck.

[Skybuck Flying]

Hello,

Here is version 0.02 of the program which implements the ratio idea.

There is a further possibly logical problem with this idea.

If there is only one truely optimal solution for the waste, and this
solution has a very bad ratio then that kinda sucks...

So maybe it's better for "opengl performance reasons" to find a good balance
between waste and performance.
(Since this algorithm will be used for opengl 3d textures ;))

The assumption (for now) is that more cube like textures give better
performance... while whacky forms would be worse...

So this "relaxation" could be achieved by implementing something like an
"acceptable waste percentage" or so...

This might be tried in a future version 0.03.

For now here is version 0.02:

// *** BEGIN OF PROGRAM 0.02 ***

program TestProgram;

{$APPTYPE CONSOLE}

{

So new algorithm requirements:

}

{

version 0.02 created on 16 january 2010 by Skybuck Flying.

Version 0.02 will accept duplicate best space wasted solutions but will
try to find the best "cube-like-ratio" dimensions.

For I need to figure out how to tell if a bar is more or less like a cube !
;)

So idea's: Width/Height/Depth

10/10/10 = 0.1

12/10/10 = 0.12
11/10/10 = 0.11

0.11 is closer to 0.1 so it's a bitter fit me thinks ;)
1/100/10 = 0.001
10/10/1 = 1
10/100/1 = 0.1 <- bad situation.

Or:
Width / CubeSize
Height / CubeSize
Depth / CubeSize

Then somehow figure it out... maybe a single ratio as above is better ;) :)
It also fits more closy the width/height ratio method ! ;) :)
Above a bad situation is displayed.. so it seems that not such a good
method...
Something better is needed... maybe the second method is better ;)

Anyway I tried to find a mathematical approach to "cubeness" but it seems to
complex.
Furthermore those mathmetical techniques seem to try and stuff the
measurement into
one variable which for us as programmers is not really needed since we can
use if
statements to test the worst one... so it seems the "math" guys are trying
to hard ;)

So I decided to roll my own technique which is technique 2.

The worst ratio of width or height or depth is taken.

This has been implemented in version 0.02

However there could be a new logical problem.

Let's suppose the a certain solution is optimal meaning wasted space is
zero.

Suppose this is the only solution... and it has a very bad ratio... then
that kinda sux... no better ratio will be find.

So that's where the logical problem begins... we might have to "relax" the
rules
a little bit... "some waste" might be acceptable to encourage better
ratio's.

Alternatively I was thinking about trying to use some sort of "waste ratio
vs cubeness ratio" or so.
But I guess that's too whacky and won't work well...

What could work as a "percentage of acceptable waste"... and to keep looking
for better
ratio's among those solutions that qualify the "percentage of acceptable
waste".

This idea will be tried out in a future version 0.03.

For now here is version 0.02 ;) :)

}

uses
SysUtils;

var
mItems : integer;

mMaxWidth : integer;
mMaxHeight : integer;
mMaxDepth : integer;

procedure Main;
var
mWidth : integer;
mHeight : integer;
mDepth : integer;

vArea : int64;
vSpaceWasted : int64;

vBestSpaceWasted : int64;
vBestWidth : integer;
vBestDepth : integer;
vBestHeight : integer;

vBestWorstRatioDifference : double;

vMainSolution : int64;
vSubSolution : int64;

vMaxCubeSize : integer;

vWidthRatio : double;
vHeightRatio : double;
vDepthRatio : double;

vWidthRatioDifference : double;
vHeightRatioDifference : double;
vDepthRatioDifference : double;

vWorstRatioDifference : double;

begin
writeln('program started');

mItems := (512 * 1024 * 1024) div 6;
mMaxWidth := 4096;
mMaxHeight := 4096;
mMaxDepth := 4096;

// start with the worst values
vBestSpaceWasted := mMaxWidth;
vBestSpaceWasted := vBestSpaceWasted * mMaxHeight;
vBestSpaceWasted := vBestSpaceWasted * mMaxDepth;
vBestSpaceWasted := vBestSpaceWasted - mItems;

vBestWidth := mMaxWidth;
vBestHeight := mMaxHeight;
vBestDepth := mMaxDepth;
vBestWorstRatioDifference := 1.0;

vMainSolution := 0;
vSubSolution := 0;

// start searching for better 3D bars with naive/brute force algorithm:
for mWidth := 0 to mMaxWidth-1 do
begin
for mHeight := 0 to mMaxHeight-1 do
begin
for mDepth := 0 to mMaxDepth-1 do
begin
vArea := mWidth;
vArea := vArea * mHeight;
vArea := vArea * mDepth;

// only examine valid 3d bars which can hold all items.
if vArea >= mItems then
begin
vSpaceWasted := vArea - mItems;

if vSpaceWasted < vBestSpaceWasted then
begin
vBestWidth := mWidth;
vBestHeight := mHeight;
vBestDepth := mDepth;
vBestSpaceWasted := vSpaceWasted;

// determine worst ratio difference.
vMaxCubeSize := vBestWidth;

if vBestHeight > vMaxCubeSize then vMaxCubeSize := vBestHeight;
if vBestDepth > vMaxCubeSize then vMaxCubeSize := vBestDepth;

vWidthRatio := vBestWidth / vMaxCubeSize;
vHeightRatio := vBestHeight / vMaxCubeSize;
vDepthRatio := vBestDepth / vMaxCubeSize;

// cube ratio is 1.0, calculate differences in ratio's.
vWidthRatioDifference := abs( 1.0 - vWidthRatio );
vHeightRatioDifference := abs( 1.0 - vHeightRatio );
vDepthRatioDifference := abs( 1.0 - vDepthRatio );

vWorstRatioDifference := vWidthRatioDifference;
if vHeightRatioDifference > vWorstRatioDifference then
vWorstRatioDifference := vHeightRatioDifference;
if vDepthRatioDifference > vWorstRatioDifference then
vWorstRatioDifference := vDepthRatioDifference;

vBestWorstRatioDifference := vWorstRatioDifference;

vMainSolution := vMainSolution + 1;
vSubSolution := 1;

writeln( 'vMainSolution: ', vMainSolution );
writeln( 'vSubSolution: ', vSubSolution );

writeln( 'vBestSpaceWasted: ', vBestSpaceWasted );
writeln( 'vBestWidth: ', vBestWidth );
writeln( 'vBestHeight: ', vBestHeight );
writeln( 'vBestDepth: ', vBestDepth );

writeln( 'vBestWorstRatioDifference: ',
vBestWorstRatioDifference:1:23 );
writeln;
end else
// else if space wasted is equal then try to determine the better ratio
(closer to a cube)
if vSpaceWasted = vBestSpaceWasted then
begin
// determine worst ratio difference.
vMaxCubeSize := vBestWidth;

if vBestHeight > vMaxCubeSize then vMaxCubeSize := vBestHeight;
if vBestDepth > vMaxCubeSize then vMaxCubeSize := vBestDepth;

vWidthRatio := vBestWidth / vMaxCubeSize;
vHeightRatio := vBestHeight / vMaxCubeSize;
vDepthRatio := vBestDepth / vMaxCubeSize;

// cube ratio is 1.0, calculate differences in ratio's.
vWidthRatioDifference := abs( 1.0 - vWidthRatio );
vHeightRatioDifference := abs( 1.0 - vHeightRatio );
vDepthRatioDifference := abs( 1.0 - vDepthRatio );

vWorstRatioDifference := vWidthRatioDifference;
if vHeightRatioDifference > vWorstRatioDifference then
vWorstRatioDifference := vHeightRatioDifference;
if vDepthRatioDifference > vWorstRatioDifference then
vWorstRatioDifference := vDepthRatioDifference;

if vWorstRatioDifference < vBestWorstRatioDifference then

begin
vBestWidth := mWidth;
vBestHeight := mHeight;
vBestDepth := mDepth;
vBestSpaceWasted := vSpaceWasted;

vBestWorstRatioDifference := vWorstRatioDifference;

vSubSolution := vSubSolution + 1;

writeln( 'vMainSolution: ', vMainSolution );
writeln( 'vSubSolution: ', vSubSolution );

writeln( 'vBestSpaceWasted: ', vBestSpaceWasted );
writeln( 'vBestWidth: ', vBestWidth );
writeln( 'vBestHeight: ', vBestHeight );
writeln( 'vBestDepth: ', vBestDepth );

writeln( 'vBestWorstRatioDifference: ',
vBestWorstRatioDifference:1:23 );
writeln;

end;
end;
end;
end;
end;
end;

writeln('program finished');
end;

{

Results after a few seconds of running:

vMainSolution: 7
vSubSolution: 1
vBestSpaceWasted: 3
vBestWidth: 8
vBestHeight: 2761
vBestDepth: 4051
vBestWorstRatioDifference: 0.99802517896815601000000

vMainSolution: 8
vSubSolution: 1

vBestSpaceWasted: 0
vBestWidth: 43
vBestHeight: 565
vBestDepth: 3683

vBestWorstRatioDifference: 0.98832473527016018000000

}

begin
try
Main;
except
on E:Exception do
Writeln(E.Classname, ': ', E.Message);
end;
ReadLn;
end.

// *** END OF PROGRAM 0.02 ***

Bye,
Skybuck.

[Skybuck Flying]

There was a little bug in the version 0.02 which affected the sub solution.

The ratio's for sub solutions where being calculated on "best" variables
instead of "active/loop" variables.

Code has been fixed so that never happens again ;)

The results are now a little bit better... however work on version 0.03 with
"acceptable waste" idea will continue ! =D

After that maybe I try my "dynamic looping construct" idea for faster
looping, this algorithm has not been described in any delphi thread yet...
but it was described on some other newsgroup ;) google is your friend if you
interested in it.. or maybe later if it works then maybe I'll post it here
as my entry :)

So you can expect version 0.03, and maybe version 0.04 for the competition
;) :)

I doubt anybody will enter, especially after version 0.04... but one never
knows does one ! =D

Maybe me owning big time ! LOL. It's up to you to prove otherwise ;) :)

// *** Begin of Program 0.02 bug fixed ***

program TestProgram;

{$APPTYPE CONSOLE}

{

So new algorithm requirements:

}

{

So idea's: Width/Height/Depth

10/10/10 = 0.1

Little bug fixed in version 0.02... results now a bit better ;)

}

uses
SysUtils;

var
mItems : integer;

vArea : int64;
vSpaceWasted : int64;

vMainSolution : int64;
vSubSolution : int64;

vMaxCubeSize : integer;

// vBestWidth := mMaxWidth;
// vBestHeight := mMaxHeight;

// vBestDepth := mMaxDepth;
vBestWorstRatioDifference := 1.0;

vMainSolution := 0;
vSubSolution := 0;

// start searching for better 3D bars with naive/brute force algorithm:
for mWidth := 0 to mMaxWidth-1 do
begin
for mHeight := 0 to mMaxHeight-1 do
begin
for mDepth := 0 to mMaxDepth-1 do
begin
vArea := mWidth;
vArea := vArea * mHeight;
vArea := vArea * mDepth;

// only examine valid 3d bars which can hold all items.
if vArea >= mItems then
begin
vSpaceWasted := vArea - mItems;

if vSpaceWasted < vBestSpaceWasted then
begin
vBestWidth := mWidth;
vBestHeight := mHeight;
vBestDepth := mDepth;
vBestSpaceWasted := vSpaceWasted;

// determine worst ratio difference.

vMaxCubeSize := mWidth;

if mHeight > vMaxCubeSize then vMaxCubeSize := mHeight;
if mDepth > vMaxCubeSize then vMaxCubeSize := mDepth;

vWidthRatio := mWidth / vMaxCubeSize;
vHeightRatio := mHeight / vMaxCubeSize;
vDepthRatio := mDepth / vMaxCubeSize;

vBestWorstRatioDifference := vWorstRatioDifference;

vMaxCubeSize := mWidth;

if mHeight > vMaxCubeSize then vMaxCubeSize := mHeight;
if mDepth > vMaxCubeSize then vMaxCubeSize := mDepth;

vWidthRatio := mWidth / vMaxCubeSize;
vHeightRatio := mHeight / vMaxCubeSize;
vDepthRatio := mDepth / vMaxCubeSize;

{

vMainSolution: 8
vSubSolution: 5
vBestSpaceWasted: 0
vBestWidth: 127
vBestHeight: 565
vBestDepth: 1247
vBestWorstRatioDifference: 0.89815557337610263000000

}

begin
try
Main;
except
on E:Exception do
Writeln(E.Classname, ': ', E.Message);
end;
ReadLn;
end.

// *** End of Program 0.02 bug fixed ***

Bye,
Skybuck.

[Skybuck Flying]

The naive/brute force algorithm/loop construct takes a few minutes to find a
"cube like" solution... which is almost the same as Width=Height=Depth =
Ceil( Items ^ (1/3) ).

It was interesting to see the algorithm in action... apperently in the third
dimension... with a modest ammount of items (N) the number of possibilities
is not that great... for cubeness like priorities... and the solution will
lie very close to the power of 1/3.

So I might as well use that for an estimate/setting, unless ofcourse
different dimensions give different performance but for now I have no clue
about that...

Maybe there is a benchmark out there that tests different 3d texture
dimensions ;) If not then such a tool could be made... Ultimately... maybe
the performance also depends on actual algorithm... but still such a
benchmark could be interesting to spot any weirdness ;)

For now, for what it's worth, here is the waste percentage idea
implemented... (the acceptable waste percentage was 1 MB out of 512 MB so
that's about. So that's almost 0.2 percentage waste. (The code actually uses
a factor (*100 is not done)) So 0.2 percentage is not a lot of room to
diverge from the cubeness ;) :)

// *** Begin of Program 0.03 ***

program TestProgram;

{$APPTYPE CONSOLE}

{

So new algorithm requirements:

}

{

So idea's: Width/Height/Depth

10/10/10 = 0.1

}

{

version 0.03 created on 16 january 2010 by Skybuck Flying.

The rules will be changed a little bit as described in version 0.02
idea's/comments.

The idea is to relaxed the "wasted space" contraint... Previously it would
search for wasted space 0.

This will now be changed to a certain "acceptable waste percentage" to relax
this constraint somewhat... so it starts focussing on better ratio's (cube
like ratio's).

The AcceptableWastePercentage can be custom set...

For now I will simply use mb's as an indication of acceptable waste ammount
and divide it by the mem available
on the card.

This will be the acceptable waste percentange, or it could be custom set for
benchmarking
purposes and jury/evaluation purposes ;)

This versions show that if the "cubeness" priority is desirable then the
number of possibilities
isn't really that great and the solution apperently quickly becomes:

Ceil( Items ^ (1/3) )

This means the competition has become less interesting, the dynamic loop
construct could
still be interesting as well as any other new construct which would even be
simpler ;) :)

None the less it was still interesting to see naive/brute force algorithm in
action ;) :)

}

uses
SysUtils;

var
mItems : integer;

mMaxWidth : integer;
mMaxHeight : integer;
mMaxDepth : integer;

procedure Main;
var
mMemoryAvailable : integer;
mMemoryMaxWaste : integer;

mAcceptableWastePercentage : double;

mWidth : integer;
mHeight : integer;
mDepth : integer;

vArea : int64;

vBestWidth : integer;

vBestDepth : integer;
vBestHeight : integer;
vBestWorstRatioDifference : double;

vSolution : int64;

vMaxCubeSize : integer;

vWidthRatio : double;
vHeightRatio : double;
vDepthRatio : double;

vWidthRatioDifference : double;
vHeightRatioDifference : double;
vDepthRatioDifference : double;

vWorstRatioDifference : double;

vWastePercentage : double;

begin
writeln('program started');

mMemoryAvailable := 512 * 1024 * 1024;
mMemoryMaxWaste := 1024 * 1024;

mAcceptableWastePercentage := mMemoryMaxWaste / mMemoryAvailable;

mItems := mMemoryAvailable div 6; // 6 is instruction length ;)

mMaxWidth := 4096;
mMaxHeight := 4096;
mMaxDepth := 4096;

// start with the worst values

// vBestWidth := mMaxWidth;
// vBestHeight := mMaxHeight;
// vBestDepth := mMaxDepth;
vBestWorstRatioDifference := 1.0;

vSolution := 0;

// start searching for better 3D bars with naive/brute force algorithm:
for mWidth := 0 to mMaxWidth-1 do
begin
for mHeight := 0 to mMaxHeight-1 do
begin
for mDepth := 0 to mMaxDepth-1 do
begin
vArea := mWidth;
vArea := vArea * mHeight;
vArea := vArea * mDepth;

// only examine valid 3d bars which can hold all items.
if vArea >= mItems then
begin

vWastePercentage := (vArea - mItems) / vArea;

// consider all solutions which fall within the acceptable waste
percentage
if vWastePercentage < mAcceptableWastePercentage then

begin
// determine worst ratio difference.
vMaxCubeSize := mWidth;

if mHeight > vMaxCubeSize then vMaxCubeSize := mHeight;
if mDepth > vMaxCubeSize then vMaxCubeSize := mDepth;

vWidthRatio := mWidth / vMaxCubeSize;
vHeightRatio := mHeight / vMaxCubeSize;
vDepthRatio := mDepth / vMaxCubeSize;

// cube ratio is 1.0, calculate differences in ratio's.
vWidthRatioDifference := abs( 1.0 - vWidthRatio );
vHeightRatioDifference := abs( 1.0 - vHeightRatio );
vDepthRatioDifference := abs( 1.0 - vDepthRatio );

vWorstRatioDifference := vWidthRatioDifference;
if vHeightRatioDifference > vWorstRatioDifference then
vWorstRatioDifference := vHeightRatioDifference;
if vDepthRatioDifference > vWorstRatioDifference then
vWorstRatioDifference := vDepthRatioDifference;

// remember the solution with the best worst ratio difference, the
best solution which looks like a cube.

if vWorstRatioDifference < vBestWorstRatioDifference then
begin
vBestWidth := mWidth;
vBestHeight := mHeight;
vBestDepth := mDepth;

vBestWorstRatioDifference := vWorstRatioDifference;

vSolution := vSolution + 1;

writeln( 'vSolution: ', vSolution );

writeln( 'vBestWidth: ', vBestWidth );
writeln( 'vBestHeight: ', vBestHeight );
writeln( 'vBestDepth: ', vBestDepth );
writeln( 'vBestWorstRatioDifference: ',
vBestWorstRatioDifference:1:23 );
writeln;
end;
end;
end;
end;
end;
end;

writeln('program finished');
end;

{

Results after many minutes:

vSolution: 9814
vBestWidth: 447
vBestHeight: 447
vBestDepth: 448
vBestWorstRatioDifference: 0.00223214285714290000000

which almost equals very simply:

Ceil( Items ^ (1/3) )

(Items to the power of one third)

}

begin
try
Main;
except
on E:Exception do
Writeln(E.Classname, ': ', E.Message);
end;
ReadLn;
end.

// *** End of Program 0.03 ****

Bye,
Skybuck.

[Skybuck Flying]

Two little comments added, for the record ! ;):

"Skybuck Flying" <IntoTh...@hotmail.com> wrote in message

news:c7374$4b51677c$d53371df$13...@cache6.tilbu1.nb.home.nl...

// this is actually more of a factor but ok... officialy it should have
been * 100 ;)
// probably doesn't matter ;) but does matter for speed reasons ;)

> mAcceptableWastePercentage := mMemoryMaxWaste / mMemoryAvailable;
>
> mItems := mMemoryAvailable div 6; // 6 is instruction length ;)
> mMaxWidth := 4096;
> mMaxHeight := 4096;
> mMaxDepth := 4096;
>
> // start with the worst values
> // vBestWidth := mMaxWidth;
> // vBestHeight := mMaxHeight;
> // vBestDepth := mMaxDepth;
> vBestWorstRatioDifference := 1.0;
>
> vSolution := 0;
>
> // start searching for better 3D bars with naive/brute force algorithm:
> for mWidth := 0 to mMaxWidth-1 do
> begin
> for mHeight := 0 to mMaxHeight-1 do
> begin
> for mDepth := 0 to mMaxDepth-1 do
> begin
> vArea := mWidth;
> vArea := vArea * mHeight;
> vArea := vArea * mDepth;
>
> // only examine valid 3d bars which can hold all items.
> if vArea >= mItems then
> begin

// this is actually more of a factor but ok... officialy it should have
been * 100 ;)
// probably doesn't matter ;) but does matter for speed reasons ;)

[Skybuck Flying]

This question could not be changed to: "Distributing N items into a Texture
3D" :)

Some googling has learned that width, height, depth values need to be power
of two.

Furthermore 3D textures might be implemented by gpu as "slices" of 2D
textures.

So it would make sense to try and keep the 2d part of it as large as
possible... and then scale this up the Z axis for as far as needed ;)

However such algorithms should be simple to come up with... (and execute
fast, only a few possibilities to test) thus this is left as an exercise to
the reader ! LOL =D

Bye,
Skybuck ;) =D

[Gordon Sande]

On 2010-01-16 01:28:04 -0400, "Skybuck Flying"
<IntoTh...@hotmail.com> said:

Based on observed behavior "Skybuck Flying" is more likely to banned.

[A.L.]

You go to kill file

A.L.

[Skybuck Flying]

"Gordon Sande" <g.s...@worldnet.att.net> wrote in message
news:2010011611332975249-gsande@worldnetattnet...

There is nothing wrong with my behaviour... but yours sucks as well...

I am gonna put you on my ban list as well :P ;) :) :P

Bye,
Skybuck.

[Ruud van Gaal]

Talking extensively to ones self is better left in the loony department.
You sound like a quite disturbed person, get some social life. Really.

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[Rudy Velthuis]

Ruud van Gaal wrote:

> Talking extensively to ones self is better left in the loony
> department. You sound like a quite disturbed person, get some social
> life. Really.

And to whom were you actually talking? I assume you meant Skybuck, but
that is not so clear.

--
Rudy Velthuis http://rvelthuis.de

"Conservatives are not necessarily stupid, but most stupid people
are conservatives" -- John Stuart Mill

[Skybuck Flying]

Welcome to banlist ! ;)

Bye,
Skybuck.

"Ruud van Gaal" <ru...@racer.nl> wrote in message
news:hivq9c$15q3$2...@adenine.netfront.net...

[Ruud van Gaal]

Rudy Velthuis wrote:
> Ruud van Gaal wrote:
>
>> Talking extensively to ones self is better left in the loony
>> department. You sound like a quite disturbed person, get some social
>> life. Really.
>
> And to whom were you actually talking? I assume you meant Skybuck, but
> that is not so clear.

Sorry about that, but who else could it be but... Skybuck. :)

[Skybuck Flying]

"Skybuck Flying" <IntoTh...@hotmail.com> wrote in message

news:ea5be$4b517d6c$d53371df$15...@cache4.tilbu1.nb.home.nl...

> This question could not be changed to: "Distributing N items into a
> Texture 3D" :)
>
> Some googling has learned that width, height, depth values need to be
> power of two.

Then again...

This document is about relaxing this restriction:

http://oss.sgi.com/projects/ogl-sample/registry/ARB/texture_non_power_of_two.txt

And this extension does seem to be supported by my graphics cards.

However I could make an option in my software in case some graphics cards
don't have it... but those probably
so old... they probably can't do certain things but ok...

So I wonder how things will turn out...

This is important to know though... because this determines what it can do
more or less and what the performance will be... hmm ;) :)

Bye,
Skybuck.

[Skybuck Flying]

However this algorithm assumed the waste was allocatable...

In reality ofcourse it is not... so the algorithm should be changed a little
to search for best fit...

When that's done the solutions change... and the statement below does not
seem true anymore... especially when searching for the largest width,
followed by the largest height, followed by the largest (smallest) depth.

To hopefully benefit from caching effects in textures...

So it seems a powerfull algorithm is still needed... the one in place now
(unpublished) is still a bit too brute force.

However the idea in the research in operations newsgroup might provide
further optimizations to the brute force algorithm... like skipping loops
which are way out of range anyway... the "dynamic loop construct idea" ;)

Bye,
Skybuck.