15
\$\begingroup\$

Given a non negative integer number tell if it can be erased by repeatedly removing all occurrences of the length of that number from it including overlapping matches.

  • Erasing means cancel all its digits. For example the number 4440 is not lengthy because after removing all 4's you obtain 0 which cannot be erased.
    Neither the number 50022 or 50044 is lengthy A because you first remove 5 obtaining 0022 or 0044 and there's no way to cancel leading 0's.

Examples

3610106336 has 10 digits: remove 10's
36xxXX6336 -> 366336

366336 has 6 digits: remove 6's
3xx33x -> 333

333 remove 3's -> erased

Here an example with overlapping matches.

11111666661 has 11 digits

xxXX1666661  \ overlapping 11's
1XXxx666661  / 
We have 5 '1' for a total of 4 '11' matched, remove all


666661  -> remove 6's
1 -> and finally 1

Test cases

Truthy

1, 12, 21, 22, 123, 321, 322, 331, 333, 4441, 4444, 12345, 987654321, 3610106226, 1010101010, 11111111111, 10812816208148888188, 82428208832101683082414123828341883888,3919555395539111955255533922519455392511539551925395511, 1515515551555515555515555551555555155555155551555155151, 999199999915999991599999999915999915999999919399999999991915999999999999999999999915999999929999999, 10121111011011011011011011011011011012110110110121101110110121111011123101101101101121011011110110111, 15101251011012229752519101110101010101010111111101101101101101111011011011011110111101101101101101915, 2020220202202022020220202232020220202202022020223220232020222220220222202202202202202202202202202202202220223202202202202202202202202222022022022022022022222202202202202202222022022022022022023876543213

Falsy

0, 2, 9, 10, 11, 23, 233, 4440, 50022, 50044, 1101010101, 11131111311, 121666626162, 181811818128181818, 127271272722672224724122727122712242722472727272722472727272247272127272, 1001023010023100160010010010010061110250100123001001001230061001010100102370100610016001001001110230, 1241242212412241241241241241241241241241241241141624124114241241241242612412412416241222412411424221241244124142412412144124, 108484298442981044294284942984429844294291042942942942849429429484284948429484842942942984104842984429429844298448429429429429429429429428494294294842942942948429428484942942942942984429429844284948429428494842849484284942942942942942984484294294284942942942942942942942942942910429429484294294

This is , standard rules apply.

  • Input can be given in any convenient method.

  • Output any two different values telling if the number is lengthy or not lengthy.

\$\endgroup\$
18
  • 1
    \$\begingroup\$ I assume 2244668810121416182022 is falsy because you can't leave the leading 22 until the end? \$\endgroup\$
    – Neil
    Nov 16, 2022 at 23:10
  • \$\begingroup\$ @Neil 2244668810121416182022 is falsy because both 22 have to be removed first then the 0 remains at the end \$\endgroup\$
    – AZTECCO
    Nov 16, 2022 at 23:24
  • 6
    \$\begingroup\$ Maybe you can use a different example for the overlapping test case. Because even without overlap, 11111111111 is truthy, since removing 11 without overlap becomes 1, which we can then also remove. You may also want to change "from it ( including overlapping matches )" to "from it, including overlapping matches", since it's a pretty big part of the challenge and makes it for some languages quite a bit more tricky. \$\endgroup\$ Nov 17, 2022 at 7:49
  • 1
    \$\begingroup\$ @KevinCruijssen Thank you. That makes a lot more sense. \$\endgroup\$ Nov 17, 2022 at 12:00
  • 1
    \$\begingroup\$ @Ismael Miguel I changed the example hope is clear now, sorry for being not clear as needed \$\endgroup\$
    – AZTECCO
    Nov 17, 2022 at 12:30

13 Answers 13

7
\$\begingroup\$

Retina, 16 bytes

+~`^.*
v`$.&¶
^$

Try it online! Link includes test cases. Explanation:

^.*
v`$.&¶

Replace the input with a Retina program that erases all overlapping occurrences of its length from it. (Replacing overlapping matches can do weird things in Retina but fortunately only if the matches are variable length.)

~`

Execute that program on the input.

