Solved

# Algorithm for Determining Column Counts

Posted on 2012-09-04
504 Views
Let me start by assuring you that this is not a homework question. I am programmatically trying to lay out printed items on a page, and I think the long holiday weekend has fried my brain = )

I have a list of items that will be laid out on a printed page. The maximum number of items is unbounded. What I would like to achieve is a layout such as:

``````* * *
* *
* *
* *
``````

...where each column (maximum of 3, currently) is filled prior to the next column being started; however, the space should be consumed in an optimal way--meaning that, if possible, reduce the number of rows for the sake of filling a right-hand column more fully. I should not have more than one column with a different number of rows. Another way of looking at the layout would be:

``````1 5 9
2 6
3 7
4 8
``````

In the interest of simplicity and performance, I was hoping to work out an algebraic expression (or expressions) that would give me the count of items in each column (hence the Science/Math category), but I would settle for pseudo-code examples as well. (Note: the language in use is a proprietary language specific to the software--PlanetPress--in use. This language is rather Visual Basic-esque, so VB examples would be adequate.)

I added the C category because I know you guys are always locked away somewhere dreaming up wild algorithms. C/C++ (or just about any language--except BrainF***!!) code would suffice as well.

Here is a larger sampling of what the layouts would look like (1 - 12 items):

``````1 Item
======
*

2 Items
=======
* *

3 Items
=======
* * *

4 Items
=======
* *
* *

5 Items
=======
* * *
* *

6 Items
=======
* * *
* * *

7 Items
=======
* * *
* *
* *

8 Items
=======
* * *
* * *
* *

9 Items
=======
* * *
* * *
* * *

10 Items
========
* * *
* * *
* *
* *

11 Items
========
* * *
* * *
* * *
* *

12 Items
========
* * *
* * *
* * *
* * *
``````

Thanks!
0
Question by:käµfm³d   👽

LVL 43

Expert Comment

This formula will give you the number of rows

=INT((A1-1)/3)+1
0

LVL 84

Expert Comment

perl -Minteger -le 'for \$Items (1..12){ \$rows=(\$Items+2)/3; print "\$Items Item",\$Item!=1&&"s";print"========"; for (reverse \$Items..\$Items+\$rows-1 ){ print "* "x(\$_/\$rows) } print } '
0

LVL 43

Expert Comment

In an excel file if you enter this formula in A1 and copy it across to C1 and down far enough then you can change the value in H1 to see your desired sequence

=IF(OR((INT((\$H\$1-1)/3)+1)<ROW(),((ROW()-1)+(COLUMN()-1)*(INT((\$H\$1-1)/3)+1)+1)>\$H\$1),"",(ROW()-1)+(COLUMN()-1)*(INT((\$H\$1-1)/3)+1)+1)
0

LVL 25

Assisted Solution

- nentries + ( ncols - nentries % ncols ) / ncols

- ceil( nentries / ncols )

should both give the number of elements to fill the first column with providing that ceil() returns the integer following the given parameter or the parameter itself if already an integer and % stands for modulo and has precedence over +/-
0

LVL 74

Accepted Solution

My apologies for the delay. I was so focused on completing our sprint that this question just slipped my mind. My requirement changed just a tad, so that threw me for a good loop. Here is a summary of my findings for each suggestion above, as well as what I ultimately ended up doing.

@ssaqibh

I do apologize. I realize I said that any language should be fine, but I have to admit that I don't do much in the way of Excel. I tried plugging your formula into Excel, and it did not seem to yield what I was looking for. This could simply be my ignorance of Excel.

@ozo

Unless I completely misunderstand your script, it seems that you took the example a bit too literally. The snippet does print the stars as I have laid them out above; however, the use of the repetition operator doesn't fit this particular scenario. I needed the distinctness of the numeric example I posted above:  every item is unique, and the items should be displayed in such a manner as they fill the first colum, then fill the second column, then put whatever is left in the third column--all while maximizing the amount of horizontal space used. I always love your one-liners, but in this case I don't think it fits the scenario.

@skullnobrains

Your first one does not work, so far as I can see. Take 12, for example. Plugging 12 into your formula yields:

12 + ( 3 - 12 % 3 ) / 3

That would yield 13 due to precedence rules. I'm guessing there are some missing parens in there somewhere, but I'm not certain where.

Your second does work, and this is pretty much what I was doing before and now. My hangup was that I could not transition past this first column to determine how many items were in the remaining columns. While your answer does solve the first column, I didn't fully see how to calculate the remaining columns, and this was my primary reason for asking the question. This is why I have awarded a partial solution.

---------------------
Explanation
---------------------

As skullnobrains mentioned, it is simple to get the first column's count:  simply divide the total number of items by the the number of columns. I used integer division for mine, but ceiling works as well (though with a slightly different result which you may need to account for).

Now my requirement changed in that the user wanted between 1 and 5 items to show as one column. For the second column I did not immediately see how to calculate the number of items. However, in my case it is ridiculously simple:  Barring 1, 2, 3, 4, and 5 items, the second column will have the same number of items as the first column--always. It is only the third column which fluctuates. The end result became a matter of calculating the number of items in the first column, (effectively) multiplying that by 2 to get total count of column 1 and column 2, and then subtracting from the total number of items to get column 3. In other words:

column1 = (total_items / num_cols)
column2 = column1
column3 = (total_items - (column1 + column2))

Thank you to all!
0

LVL 84

Expert Comment

Could you give an example a layout that meets your current requirements and differs from what my script produces?
0

LVL 74

Author Comment

ozo,

``````1 Item
======
This is item one

2 Items
=======
This is item one

This is item two

3 Items
=======
This is item one

This is item two

This is item three

4 Items
=======
This is item one

This is item two

This is item three

This is item four

5 Items
=======
This is item one

This is item two

This is item three

This is item four

This is item five

6 Items
=======
This is item one            This is item three            This is item five

This is item two            This is item four             This is item six

7 Items
=======
This is item one            This is item four            This is item seven

This is item two            This is item five

This is item three          This is item six

8 Items
=======
This is item one            This is item four            This is item seven

This is item two            This is item five            This is item eight

This is item three          This is item six

9 Items
=======
This is item one            This is item four            This is item seven

This is item two            This is item five            This is item eight

This is item three          This is item six             This is item nine

10 Items
=======
This is item one            This is item five            This is item nine

This is item two            This is item six             This is item ten

This is item three          This is item seven

This is item four           This is item eight

11 Items
=======
This is item one            This is item five            This is item nine

This is item two            This is item six             This is item ten

This is item three          This is item seven           This is item eleven

This is item four           This is item eight

12 Items
=======
This is item one            This is item five            This is item nine

This is item two            This is item six             This is item ten

This is item three          This is item seven           This is item eleven

This is item four           This is item eight           This is item twelve
``````

I used phrases instead of stars this time, for clarity.
0

LVL 25

Expert Comment

just in case you still want to balance evenly,
entries % cols should give the number of columns that  have one more entry than the last one(s)

my formula was actually written a bit too fast, sorry about that, but i guess it would be useless to rewrite it now. i won't mind if you request a refund

happy coding
0

LVL 74

Author Closing Comment

Selecting my own comment for the explanation of how to calculate size of all columns.
0

## Featured Post

### Suggested Solutions

Have you ever thought of installing a power system that generates solar electricity to power your house? Some may say yes, while others may tell me no. But have you noticed that people around you are now considering installing such systems in their …
Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.