![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
lederhosenResponding to problem given here.
The problem (all measurements in pixels): Given a 'canvas' size c, and an integer k (in this particular example, k= 3, 4, or 12) we want to find suitable values for the following:
t (constraint)
u (grid unit width, not counting gutters)
g (gutter width)
so that both the canvas and constraint can be divided into some multiple of k units, each of width u, separated by gutters of width g. We want to exactly cover the constraint, but we don't need to completely cover the canvas.
That translates to:
t = k*m(u+g)-g
c' = k*n(u+g)-g
for some integers m, n (greater than m), and where c' is an integer close to (and not greater than) c. There will be various constraints on t, u, and g - for instance, we'd like t to be between 360 and 500, u somewhere around 50-90, and g small.
Let's start by picking a value for c' (might as well start by trying c' = c) and look for possible solutions for the other variables. What do we know?
c' = k*n(u+g)-g
Therefore, (c'+g) = kn(u+g), which tells us that k divides (c'+g). We know k and c', so we can easily identify all values of g that satisfy this. The lowest positive one will be g1 = k-c'+k*floor(c'/k), the next will be g2 = g1+k, then g3 = g1+2k, and so on; the constraints on g mean that there will probably only be a handful of acceptable values.
So we have a value for g. (If we have multiple values, start a 'for g = ...' loop at this point.)
Next, let's find possible values for t. The same argument as used above tells us that k also divides (t+g). Now that we know g, we can quickly find all values of t within the allowable range that satisfy this condition: for t_count in allowable range for t, t_count is a possibility only if k divides (t_count+g). Here we start a 'for t' loop.
Next, what possible values are there for u? Repeating from above:
(c'+g) = kn(u+g), so (u+g) divides (c'+g)/k.
Similarly, (u+g) divides (t+g)/k.
This tells us that (u+g) must be a common factor of (c'+g)/k and (t+g)/k (both of which are integers).
Find the common factors of (c'+g)/k and (t+g)/k* [probably the easiest way is to start by finding their greatest common divisor - if you don't have a GCD function in your software library already, the Euclidean algorithm is simple and efficient - and then find all factors of that]. Subtract g from each of them to find a possible value for u. If the result is within your acceptable range for u, you're finished - you now have acceptable values for g, t, and u. More likely, they will not have any common factors, or none that give you an acceptable value for u.
If this happens, go on to next t; if you exhaust t-values, go on to next g. If you still don't have any success, then subtract 1 from c' and begin again.
Example: canvas c = 960 pix, k = 12, with constraints:
360 LE t LE 500, and t = multiple of 5.
50 LE u LE 90.
1 LE g LE 18.
Start by trying c' = 960.
We know 12 divides (960+g); the smallest value of g satisfying this is 12, and the next one up (24) is too big, so g=12 is the only possible candidate here.
Next, calculate t. We know 12 divides (t+g). Within the range specified above, the values satisfying this are: t=360, t=420, t=480.
Next, for each of these t-values, try to solve for u.
(1) t=360: (u+g) must be a common divisor of (c'+g)/k and (t+g)/k. Substituting in the values we already know: (u+12) must be a common divisor of (972/12) (= 81) and (372/12) (= 31). No possible solutions.
(2) t=420: (u+12) must be a common divisor of 81 and (432/12) = 36. Their greatest common divisor is 9, which isn't big enough to be useful.
(3) t=480: no possible solutions.
So we've shown it's impossible to satisfy these criteria with c'=960. Subtract 1 from c', and repeat...
Whether there are many, one, or no solutions depends on how tight the constraints are for each of these variables. In particular, allowing smaller values of u and k will make it much easier to find a solution.
In this particular example, a little thought shows that it's impossible to solve it within these constraints - if t is at most 500, it's impossible to divide that space up into 12 grids that are each at least 50 pix wide. Let's try again, but reduce k to 3:
k divides (960+g) - this now gives us six possible values for g (3, 6, 9, 12, 15, 18).
k divides (t+g) - this now gives us 10 possible values for t (360, 375, 390, 405, 420, 435, 450, 465, 480, 495). [It so happens that in this particular case, each of the g-values allows the same range of t-values, but that won't always happen; it has to do with whether k divides the canvas size.]
(u+g) must be a common divisor of (c'+g)/k and (t+g)/k. It turns out that for c'=960 there is exactly one solution satisfying all these restrictions:
c'=960
g=15
t=375
u=50.
So we end up with a grid of 50-pixel columns separated by 15-pixel gutters. The constraint area is 375 pixels wide, containing 6 columns (and 5 gutters); the canvas is 960 pixels wide, containing 15 columns (and 14 gutters).
EDIT: Pseudocode below. This is a bit less efficient in some parts than the implementation described above, but should be easier to follow and avoids coding in a GCD function.
% Input required:
% c (canvas size)
% cdash_min (minimum acceptable cropped canvas size)
% k (set to 3 if you want the number of columns to divide by 3, and so on)
% t_min (minimum size of constraint area)
% t_max (maximum ditto)
% u_min (minimum grid unit width)
% u_max (maximum ditto)
% g_min (minimum gutter width)
% g_max (maximum ditto)
for cdash=c:-1:cdash_min % i.e. counting down from c to cdash_min in steps of -1
for g=g_min:g_max
if ((g+cdash)/k)==floor((g+cdash)/k) % This could be made more efficient, but this method is simpler and I'm lazy.
for t=t_min:t_max
if ((g+t)/k)==floor((g+t)/k) AND (any other limitations you might place on t go here))
for u=u_min:u_max
if (cdash+g)/(k*(u+g))==floor(cdash+g)/(k*(u+g))) AND (t+g)/(k*(u+g))==floor(t+g)/(k*(u+g)))
$ if that condition's satisfied, (cdash, g, t, u) is a solution. If you just want one solution, exit & return these values; if you want all solutions, add it to the list and keep working through the for loops.
next u
next t
next g
next cdash
if cdash==cdash_min and no solutions have been found, fail with message "No solutions exist for these constraints."
EDIT the second: Misunderstood one aspect of the problem - the constraint doesn't have to divide by k, only the canvas. With that in mind, revised algorithm:
% Input required:
% c (canvas size)
% cdash_min (minimum acceptable cropped canvas size)
% k (set to 3 if you want the number of columns to divide by 3, and so on)
% t_min (minimum size of constraint area)
% t_max (maximum ditto)
% u_min (minimum grid unit width)
% u_max (maximum ditto)
% g_min (minimum gutter width)
% g_max (maximum ditto)
for cdash=c:-1:cdash_min % i.e. counting down from c to cdash_min in steps of -1
for g=g_min:g_max
if ((g+cdash)/k)==floor((g+cdash)/k) % This could be made more efficient, but this method is simpler and I'm lazy.
for t=t_min:t_max
if (any other limitations you might place on t - e.g. "has to be divisible by 5" - go here)
for u=u_min:u_max
if (cdash+g)/(k*(u+g))==floor(cdash+g)/(k*(u+g))) AND (t+g)/(u+g)==floor((t+g)/(u+g)) % note, this line changed from previous version
$ if that condition's satisfied, (cdash, g, t, u) is a solution. If you just want one solution, exit & return these values; if you want all solutions, add it to the list and keep working through the for loops.
next u
next t
next g
next cdash
if cdash==cdash_min and no solutions have been found, fail with message "No solutions exist for these constraints."
The problem (all measurements in pixels): Given a 'canvas' size c, and an integer k (in this particular example, k= 3, 4, or 12) we want to find suitable values for the following:
t (constraint)
u (grid unit width, not counting gutters)
g (gutter width)
so that both the canvas and constraint can be divided into some multiple of k units, each of width u, separated by gutters of width g. We want to exactly cover the constraint, but we don't need to completely cover the canvas.
That translates to:
t = k*m(u+g)-g
c' = k*n(u+g)-g
for some integers m, n (greater than m), and where c' is an integer close to (and not greater than) c. There will be various constraints on t, u, and g - for instance, we'd like t to be between 360 and 500, u somewhere around 50-90, and g small.
Let's start by picking a value for c' (might as well start by trying c' = c) and look for possible solutions for the other variables. What do we know?
c' = k*n(u+g)-g
Therefore, (c'+g) = kn(u+g), which tells us that k divides (c'+g). We know k and c', so we can easily identify all values of g that satisfy this. The lowest positive one will be g1 = k-c'+k*floor(c'/k), the next will be g2 = g1+k, then g3 = g1+2k, and so on; the constraints on g mean that there will probably only be a handful of acceptable values.
So we have a value for g. (If we have multiple values, start a 'for g = ...' loop at this point.)
Next, let's find possible values for t. The same argument as used above tells us that k also divides (t+g). Now that we know g, we can quickly find all values of t within the allowable range that satisfy this condition: for t_count in allowable range for t, t_count is a possibility only if k divides (t_count+g). Here we start a 'for t' loop.
Next, what possible values are there for u? Repeating from above:
(c'+g) = kn(u+g), so (u+g) divides (c'+g)/k.
Similarly, (u+g) divides (t+g)/k.
This tells us that (u+g) must be a common factor of (c'+g)/k and (t+g)/k (both of which are integers).
Find the common factors of (c'+g)/k and (t+g)/k* [probably the easiest way is to start by finding their greatest common divisor - if you don't have a GCD function in your software library already, the Euclidean algorithm is simple and efficient - and then find all factors of that]. Subtract g from each of them to find a possible value for u. If the result is within your acceptable range for u, you're finished - you now have acceptable values for g, t, and u. More likely, they will not have any common factors, or none that give you an acceptable value for u.
If this happens, go on to next t; if you exhaust t-values, go on to next g. If you still don't have any success, then subtract 1 from c' and begin again.
Example: canvas c = 960 pix, k = 12, with constraints:
360 LE t LE 500, and t = multiple of 5.
50 LE u LE 90.
1 LE g LE 18.
Start by trying c' = 960.
We know 12 divides (960+g); the smallest value of g satisfying this is 12, and the next one up (24) is too big, so g=12 is the only possible candidate here.
Next, calculate t. We know 12 divides (t+g). Within the range specified above, the values satisfying this are: t=360, t=420, t=480.
Next, for each of these t-values, try to solve for u.
(1) t=360: (u+g) must be a common divisor of (c'+g)/k and (t+g)/k. Substituting in the values we already know: (u+12) must be a common divisor of (972/12) (= 81) and (372/12) (= 31). No possible solutions.
(2) t=420: (u+12) must be a common divisor of 81 and (432/12) = 36. Their greatest common divisor is 9, which isn't big enough to be useful.
(3) t=480: no possible solutions.
So we've shown it's impossible to satisfy these criteria with c'=960. Subtract 1 from c', and repeat...
Whether there are many, one, or no solutions depends on how tight the constraints are for each of these variables. In particular, allowing smaller values of u and k will make it much easier to find a solution.
In this particular example, a little thought shows that it's impossible to solve it within these constraints - if t is at most 500, it's impossible to divide that space up into 12 grids that are each at least 50 pix wide. Let's try again, but reduce k to 3:
k divides (960+g) - this now gives us six possible values for g (3, 6, 9, 12, 15, 18).
k divides (t+g) - this now gives us 10 possible values for t (360, 375, 390, 405, 420, 435, 450, 465, 480, 495). [It so happens that in this particular case, each of the g-values allows the same range of t-values, but that won't always happen; it has to do with whether k divides the canvas size.]
(u+g) must be a common divisor of (c'+g)/k and (t+g)/k. It turns out that for c'=960 there is exactly one solution satisfying all these restrictions:
c'=960
g=15
t=375
u=50.
So we end up with a grid of 50-pixel columns separated by 15-pixel gutters. The constraint area is 375 pixels wide, containing 6 columns (and 5 gutters); the canvas is 960 pixels wide, containing 15 columns (and 14 gutters).
EDIT: Pseudocode below. This is a bit less efficient in some parts than the implementation described above, but should be easier to follow and avoids coding in a GCD function.
% Input required:
% c (canvas size)
% cdash_min (minimum acceptable cropped canvas size)
% k (set to 3 if you want the number of columns to divide by 3, and so on)
% t_min (minimum size of constraint area)
% t_max (maximum ditto)
% u_min (minimum grid unit width)
% u_max (maximum ditto)
% g_min (minimum gutter width)
% g_max (maximum ditto)
for cdash=c:-1:cdash_min % i.e. counting down from c to cdash_min in steps of -1
for g=g_min:g_max
if ((g+cdash)/k)==floor((g+cdash)/k) % This could be made more efficient, but this method is simpler and I'm lazy.
for t=t_min:t_max
if ((g+t)/k)==floor((g+t)/k) AND (any other limitations you might place on t go here))
for u=u_min:u_max
if (cdash+g)/(k*(u+g))==floor(cdash+g)/(k*(u+g))) AND (t+g)/(k*(u+g))==floor(t+g)/(k*(u+g)))
$ if that condition's satisfied, (cdash, g, t, u) is a solution. If you just want one solution, exit & return these values; if you want all solutions, add it to the list and keep working through the for loops.
next u
next t
next g
next cdash
if cdash==cdash_min and no solutions have been found, fail with message "No solutions exist for these constraints."
EDIT the second: Misunderstood one aspect of the problem - the constraint doesn't have to divide by k, only the canvas. With that in mind, revised algorithm:
% Input required:
% c (canvas size)
% cdash_min (minimum acceptable cropped canvas size)
% k (set to 3 if you want the number of columns to divide by 3, and so on)
% t_min (minimum size of constraint area)
% t_max (maximum ditto)
% u_min (minimum grid unit width)
% u_max (maximum ditto)
% g_min (minimum gutter width)
% g_max (maximum ditto)
for cdash=c:-1:cdash_min % i.e. counting down from c to cdash_min in steps of -1
for g=g_min:g_max
if ((g+cdash)/k)==floor((g+cdash)/k) % This could be made more efficient, but this method is simpler and I'm lazy.
for t=t_min:t_max
if (any other limitations you might place on t - e.g. "has to be divisible by 5" - go here)
for u=u_min:u_max
if (cdash+g)/(k*(u+g))==floor(cdash+g)/(k*(u+g))) AND (t+g)/(u+g)==floor((t+g)/(u+g)) % note, this line changed from previous version
$ if that condition's satisfied, (cdash, g, t, u) is a solution. If you just want one solution, exit & return these values; if you want all solutions, add it to the list and keep working through the for loops.
next u
next t
next g
next cdash
if cdash==cdash_min and no solutions have been found, fail with message "No solutions exist for these constraints."
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2007-03-26 03:48 am (UTC)I think the wrong problem is being solved here, which is why it's hard to come up with a good solution. After going through the powerpoint slides, my understanding is that the problem is actually this:
Given a set of design elements with widths a1, a2... a[x], what set of values for content and gutter widths yields the lowest number of columns?
The advantage of asking that question (or similar variant) is that it allows you to present less information - otherwise your output gets filled with 'cell 1, gutter 1' and similar garbage values. Whereas the objective seems to be to get the cells to be as big as possible, given the constraints. Phrasing 'largest possible cell' as 'fewest possible columns' is just a product of how my brain works.
The other nice thing about doing it that way would be that you could then get the code to search in a particular direction and terminate early. You know that every element has to fit neatly into at least one column - so you take your smallest element and see if you can get it to fit into exactly one column, testing various gutter values to see if you can get the larger elements to align neatly. If none of those values work, you test it with two columns, then three columns, etc, until you reach the point where the minimum gutter values for the columns fill the entire (smallest) design element, at which point you know that there is no solution.
User inputs should include minimum and maxiumum gutter sizes, since this is a primarily aesthetic judgement. And it provides nice constraints to feed into the search for an answer.
Assuming for a moment that there is a better solution than the 'fewest columns' solution, it would not be difficult to modify that search method to return the first X results.
As for how many of the columns will fit into a 960 pixel width, that's trivially easy once you've got your column and gutter widths sorted :)
Pseudocode implementation
Date: 2007-03-26 04:05 am (UTC)SmallestConstraint := Constraints[1];
Get From User (MinGutter, MaxGutter, DesiredResultCount);
NumberOfCols := 1;
Finished := False;
Results := 0;
while not Finished
foreach Gutter in MinGutter to MaxGutter
ColWidth := (SmallestConstraint - ((NumberOfCols - 1) * Gutter))/NumberOfCols;
OKSoFar := True;
Index := 1;
while Index <= NumConstraints and OKSoFar
OKSoFar := TestForFit (Constraint[Index], ColWidth, GutterWidth);
Index ++
end while;
if OKSoFar;
Output(SuccessMessage, ColWidth, GutterWidth);
Results++;
/* Yeah, we should check the result count and update Finished here. But I'm sacrificing accuracy for readbility in this pseudocode. */
end if;
end foreach;
NumberOfCols ++;
If (Results >= DesiredResultCount) or (NumOfCols * GutterWidth > SmallestConstraint) then
Finished := True;
end if;
end while;
Output ("Found this many results:", Results);
Re: Pseudocode implementation
Date: 2007-03-26 04:05 am (UTC)no subject
Date: 2007-03-26 05:33 am (UTC)Given a set of design elements with widths a1, a2... a[x], what set of values for content and gutter widths yields the lowest number of columns?
We're not aiming for lowest number of columns - we're aiming for a nice divisible number of columns, preferably a multiple of 3, 4, or both.
The approach we ended up figuring out was:
(1) Round canvas down to a multiple of 12, if it isn't already.
(2) Pretend there's a gutter on the right-hand edge - this will actually be a crop to the canvas, but it simplifies the mathematics.
(3) Divide canvas side by 12 to get (grid unit + gutter).
(4) Note that constraint area will be n*(grid unit) + (n+1)*gutter, for some n. This means that shifting one pixel from grid unit size to gutter will make that value decrease by 1, and shifting it the other way will increase it, which lets us fine-tune for an exact fit to the constraint.
no subject
Date: 2007-03-26 06:01 am (UTC)Although, if the constraints are being determined by the columns (as seems to be suggested here), then it seems to me that this isn't properly a mathematics problem. Meh.
no subject
Date: 2007-03-31 05:22 am (UTC)The "pick 12 and fudge it" method is because 12 is generally a useful number of columns to use for layout, as a rule of thumb. Currently turning the pseudocode above into actual code to automagically generate grids to test for layout, as I really can't be arsed with manually dragging grid lines in photoshop.