6
\$\begingroup\$

Thanks @NathanMerrill for allowing me to post this! The following is entirely his wording from this sandbox post (deleted):


We define a "Fresh" substring as a substring that is different from any other substring that starts earlier.

For example, if I take the string "abababc" and split it: ["ab","ab","a","bc"], the first and the last substring are fresh, but the middle two are not, because they can be found earlier in the string.

For this challenge, you need create a list of the smallest possible fresh substrings for each position in the string. If there are no fresh substrings, output and empty list or empty string, etc.

For example, if you were passed "ABABCBA", you should return ["A","B","ABC","BC","C"].

Test Cases:

ABABCBA          A,B,ABC,BC,C,   // ABC instead of AB because there is an AB earlier in the string
AAAAAAA          A,,,,,,
ABCDEFG          A,B,C,D,E,F,G
ABDBABDAB        A,B,D,BA,ABDA,BDA,DA,,
ACABCACBDDABADD  A,C,AB,B,CAC,ACB,CB,BD,D,DA,ABA,BA,AD,,

The empty items are not mandatory.

\$\endgroup\$
  • 1
    \$\begingroup\$ Is this case sensitive i.e. in Aa can we return A,a or A? If there are no fresh substrings, then it shouldn't be included in the list.: Can we have an empty item at that position in the list? \$\endgroup\$ – TheLethalCoder Jun 9 '17 at 15:02
  • \$\begingroup\$ Typo in test case ABCDEEFG -> ABCDEFG? \$\endgroup\$ – TheLethalCoder Jun 9 '17 at 15:16
  • \$\begingroup\$ I think you have a few more typos in your tests, I'll post my answer and show the results. Though I might have made a mistake. \$\endgroup\$ – TheLethalCoder Jun 9 '17 at 15:18
  • \$\begingroup\$ @JonathanAllan D is where you believe DD to be: smallest possible fresh substrings for each position in the string \$\endgroup\$ – TheLethalCoder Jun 9 '17 at 15:46
  • 2
    \$\begingroup\$ A,C,AB,B,CAC,ACB,CB,BD,D,DA,ABA,BA,AD for the last test case CBDis greater as CB and CB is not earlier in the string \$\endgroup\$ – Jörg Hülsermann Jun 9 '17 at 17:22
4
\$\begingroup\$

PHP, 141 bytes

for($r=[];$i<$l=strlen($a=$argn);$i++)for($t=1;$t;$t*=$t<$l)in_array($s=substr($a,$i,$t),$r)|strpos($a,$s)<$i?$t++:$r[]=$s.$t="";print_r($r);

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ All cleared up - this implementation is how it should be. \$\endgroup\$ – Jonathan Allan Jun 9 '17 at 17:00
  • \$\begingroup\$ @JonathanAllan Come on with your I assume python answer \$\endgroup\$ – Jörg Hülsermann Jun 9 '17 at 17:07
  • \$\begingroup\$ ...nope Jelly, was tricky - probably missed a trick or two though! \$\endgroup\$ – Jonathan Allan Jun 9 '17 at 17:34
4
\$\begingroup\$

Haskell, 105 103 88 81 79 bytes

-15 24 bytes (!) thanks to user1502040

import Data.List
f s=[a|a:_<-zipWith(\\)<*>scanl(++)[]$map(tail.inits)$tails s]

Try it online!

t gets a list of lists of all of the substrings starting from each position.

f builds up that list using scanl, so at index i we have a list of all of the substrings possible before index i. At each index, we take the set difference between the substrings calculated in t and those made illegal by f, to get the legal substrings at that index.

The lists are guaranteed to be sorted by length, so we can finally just take the first item if it exists. It skips empty items, as they are "not mandatory" per the spec.

