| Bytes | Lang | Time | Link |
|---|---|---|---|
| 198 | Excel ms365 | 250723T122140Z | JvdV |
| 120 | Perl 5 Mntheory=all p | 250723T134938Z | good old |
| 135 | JavaScript ES6 | 250720T001936Z | Arnauld |
| 074 | Charcoal | 250719T210528Z | Neil |
| 194 | jq | 250721T124224Z | GammaFun |
| 019 | 05AB1E | 250721T083416Z | Kevin Cr |
| 018 | Jelly | 250720T172339Z | Jonathan |
| 383 | Python3 | 250719T160138Z | Ajax1234 |
Excel ms365, 198 bytes
=LET(f,REGEXREPLACE,g,SORTBY,s,g(A.:.A,-LEN(A.:.A)),d,REDUCE(,s,LAMBDA(x,y,TOCOL(IF(REGEXTEST(x,y),x,f(HSTACK(x&0&y,y&0&x),"(.*)0\1","$1")),3))),REDUCE(@g(d,LEN(d)),s,LAMBDA(a,b,f(a,b,"\u$0",1,1))))
Perl 5 -Mntheory=:all -p, 120 bytes
$x=$_;forperm{$_='';for$s(@a[@_]){$S=$s;/$/;s/.{$+[0]}\K/chop$S/e until s/$s/\u$&/i}$_=$x=length$x>y///c?$_:$x}@a=/\w+/g
Looks like it's waste of time to try to avoid checking all permutations.
Input is lowercase, single line, with any non-word separators between words. More readable:
$x = $_;
forperm {
$_ = '';
for $s ( @a[ @_ ]){
$S = $s;
/$/;
s/.{$+[0]}\K/chop$S/e until s/$s/\u$&/i
}
$_ = $x = length $x > y///c ? $_ : $x
} @a = /\w+/g
JavaScript (ES6), 135 bytes
Expects a list of words in title case.
f=(a,p=o=0)=>a.map(w=>f(a.filter(W=>W!=w),(p+0+w).replace(/(.?(.*))(?:(.*)0\1$|0\1)/i,(_,a,b,c)=>[w[-!a]]+b+[c])))+a||p[o.length]?o:o=p
Method
For each permutation \$[w_1,w_2,\dots,w_n]\$ of the input list:
- we start with an empty string \$p\$
- for each word \$w_i\$, we do \$p\gets p\oplus w_i\$
Where the operator \$\oplus\$ will either:
If a full occurrence of \$w_i\$ already exists anywhere in \$p\$ (case insensitive):
→ capitalize the leading letter of \$w_i\$ in \$p\$
Example: \$``\text{Clocks"}\oplus``\text{Lock"}=``\text{C}\color{red}{\text{L}}\text{ocks"}\$
If \$p\$ ends with a prefix of \$w_i\$ (case insensitive):
→ capitalize the leading letter of \$w_i\$ in \$p\$ and append the missing letters
Example: \$``\text{Fish"}\oplus``\text{Shrimp"}=``\text{Fi}\color{red}{\text{S}}\text{h}\color{red}{\text{rimp"}}\$
Otherwise:
→ append \$w_i\$ to \$p\$ (standard concatenation)
Example: \$``\text{Cat"}\oplus``\text{Dog"}=``\text{Cat}\color{red}{\text{Dog}}\text{"}\$
The output is the shortest \$p\$.
Implementation of \$\oplus\$
(p + 0 + w) // we work on the concatenation of p, "0" and w
.replace( //
/(.?(.*))(?:(.*)0\1$|0\1)/i, // /(.?(.*)) capture a reference substring in p
// with the leading letter apart
// (?: followed by either:
// (.*) an optional padding string,
// 0 the separator,
// \1 the reference substring,
// $ the end of the string
// (i.e. the reference substring is
// a full occurrence of w)
// | or:
// 0 the separator,
// \1 the reference substring
// (i.e. the reference substring is
// a suffix of p and a prefix of w)
// )/i case insensitive
( //
_, // the full match is ignored
a, // a = ref. substring
b, // b = ref. substring without its leading letter
c // c = padding string
) => //
[w[-!a]] + // if a is not empty, append the leading letter
// of w (which is capitalized)
b + // append the other letters of the ref. substring
[c] // append the padding string
// (or an empty string if undefined)
) //
Charcoal, 99 74 bytes
WS⊞υι≔Συη≔⟦ω⟧θFθ¿⬤υ№ικF‹LιLη≔ιηFΦυ¬№ικFLκ«F⁼…κλ✂ι⁻Lιλ⊞θ⁺ι✂κλ»⭆η⎇⊙υ⁼κ⌕ηλ↥ιι
Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated lower case strings. Explanation:
WS⊞υι
Read in the inupt list.
≔Συη
Assume the worst case that the solution is the concatenation of the input.
≔⟦ω⟧θFθ
Start a breadth-first search for a solution from the empty string.
¿⬤υ№ικ
If the current string contains all of the input words, then...
F‹LιLη≔ιη
... if it is the shortest so far then make it the current solution.
FΦυ¬№ικ
Otherwise, loop through the words that aren't contained by the current string.
FLκ«
Loop through all of the potential overlap positions of the word with the end of the string.
F⁼…κλ✂ι⁻Lιλ⊞θ⁺ι✂κλ
If the word overlaps the string then add the result to the search list.
»⭆η⎇⊙υ⁼κ⌕ηλ↥ιι
Output the shortest string, but capitalise every letter that is the first occurrence of any word on the list.
Edit: Saved 20 bytes by only considering overlaps at the end of the string and a further 5 bytes by calculating the overlap more efficiently.
jq, 194 bytes
def p:.[]as$x|[$x]+(.-[$x]|p//[]);[p|reduce.[]as$x("";[.+$x[range(length;-1;-1):]|select(ascii_downcase|contains($x))][0]|sub("(?<m>\($x))";($x[:1]|ascii_upcase)+.m[1:];"i"))]|sort_by(length)[0]
Ungolfed:
def permutations:
.[] as $first | [$first] + (. - [$first] | permutations // []);
[ permutations | reduce .[] as $word ( # for each permutation, fold:
""; # starting with empty string
[
. + $word[range(length;-1;-1):] # append "", "d", "rd", "ord", "word"
| select(ascii_downcase|contains($word)) # filter to when the full word appears
][0] # get first (i.e. shortest)
| sub(
"(?<m>\($word))"; # capture word as .m
($word[:1] | ascii_upcase) + .m[1:]; # uppercase first letter
"i" # match case insensitively
)
)] | sort_by(length)[0] # shortest final string
The inner [ .. ][0] seems like it should be able to be removed, but it can't. This is because reduce iterates with the last object generated, rather than every one.
05AB1E, 19 bytes
œJJæé.ΔIåP}ÐIk©èu®ǝ
Based on @JonathanAllan's Jelly answer, but even slower. 😅
Input-list of words in full lowercase.
A slightly faster approach (replacing œJJæé with S©ε®N>.Æ}€`J) that is able to output most individual test cases (although it's still pretty slow, and still won't be able to output the first two test cases..):
S©ε®N>.Æ}€`J.ΔIåP}ÐIk©èu®ǝ
Explanation:
œ # Get all permutations of the (implicit) input-list
J # Join each inner list of words together
J # Then join everything together to one large string
æ # Get the powerset of this
é # Sort it by length (shortest to longest)
.Δ # Pop and find the first/shortest that's truthy for:
å # It contains as substrings
P # all
I # the input-words
}Ð # After we've got our shortest string: triplicate it
I # Push the input-list of words
k # Get the index of each word in the top copy
© # Store those indices in variable `®` (without popping)
è # Pop another copy, and get the characters at those indices
u # Uppercase each character
®ǝ # Insert them back into the string at indices `®`
# (after which the result is output implicitly)
Jelly, 18 bytes
FṗⱮL$ṚẎẇ@ⱮÞ⁸ṪŒuwⱮ¦
A (very inefficient!) monadic Link that accepts a non-empty list of non-empty lists of lowercase characters and yields a list of characters.
Try it online! (Although there's not much point trying more than seven total characters!)
How?
FṗⱮL$ṚẎẇ@ⱮÞ⁸ṪŒuwⱮ¦ - Link: list of lists of lowercase characters, Words
F - flatten {Words} -> Chars
$ - last two links as a monad - f(Chars):
L - length
Ɱ - map with:
ṗ - Cartesian power
-> [All length N strings using Chars for N in [1..length(Chars)]]
(duplicates abound with duplicated characters in Chars)
Ṛ - reverse
Ẏ - tighten
Þ - (stable) sort (these Strings) by:
Ɱ ⁸ - map across Words with:
ẇ@ - sublist {Word} exists in {String}?
Ṫ - tail
-> a shortest string containing all Words
¦ - sparse application...
Ɱ - ...to indices: map with:
w - {String} first index of sublist {Word}
Œu - ...apply: convert to uppercase
Python3, 383 bytes
S=str.capitalize
L=str.lower
def f(w):
q,r=[(S(i),w-{i})for i in w],[]
for a,b in q:
if not b:r+=[a];continue
q+=[(a[:(O:=-max(i for i in range(len(j)+1)if L(a[(-i or len(a)):])==j[:i])or len(a))]+''.join(A if u==0 or u>=len(a[O:])else a[O:][u]for u,A in enumerate(S(j)))if(J:=L(j))not in L(a)else a[:(I:=L(a).index(J))]+S(a[I])+a[I+1:],b-{j})for j in b]
return min(r,key=len)
