You are given a string \$s\$ of characters from a to z. Your task is to count how many unique strings of length \$n\$ you can make by concatenating multiple prefixes of the string \$s\$ together.
Since the result can be superlative you can either choose to output the whole result, the result mod \$2^{32}\$ or the result mod \$2^{64}\$.
This is code-golf, shortest code wins.
Tests:
aaaaa 8 -> 1
abcdef 10 -> 492
aerodynamics 10 -> 507
disbelief 10 -> 511
rJᵐ#rj@au#
rJᵐ#rj@au#
rJᵐ# Ordered integer partition
r Range each
j Concatenate
@ Nth (vectorized)
au# Count unique results
Expects (s)(n), where s is given as an array of characters.
s=>g=(n,q=t=0)=>s.map(c=>q[n]?g[q]||=++t:g(n,q+=c))|t
s => // outer function taking s[] = input string
g = ( // inner recursive function taking:
n, // n = target length
q = // q = generated string (initially set to 0, then
// coerced to "0something")
t = 0 // t = output counter (defined in the global scope)
) => // NB: g is also used as an object to store all
// generated strings
s.map(c => // for each character c in s[]:
q[n] ? // if q[n] is defined (target length reached):
g[q] ||= // unless g[q] is already defined,
++t // set it to a truthy value and increment t
: // else:
g( // do a recursive call:
n, // pass n unchanged
q += c // append c to q
) // end of recursive call
) // end of map()
| t // return t
f=lambda s,n,j=0:n<2or sum(f(s,n-(j:=j+1))*all(s.find(s[k:j])for k in range(1,j))for c in s[:n])
Does the recursion
\$f(n) = \sum_{j=1\ldots\min(n,|s|)}x(j)f(n-j)\$
where
\$x(n):=\begin{cases}0 & \text{if } s[:n] \text{ has a proper prefix equaling a suffix} \\\\ 1 & \text{else}\end{cases}\$
is there to avoid double counting.
¹ƤṗF€ḣ€QL
This is very slow, so it will not run well for any of the test cases provided.
¹ƤṗF€ḣ€QL Main Link: word as left argument, number as right argument
¹Ƥ get prefixes of the word
ṗ cartesian power
F€ flatten (join into one string) each list of prefixes
ḣ€ take the first N characters of each string
Q deduplicate
L count the number of strings
(a=#1;n=#2;Length[Union@@Map[a[[;;#]]&,Permutations/@IntegerPartitions[n,All,Range@Length@a],{3}]])&
Try it online!
Based on idea, that lengths of all prefixes in valid combination is integer partition of given number.
Very fast, but may be golfed more, I'll try!
Needs input as array of chars and number.
ηIиæJIùÙg
Try it online. (Extremely slow, so no test suite. It'll even time out for all provided test cases..)
Or alternatively, a port of @hyper-neutrino♦'s Jelly answer is 9 bytes as well:
ηIãJIδ∍Ùg
Try it online. (Faster than my approach above, but still extremely slow, so again no test suite.)
Explanation:
η # Get the prefixes of the first (implicit) input-string
Iи # Repeat this list the second input-integer amount of times as flattened list
æ # Get the powerset of this
J # Join each inner list together to a string
Iù # Only keep strings of a length equal to the second input-integer
Ù # Uniquify this list of strings
g # Pop and push the length to get the amount of unique strings
# (which is output implicitly as result)
η # Get the prefixed of the first (implicit) input-string
Iã # Get the cartesian power with the second input-integer
J # Join each inner list together to a string
δ # Map over each inner string:
I ∍ # Extend or shorten it to a length of the second input-integer
Ùg # Same as above (including implicit output)
import Data.List.Ordered
s#n=length(m!!n)where m=map(\n->nubSort$take n(cycle s):[p++q|l<-[1..n-1],p<-m!!l,q<-m!!(n-l)])[0..]
L, 11 bytesƒọʠ€Jæl¹=;U
Port of Kevin Cruijssen's 05AB1E answer.
Warning: this is very slow. It manages to complete the test case in the screenshot in ~10s on my computer.
ƒọʠ€Jæl¹=;U # Implicit input
ƒ # Prefixes of the first input
ọ # Repeated second input number of times
ʠ # Powerset of this list
€J # Join each inner list
æ ; # Filtered by:
l # Pop and push the length
¹= # Equals the second input?
U # Uniquify this list
# L flag gets the length
# Implicit output
Thunno 2 isn't on ATO yet, so here's a screenshot of the local interpreter:
-2 bytes thanks to @The Thonnu
def g(s,n):a={0};f=lambda n,l="":n and[f(n-i,l+s[:i])for i in range(1,1+min(n,len(s)))]or a.add(l);f(n);return~-len(a)
Ｎθ⊞υωＦυＦ⁻Ｅθ…⁺ι…ηθ⊕κυ⊞υκＩ№ＥυＬιθ
Try it online! Link is to verbose version of code. Takes n as the first input and s as the second input. Explanation:
Ｎθ
Input n.
⊞υωＦυ
Start a breadth-first search of concatenations of prefixes with the empty string.
Ｆ⁻Ｅθ…⁺ι…ηθ⊕κυ
For each concatenation so far, extend it up to the desired length with a cyclic prefix of the input string, then take each prefix of the result that has not yet been discovered.
⊞υκ
Push each new discovery to the list so that it can be processed on a later iteration.
Ｉ№ＥυＬιθ
Count how many strings were of the desired length.
For example, with an input of 10 and abcdef, the first pass produces the strings a, ab, abc, abcd, abcde, abcdef, abcdefa, abcdefab, abcdefabc and abcdefabcd. This is golfier than only producing the first six strings and waiting until abcdef is processed to produce the remaining four.
Modified from @97.100.97.109's answer.
Golfed version, try it online!
def g(s:String,n:Int)={val a=mutable.Set[String]("");def f(n:Int,l:String=""):Unit=if(n>0)(1 to math.min(n,s.length)).foreach(i=>f(n-i,l+s.substring(0,i)))else a.add(l);f(n);a.size-1}
Ungolfed version
import scala.collection.mutable
object Main {
def g(s: String, n: Int): Int = {
val a = mutable.Set[String]("")
def f(n: Int, l: String = ""): Unit =
if (n > 0) (1 to math.min(n, s.length)).foreach(i => f(n - i, l + s.substring(0, i)))
else a.add(l)
f(n)
a.size - 1
}
def main(args: Array[String]): Unit = {
println(g("aaaa", 8))
println(g("abcdef", 10))
println(g("aerodynamics", 10))
println(g("disbelief", 10))
}
}
