14
\$\begingroup\$

Given a list of lists find the shortest list that is a contiguous sublist of exactly one list.

For example if we had

[[1,2,3],
 [1,2,3,4],
 [2,4,5,6],
 [1,2,4,5,6]]

the shortest contiguous sublist would be [3,4] since it only appears in the second list.

If there is no unique contiguous sublist (this requires at least one duplicate entry), output an empty list. Here is an example

[[1,2,3],
 [1,2,3],
 [1,2]]

If there are multiple contiguous sublists of minimal size, you may output any one of them or a list containing all of them. For example if the input was

[[1,2,3],[2],[1],[3]]

You could output either [1,2], [2,3] or [[1,2],[2,3]]. If you choose to do the latter option you may output singleton lists for the cases where there is only one solution.

The output may occur in the same list more than once as long as it appears in no other list. For example

[[1,2,1,2],[2,1]]

should output [1,2] because [1,2] is a sublist of the first list but not the second, even though it is a sublist of the first list in two different ways.

You may take as input a list of lists containing any type so long as that type has more than 100 possible values, i.e. no Booleans.

This is so answers will be scored in bytes with less bytes being better.

Test Cases

[[1,1]] : [1]
[[1],[1]] : []
[[1,1],[1]] : [1,1]
\$\endgroup\$
5
\$\begingroup\$

Husk, 12 14 15 bytes

+3 bytes for case [[1,1]]

Ṡḟȯ¬€Ṡ-uÖLṁȯtuQ

Try it online!

Explaination

          ṁ      -- map and concatenate
           ȯt    --   all but the first
             u   --   unique elements of
              Q  --   contiguous sublist
        ÖL       -- sort by length
Ṡḟ               -- find the first element satisfying this predicate
  ȯ¬€            --   not an element of
     Ṡ-          --   the list of sublists minus
       u         --   its unique elements

Note: Ṡ f g x = f (g x) x and this is hard to explain using the method above.

\$\endgroup\$
  • \$\begingroup\$ 14 bytes with a lambda. \$\endgroup\$ – Zgarb Aug 12 '17 at 23:44
  • \$\begingroup\$ That fails for [[1,1]] \$\endgroup\$ – H.PWiz Aug 12 '17 at 23:47
  • \$\begingroup\$ Hmm, and fixing that makes it over 15 bytes. Oh well. \$\endgroup\$ – Zgarb Aug 13 '17 at 1:33
4
\$\begingroup\$

Pyth, 15 bytes

halDs-M.p.:R)QY

Test suite

First, we generate all substrings of each input list with .:R)Q. Then, we generate all possible orderings, of those substring groups .p.

Now for the tricky part: -M. This folds the - function over each ordering list. It starts with the first substring list, then filters out all occupants of all of the other lists.

Then, the results are concatenated, ordered by length, a [] is appended, and then the first element of the resulting list is extracted with h.

This would be 4 bytes shorter if I could error on no unique sublists rather than output an empty list.

\$\endgroup\$
  • \$\begingroup\$ What is your 11-byte version? \$\endgroup\$ – Leaky Nun Aug 12 '17 at 19:58
  • \$\begingroup\$ @LeakyNun hlDs-M.p.:R is probably what he means. \$\endgroup\$ – FryAmTheEggman Aug 12 '17 at 20:06
3
\$\begingroup\$

Pyth - 20 bytes

Ksm.:d)QhalDfq1/KTKY

Test Suite.

\$\endgroup\$
  • \$\begingroup\$ Got 16 bytes, but I'm not sure this is correct. Otherwise it's pretty similar. \$\endgroup\$ – FryAmTheEggman Aug 12 '17 at 19:08
  • \$\begingroup\$ @FryAmTheEggman cool, you should post it. \$\endgroup\$ – Maltysen Aug 12 '17 at 19:49
  • \$\begingroup\$ Fails for the recently added edge case test [[1,1]]. \$\endgroup\$ – Jonathan Allan Aug 12 '17 at 20:24
2
\$\begingroup\$

Haskell, 149 128 126 113 bytes

import Data.List
f l=[x|x<-l,sum[1|y<-l,y==x]<2]
h[]=[]
h(x:y)=x
i=h.f.sortOn length.(>>=tail.nub.(>>=tails).inits)

Try it online!

Saved 21 bytes thanks to Wheat Wizard, H.PWiz and Bruce Forte.

Saved two more bytes thanks to H.PWiz.

Saved 13 bytes thanks to nimi.

EDIT This was the original explanation:

  • a is a shortcut for joining lists.

  • s computes all the continous sublists (all tails from all inits). Note that nub keeps only the first occurence of each element, so tail will remove the empty list from the sublists.

  • g merges all sublists from all given lists in a big list of sublists, and sort them by length.

  • f f is a filter on elements that appear only once in the big list

  • h is a secure version of head

  • i is the glue

Quite inelegant! There should be a better solution...

