9
\$\begingroup\$

Description

Given a length n, and an alphabet size k>0, your program must determine the number of strings with those parameters which have a maximal number of unique substrings. In the case of k=2, this generates OEIS A134457.

Example

For example, 2210 has the substrings , 2, 22, 221, 2210, 2, 21, 210, 1, 10, and 0, for a total of 11. However, 2 appears twice, so it only has 10 unique substrings.

This is as many as possible for a length 4 string containing 3 different symbols, but it ties with 35 other strings for a total of 36 tieing strings including 0012, 2101, and 0121. Therefore, for n=4 and k=3, your program should output 36.

Test Cases

n    k    output

0    5    1
1    3    3
5    1    1
9    2    40
2    3    6
5    5    120
\$\endgroup\$
  • 3
    \$\begingroup\$ Could you please give some examples? It's kind of hard to follow the challenge from that very short description. \$\endgroup\$ – ETHproductions Jul 8 '17 at 15:09
  • \$\begingroup\$ So wouldn't n=2, k=3 output 9: 11,12,21,22,31,32,33,13,23? \$\endgroup\$ – veganaiZe Jul 9 '17 at 9:53
  • \$\begingroup\$ @veganaiZe The double digits have a repeated substring. \$\endgroup\$ – user1502040 Jul 9 '17 at 19:43
2
\$\begingroup\$

Jelly, 9 bytes

ṗµẆQLµ€ML

Try it online!

Input in reversed order. Brute force.

\$\endgroup\$
  • \$\begingroup\$ Save a byte by avoiding the three-atom chain with a transpose and tail: ṗẆQ$€ZṪL \$\endgroup\$ – Jonathan Allan Jul 8 '17 at 16:25
3
\$\begingroup\$

Pyth, 12 bytes

l.Ml{.:Z)^UE

Try it online.

Pure brute force.

Explanation

  • Implicit: append Q to the program.
  • Implicit: read and evaluate a line of input (n) in Q.
  • E: read and evaluate a line of input (k).
  • U: get a range [0, ..., k-1].
  • ^: get all n-length strings of [0, ..., k-1].
  • .M: find the ones that give a maximum for function f(Z):
    • .:Z: find the substrings of Z
    • {: remove duplicates
    • l: get the number of unique substrings
  • l: get the number of such strings
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 96 bytes

Last[Last/@Tally[Length@Union@Flatten[Table[Partition[#,i,1],{i,s}],1]&/@Tuples[Range@#2,s=#]]]&
\$\endgroup\$
2
\$\begingroup\$

Haskell, 82 bytes

import Data.Lists
l=length
n#k=l$argmaxes(l.nub.powerslice)$mapM id$[1..k]<$[1..n]

Usage example: 9 # 2 -> 40.

How it works:

       [1..k]<$[1..n]  --  make a list of n copies of the list [1..k]
      mapM id          --  make a list of all combinations thereof, where
                       --  the 1st element is from the f1st list, 2nd from 2nd etc
  argmaxes             --  find all elements which give the maximum value for function:
     l.nub.powerslice  --    length of the list of unique sublists
l                      --  take the length of this list
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.