+`

Repeat the above until no more erasures can be made.

^$

Test whether the input was completely erased.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ falsy cases checked, Retina worked well on this \$\endgroup\$
    – AZTECCO
    Nov 17, 2022 at 1:23
  • \$\begingroup\$ @AZTECCO Whoops, I meant to include the falsy test cases too. Sorry about that. \$\endgroup\$
    – Neil
    Nov 17, 2022 at 9:37
5
\$\begingroup\$

J, 42 bytes

''-:(#~1-]+./@(-@i.@#@]|.!.0"{E.~)":@#)^:_

Try it online!

Handling overlaps made this awkward, and this was the shortest approach I could find.

Consider string input '82428208832101683082414123828341883888'.

The approach is to do the following until a fixed point:

  • Find all matches E. of the length within the input. This returns a boolean vector where the ones indicate the start of each match.

    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 
    

    But we need to mark every position of each match....

  • -@i.@#@] So we generate the numbers 0 1 ... <length of length> (in this case just 0 1) and then rotate our boolean vector right by each, creating copies of it:

    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0
    
  • +./ And sum the rows:

    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0
    
  • Finally we invert the mask and use that to filter the input:

    8242820883210168308241412283418888
    
  • ''-: Once the fixed point is reach, we just check if the final result is empty.

\$\endgroup\$
5
\$\begingroup\$

Ruby, 90 ... 65 bytes

->n{n.gsub!(/#{n.size.to_s[/(.*)(.*\1)\2*/]}(#$2)*/){}?redo:n<?0}

Try it online!

How?

To replace overlapping occurrences use the following regex to split:

/(.*)(.*\1)\2*/

This will always match the whole number that we are searching, but if some parts are repeated in an ABABABABA pattern, then the regex groups will capture A and BA. B will be empty if only A is repeated, and A will be empty if the pattern is not repeating.

So, now that we have captured A plus any number of occurrences of BA, we can use a new regex to find overlapping matches, we need to add (BA)* at the end:

/#{n.size.to_s[/(.*)(.*\1)\2*/]}(#$2)*/

Repeat until there is nothing left to substitute, then check if the string is empty.

Thanks AZTECCO and Dingus each for -1 byte ideas which put together brought the byte count down by 3.

\$\endgroup\$
0
3
\$\begingroup\$

K (ngn/k), 36 33 bytes

-2 bytes from @Traws' improvement, -1 more from tweaking more

~#{x@i^/(#n:$#x)#[n~x@;]':i:!#x}/

Try it online!

Takes input as a string. If it is okay to return empty lists for "Truthy" inputs, and non-empty lists for "Falsy" inputs, 2 bytes can be trimmed (the leading ~#).

  • {...}/ set up a converge-reduce, running the code in {...} until two successive iterations return the same value or the original input
    • (#n)#[...;]':i set up a stencil-apply, with a (#n) window size, applying #[...;] to each slice of i
      • i:!#x generate a list of indices of the input, storing in i
      • (#n:$#x) determine the string to remove, storing in n; calculate its length, and use that as the window size
      • #[n~x@;] filter each slice down to those that match the string to remove (n) (slices that do not match the string to remove become empty lists)
    • i^/ remove those indices
    • x@ index into the input, and (implicitly) return
  • ~# convert empty lists to 1, and non-empty lists to 0
\$\endgroup\$
2
  • 1
    \$\begingroup\$ you can save 2 bytes constructing the indices with a sliding window: ~#{x@i^/(n~/:x@)#(#n:$#x)':i:!#x}/ \$\endgroup\$
    – Traws
    Nov 20, 2022 at 16:31
  • 1
    \$\begingroup\$ Thanks! Building off that I was able to trim another byte with ~#{x@i^/(#n:$#x)#[n~x@;]':i:!#x}// \$\endgroup\$
    – coltim
    Nov 21, 2022 at 18:46
2
\$\begingroup\$

Mathematica, 114 bytes

StringReplacePart[#,"",List@@Interval@@StringPosition[#,ToString@StringLength@#,Overlaps->All]]&~FixedPoint~#==""&

View it on Wolfram Cloud!

\$\endgroup\$
2
\$\begingroup\$

PowerShell Core, 144 bytes

param($a)for(;($i=$a|% Le*)*($l-$i)){$a=-join$a[(($k=0..($l=$a|% Le*))|?{$_-notin($k|?{$a|% su* $_|% s*h "$l"}|%{$_..($_+"$l".Length-1)})})]}!$a

Try it online!

Takes the number as a string, returns $true or $false.
The timeout is caused by the "overlapping remove" that generates lots of strings in memory

So here is a version that does not timeout, calculating the array of characters to remove only once: Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 22 bytes

ΔÐgU.sRXδÅ?XgGDÁ~}_Ï}d

Port of @Jonah's J answer.

Outputs 0 for truthy and 1 for falsey.

Try it online or verify all test cases.

Explanation:

Δ         # Loop until the result no longer changes:
          # (using the implicit input-integer in the first iteration)
 Ð        #  Triplicate the current integer
  g       #  Pop one, and get its length
   U      #  Pop and store this length in variable `X`
  .s      #  Pop another one, and get a list of its suffices
    R     #  Reverse this list of suffices
      δ   #  Map over the list of suffices:
     X Å? #   Check which suffix starts with the length we stored in variable `X`
  X       #  Push the length from variable `X` again
   g      #  Get the length of that length
    G     #  Loop that length-2 amount of times:
     D    #   Duplicate the current list of 0s/1s
      Á   #   Rotate it once towards the right
       ~  #   Bitwise-OR the values at the same positions together
    }_    #  After the inner loop: invert all 1s/0s
      Ï   #  Only keep the digits in the integer at the truthy indices
}d        # After the changes-loop: check if what remains is a non-negative number
          # (resulting in 0 for the empty strings; 1 if any digits still remain)
          # (which is output implicitly as result)

Unfortunately 05AB1E lacks a builtin to get all indices of a match (it only has a builtin k for the first index of a match). Otherwise the .sRXδÅ? could probably have been a bit shorter.

PS: Without having to deal with overlapping matches, this could be 6 bytes instead: ΔDgK}d.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 23 bytes

W⌕AθILθ≔Φθ¬⊙ILθ№ι⁻λνθ¬θ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for lengthy, nothing if not. Explanation:

W⌕AθILθ

While there are overlapping matches of the inputs length in the input...

≔Φθ¬⊙ILθ№ι⁻λνθ

... filter out each character that matched at least one of the digits in the length.

¬θ

Output whether the input was lengthy.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 101 bytes

Returns a Boolean value.

f=s=>s==(s=s.replace(/./g,(c,i)=>[...q=s.length+''].some(_=>s.slice(i--).match('^'+q))?'':c))?!s:f(s)

Try it online!

Or 92 bytes by throwing an error if the input cannot be fully erased:

f=s=>s&&f(s.replace(/./g,(c,i)=>[...q=s.length+''].some(_=>s.slice(i--).match('^'+q))?'':c))

Try it online!

\$\endgroup\$
2
\$\begingroup\$

C (gcc), 153 142 137 bytes

-4 bytes thanks to AZTECCO

char*o,*a,b[999];k;z;d;f(i,n){a=i;o=b;for(z=k=0;*a;a++)atoi(strndup(a,d=log10(n)+1))^n?k<1?*o++=*a:k--:(z=1,k=d-1);*o=0;z=z?f(b,o-b):!n;}

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Nice work! You can save 4 Bytes by putting some initializations in arguments to built ins \$\endgroup\$
    – AZTECCO
    Nov 17, 2022 at 18:57
  • 1
    \$\begingroup\$ @AZTECCO, thanks! I'm sure that there are some more bytes to golf here. \$\endgroup\$
    – jdt
    Nov 17, 2022 at 19:50
1
\$\begingroup\$

Ruby, 117 109 bytes

-8 bytes thanks to AZTECCO

f=->s{a=*0...x=s.size
s.scan(/(?=#{x})/){a-=[*(y=$`.size)...y+x.to_s.size]}
s!=(x=a.map{s[_1]}*"")?f[x]:s>""}

