Lengthy numbers type A : remove all occurrences of length

Question

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 code-golf, 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.

I assume 2244668810121416182022 is falsy because you can't leave the leading 22 until the end? — Neil, Nov 16, 2022 at 23:10
@Neil 2244668810121416182022 is falsy because both 22 have to be removed first then the 0 remains at the end — AZTECCO, Nov 16, 2022 at 23:24
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. — Kevin Cruijssen, Nov 17, 2022 at 7:49
@Ismael Miguel I changed the example hope is clear now, sorry for being not clear as needed — AZTECCO, Nov 17, 2022 at 12:30

Neil · Accepted Answer · 2022-11-16 23:16:00Z

7

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.

answered Nov 16, 2022 at 23:16

Neil

166k12 gold badges69 silver badges273 bronze badges

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

Add a comment |

Jonah · Accepted Answer · 2022-11-17 05:36:40Z

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.

G B · Accepted Answer · 2022-11-18 09:34:55Z

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.

coltim · Accepted Answer · 2022-11-21 18:51:36Z

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

you can save 2 bytes constructing the indices with a sliding window: ~#{x@i^/(n~/:x@)#(#n:$#x)':i:!#x}/ — Traws, Nov 20, 2022 at 16:31
Thanks! Building off that I was able to trim another byte with ~#{x@i^/(#n:$#x)#[n~x@;]':i:!#x}// — coltim, Nov 21, 2022 at 18:46

hakr14 · Accepted Answer · 2022-11-17 06:39:44Z

2

Mathematica, 114 bytes

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

View it on Wolfram Cloud!

answered Nov 17, 2022 at 6:39

hakr14

4,9641 gold badge10 silver badges18 bronze badges

Add a comment |

Julian · Accepted Answer · 2022-11-17 07:28:19Z

2

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!

edited Nov 17, 2022 at 7:28

answered Nov 17, 2022 at 5:33

Julian

2,6886 silver badges16 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-11-17 08:37:19Z

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.

Neil · Accepted Answer · 2022-11-17 10:03:19Z

Charcoal, 23 bytes

Ｗ⌕ＡθＩＬθ≔Φθ¬⊙ＩＬθ№ι⁻λνθ¬θ

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

Ｗ⌕ＡθＩＬθ

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

≔Φθ¬⊙ＩＬθ№ι⁻λνθ

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

¬θ

Output whether the input was lengthy.

Arnauld · Accepted Answer · 2022-11-17 11:55:09Z

2

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!

edited Nov 17, 2022 at 11:55

answered Nov 17, 2022 at 2:22

Arnauld

188k20 gold badges171 silver badges631 bronze badges

Add a comment |

jdt · Accepted Answer · 2022-11-17 22:52:02Z

2

C (gcc), ¹⁵³ ¹⁴² 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!

edited Nov 17, 2022 at 22:52

answered Nov 17, 2022 at 16:34

jdt

3,4321 gold badge11 silver badges17 bronze badges

\$\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

Add a comment |

Jordan · Accepted Answer · 2022-11-17 15:23:29Z

1

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!

edited Nov 17, 2022 at 15:23

answered Nov 17, 2022 at 2:07

Jordan

9,7261 gold badge30 silver badges47 bronze badges

\$\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

Add a comment |

CursorCoercer · Accepted Answer · 2022-11-17 16:00:34Z

1

Pyth, 32 bytes

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

Try it online!

answered Nov 17, 2022 at 16:00

CursorCoercer

3,9779 silver badges18 bronze badges

Add a comment |

Kamil Drakari · Accepted Answer · 2022-11-17 19:36:12Z

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.

Stack Exchange Network

Lengthy numbers type A : remove all occurrences of length

Test cases

13 Answers 13

Retina, 16 bytes

J, 42 bytes

Ruby, 90 ... 65 bytes

How?

K (ngn/k), 36 33 bytes

Mathematica, 114 bytes

PowerShell Core, 144 bytes

05AB1E, 22 bytes

Charcoal, 23 bytes

JavaScript (ES6), 101 bytes

C (gcc), ¹⁵³ ¹⁴² 137 bytes

Ruby, 117 109 bytes

Pyth, 32 bytes

Japt, 26 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
decision-problem
or ask your own question.

Hot Network Questions

Lengthy numbers type A : remove all occurrences of length

Test cases

13 Answers 13

Retina, 16 bytes

J, 42 bytes

Ruby, 90 ... 65 bytes

How?

K (ngn/k), 36 33 bytes

Mathematica, 114 bytes

PowerShell Core, 144 bytes

05AB1E, 22 bytes

Charcoal, 23 bytes

JavaScript (ES6), 101 bytes

C (gcc), 153 142 137 bytes

Ruby, 117 109 bytes

Pyth, 32 bytes

Japt, 26 bytes

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

C (gcc), ¹⁵³ ¹⁴² 137 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
decision-problem
or ask your own question.