Still learning Haskell, so I'm sure I've done something odd somewhere. The map head(filter(>[]) seems especially verbose to say "take the first item if exists, else nothing."

\$\endgroup\$
  • 1
    \$\begingroup\$ You can use a list comprehension instead of map head$filter(>[]). Something like [x|x:_<-myList]. \$\endgroup\$ – user1502040 Jun 9 '17 at 20:48
  • \$\begingroup\$ and you can combine the two maps in the definition of t. \$\endgroup\$ – user1502040 Jun 9 '17 at 20:50
  • \$\begingroup\$ Thanks @user1502040! I didn't realize you could filter by pattern in a list comprehension like that \$\endgroup\$ – vroomfondel Jun 9 '17 at 21:20
  • 1
    \$\begingroup\$ You can compress the whole thing into one line with a little point-free magic: f s=[a|a:_<-zipWith(\\)<*>scanl(++)([])$map(tail.inits)$tails s] \$\endgroup\$ – user1502040 Jun 9 '17 at 21:31
  • \$\begingroup\$ Nice. certain language constructs (<*>) can seem pretty obscure until I see such a useful example \$\endgroup\$ – vroomfondel Jun 9 '17 at 21:38
3
\$\begingroup\$

C#, 175 158 bytes

s=>{int i=0,j,l=s.Length;var a=new string[l];for(;i<l;++i)for(j=0;j<l-i;){var t=s.Substring(i,++j);if(!s.Substring(0,i).Contains(t)){a[i]=t;break;}}return a;}

Full/Formatted Version:

using System;

class P
{
    static void Main()
    {
        Func<string, string[]> f = s =>
        {
            int i = 0, j, l = s.Length;
            var a = new string[l];

            for (; i < l; ++i)
                for (j = 0; j < l - i;)
                {
                    var t = s.Substring(i, ++j);
                    if (!s.Substring(0, i).Contains(t))
                    {
                        a[i] = t;
                        break;
                    }
                }

            return a;
        };

        Console.WriteLine(string.Join(",", f("ABABCBA")));
        Console.WriteLine(string.Join(",", f("AAAAAAA")));
        Console.WriteLine(string.Join(",", f("ABCDEFG")));
        Console.WriteLine(string.Join(",", f("ABDBABDAB")));
        Console.WriteLine(string.Join(",", f("ACABCACBDDABADD")));

        Console.ReadLine();
    }
}
\$\endgroup\$
3
\$\begingroup\$

Python 3, 136 bytes

l=[];n=input();a=len(n)
for x in range(a):
 i=x+1
 while n[x:i]in l or n[x:i]in n[:i-1]:
  i+=1
  if i>a:x=i;break
 l+=[n[x:i]]
print(l)

Try it online!

Includes the empty items

\$\endgroup\$
  • \$\begingroup\$ @JörgHülsermann I think it is fixed now \$\endgroup\$ – ovs Jun 9 '17 at 17:11
  • 1
    \$\begingroup\$ Works in my opinion \$\endgroup\$ – Jörg Hülsermann Jun 9 '17 at 17:18
3
\$\begingroup\$

Jelly,  19  17 bytes

;\0;Ṗ
ṫJ;\€µḟ"ÇZḢ

A monadic link accepting a list of characters and returning a list of lists of characters.

Try it online! (the footer formats the list separating it with commas so it does not get implicitly printed as the representation would be smashed together).

How?

;\0;Ṗ - Link 1, offset prefixes: list  e.g. [["x","xy","xyz"],["y","yz"],["z"]]
 \    - cumulative reduction with:
;     -   concatenation                     [["x","xy","xyz"],["x","xy","xyz","y","yz"],["x","xy","xyz","y","yz","z"]]
  0;  - prepend a zero                    [0,["x","xy","xyz"],["x","xy","xyz","y","yz"],["x","xy","xyz","y","yz","z"]]
    Ṗ - pop (head to penultimate)         [0,["x","xy","xyz"],["x","xy","xyz","y","yz"]]

ṫJ;\€µḟ"ÇZḢ - Main link: list of characters  e.g. "ABABC"
 J          - range of length                     [1,2,3,4,5]
ṫ           - tail                                ["ABABC","BABC","ABC","BC","C"]
   \€       - cumulative reduction for €ach with:
  ;         -   concatenation                    [["A","AB","ABA","ABAB","ABABC"],["B","BA","BAB","BABC"],["A","AB","ABC"],["B","BC"],["C"]]
     µ      - monadic chain separation, call that p
        Ç   - call last link as a monad with p - gets relevant substrings to not use (with a zero in place of an empty list for the first index)
            -                      ... that is:  [0,["A","AB","ABA","ABAB","ABABC"],["A","AB","ABA","ABAB","ABABC","B","BA","BAB","BABC"],["A","AB","ABA","ABAB","ABABC","B","BA","BAB","BABC","A","AB","ABC"],["A","AB","ABA","ABAB","ABABC","B","BA","BAB","BABC","A","AB","ABC","B","BC"]]
       "    - zip with:
      ḟ     -   filter discard                   [["A","AB","ABA","ABAB","ABABC"],["B","BA","BAB","BABC"],["ABC"],["BC"],["C"]]
         Z  - transpose                         [["A","B","ABC","BC","C"],["AB","BA"],["ABA"],["ABAB"],["ABABC"]]
          Ḣ - head                               ["A","B","ABC","BC","C"]
\$\endgroup\$
  • \$\begingroup\$ I love it you get the same result for the last test case \$\endgroup\$ – Jörg Hülsermann Jun 9 '17 at 17:40
  • \$\begingroup\$ I was also going to comment the same, but saw yours and just upvoted it :) \$\endgroup\$ – Jonathan Allan Jun 9 '17 at 17:41
  • \$\begingroup\$ We have now 4 programs that do the same for the last test case. I am not sure what the C# Answer make \$\endgroup\$ – Jörg Hülsermann Jun 9 '17 at 17:44
3
\$\begingroup\$

JavaScript (ES6), 81 bytes

f=(s,t=0,u=t+1,v=s.slice(t,u))=>s.indexOf(v)<t?s[u]?f(s,t,u+1):[]:[v,...f(s,t+1)]
<input oninput=o.textContent=f(this.value).join`\n`><pre id=o>

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

Retina, 19 18 bytes

-1 byte because empty items can be ommitted

!&`(.+?)(?<!\1.+)

Try it online!

Explanation:

!                   Print matches as newline separated list
 &`                 Consider overlapping matches
   (.+?)            Capture the shortest possible substring
        (?<!\1.+)   Enforce freshness
              .+    Scan backwards
            \1      Fail if the match appears earlier in the string
                    If matching is impossible, skip this element
\$\endgroup\$
  • \$\begingroup\$ Explanation requested. \$\endgroup\$ – programmer5000 Jun 9 '17 at 18:38
  • \$\begingroup\$ Why do you need the |? \$\endgroup\$ – Neil Jun 9 '17 at 19:29
  • \$\begingroup\$ Otherwise, impossible cases are not included in the list. \$\endgroup\$ – CalculatorFeline Jun 9 '17 at 20:20
  • \$\begingroup\$ @CalculatorFeline I may have misread, but I thought you were allowed to stop once there were no more fresh substrings. \$\endgroup\$ – Neil Jun 10 '17 at 0:52

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.