Find acronym-like words in a sentence

Question

Let's say you have a sentence like:

this is a very long sentence with several words of no significance

It contains only the 26 lowercase letters of the alphabet and spaces.

And you have a dictionary, where each word contains any number of the 26 lowercase letters and nothing else:

henge
renton

Then the output should contain, among others:

• tHis is a vEry long seNtence with several words of no siGnificancE
• tHis is a vEry long senteNce with several words of no siGnificancE
• this is a veRy long sENTence with several wOrds of no significaNce

So, every line of the output is the original sentence, but if only the uppercase letters of a line are taken, they should form a dictionary word. The program should find all possible such lines.

Answer 1

JavaScript, 474 bytes

k=((e,r)=>{for(o=[],e=[...e],r=[...r],w=r.reduce((r,h,n)=>!(r[n]=e.map((e,r)=>h==e?r:"").filter(Number))||r,[]),[z]=w,h=[],x=0;x<w.reduce((e,r)=>e*=r.length||e,1);x++)z.forEach((e,r)=>{for(g=[z[r]],j=1;j<w.length;j++)for(n=w[j],y=0;y<n.length;y++)if(g.slice(-1)[0]<n[y]&&!h.some(e=>e.toString()==[...g,n[y]].toString())){g.push(n[y]);break}h.push(g)});return h.filter(e=>e.length==w.length).forEach(r=>{d=[...e],r.forEach(e=>d[e]=d[e].toUpperCase()),o.push(d.join(""))}),o})

Live example:

k=((e,r)=>{for(o=[],e=[...e],r=[...r],w=r.reduce((r,h,n)=>!(r[n]=e.map((e,r)=>h==e?r:"").filter(Number))||r,[]),[z]=w,h=[],x=0;x<w.reduce((e,r)=>e*=r.length||e,1);x++)z.forEach((e,r)=>{for(g=[z[r]],j=1;j<w.length;j++)for(n=w[j],y=0;y<n.length;y++)if(g.slice(-1)[0]<n[y]&&!h.some(e=>e.toString()==[...g,n[y]].toString())){g.push(n[y]);break}h.push(g)});return h.filter(e=>e.length==w.length).forEach(r=>{d=[...e],r.forEach(e=>d[e]=d[e].toUpperCase()),o.push(d.join(""))}),o})

console.log(k('this is a very long sentence with several words of no significance', 'henge'));

Explanation:

For each letter in the word, an array of indices is constructed corresponding to every position of that letter in the sentence.

Then inside a nest of 4 for loops, every possible path from the first array to the last array is computed, where each step is into an element with greater numeric value in the next array.

This produces an array of paths whose length is equal to the maximum possible paths, which is the product of multiplying the length of each letter indices array (this number gets big real quick as the length of the word increases).

Then all paths whose length is smaller than the word are excluded, since they failed to find a valid step between each array.

You can see the unminified logic at this stackoverflow answer.

I am confused by this line (even though it's my code), whose intent is to check the existing paths before adding a step to the current path to make sure its constructing a unique path:

if (!paths.some(p => p.toString() == [...path, arrays[j][y]].toString())) {
  path.push(arrays[j][y]);
  break;
}

It seems to me like this should erroneously prevent construction of multiple paths who share any beginning steps. But it actually works as intended. So I am stumped.

Answer 2

Python 3, 169 bytes

a=lambda c,w:(([c[0]+k for k in a(c[1:],w)]+([c[0].upper()+k for k in a(c[1:],w[1:])]if c[0]==w[0]else[]))if c else[])if w else[c]
lambda c,d:sum((a(c,w)for w in d),[])

Takes as input the sentence as a string and the dictionary as a list of strings. Uses a recursive helper function a(c,w) to compute the output for each word in the dictionary at a time, then sums the lists together to get the final output. The helper function works through the sentence/word one character at a time, and has several cases:

1. No more characters in the word, return what's left of the sentence

2. No more characters in the sentence, return empty list

3. Characters left in both, return same results as a(c[1:],w), with c[0] prepended to each result.

4. Characters left in both, and beginning characters match, return (3.) in addition to a(c[1:],w[1:]), with c[0].upper() prepended to each result.

There's definitely a few bytes of savings to be had in the helper method; I wasn't being super careful with my parentheses around the inline if-expressions (and the precedence is slightly confusing) -- I might take a closer look tomorrow to see if I can shave off a few bytes.

Answer 3

Perl 5 -pF, 96 bytes

Takes the sentence as the first input and all subsequent inputs are treated as the dictionary. Could produce the strings in the reverse order for +1 byte. I still feel there's room to golf this...

$"=").*(";m#(@{[<>=~/./g]})(?{$a=%h=();$h{$_}++for@-;map$\.=$h{$a++}?uc:lc,@F})(?!)# while!eof}{

Try it online!

Explanation

This script uses Perl's regex engine to perform the matching.

First $" is set to ).*(, this is the separator that's used when lists are interpolated. A m//atch is then started (with # as the delimiter) which contains the current input dictionary word (<>), interpolated (@{[...]}) into the match as as a list (=~/./g). Example.

The next part of the m// operation is a zero-length code block. In here there is access to all the magic variables associated with regex ($&, $1, etc). $a and %h are initialised as empty (() - technically $a is set to the length, which is 0) and @-, which contains the start of each matched group, is used to populate the indices of %h with 1 (++) for the position of all the matches.

Finally, @F (which is automatically filled with the chars from the input via -F) is looped over while there's still input (!eof), checking %h's key $a (incremented for each char in @F) to see if it's truthy (1) or not (undef for missing key). If it's truthy uc returns (its operand, or $_ if none passed, which is set for each item in @F via map{...}@F) the item uppercased, otherwise lc returns it lowercased. This is appended to $\ which is implicitly output after anything is printed, which because -p is specified, will happen after the (implicit - from -p) input loop exits. Due to this, it's also necessary to break out of the surrounding loops with }{ so that we don't get an unmodified copy of the input printed too.