\$\endgroup\$
  • 2
    \$\begingroup\$ It looks like a couple of your functions could be shorter if written as point-free functions. \$\endgroup\$ – Sriotchilism O'Zaic Aug 12 '17 at 23:53
  • 1
    \$\begingroup\$ You also don't have to count the i= at the end of your program because point-free functions do not need to be assigned according to our rules. \$\endgroup\$ – Sriotchilism O'Zaic Aug 12 '17 at 23:54
  • 2
    \$\begingroup\$ Is foldl1(++) just concat? \$\endgroup\$ – H.PWiz Aug 12 '17 at 23:55
  • 2
    \$\begingroup\$ (length$filter(==x)l) could be shorter as length(filter(==x)l) or even shorter as sum[1|y<-l,y==x] \$\endgroup\$ – Sriotchilism O'Zaic Aug 12 '17 at 23:58
  • 2
    \$\begingroup\$ @H.PWiz Except for [] it is, but >>=id is even shorter ;) Also @jferard: You can inline a lot of functions (eg. f,g etc.) since you only use them once. \$\endgroup\$ – ბიმო Aug 13 '17 at 0:02
2
\$\begingroup\$

Java 8, 251 + 19 = 270 bytes

A very gross lambda from, minimally, List<List> to List (best to cast it to Function<List<List<Integer>>, List<Integer>> though). It's a brute force solution that iterates chunk lengths from 1 to the size of the largest list, in each case iterating over every chunk of that length in every list and checking each such chunk against each chunk of equal size in every other list.

Fear me, garbage collector.

import java.util.*;

i->{int x,l=x=0,s,t;for(List z:i)x=Math.max(x,z.size());List r=i;while(l++<=x)for(List a:i)c:for(s=0;s<=a.size()-l;s++){for(List b:i)for(t=0;t<=b.size()-l;)if(b.subList(t,l+t++).equals(r=a.subList(s,s+l))&a!=b)continue c;return r;}return new Stack();}

Ungolfed lambda

i -> {
    int
        x,
        l = x = 0,
        s, t
    ;
    for (List z : i)
        x = Math.max(x, z.size());
    List r = i;
    while (l++ <= x)
        for (List a : i)
            c: for (s = 0; s <= a.size() - l; s++) {
                for (List b : i)
                    for (t = 0; t <= b.size() - l; )
                        if (b.subList(t, l + t++).equals(r = a.subList(s, s + l)) & a != b)
                            continue c;
                return r;
            }
    return new Stack();
}

Try It Online

Java 8, 289 + 45 = 334 bytes

This is a more functional approach using streams. If there were a method on Stream to reduce to only elements that appear once, this solution would have beaten the one above. Assign to the same type as above.

import java.util.*;import java.util.stream.*;

l->{List<List>o=l.stream().flatMap(a->IntStream.range(1,a.size()+1).boxed().flatMap(n->IntStream.range(0,a.size()-n+1).mapToObj(k->a.subList(k,k+n)))).collect(Collectors.toList());o.sort((a,b)->a.size()-b.size());for(List a:o)if(o.indexOf(a)==o.lastIndexOf(a))return a;return new Stack();}

Ungolfed lambda

l -> {
    List<List> o = l.stream()
        .flatMap(a -> IntStream.range(1, a.size() + 1)
            .boxed()
            .flatMap(n -> IntStream.range(0, a.size() - n + 1)
                .mapToObj(k -> a.subList(k, k + n))
            )
        )
        .collect(Collectors.toList())
    ;
    o.sort((a, b) -> a.size() - b.size());
    for (List a : o)
        if (o.indexOf(a) == o.lastIndexOf(a))
            return a;
    return new Stack();
}

Try It Online

\$\endgroup\$
1
\$\begingroup\$

Jelly, 15 bytes

Ẇ€Q€ẎɓċỊµÐf⁸LÐṂ

Try it online!

-3 bytes thanks to Jonathan Allan

\$\endgroup\$
  • \$\begingroup\$ Can ċ1 be replaced with S? \$\endgroup\$ – user72349 Aug 12 '17 at 19:02
  • \$\begingroup\$ @ThePirateBay Indeed it can, thanks. I made a different version though. (though it would bring it to the same bytecount) \$\endgroup\$ – HyperNeutrino Aug 12 '17 at 19:05
  • \$\begingroup\$ Your new solution prints [1, 2, 1] for input [[1,2],[1,2,1],[2,1,1]] while [1,1] is shorter. \$\endgroup\$ – user72349 Aug 12 '17 at 19:10
  • \$\begingroup\$ @ThePirateBay Fixed, thanks. \$\endgroup\$ – HyperNeutrino Aug 12 '17 at 19:11
  • 1
    \$\begingroup\$ @JonathanAllan oh um. I can't count whoops. :P \$\endgroup\$ – HyperNeutrino Aug 12 '17 at 20:44
0
\$\begingroup\$

05AB1E, 15 bytes

εŒÙ}€`{γʒg}€`éн

Try it online!

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

Pyth, 14 bytes

sfq1lT.gksm{.:

Try it here.

\$\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.