| Bytes | Lang | Time | Link |
|---|---|---|---|
| 091 | Python 3 | 241101T181713Z | nneonneo |
| 212 | C# Visual C# Interactive Compiler with /uSystem.Linq.Enumerable & /uSystem.String flags | 241031T143226Z | Kevin Cr |
| 007 | Vyxal | 241031T211535Z | emanresu |
| 011 | Vyxal 3 | 241031T184534Z | Ginger |
| 076 | Charcoal | 241031T171555Z | Neil |
| 012 | Japt | 241031T142655Z | Shaggy |
| 006 | Jelly | 241031T132440Z | Jonathan |
| 008 | 05AB1E | 241031T135413Z | Kevin Cr |
Python 3, 91 bytes
{t for i in range(len(d))for t in __import__("itertools").permutations(d,i)if"".join(t)==s}
Straightforward bruteforce. This is an expression which expects variables s (the word) and d (the wordlist) to already be defined, and produces the result as a set of tuples of strings.
The running time is horrendous; it's likely never going to finish the first test case, but it runs the rest pretty quickly.
C# (Visual C# Interactive Compiler) with /u:System.Linq.Enumerable & /u:System.String flags, 243 236 214 212 bytes
w=>d=>{var t=w.SelectMany((_,j)=>w.Skip(j).Select((_,k)=>w.Substring(j,k+1))).Where(d.Contains);return Range(0,1<<t.Count()).Select(i=>t.Where((_,j)=>(i&1<<j)>0)).Where(e=>Concat(e)==w&e.All(d.ToList().Remove));}
-7 bytes thanks to @jdt, changing the .Equals(w) to ==w (which unlike Java in which I usually program, is fine in C# when comparing strings specifically) and another
-22 bytes thanks to @jdt simplifying getting all valid substrings for variable t
-2 bytes thanks to @ceilingcat (removing the parenthesis from i&(1<<j) - I should have checked operation precedence..)
Explanation:
Explanation in pseudo-code:
- Generate all substrings of the given \$str\$, and only keep those that:
- occurs in list \$d\$ †
- Get all combinations of these substrings, and only keep those that:
- joined together without delimiter is equal to \$str\$
- all occur at least that many times in list \$d\$
w=>d=>{ // Method with string and string-array parameters,
// and IEnumerable<IEnumerable<string>> result
var t= // Create a temp list
// of all substrings of `w` that are present in `d`:
w.SelectMany( // Flat-map over the characters of `w`:
(_,j)=> // Only use the index within `w` as `j`:
w.Skip(j) // Take `w` without its first `j` characters
.Select( // Map over the remaining characters:
(_,k)=> // Again only use the index as `k`:
w.Substring(j,k+1))
// Take a substring of `w` starting at index `j` with a length of `k+1`
).Where( // After the flat-map, filter it by:
d.Contains);// Only leave substrings that are present in `d`
return // Then return all combinations of valid substrings
// where each valid substring is that many times available in `d`
// and which concatenated are equal to string `w`:
Range(0,1<<t.Count()) // Create the range [0,2 to the power the size of `t`):
.Select(i=> // Map those values to:
t.Where( // Use `t`, filtered further by:
(_,j)=> // Only use the index within `t` as `j`:
(i&1<<j)>0)) // Check whether (2 to the power `j`) bitwise-AND `i` is NOT 0
.Where(e=> // Then filter this list of substrings:
Concat(e) // Join them together without delimiter
==w // and check whether this equals the given `w`
& // And also check that `e` doesn't use an item in `d` too many times:
e.All( // Check that all currently used substrings
d.ToList().Remove));}
// can one by one successfully be removed from a copy of `d`
Sources:
Get all substrings of a string is taken as a simplified version of this. Which isNow golfed by @jdt toRange(0,w.Length).SelectMany(j=>Range(1,w.Length-j).Select(k=>w.Substring(j,k)))in my code.w.SelectMany((_,j)=>w.Skip(j).Select((_,k)=>w.Substring(j,k+1)))- Combinations of List is taken from here. Which is
Range(0,1<<t.Count()).Select(i=>t.Where((_,j)=>(i&1<<j)>0))in my code. - List intersection with duplicated items is taken from here. Which modified to an All-check is
e.All(d.ToList().Remove))in my code.
† Limitation: since C# uses unsigned integers by default and I use 1<<t.Count() in my code, the maximum amount of valid substrings it can handle is 30, which will become 1073741824. One higher 1<<31 would be -2147483648, which gives incorrect results with the Range. This is also why I've added the .Where(s=>d.Contains(s)) even though it's redundant with the later e.All(d.ToList().Remove) check, since it otherwise wouldn't be able to handle the larger test case wordbreakproblem, reducing the amount of substrings 136 to the amount of valid substrings 16, and it would also time out for test case choices, reducing the amount of substrings 28 to the amount of valid substrings 8.
Vyxal, 7 bytes
øṖ'⁰Þ∩⁼
Port of Jonathan Allan's Jelly answer
øṖ # Partitions
' # Where
⁼ # Remains the same under
⁰Þ∩ # (multiset) intersection with input
Vyxal 3, 11 bytes
It's certainly not a marvel of efficiency.
ṖᵛṢ1⁾Ω“¹=}u
Explanation
ṖᵛṢ1⁾Ω“¹=}u
Ṗ # Permutations of the dictionary
ᵛṢ1⁾ # Sublists of those permutations
Ω } # Filter sublists which:
“ # joined together,
¹= # equal the input word.
u # Only unique sublists.
💎
Created with the help of Luminespire.
Charcoal, 76 bytes
SθWS⊞υι≔⟦⟦⟦⟧υθ⟧⟧υFυ¿§ι²FΦ§ι¹∧⁼λ⌕§ι¹κ¬⌕§ι²κ⊞υ⟦⁺§ι⁰⟦κ⟧Φ§ι¹⁻μ⌕§ι¹κ✂§ι²Lκ⟧⟦⭆¹§ι⁰
Try it online! Link is to verbose version of code. Explanation:
SθWS⊞υι
Input the target string and list of words. (These bytes could be saved by taking the input in JSON format.)
≔⟦⟦⟦⟧υθ⟧⟧υFυ
Start a breadth-first search with no words found so far, all of the words remaining, and the entire string remaining.
¿§ι²
If there is still string left to match, then...
FΦ§ι¹∧⁼λ⌕§ι¹κ¬⌕§ι²κ
... filtering on those words that are unique prefixes of the remainder, ...
⊞υ⟦⁺§ι⁰⟦κ⟧Φ§ι¹⁻μ⌕§ι¹κ✂§ι²Lκ⟧
Add the current word to the match list, remove one instance of it from the word list, remove it from the start of the string, and push the result to the search list.
⟦⭆¹§ι⁰
Otherwise, pretty-print the matched words.
Japt, 12 bytes
à cá fȬ¶VÃâ
à cá fȬ¶VÃâ :Implicit input of dictionary array U & target string V
à :Combinations of U
c :Flat map
á : Permutations
f :Filter
È :Through the following function
¬ : Join
¶V : Equal to V?
à :End filter
â :Deduplicate
Jelly, 10 6 bytes
ŒṖœ&ƑƇ
A monadic Link that accepts the target on the left and the word list on the on the right and yields a list of lists of words.
Try it online! (Footer prints each on its own line, space separated)
Or see the test-suite.
How?
ŒṖœ&ƑƇ - Link: Target; Wordlist
ŒṖ - all partitions of {Target}
Ƈ - keep those for which:
Ƒ - is invariant under?:
œ& - {Potential} multiset intersection {Wordlist}
05AB1E, 8 bytes
.œʒI1.;P
Inputs in the order \$str,d\$.
Pretty slow for large \$str\$, but it's still able to do all test cases simultaneously in about 35-40 seconds on TIO.
Try it online or verify all test cases.
Explanation:
.œ # Get all partitions of the first (implicit) input-string `str`
ʒ # Filter this list of partitions by:
I # Push the input-list `d`
1.; # Replace each first occurrence of a value in `d` in the current
# partition by a 1
P # Product, to check if all parts in the partition are now 1s
# (after which the remaining partitions are output implicitly as result)