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


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)


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.


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!");

  • 6
    \$\begingroup\$ It's well defined, but why there's no answer? \$\endgroup\$
    – Xwtek
    Nov 2, 2015 at 9:34
  • 1
    \$\begingroup\$ Somehow I missed this; nice spin-off! Perhaps I'll try to write an answer later. \$\endgroup\$ Nov 2, 2015 at 16:06
  • \$\begingroup\$ This reminds me of the time a friend of mine sent text through UDP \$\endgroup\$
    – TRGWII
    Nov 22, 2015 at 10:15
  • 1
    \$\begingroup\$ I think your final test case needs a fix. You include the first character (1every time) in the runs. \$\endgroup\$ Nov 28, 2015 at 17:26
  • \$\begingroup\$ I honestly do not understand what I'm supposed to do... Sorry. Could you add some inputs and outputs and add some examples with the explaination? Sorry. \$\endgroup\$ Dec 3, 2015 at 20:28

1 Answer 1


CJam, 207


Try it online


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
  • 1
    \$\begingroup\$ Holy cow... that's one heck of a CJam program! Nice work. \$\endgroup\$ Feb 22, 2016 at 1:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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