telgif: inverse figlet

Question

figlet is utility that converts plain text to an ascii-art representation for use in banners and the like. For example:

$ figlet "CODE GOLF"
  ____ ___  ____  _____    ____  ___  _     _____ 
 / ___/ _ \|  _ \| ____|  / ___|/ _ \| |   |  ___|
| |  | | | | | | |  _|   | |  _| | | | |   | |_   
| |__| |_| | |_| | |___  | |_| | |_| | |___|  _|  
 \____\___/|____/|_____|  \____|\___/|_____|_|    
                                                  
$

Write a program or function that takes the ascii-art output from figlet and returns it to its original plain text.

It may be helpful to you to install figlet. I have version 2.2.5 which is what you get if you sudo apt-get install figlet on Ubuntu 14.04. This figlet actually has several "fonts". For the purposes of this context, we will just be dealing with the default standard font.

Input text will be no more that 80 characters wide, and will have been generated from plain text containing only the uppercase characters and space.

Your program may not call figlet or its source code in any way.

Example

Input:

    _    ____   ____ ____  _____ _____ ____ _   _ ___ 
   / \  | __ ) / ___|  _ \| ____|  ___/ ___| | | |_ _|
  / _ \ |  _ \| |   | | | |  _| | |_ | |  _| |_| || | 
 / ___ \| |_) | |___| |_| | |___|  _|| |_| |  _  || | 
/_/   \_\____/ \____|____/|_____|_|   \____|_| |_|___|
                                                      
     _ _  ___     __  __ _   _  ___  ____   ___  ____  
    | | |/ / |   |  \/  | \ | |/ _ \|  _ \ / _ \|  _ \ 
 _  | | ' /| |   | |\/| |  \| | | | | |_) | | | | |_) |
| |_| | . \| |___| |  | | |\  | |_| |  __/| |_| |  _ < 
 \___/|_|\_\_____|_|  |_|_| \_|\___/|_|    \__\_\_| \_\
                                                       
 ____ _____ _   ___     ____        ____  ____   _______
/ ___|_   _| | | \ \   / /\ \      / /\ \/ /\ \ / /__  /
\___ \ | | | | | |\ \ / /  \ \ /\ / /  \  /  \ V /  / / 
 ___) || | | |_| | \ V /    \ V  V /   /  \   | |  / /_ 
|____/ |_|  \___/   \_/      \_/\_/   /_/\_\  |_| /____|

Output:

ABCDEFGHI
JKLMNOPQR
STUVWXYZ

Input:

 ____ _____  _    ____   __        ___    ____  ____  
/ ___|_   _|/ \  |  _ \  \ \      / / \  |  _ \/ ___| 
\___ \ | | / _ \ | |_) |  \ \ /\ / / _ \ | |_) \___ \ 
 ___) || |/ ___ \|  _ <    \ V  V / ___ \|  _ < ___) |
|____/ |_/_/   \_\_| \_\    \_/\_/_/   \_\_| \_\____/ 

Output:

STAR WARS

---

Note a previous edit of this question allowed inputs containing upper and lower case letters plus numerals. It was pointed out that this caused several points of ambiguity with certain adjacent character combinations. It became obvious that I needed to rigorously find a set of characters with no such collisions so that the contest is actually doable. At first I tried all lowercase letters plus numerals with this shell one-liner:

for t in {0..9}{a..z} {a..z}{a..z} {a..z}{0..9} {0..9}{0..9} ; do figlet $t | tr '\n' ':'; echo ; done | sort | uniq -d | tr ':' '\n'

This yielded {j1, jl} and {i1, il} as ambiguous pairs. So instead with all uppercase letters (as suggested by @AlexA.), there are no ambiguous pairs:

for t in {A-Z} ; do figlet $t | tr '\n' ':'; echo ; done | sort | uniq -d | tr ':' '\n'

Answer 1

JavaScript, 946 bytes

