How to select next best block from next k blocks to save white space?

Questions
1

I tried to implement the following using AI but gave up after ~100 iterations…
Here is the algorithm:

  • the page has 2 columns, all blocks are breakable and come from a database, I can create an array of blocks and want to render them at width: 100%.
  • I want to render the blocks one by another using this logic:
  • if the current block C fits completely on current page at full height, use this one.
  • otherwise: search in the next k (for example k=4) blocks and find the block with the highest height that fits completely on the current page. Use this one instead. If no one from this k blocks fit, then we use C. If one from the k blocks fitted: keep in mind that C is the prefered in the next iteration.
  • repeat this after all blocks are rendered.

This would minimize white space on the page quite good because those blocks have different heights. The constant k is limited for performance reasons but also because the elements are sorted by time, so a newer element should not appear at a very late position.

Is there already a package that implements this?

AI gives me some code like this:

#set page(
  paper: "a4",
  margin: 1.5cm,
  columns: 2,
)
#set par(
  spacing: 0pt,
)


#let page-height = 26.7cm
#let k = 4

#let heights = (
  4.2cm, 8.7cm, 3.4cm, 6.1cm,
  9.3cm, 5.2cm, 7.8cm, 3.8cm,
  6.9cm, 9.8cm, 4.7cm, 7.1cm,
  5.6cm, 8.1cm, 3.2cm, 6.5cm,

  7.4cm, 4.9cm, 8.3cm, 3.7cm,
  6.4cm, 9.1cm, 5.5cm, 7.7cm,
  4.1cm, 8.9cm, 3.5cm, 6.8cm,
  9.6cm, 5.8cm, 7.2cm, 4.6cm,

  8.4cm, 3.9cm, 6.3cm, 9.2cm,
  5.1cm, 7.9cm, 4.4cm, 8.6cm,
  3.6cm, 6.7cm, 9.7cm, 5.4cm,
  7.3cm, 4.8cm, 8.2cm, 3.3cm,
)


#let blocks = heights.enumerate().map(((i, height)) => {
  rect(
    width: 100%,
    height: height - 1pt,
    fill: white,
    stroke: 0.5pt + black,
    inset: 5pt,
  )[
    #align(center + horizon)[
      #text(size: 14pt)[#i]
    ]
  ]
})

#let remaining = blocks
#let remaining-heights = heights
#let used = 0cm

#while remaining.len() > 0 {
  let first-height = remaining-heights.at(0)
  let selected = 0

  if used + first-height > page-height {
    let best-height = 0cm
    let found = false

    for i in range(0, calc.min(k, remaining.len())) {
      let h = remaining-heights.at(i)

      if used + h <= page-height {
        if not found or h > best-height {
          selected = i
          best-height = h
          found = true
        }
      }
    }

    if not found {
      selected = 0
    }
  }

  remaining.at(selected)

  used += remaining-heights.at(selected)

  remaining = (
    remaining.slice(0, selected)
    + remaining.slice(selected + 1)
  )

  remaining-heights = (
    remaining-heights.slice(0, selected)
    + remaining-heights.slice(selected + 1)
  )
}

Does only work for the first page and does not use measure. For my real blocks I do not know the heights.

2

See if this can’t get you started

full code 
#set page(columns: 2, paper: "a6")

#let blocks = (12, 46, 55, 2, 59, 12, 33, 23, 66, 4, 22, 7).map(lorem).map(block.with(breakable: true))

#let windowsize = 4

