16
\$\begingroup\$

Given a string \$X\$ we will say two strings, \$a\$ and \$b\$, are building blocks of \$X\$ if \$X\$ can be made by concatenating some \$n\$ \$a\$s with \$m\$ \$b\$s in any order. For example the string tomato has building blocks to and ma:

to ++ ma ++ to

We will say that the fineness of a set of building blocks is the sum \$n+m\$. That is the number of blocks required to build \$X\$. So in the example tomato here are some building blocks with their fineness:

to, ma -> 3
tom, ato -> 2
tomato, z -> 1

Task

Given a non-empty string as input output a set of two building blocks with maximal fineness. In the case of a tie you may output any or all of the maximal building blocks.

You may assume the input will contain only the alphabetic ASCII characters.

If there is a correct output where \$a\$ is the empty string, you may output only the \$b\$ value.

This is so the goal is to minimize the size of your source code as measured in bytes.

However, I make explicit what is usually implicit: you should consider submissions of differing time complexity as belonging to different categories for scoring. I encourage people to try and golf both efficient and inefficient algorithms to this problem.

Test cases

The following examples have unambiguous (up to order) solutions:

tomato -> to ma  F=3
tomcat -> t omca  F=3
banana -> ba na  F=3
axaaaaaaxa -> a x  F=10
axaaaaaaja -> a xaaaaaaj  F=3
aaxaaaajaaaajaaaaxaa -> a xaaaajaaaajaaaax  F=5

The following have ambiguous solutions. I've given a possible valid solution and its fineness to compare to your result. I've used the character * in the output to represent cases where that string may be empty or omitted (these two options are non-exhaustive).

bobcat -> bob cat  F=2
axaaaajaaaaxa -> axa aaajaaa  F=3
axaaaajaaaajaaaaxa -> axa aaajaaaajaaa  F=3
aaaaaaaaaa -> a *  F=10
x -> x *  F=1
\$\endgroup\$
10
  • \$\begingroup\$ For aaaaaa what's allowed as output? a,aa, a,a, a,, a,z? \$\endgroup\$
    – l4m2
    Commented Jan 23 at 17:57
  • \$\begingroup\$ @l4m2 Since the best way to split that is into all as, any pair that contains a as a building block is correct. So all of those are fine but something like aa, s or x, y would not be. \$\endgroup\$
    – Wheat Wizard
    Commented Jan 23 at 17:59
  • 1
    \$\begingroup\$ Point is a, since allowing empty string is quite bad \$\endgroup\$
    – l4m2
    Commented Jan 23 at 18:00
  • \$\begingroup\$ a, is fine. I don't really understand the point of your question. \$\endgroup\$
    – Wheat Wizard
    Commented Jan 23 at 18:02
  • 2
    \$\begingroup\$ @l4m2 No, fineness is "the number of blocks required to build \$X\$". \$\endgroup\$
    – Wheat Wizard
    Commented Jan 23 at 18:05

10 Answers 10

6
\$\begingroup\$

Pyth, 14 13 10 9 bytes, \$O(2^n)\$

-1 byte thanks to @isaacg

e<I#2{M./

Attempt This Online!

