Typesetting

Modern fonts are generally of two varieties: outline fonts, whose glyphs (the individual character shapes) are specified mathematically as a set of curves, and bitmap fonts, whose glyphs are specified as patterns of pixels. Fonts may also include embedded information such as kerning pairs (adjusting the spacing between certain pairs of glyphs, such as "AW", so that they appear spaced correctly), tracking hints (for managing inter-glyph spacing), antialiasing hints (smoothing of pixellated edges), and much more. Modern fonts are more than a simple collection of shapes, and displaying them properly is a common programming challenge.

For this problem, we will focus on bitmap fonts and a simple form of typesetting called glyph packing. The goal is to pack the glyphs as tightly as possible while maintaining at least one horizontal pixel of separation between glyphs. For example, consider the glyphs shown to the left below for the Roman characters "P" and "J". The figure to the right shows them after glyph packing. Note that they are as close as possible without touching horizontally.

Here's another example. In this case, note that the final glyph cannot be packed at all.

After packing, pixels from distinct glyphs may be adjacent diagonally or vertically, but not horizontally. The following example shows that pixels may be adjacent diagonally. The "Love" test case in the example input section demonstrates that they may be adjacent vertically.

Glyph packing has the property that it is easy to include "fancy" glyphs in the font so that glyph packing creates special effects with no extra work. Look at the "Toy" example below. The same simple packing process has been applied to these glyphs as above, but the result is more dramatic:

Glyph packing has some caveats, one of which is important for this problem. Consider the example on the left below, where a glyph for a hyphen is followed by a glyph for an underscore. According to our one horizontal pixel of separation rule, how would this be packed? Clearly, something more is needed, and that is hinting within the glyphs themselves. In practice, fonts contain kerning pairs, tracking hints, etc. For our purposes, our hinting is limited to "invisible" pixels that count as a pixel for packing, but not for display. The center image below represents invisible pixels as open dots instead of closed dots. Now the two glyphs can be properly packed, resulting in the output shown on the right.

Now for the formal definition of a proper packing: (1) Glyphs are packed as close as possible without allowing any pixels from different glyphs to be immediately horizontally adjacent; (2) Given two glyphs, they may not be packed in such a way that any pixel of the leftmost glyph at a given height ends up positioned to the right of any pixel at the same height in the rightmost glyph.

Condition (2) above is easily understood by visualizing two glyphs side by side, separated by a small space. If you press them together, condition (2) says that their pixels are not allowed to "pass through" each other. Consider the example to the left below. The center image is not the proper packing, because it violates condition (2). The image on the right is the proper packing of these glyphs.