Attempt This Online!

\$\endgroup\$
2
  • \$\begingroup\$ [Saved some ](ato.pxeger.com/…) , output negated \$\endgroup\$
    – AZTECCO
    Nov 17, 2022 at 3:39
  • 1
    \$\begingroup\$ @AZTECCO Nice work. Thanks! \$\endgroup\$
    – Jordan
    Nov 17, 2022 at 15:23
1
\$\begingroup\$

Pyth, 32 bytes

W&znz=sm*@zd.Amx>z-dklzl`lzlz;!z

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Japt, 26 bytes

_ðZl)rÈhXÊs îS Y}Z kS}gUÊN

Try it

Input is a string, output is an empty string for "truthy" or a non-empty string for "falsy". A version which specifically outputs "true" or "false" requires just an added flag. All test cases can be run here.

Explanation:

_ðZl)rÈhXÊs îS Y}Z kS}gUÊN
                         N # Starting with the input string as Z
_                    }gUÊ  # Repeat this process a number of times equal to its length:
 ð  )                      #  Find indices of this string:
  Zl                       #   The current length of Z
     rÈ         }Z         #  For each index Y apply this function to Z consecutively:
        XÊ                 #   Get the length of Z
          s                #   Turn it into a string
            îS             #   Replace each character with a space
       h       Y           #   Overwrite Z with that string starting at index Y
                   kS      #  Remove all spaces

This recursive alternative is a little longer, but I figured I would include it in case it has more room to golf.

\$\endgroup\$
0

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.