Trouvez la sous-liste unique la plus courte

14

Étant donné une liste de listes, trouvez la liste la plus courte qui est une sous-liste contiguë d'exactement une liste.

Par exemple, si nous avions

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

la sous-liste contiguë la plus courte serait [3,4]puisqu'elle n'apparaît que dans la deuxième liste.

S'il n'y a pas de sous-liste contiguë unique (cela nécessite au moins une entrée en double), affichez une liste vide. Voici un exemple

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

S'il existe plusieurs sous-listes contiguës de taille minimale, vous pouvez générer n'importe laquelle d'entre elles ou une liste les contenant toutes. Par exemple, si l'entrée était

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

Vous pouvez sortir soit [1,2], [2,3]soit [[1,2],[2,3]]. Si vous choisissez de faire cette dernière option, vous pouvez générer des listes singleton pour les cas où il n'y a qu'une seule solution.

La sortie peut apparaître plusieurs fois dans la même liste tant qu'elle n'apparaît dans aucune autre liste. Par exemple

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

devrait sortir [1,2]car [1,2]est une sous-liste de la première liste mais pas la seconde, même s'il s'agit d'une sous-liste de la première liste de deux manières différentes.

Vous pouvez prendre en entrée une liste de listes contenant n'importe quel type tant que ce type a plus de 100 valeurs possibles, c'est-à-dire aucun booléen.

Il s'agit de donc les réponses seront notées en octets avec moins d'octets mieux.

Cas de test

[[1,1]] : [1]
[[1],[1]] : []
[[1,1],[1]] : [1,1]
Post Rock Garf Hunter
la source

Réponses:

5

Husk , 12 14 15 octets

+3 octets pour le cas [[1,1]]

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

Essayez-le en ligne!

Explication

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

Remarque: Ṡ f g x = f (g x) xet cela est difficile à expliquer en utilisant la méthode ci-dessus.

H.PWiz
la source
14 octets avec un lambda.
Zgarb
Cela échoue pour[[1,1]]
H.PWiz
Hmm, et la fixation qui fait plus de 15 octets. Tant pis.
Zgarb
4

Pyth, 15 octets

halDs-M.p.:R)QY

Suite de tests

Tout d'abord, nous générons toutes les sous-chaînes de chaque liste d'entrée avec .:R)Q. Ensuite, nous générons tous les ordres possibles, de ces groupes de sous-chaînes .p.

Maintenant , pour la partie la plus délicate: -M. Cela replie la -fonction sur chaque liste de commande. Il commence par la première liste de sous-chaînes, puis filtre tous les occupants de toutes les autres listes.

Ensuite, les résultats sont concaténés, classés par longueur, a []est ajouté, puis le premier élément de la liste résultante est extrait avec h.

Ce serait 4 octets plus court si je pouvais faire une erreur sur aucune sous-liste unique plutôt que de sortir une liste vide.

isaacg
la source
Quelle est votre version à 11 octets?
Leaky Nun
@LeakyNun hlDs-M.p.:Rest probablement ce qu'il veut dire.
FryAmTheEggman
3

Pyth - 20 octets

Ksm.:d)QhalDfq1/KTKY

Suite de tests .

Maltysen
la source
Vous avez 16 octets , mais je ne suis pas sûr que ce soit correct. Sinon, c'est assez similaire.
FryAmTheEggman
@FryAmTheEggman cool, vous devriez le poster.
Maltysen
Échoue pour le test de cas de bord récemment ajouté [[1,1]].
Jonathan Allan
2

Haskell , 149 128 126 113 octets

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)

Essayez-le en ligne!

Enregistrement de 21 octets grâce à Wheat Wizard, H.PWiz et Bruce Forte.

Enregistré deux octets supplémentaires grâce à H.PWiz.

Enregistré 13 octets grâce à nimi.

EDIT C'était l'explication originale:

  • a est un raccourci pour rejoindre des listes.

  • scalcule toutes les sous-listes continues (toutes tailsde toutes inits). Notez que nubne conserve que la première occurrence de chaque élément, tailsupprimera donc la liste vide des sous-listes.

  • g fusionne toutes les sous-listes de toutes les listes données dans une grande liste de sous-listes et triez-les par longueur.

  • f f est un filtre sur les éléments qui n'apparaissent qu'une seule fois dans la grande liste

  • h est une version sécurisée de head

  • i est la colle

Assez inélégant! Il devrait y avoir une meilleure solution ...

jferard
la source
2
Il semble que quelques-unes de vos fonctions pourraient être plus courtes si elles étaient écrites en tant que fonctions sans point.
Post Rock Garf Hunter
1
Vous n'avez pas non plus à compter le i=à la fin de votre programme car les fonctions sans point n'ont pas besoin d'être attribuées selon nos règles.
Post Rock Garf Hunter
2
Est-ce foldl1(++)juste concat?
H.PWiz
2
(length$filter(==x)l)pourrait être plus court length(filter(==x)l)ou même plus courtsum[1|y<-l,y==x]
Post Rock Garf Hunter
2
@ H.PWiz Sauf pour []cela, mais >>=idest encore plus court;) Aussi @jferard: Vous pouvez incorporer de nombreuses fonctions (par exemple f, getc.) car vous ne les utilisez qu'une seule fois.
ბიმო
2

Java 8, 251 + 19 = 270 octets

Un lambda très grossier de, au minimum, List<List>à List(préférable de le lancer Function<List<List<Integer>>, List<Integer>>). C'est une solution de force brute qui itère les longueurs de blocs de 1 à la taille de la plus grande liste, dans chaque cas, itère sur chaque bloc de cette longueur dans chaque liste et vérifie chacun de ces blocs par rapport à chaque bloc de taille égale dans toutes les autres listes.

Craignez-moi, ramasseur d'ordures.

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();}

Lambda non golfé

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();
}

Essayez-le en ligne

Java 8, 289 + 45 = 334 octets

Il s'agit d'une approche plus fonctionnelle utilisant des flux. S'il y avait une méthode Streampour réduire à seulement les éléments qui apparaissent une fois, cette solution aurait battu celle ci-dessus. Attribuez au même type que ci-dessus.

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();}

Lambda non golfé

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();
}

Essayez-le en ligne

Jakob
la source
1

Gelée , 15 octets

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

Essayez-le en ligne!

-3 octets grâce à Jonathan Allan

HyperNeutrino
la source
Peut ċ1être remplacé par S?
@ThePirateBay En effet, merci. J'ai fait une version différente cependant. (bien que cela le ramènerait au même nombre de fois)
HyperNeutrino
Votre nouvelle solution imprime [1, 2, 1]pour la saisie [[1,2],[1,2,1],[2,1,1]]tandis qu'elle [1,1]est plus courte.
@ThePirateBay Fixed, merci.
HyperNeutrino
1
@JonathanAllan oh um. Je ne peux pas compter les whoops. : P
HyperNeutrino
0

Pyth, 14 octets

sfq1lT.gksm{.:

Essayez-le ici.

Erik le Outgolfer
la source