Fix the Meeesesessessesseesseessedessed upp teeexexextext

Question

This is inspired by Monday Mini-Golf #6: Meeesesessess upp teeexexextext

Background

ETHproductions have difficulty entering text on his usual webpage. Whenever he use digits or letters, the text will be meeesesessessesseesseessedessed up. Your task is to help him type so the normal behavior is achieved.

The transform

The transform affects runs of alphanumeric ([0-9A-Za-z]) characters delimited by any nonalphanumeric characters. In the following example, the first line would be transformed into the second (the other lines show the breakdown of the transform)

An12num:
Annn1n12n12nn12nn12nun12nun12numn12num
A
 nn
   n1
     n12
        n12nn12n
                n12nun12nu
                          n12numn12num

In particular, any alphanumeric character after the first in a run will be transformed into the entire run so far except for the first character. Furthermore, if the character is a letter (as opposed to a digit), the character will be turned into twice the run.

Thankfully, backspace will delete last character and also resets the beginning of the run.

Task

This time your task is not to perform the transformation. Instead, given an input string, you must return an encoded text that, if transformed, will result in the input. The output must be as short as possible, where \<char> counted as a single character.

Text is encoded as follows:

\                   -> \\
backspace character -> \b
linefeed            -> \n

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Test cases

Each test case is two lines, the first being input, the second output.

Heeeeeelp me. It shouldn't be messed up.
Hee \blp\b me\b. It\b sh\bou\bld\bn't be\b me\bss\bed\b up\b.

alert("Hello, world!");
al\ber\bt("He\bll\bo, wo\brl\bd!");

1223234234523456
123456

Answer 1

CJam, 207

{_,1>{:E1<_0{:I2$,+E=:C+:R1>C'9>)*+:P,E,<{EP#{L0}{PRI)1}?}{PE#L{R8cP,E,-*+}?0}?}g}&}:U;LqS+'a+{_'[,_el^A,s+&,V={+}{s\V!:V{L{:BU_aL?B,,1>Bf{_2$<U_{_W=8>S8c+*+\@>j+}{?;}?}+{,}$0=}j}|\}?}%s'\8cN++'\"\bn"f+er-2<

Try it online

Explanation:

Almost forgot to write this :p

The problem is solved in several steps:

• the text is separated into runs of alphanumeric characters (let's call them words) and runs of non-alphanumeric characters (non-words)
• non-words are printed as they are, and words are fixed
• fixing a word is done recursively (with memoization): split the word into 2 chunks in every possible way (including empty 2nd chunk), try to unmess the first chunk (see below), fix the 2nd chunk and join the results with a space-backspace if needed; take the shortest sub-solution
• unmessing a chunk means finding a minimal string of alphanumeric characters possibly followed by some backspaces (but with no backspaces in the middle) that when messed up, result in the given chunk; it is done with a simple greedy algorithm, going from left to right, building the unmessed string and its messed version in parallel, and determining the next needed character at each step; some chunks can not be unmessed