Find the shortest unique sublist

Question

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 code-golf so answers will be scored in bytes with less bytes being better.

Test Cases

[[1,1]] : [1]
[[1],[1]] : []
[[1,1],[1]] : [1,1]

Answer 1

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.

Answer 2

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.

Answer 3

Pyth - 20 bytes

Ksm.:d)QhalDfq1/KTKY

Test Suite.

Answer 4

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

Answer 5

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

Answer 6

Jelly, 15 bytes

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

Try it online!

-3 bytes thanks to Jonathan Allan

Answer 7

05AB1E, 15 bytes

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

Try it online!

Answer 8

Pyth, 14 bytes

sfq1lT.gksm{.:

Try it here.