i=>i.split(/\n *\n/).slice(n=0,-1).map(x=>[...(x=x.split`
`)[0]].map((_,i)=>parseInt([0,1,2,3,4].map(j=>"_/\\|".indexOf(x[j][i])+1).join(""),5)).map((n,i,x)=>o[x.slice(i).map(a=>v=v*5+a,v=0).find(v=>o[v])]||"").join``," 0JiivI1d5JysyKgx0X5qyZegzZfZ9mtZfO3288Q9CboCfG28CkO29Q9J1bg3N2d9pLh0dLfL2sLdwH14uLwdU1b4LkyYbbwY1Y2YhY1fjY1Y2YhY1fjY1Y2YhL3nfY126Y1Y2YhY20dY1Y2YhY1fjY1Y2YhR173PjP2P2P7RgjPjP2Fc6FsFtF1rDpcDhdB1ptBhdExgEfE2sSelvS6ySdwJ5wiSr3S6ySdwJaq4Jc21T8zaT1TrT2kA28bA2sAdwT3vT1TrT2kA1ufA1w2TwcT1TrT2kT1xlT1TrT2kA7ccTv58T1TrT2kT1crT1TrT2kT83tT1TrT2kT1crT1TrT2kO48kQ9CboCfG28CkO29Q9AvrtiA2sAdwA21mA1w2AacxM6z18A2cpp6A2sAdwA21mA1w2AacxA7yngA2sAdwA21mA1w2AacxA1ukibA2sAdwA21mA1w2AacxV1brpkV3V4VdV105jV3V4VdV2e9V3V4VdV105jV3V4VdV4md1V3V4VdV105jV3V4VdAruayA2sAdwA21mA1w2AacxAgc25A2sAdwA21mA1w2AacxWozq07rW3W4WdW3hl3vW3W4WdW8de5W3W4WdW3hl3vW3W4WdWg1p5dW3W4WdW3hl3vW3W4Wd".split(/(?=[A-Z ])/).map(x=>o[n+=parseInt(x.slice(1),36)]=x[0],o={})).join`
`

Try it online!

Note that figlet by default outputs two trailing blank lines; if those can be assumed to not exist, like in the challenge examples, the initial slice can be removed for -10 bytes. Otherwise, make sure the blank lines are present in the "Input" field on TIO, or the last line of output will be omitted.

Explanation

At a high level, this scans the strings for patterns, and outputs the ones it finds.

A single character can have multiple patterns; for example, these are all valid patterns for A: (the first and last column are omitted, as they are not necessary for matching)

   _   
  / \  
 / _ \ 
/ ___ \
_/   \_

_  _   
_|/ \  
 / _ \ 
/ ___ \
_/   \_

 _____ 
/ / \ \
 / _ \ 
/ ___ \
_/   \_

The first appears in bare As, or uncombined As such as in AX, the second appears in TA, and the third appears in e.g. WAV:

    _      _____  _     __        _____     __
   / \    |_   _|/ \    \ \      / / \ \   / /
  / _ \     | | / _ \    \ \ /\ / / _ \ \ / / 
 / ___ \    | |/ ___ \    \ V  V / ___ \ V /  
/_/   \_\   |_/_/   \_\    \_/\_/_/   \_\_/   
 -------       -------           -------

Thus, for every character, there is a pattern for:

• Each triplet of characters with it at the center
• Each pair of characters containing it
• It on it's own

Some of these patterns are identical, for example, the As in VAV and WAV are identical, and the As in AX, XA, and A are identical.

Each pattern needs a unique representation, and since this is code golf, it should be as compact as possible.

Because the mega-characters have a fixed height of 5, but are not fixed-width, the patterns are defined principally by columns.

First, each of the symbols in the pattern are converted to a single base-5 digit, where _/\| respectively correspond to 0-4, and other symbols are treated as spaces.

   _   
  / \  
 / _ \ 
/ ___ \
_/   \_

0001000
0020300
0201030
2011103
1200032

Then, the 5 base-5 digits in a column are combined to make a single base-5 number.

00021, 00202, 02010, 10110, 03010, 00303, 00032

Represented in decimal, the column numbers are 11, 52, 255, 655, 380, 78, 16.

These numbers must be combined into one number that identifies the pattern. The correct way would be to concatenate all of the base-5 numbers (or, equivalently, to treat the list of column numbers as a base-3125 number).

As this is code-golf, the correct way will not be used, due to a bug that happened to not break stuff for this set of patterns and is now considered a byte-saving feature.

Thus, the column numbers are combined into one number that identifies the pattern:

   11 * 5^6
