Writing erasable code

Question

My phone number (which I will not be sharing here) has a neat property where there is a two digit number, which when iteratively removed from my phone number will eventually remove all the digits. For example if my phone number were

abaababbab

Then by repeatedly removing ab we would eventually get nothing (I encluse the string I am removing in brackets to make it clear)

abaababb[ab]
abaab[ab]b
aba[ab]b
ab[ab]
[ab]

Now to generalize this property lets have any string. A "minimal eraser" of that string will be the smallest substring such that if iteratively removed it will eventually make the string empty.

Some examples at the bottom.

Task and Scoring

Warning: This challenge is not code-golf. Do not assume it is without reading the scoring

Your challenge will be to take a string as input and output a minimal eraser of that string.

Your answers will be scored by taking them as a string of bytes and calculating that string's minimal eraser. The length in bytes of that eraser is your score, with lower being better.

Your answer must support strings containing all printable ascii plus any characters that appear in your program.

Test cases

abaababbab -> ab
baababbab -> baababbab
baababab -> baababab
echoecho -> echo
ototoo -> oto
ibiibibii -> ibi
aabaabaa -> abaa / aaba

Answer 1

Python 3, score ^{... 48 29} 20

+1,eval(bytes([57]))

A completely different approach from the last 2 versions (and also result in manageable generated program). Check out the revision history for some (possibly) interesting ideas.

---

Given an arbitrary Python program:

print(1)

it can be transformed, without changing the behavior:

exec("print(1)")

eval(rb'exec("print(1)")')

eval(bytes([101, 120, 101, 99, 40, 34, 112, 114, 105, 110, 116, 40, 49, 41]))

The number list is getting long, so I'll use a shorter list for demonstration. Note that only printable ASCII characters can appear in the string representation and the first character is e, so the first number is 101 and all numbers are at least 32.

eval(bytes([101, 32, 32]))

Rewrite the first number to 57+1+1+1+...+1+1+1, the rest into 9+1+1+...+1; then add some ,9 at the end of the list. This is always possible because of the conditions mentioned before, and the program's behavior is unchanged because the byte 9 is \t, a whitespace character.

eval(bytes([57+1+1+...+1, 9+1+1+...+1+1, 9+1+1+...+1, 9, 9,..., 9]))

The number of ,9 added must satisfy that the total number of 9s is equal to the number of +1.

Then replace all the 9 with eval(bytes([57]), and prepend +1,.

+1,eval(bytes([57+1+1+...+1,eval(bytes([57])+1+1+...+1+1,eval(bytes([57])+1+1+...+1,eval(bytes([57]),eval(bytes([57]),...,eval(bytes([57])]))

Done! It's easy to see that this string has the eraser string +1,eval(bytes([57]).

---

It's trivial to see that there exists a Python snippet that solves the given problem.

g=lambda s, e: not s or any(
	s[i:].startswith(e) and g(s[:i]+s[i+len(e):], e)
	for i in range(len(s)-len(e)+1))
f=lambda s: min((s[i:j] for j in range(len(s)+1) for i in range(j) if g(s, s[i:j])), key=len)
print(f(input()))

Try it online!

Answer 2

Brachylog, 23 bytes, score 23

Rather boring, as it doesn't have a non-trivial eraser.

{|~c₃↺↔At.l>0∧Akc↰}ᶠlᵒh

Try it online! or verify the other test cases (split in two, so TIO doesn't time out.)

How it works

{|~c₃↺↔At.l>0∧Akc↰}ᶠlᵒh
{                 }ᶠ     Find all outputs for the implicit input, that …
 |                        either is itself or …
  ~c₃                     split into three groups in every possible way
                           [,,AAABBB],[,AA,AABB],[AAA,B,BB],[AA,AB,BB] etc. …
     ↺↔                    with the middle moved to the back [AA,BB,AB] …
       A                   assign to A
        t.                 the tail AB is the output of this predicate
          l>0              and its length is greater than 0.
             ∧Ak          Also, [AA,BB] …
                c          concatenated AABB …
                 ↰         used in a recursive call
                           has the same output as this predicate: AB.
                     lᵒh Order all possible erasers by length, take first

Answer 3

Javascript, 228 bytes, score 228

Naive solution I guess:

(r,d)=>{w=0;l=r.length;for(var i=0;i!=-1&&i<l;){i=r.indexOf(d,i);w=w||((i<0)?0:t(r.substr(0,i)+r.substr((i++)+d.length,l),d))}return !r?1:w}
f=a=>{n=a.length;for(p=1;p<=n;p++)for(i=0;i<=n-p;i++)if(t(a,b=a.substr(i,p)))return b}

Try it online!