13
\$\begingroup\$

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 . 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
\$\endgroup\$
9
  • 2
    \$\begingroup\$ Suggested test case: aabaabaa -> abaa or aaba. \$\endgroup\$
    – Neil
    Jul 16 '20 at 17:25
  • 2
    \$\begingroup\$ I'm thinking of how one might score well without golfing the actual task. I'd want a language with a char that ignores the next char including another of itself, and also a no-op char. Anyone got one? Call _ the ignore-next and n the no-op. Make an eraser string _n_a_b_c where a,b,c are minimal distinct chars needed. By inserting into itself as _n_a__?_a_b_cb_c, we can reduce to just b, and likewise any chars. This lets us make any program be erased by this string. \$\endgroup\$
    – xnor
    Jul 17 '20 at 0:45
  • \$\begingroup\$ @xnor Well lenguage can score 1 on this challenge, if you are looking for a language. And I would think that glypho could probably score pretty low too, maybe 2 or 3. But as for your schema I think klein should fit the bill with ! as the skip and . as the noop. \$\endgroup\$
    – Wheat Witch
    Jul 17 '20 at 1:53
  • 1
    \$\begingroup\$ @Jonah ibiibibii doesn't work if you remove only the last one. It is an eraser if there is any way to do it. \$\endgroup\$
    – Wheat Witch
    Jul 17 '20 at 3:36
  • 7
    \$\begingroup\$ The quest for a unary answer begins... \$\endgroup\$
    – FlipTack
    Jul 17 '20 at 17:38
13
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ 24B: +eval('%c'*3%(32,49,32)) (will prove later) \$\endgroup\$
    – DELETE_ME
    Jul 21 '20 at 8:31
  • \$\begingroup\$ 20B: +1,eval(bytes([57])) seems to work too. \$\endgroup\$
    – DELETE_ME
    Jul 21 '20 at 8:41
  • 1
    \$\begingroup\$ That 20B solution can be ported to JavaScript -- but String.fromCharCode is significantly longer. \$\endgroup\$
    – DELETE_ME
    Jul 21 '20 at 9:03
4
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ Can't you replace .substr(0,i) with slice(0,i)? And remove var ? \$\endgroup\$
    – GirkovArpa
    Jul 21 '20 at 17:37

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.