e<I#2{M./Q
       ./Q  # all partitions of input
     {M     # remove duplicates in each partition
 <I#2       # filter for elements where elem[:2] == elem
e           # last element
\$\endgroup\$
2
  • 2
    \$\begingroup\$ With the most recent edit to the challenge, you could omit the .[2 \$\endgroup\$ Commented Jan 23 at 22:54
  • 1
    \$\begingroup\$ You can save a byte by replacing f>3lT with <I#2. Also, glad to see people using my language! \$\endgroup\$
    – isaacg
    Commented Jan 24 at 4:15
4
\$\begingroup\$

JavaScript (ES11), 107 bytes, \$O(n^3)\$ *

* or worse, depending on the time complexity of the regular expression algorithm, which is likely to be implementation-dependent

A regex-based solution. Much more convoluted than I would like.

f=(s,n=(w=s.length)*w)=>n--?s.match(`^(.+)\\1{${x=n%w}}(.+)(\\1|\\2){${n/w-x|0}}$`)?.slice(1,3)||f(s,n):[s]

Attempt This Online!


JavaScript (ES6), 107 bytes, \$O(2^n)\$

f=([c,...a],k,u=o=[],s,b=[...u,s])=>c?f(a,k,u,[s]+c)|f(a,-~k,b,c)||new Set(o):new Set(b).size>2||o[k]?0:o=b

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ does not work for single character inputs \$\endgroup\$ Commented Jan 23 at 19:17
  • \$\begingroup\$ 104 \$\endgroup\$
    – l4m2
    Commented Jan 23 at 19:24
  • \$\begingroup\$ @Mukundan314 I've added a quick and dirty fix for these edge cases. \$\endgroup\$
    – Arnauld
    Commented Jan 23 at 19:57
  • \$\begingroup\$ What's the complexity of JS's regex parser? Is it better than \$O(n^2)\$? \$\endgroup\$
    – Xcali
    Commented Jan 24 at 0:02
  • 1
    \$\begingroup\$ Isn't the complexity of the first solution at least \$n^3\$? There's no way the regex is sublinear \$\endgroup\$ Commented Jan 24 at 6:05
3
\$\begingroup\$

Haskell, 155 bytes, \$O(n^3)\$

(%)=splitAt
l=length
x#w=maximum$((w==[],0),x):[((a,b+1),c)|((a,b),c)<-[x#p|y<-x,(s,p)<-[l y%w],s==y]++[(s:x)#p|l x<2,(s,p)<-map(%w)[1..l w]]]
f x=snd$[]#x

Attempt This Online!

Outputs a list of two strings if the input has length \$\geq 2\$, otherwise a list of a single string.

Can be reduced to 136 bytes if outputting more stuff is allowed.

\$\endgroup\$
2
\$\begingroup\$

Vyxal 3, 9 bytes, \$O(2^n)\$

ṗSᵛuᶻϩḢḢt

Try it Online!

ṗSᵛuᶻϩḢḢt­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌­
ṗ          # ‎⁡all partitions of input
 S         # ‎⁢sort by length
  ᵛu       # ‎⁣uniquify each
    ᶻϩḢḢ   # ‎⁤keep only elements with length less than 3
        t  # ‎⁢⁡last element
\$\endgroup\$
2
\$\begingroup\$

Jelly, 11 bytes, \$O(2^n)\$

ŒṖLÞQ€ṫÐḟ3Ṫ

Try it online!

A monadic link taking a string and returning a list of two strings.

Explanation

ŒṖ          | Partition
  LÞ        | Sort by length (number of pieces in the partition)
    Q€      | Ubiquity each
      ṫÐḟ3  | Filter out those length 3 or longer (technically those where taking the tail starting at position 3 is non-empty)
          Ṫ | Tail
\$\endgroup\$
1
\$\begingroup\$

Retina, 65 bytes, \$ O(n^3) \$

L$w`(.+)(?=((.+?)\3*)?$(?<=^(\1|\3)+))
$#4¶$1¶$3
N^`.+¶.+¶.*
1G`¶

Try it online! Link includes test cases. Explanation:

L$w`(.+)(?=((.+?)\3*)?$(?<=^(\1|\3)+))
$#4¶$1¶$3

List the fineness and pair of building blocks all substrings of the input whose suffix is a multiple of a second building block whereby the input string can be constructed using only the two building blocks, unless the suffix is empty, in which case it is not counted (this would otherwise throw off the count by 1).

N^`.+¶.+¶.*

Sort in descending order of fineness.

1G`¶

Keep only the pair of building blocks with the greatest fineness. (Alternatively, the ^ can be removed to sort the building blocks in ascending order in which case a - must be prefixed to this line so that the greatest fineness is selected.)

\$\endgroup\$
0
\$\begingroup\$

Python, 116 bytes, between \$O(n^3)\$ and \$O(2^n)\$

Port of Xcali's answer

lambda x,l="":max((subn(a:=(l:=l+i)+sub(r'^(%s)*(.+?)(\2|\1)*$'%l,"|\\2",x),i,x)[1],a)for i in x)[1]
from re import*

Attempt This Online!

Python, 135 bytes, between \$O(n^3)\$ and \$O(2^n)\$

Port of Arnauld's regex answer

lambda x:[n:=len(x),[x],*[[m[1],m[2]]for i in range(n*n)if(m:=re.match(r"^(.+)\1{%d}(.+)(\1|\2){%d}$"%(i/n-i%n,i%n),x))]][-1]
import re

Attempt This Online!

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 11 bytes, \$O(2^n)\$

.œé€Ùʒg3‹}θ

Try it online or verify (almost) all test cases.

Explanation:

.œ         # Get all partitions of the (implicit) input-string
  é        # Sort them by length
   €Ù      # Uniquify the parts of each partition
     ʒ     # Filter the partitions by:
      g    #  Where the length (aka the amount of unique parts)
       3‹  #  Is smaller than 3
     }θ    # After the filter: pop and keep the last one
           # (which is output implicitly as result)
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 88 bytes, worst case \$ O(2^n) \$