+  52 * 5^5
+ 255 * 5^4
+ 655 * 5^3
+ 380 * 5^2
+  78 * 5^1
+  16 * 5^0

= 585531

Now, these numbers are inserted into a giant lookup table, along with 0 for :

{
  0: " ",
  585531: "A",
  591231: "A",
  // ...
}

At this point, the table could be serialized and plopped into the code, but it is not very golfy. Thus, this explanation branches into two parts: matching the patterns and compressing the lookup table.

Matching the Patterns

Matching the patterns is fairly simple. First, the input is split into paragraphs; each paragraph is a line of mega-text. The paragraphs/mega-lines are converted independently, and then joined again with newlines.

Each mega-line is first converted into an array of column numbers:

  ____ ___  ____  _____    ____  ___  _     _____ 
 / ___/ _ \|  _ \| ____|  / ___|/ _ \| |   |  ___|
| |  | | | | | | |  _|   | |  _| | | | |   | |_   
| |__| |_| | |_| | |___  | |_| | |_| | |___|  _|  
 \____\___/|____/|_____|  \____|\___/|_____|_|

[
  120, 253, 746, 756, 756, 871, 253, 746, 756,
  746, 377, 624, 626, 746, 756, 746, 377, 624,
  626, 771, 781, 856, 756, 504,   0, 120, 253,
  746, 756, 771, 776, 624, 253, 746, 756, 746,
  377, 624, 626, 621,   6,   6,   6, 624, 626,
  729, 780, 770, 750, 500
]

Then, this array is iterated across; for every number in the array:

1. If this number is in the lookup table, add the corresponding character to the string and continue iteration.
2. Multiply the number by 5, and add the next number in the array. Go to #1, and repeat until the number matches or there are no numbers left.

Note that it searches for a character starting at every column, regardless of the previous matches. Additionally, the only way it finds no character starting at a column is if it exhaustively checks all possible ending columns to the end of the array, completely ignoring the fact that no patterns are longer than 12 columns.

After this highly inefficient process completes, the string will be CODE GOLF.

Compressing the Lookup Table

If the lookup table were simply serialized, it would be a whopping 23,094 bytes, which is clearly unacceptable.

The lookup table is transformed as follows:

Original:
  0: " "
  12: A
  63: B
  209: A
  1040: C
  30: A
  512: C

Sorted:
  0: " "
  12: A
  30: A
  63: B
  209: A
  512: C
  1040: C

Difference from last:
  +0: " "
  +12: A
  +18: A
  +33: B
  +146: A
  +303: C
  +528: C

Final (numbers are encoded in base 36):
  " 0AcAiBxA42C8fCeo"

The final string is:

 0JiivI1d5JysyKgx0X5qyZegzZfZ9mtZfO3288Q9CboCfG28CkO29Q9J1bg3N2d9pLh0dLfL2sLdwH14uLwdU1b4LkyYbbwY1Y2YhY1fjY1Y2YhY1fjY1Y2YhL3nfY126Y1Y2YhY20dY1Y2YhY1fjY1Y2YhR173PjP2P2P7RgjPjP2Fc6FsFtF1rDpcDhdB1ptBhdExgEfE2sSelvS6ySdwJ5wiSr3S6ySdwJaq4Jc21T8zaT1TrT2kA28bA2sAdwT3vT1TrT2kA1ufA1w2TwcT1TrT2kT1xlT1TrT2kA7ccTv58T1TrT2kT1crT1TrT2kT83tT1TrT2kT1crT1TrT2kO48kQ9CboCfG28CkO29Q9AvrtiA2sAdwA21mA1w2AacxM6z18A2cpp6A2sAdwA21mA1w2AacxA7yngA2sAdwA21mA1w2AacxA1ukibA2sAdwA21mA1w2AacxV1brpkV3V4VdV105jV3V4VdV2e9V3V4VdV105jV3V4VdV4md1V3V4VdV105jV3V4VdAruayA2sAdwA21mA1w2AacxAgc25A2sAdwA21mA1w2AacxWozq07rW3W4WdW3hl3vW3W4WdW8de5W3W4WdW3hl3vW3W4WdWg1p5dW3W4WdW3hl3vW3W4Wd

I haven't done much kolmogorov-complexity, so if anyone has ideas on how to compress this further, I'd love to hear them.