#layout(page => {
  let blocks-and-heights = blocks.zip(
    blocks.map(
      b => measure(b, width: page.width).height
    )
  )

  let current-height = 0pt

  let block-window = blocks-and-heights.slice(0, windowsize + 1)
  let curr-idx = windowsize + 1

  for _ in range(blocks-and-heights.len()) {
    let display-idx = 0
    let max-other-idx = 0
    let max-other-height = -1pt
    if block-window.at(display-idx).last() + current-height > page.height {
      // attempt to swap
      for (idx, (b, h)) in block-window.slice(1).enumerate() {
        if h + current-height <= page.height and h > max-other-height {
          max-other-idx = idx + 1
          max-other-height = h
        }
      }
      display-idx = max-other-idx
    }
    let (b, h) = block-window.remove(display-idx)
    set text(fill: red) if max-other-idx != 0  // swapped block
    b
    if curr-idx < blocks-and-heights.len() {
      block-window.push(blocks-and-heights.at(curr-idx))
    }
    curr-idx += 1
    current-height += h + par.spacing.to-absolute()
    while current-height >= page.height {
      current-height -= page.height
    }
    let test = current-height + 35.43pt
  }
})

image
image569×911 126 KB

It’s a bit tricky because we can’t use context to re-evaluate our position (due to those blocks being read-only, and we need to keep track of which blocks are available to us), so this is only an approximation. For example, the spacing between paragraphs may also depend on block parameters so par.spacing.to-absolute() isn’t enough.

I also just noticed that you said you wanted them to fit on the same page, but I somehow interpreted that as column. Fixing this should be easy, just check for parity on the number of times the blocks overflow the page height and re-write some logic. I’d do this, but it’s getting late and want to get an answer out before logging off :slight_smile:

3

Thank you, very much! My first impression is that your code works exactly how I wanted it to work! When we check it by adding the indices, we can see small mistakes for example number 34 is used before 30 even though 34 does not fit completely. But I think it’s good enough!

#let blocks = (
  (1, 37),
  (2, 82),
  (3, 14),
  (4, 56),
  (5, 103),
  (6, 29),
  (7, 71),
  (8, 45),
  (9, 118),
  (10, 63),
  (11, 22),
  (12, 94),
  (13, 48),
  (14, 77),
  (15, 31),
  (16, 109),
  (17, 53),
  (18, 16),
  (19, 86),
  (20, 41),
  (21, 67),
  (22, 125),
  (23, 35),
  (24, 58),
  (25, 91),
  (26, 24),
  (27, 73),
  (28, 112),
  (29, 46),
  (30, 80),
  (31, 19),
  (32, 99),
  (33, 61),
  (34, 34),
  (35, 107),
  (36, 52),
  (37, 27),
  (38, 88),
  (39, 43),
  (40, 116),
  (41, 69),
  (42, 38),
  (43, 97),
  (44, 21),
  (45, 75),
  (46, 54),
  (47, 121),
  (48, 32),
  (49, 84),
  (50, 47),
)

#let blocks = blocks.map(((index, amount)) =>
  block(
    [#index #lorem(amount)],
    breakable: true,
  )
)
4

yes, this is somewhat unavoidable as calculating spacing manually is complicated. The biggest issue has to do with page/colbreaks, where we might have a small amount of space remaining, less than one line. In that case typst’s layout engine pushes the block onto the next column, but my code does not reflect this. It can be (somewhat) mitigated by adding the condition

if page.height - current-height - par.leading.to-absolute() <= measure(b).height {
  current-height = 0pt
}

at the very end of the loop, but it’s not a perfect fix. In my testing I noticed that the error between the calculated height and true height grows with the number of blocks, so you might get better results if you use a smaller number of blocks, or break them up into chunks appropriately.

BTW, you can use blocks.enumerate() instead of manually writing the index :slight_smile:

5

Thank your for further looking into this!

I think, I now understand the problem. It likely appears only with blocks that break into a new column or page. We would have to check at each new column and new page what is the actual starting height. It is not guranteed to be zero, because a block from a last page could have breaked and then could take up a few cm or even the full next page or column.
This wrong current height probably adds up with each new block. Thus, we get a bigger error with each new breaking block.

Regarding enumerate: yes, I know, also AI knows, but we both didn’t got it working. Either a typst bug with enumerate + map or it’s just completely different than using it in Rust.