FLθ⊞υ⟦¹…θ⊕ιω✂θ⊕ι⟧FυFΦ⎇§ι²✂ι¹¦³¦¹⊞OE§ι³…§ι³⊕λ§ι¹¬⌕§ι³κ⊞υ⟦⊕§ι⁰§ι¹⎇⁼κ§ι¹§ι²κ✂§ι³Lκ⟧✂⌈Φυ¬⊟ι¹

Try it online! Link is to verbose version of code. Explanation:

FLθ⊞υ⟦¹…θ⊕ιω✂θ⊕ι⟧

Get all the prefixes of the input string as a list [1, prefix, empty string, suffix] where 1 represents the number of building blocks used so far.

Fυ

Perform a search over the possible building blocks.

FΦ⎇§ι²✂ι¹¦³¦¹⊞OE§ι³…§ι³⊕λ§ι¹¬⌕§ι³κ

If two building blocks have already been picked for this entry then just search those entries otherwise search both the original building block and all of the prefixes of the string remaining. Keep only those where the string remaining starts with the prefix.

⊞υ⟦⊕§ι⁰§ι¹⎇⁼κ§ι¹§ι²κ✂§ι³Lκ⟧

Create a new entry with 1 more building block and the block removed from the suffix, updating the second building block if it is new.

✂⌈Φυ¬⊟ι¹

Get the entries where the entire string was successfully built, find the one with the most blocks used and output the blocks.

The performance is \$ O(2^n) \$ because on an input of n as the code will try both the building block a as the first possible building block and also a as the next possible building block for each character, generating two child entries each time. An input of 16 as takes about half a minute on TIO. This can be improved at a cost of 6 bytes so something probably about \$ O(n^3) \$:

FLθ⊞υ⟦¹…θ⊕ιω✂θ⊕ι⟧FυFΦ⎇§ι²✂ι¹¦³¦¹⊞OΦE§ι³…§ι³⊕λ⁻κ§ι¹§ι¹¬⌕§ι³κ⊞υ⟦⊕§ι⁰§ι¹⎇⁼κ§ι¹§ι²κ✂§ι³Lκ⟧✂⌈Φυ¬⊟ι¹

Try it online! Link is to verbose version of code. Explanation: As above, but when choosing the second building block, does not allow it to be the same as the first building block (or a multiple, not that that makes much difference, since the pathological case was for the two being equal).

\$\endgroup\$
0
\$\begingroup\$

Haskell + hgl, 16 bytes, \$\mathcal{O}(n2^n)\$

g1 lL3<nb<<sJ<pt

Attempt This Online!

Explanation

  • pt: get all partitions
  • sJ: sort them by length
  • nb: remove duplicate elements from each partition
  • g1: get the first one such that ...
  • lL3: its length is shorter than 3

Reflection

I've tried many ways to do this. I was working on a fast version, but there were so many serious gaps where I couldn't make it work.

  • There should be versions of pt and pST which output partitions sorted by length. There should also be functions to get partitions of a certain size. This would not only shorten the existing code, but it would make it \$\mathcal{O}(2^n)\$.
  • There should be joined versions of l2q and l3q. While we're at it, there should also be a joined version of l2.
  • There are a bunch of related things I really would have liked here:
    • There should be a function to take a substring and split along that. (There exists one for elements, but not substrings.)
    • There should be a function to take a substring and split along the substring leaving occurences of it in place. e.g. f "ma" "tomato" = ["to", "ma", "to"].
    • There should be a function to take a string and replace all instances of that string with another string. (There exists one that replaces the first instances but no more.)
    • There should be a function to take two elements a and b and replace all instances of a with b.
    • There should be a function to take a predicate and an element and replace all elements in a structure satisfying the predicate with the given element.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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