Build a replacement ball in regex.
In this challenge you will take a number $n$ and a string $X$ of length $\geq n$, and produce a regular expression which matches all strings that are withing $n$ character substitutions of $X$.
Specifically you will take $X$ and $n$ and ouptut all the ways to replace exactly $n$ characters with the regex wildcard ., separated by the regex or symbol |. So for bar and 2 as an input a valid output would be:
..r|.a.|b..
Order doesn't matter, but each replacement should appear exactly once, and no additional symbols should appear. Other regular expressions may perform the same task, but your output should meet the specifications above.
You can assume the input will consist only of the alphanumeric characters a-zA-Z0-9.
This is code-golf, the goal is to minimize the size of your source code as measured in bytes.
Test cases
o, 1 -> .
at, 1 -> .t|a.
moon, 1 -> .oon|m.on|mo.n|moo.
at, 2 -> ..
bar, 2 -> ..r|.a.|b..
test, 2 -> ..st|.e.t|.es.|t..t|t.s.|te..
case, 2 -> ..se|.a.e|.as.|c..e|c.s.|ca..
test, 3 -> ...t|..s.|.e..|t...
Ruby, 82 bytes ```ruby ->w …
1y ago
Haskell + hgl, 30 bytes ``` …
1y ago
Vyxal, 62 bitsv2, 8 bytes …
1y ago
3 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
Haskell + hgl, 30 bytes
ic"|"<<tv(:".")><fl<ce '.'><eq
Explanation
This performs a cartesian product to get all possible ways to replace characters with .. It then filters for those that have exactly $n$ .s, and concatenates them with |s.
Alternative version
(ic"|"<ic"."<<mm tl)<<mp"?"><pST<eL<P1
This version is much longer, but in my opinion it has better potential to be shorter than the above version if hgl were improved.
Explanation
This adds a dummy character ? to the front of the list then gets all ways to partition that list, and filters the list down to those that have $n+1$ parts. Then it takes removes the first character of each partition, and concatenates them back together with . as the separator. Finally it concatenates all those together with | as the separator.
Reflection
Reflections on the 30 byte version
-
ceandeqcould be combined into a single function which checks if an element occurs exactly $n$ times. This could actually be made to short circuit faster thanceandeqdo by default. - There should be a function that takes two elements and creates a list containing just those elements. This could be done in terms of free monoids. It would not save bytes here since
(:".")is so short, but it is close to being useful here.
Reflections on the alternative version
- There should be a function to partition a list into chunks of a certain size.
- I could really use
m4both as a prefix or an infix here. - Here I do a two dimensional intercalation using two
ics. There could be a builtin that does this.
0 comment threads
Ruby, 82 bytes
->w,n{[*0...w.size].permutation(n).map{e=w*1;_1.map{|x|e[x]='.'};e}.uniq.join '|'}
uses permutation to do most of the work. Might be shorter with something recursive, maybe.
0 comment threads
Vyxal, 62 bitsv2, ~8 bytes
ẏḋ\.vȦ\|j
Really 7.75 bytes, but leaderboard regex is a thing.
Explained
ẏḋ\.vȦ\|j
ẏ # Range [0, len(X))
ḋ # n-length combinations of X without replacement
\.vȦ # for each combination c:
# replace the item in X at each index in c with "." - basically double vectorised assignment
\|j # join that on "|"s
0 comment threads
0 comment threads