24
\$\begingroup\$

Introduction

Kerning means adjusting the spacing between the letters of a text. As an example, consider the word Top written with the following three glyphs:

##### ..... .....
..#.. ..... .....
..#.. ..##. .###.
..#.. .#..# .#..#
..#.. .#..# .#..#
..#.. ..##. .###.
..... ..... .#...
..... ..... .#...

We could just fill the gaps between the glyphs with dots and be done with it, but the gaps somehow look too wide. Instead, we slide the glyphs to the left so that they almost touch:

#####........
..#..........
..#..##..###.
..#.#..#.#..#
..#.#..#.#..#
..#..##..###.
.........#...
.........#...

This looks much better! Note how the bar of T is on top of the left border of o. In this challenge, your task is to implement a simple kerning program for such rectangular glyphs.

The kerning process

Consider two rectangular 2D character arrays of . and # of the same shape. In our simple kerning process, we first place the arrays side by side, with one column of .s in between. Then, we move each # in the right array one step to the left, until some #s of the left and right array are orthogonally or diagonally adjacent. The outcome of the kerning is the step before we introduce adjacent #s. Your task is to implement this process.

Let's take an example:

Inputs:
..###
#....
#....
..##.

...#.
...##
..###
....#

Process:
..###....#.
#........##
#.......###
..##......#

..###...#.
#.......##
#......###
..##.....#

..###..#.
#......##
#.....###
..##....#

..###.#.
#.....##
#....###
..##...#

..####.
#....##
#...###
..##..#

In the last array, we have new adjacent pairs of #s, so the second-to-last array is the result of the kerning process.

Input and output

For simplicity, you only need to handle kerning of two glyphs. Your inputs are two rectangular 2D arrays, in one of the following formats:

  • 2D arrays of integers, with 0 standing for . and 1 for #.
  • Multiline strings over .#.
  • Arrays of strings over .#.
  • 2D arrays of the characters .#.

If the inputs are taken as a single string, you can use any reasonable delimiter. However, the delimiter should go between the two arrays, meaning that you are not allowed to take the two inputs already paired row-by-row.

Your output is the result of the kerning process applied to these two arrays, which is a rectangular 2D array in the same format as the inputs. You are allowed to add or remove any number of leading or trailing columns of .s, but the output must be rectangular and have the same height as the inputs. It is guaranteed that the kerning process ends before the left edge of the second input slides over the left edge of the first input.

Rules and scoring

The lowest byte count in each programming language wins. Standard rules apply.

Test cases

To help with copy-pasting, these test cases are given as lists of strings.

["#"] ["#"] -> ["#.#"]
["#.","..",".#"] ["##","..","##"] -> ["#..##",".....",".#.##"]
["..#","#..","#.."] ["...","..#","###"] -> ["..#..","#...#","#.###"]
["###.","##..","#...","...."] ["....","...#","..#.",".#.."] -> ["###..","##..#","#..#.","..#.."]
["..##...","#......","#......"] [".....##",".....##",".#...#."] -> ["..##..##","#.....##","#.#...#."]
["...#.",".....",".....",".....","....#"] [".....","....#","#....",".....","....."] -> ["...#..",".....#",".#....","......","....#."]
["..#..",".....",".....",".....","....#"] [".....","....#","#....",".....","....."] -> ["..#..","....#","#....",".....","....#"]
["######","#.....","#.....","#.....","######"] ["......",".....#",".#...#",".....#","......"] -> ["######..","#......#","#..#...#","#......#","######.."]
["######","#.....","#.....","#.....","######"] ["......","......",".#....","......","......"] -> ["######","#.....","#.#...","#.....","######"]
["#...#","#..#.","#.#..","##...","#.#..","#..#.","#...#"] ["...#.","..#..",".#...",".#...",".#...","..#..","...#."] -> ["#...#..#","#..#..#.","#.#..#..","##...#..","#.#..#..","#..#..#.","#...#..#"]
\$\endgroup\$
  • \$\begingroup\$ Visualizer. Test case 5 seems to be wrong. \$\endgroup\$ – user202729 Nov 20 '17 at 10:20
  • \$\begingroup\$ @user202729 Thanks, it's fixed now. I went through several rounds of fixing the test cases in the sandbox, and apparently missed that one. \$\endgroup\$ – Zgarb Nov 20 '17 at 10:23
  • \$\begingroup\$ Also if the two characters "fall through" each other what should the program do? \$\endgroup\$ – user202729 Nov 20 '17 at 10:24
  • \$\begingroup\$ @user202729 You can assume that will not happen. See the last sentence of section "Input and output". \$\endgroup\$ – Zgarb Nov 20 '17 at 10:25
7
\$\begingroup\$

APL (Dyalog Classic), 40 39 bytes

-1 thanks to Erik the Outgolfer

{⌈⌿↑⍺(⍉(1-⌈/+⌿+∘×⍨2⌈/0,+/⌈\↑(⌽⍺)⍵)↑⍉⍵)}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 3, 154 bytes

lambda a,b,p=".":[c.rstrip(p)+d.lstrip(p).rjust(max(len((d+c).strip(p))for(c,d)in zip((a*3)[1:],b[:-1]+b+b[1:]))+1-len(c.rstrip(p)),p)for(c,d)in zip(a,b)]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Retina, 223 bytes

+`(.+)¶(¶(.+¶)*)(\W+(¶|$))
$2$1i$4
T`.`i`\.*i\.*
+`(¶(.)*#.*i.*¶(?<-2>.)*)i
$1@
+`(¶(.)*)i(.*¶(?<-2>.)*(?(2)(?!))#.*i)
$1@$3
T`i@`.`i*[#@]+i
mT`.`i`\.+i+$
msT`i`.`.*^\W+$.*
+`(\b(i+)\W+\2i*)i
$1.
+s`\bi((i+).+\b\2\b)
.$1
i

Try it online! Link includes test cases plus header script to reformat them to its preferred input format of two newline-delimited strings. This seems overly long yet there's probably an edge case that I've overlooked, but it does at least pass all of the test cases now. Explanation:

+`(.+)¶(¶(.+¶)*)(\W+(¶|$))
$2$1i$4

Join the two input arrays together using a letter i as a separator. (This allows use of \W and \b later on.)

T`.`i`\.*i\.*

Change all the .s to is at the join.

+`(¶(.)*#.*i.*¶(?<-2>.)*)i
$1@

Change all is below #s to @s.

+`(¶(.)*)i(.*¶(?<-2>.)*(?(2)(?!))#.*i)
$1@$3

Change all is above #s to @s.

T`i@`.`i*[#@]+i

Change all the @s to .s, plus all the is adjacent to @s or #s.

mT`.`i`\.+i+$

If there is no # after an i, then change the adjacent . back to an i again.

msT`i`.`.*^\W+$.*

If there is a line with no is, change all the is to .s, as there is nothing to do here.

+`(\b(i+)\W+\2i*)i
$1.

Calculate the minimum number of is on any line.

+s`\bi((i+).+\b\2\b)
.$1

Propagate to the other lines.

i

Delete the is, thus performing the required kerning.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.