<< Précédent Suivant >>

Grâce à la communauté PPCG, le Père Noël a réussi à trier ses cadeaux dans le bon ordre pour emménager dans le quai de transport. Malheureusement, les panneaux du quai de transport sont cassés, il ne sait donc pas où mettre tous les cadeaux! Les cadeaux sont tous regroupés et non pas par leurs gammes, ce que le Père Noël admet aurait été une meilleure idée.

Maintenant, étant donné les cadeaux dans l'ordre trié, déterminez toutes les configurations de plage minimale possibles qui entraîneraient le présent dans le bon ordre. Autrement dit, recherchez toutes les configurations de plage minimale telles que le tri des cadeaux selon l'algorithme du défi n ° 5 ne changerait pas l'ordre.

Défi

Une configuration de plage minimale est une liste de plages telles que les plages sont chacune aussi petites que possible. Autrement dit, si une plage est désignée pour couvrir un sous-ensemble spécifique de cadeaux, le minimum et le maximum de la plage doivent être les mêmes que ceux du sous-ensemble. En d'autres termes, la réduction de toute plage dans la couverture entraînerait la disparition de la couverture.

Le défi consiste à trouver toutes les configurations de gamme minimale possibles qui s'appliqueraient aux tailles actuelles. Prenons un exemple:[3, 1, 2, 5, 4, 7, 6]

Il y a un cas trivial, qui est de prendre la gamme de la configuration actuelle entière. Dans ce cas, [[1, 7]]serait une solution.

Pour des exemples avec des éléments uniques, un autre cas trivial serait [[3], [1], [2], [5], [4], [7], [6]](car les plages n'ont pas besoin d'être ordonnées).

Pour cet exemple, nous voyons également cela [[1, 3], [4, 7]]et [[1, 3], [4, 5], [6, 7]]cela fonctionnerait, ainsi que [[1, 3], [5], [4], [6, 7]]et [[1, 3], [4, 5], [7], [6]].

La réponse finale [3, 1, 2, 5, 4, 7, 6]serait [[[3], [1], [2], [5], [4], [7], [6]], [[3], [1], [2], [5], [4], [6, 7]], [[3], [1], [2], [4, 5], [7], [6]], [[3], [1], [2], [4, 5], [6, 7]], [[3], [1], [2], [4, 7]], [[3], [1, 2], [5], [4], [7], [6]], [[3], [1, 2], [5], [4], [6, 7]], [[3], [1, 2], [4, 5], [7], [6]], [[3], [1, 2], [4, 5], [6, 7]], [[3], [1, 2], [4, 7]], [[1, 3], [5], [4], [7], [6]], [[1, 3], [5], [4], [6, 7]], [[1, 3], [4, 5], [7], [6]], [[1, 3], [4, 5], [6, 7]], [[1, 3], [4, 7]], [[1, 5], [7], [6]], [[1, 5], [6, 7]], [[1, 7]]].

Spécifications de formatage

L'entrée sera donnée sous la forme d'une liste plate d'entiers positifs dans la plage de nombres pris en charge raisonnable de votre langue dans n'importe quel format raisonnable. L'entrée peut contenir des éléments en double. La sortie doit être donnée sous la forme d'une liste 3D d'entiers positifs dans n'importe quel format raisonnable.

Chaque plage de votre sortie (qui est à la deuxième couche) peut être représentée soit comme [min, max], [num]si elle est une gamme valeur unique, ou toute la gamme elle - même, mais votre format de sortie doit être cohérente. Veuillez spécifier si vous souhaitez utiliser un format de sortie raisonnable légèrement différent.

Les valeurs en double doivent être couvertes par une seule plage dans la sortie; c'est-à-dire qu'aucune plage dans la sortie ne peut avoir de chevauchement.

Votre solution peut renvoyer les plages dans n'importe quel ordre et cela ne doit pas être déterministe.

Règles

• Les échappatoires standard s'appliquent
• Il s'agit de code-golf, donc la réponse la plus courte en octets l'emporte
• Aucune réponse ne sera acceptée

Cas de test pour une liste avec des éléments en double:

2 3 2 4 -> [[[2, 3], [4]], [[2, 4]]]

Implémentation de référence

L'en-tête est le lien.

^{Remarque: je me suis inspiré de cette série de défis d' Advent Of Code . Je n'ai aucune affiliation avec ce site}

Vous pouvez voir une liste de tous les défis de la série en consultant la section 'Linked' du premier défi ici .

Bon golf!

Mathematica, 106 octets

sSelect[MinMax/@s~TakeList~#&/@Join@@Permutations/@IntegerPartitions@Tr[1^s],Unequal@@Join@@Range@@@#&]

Essayez-le en ligne!

Martin a économisé 16 octets

Brachylog , 17 16 octets

{~c⟨⌋⟦₂⌉⟩ᵐ.c≠∧}ᶠ

Fonctionne également sur les listes avec doublons. Les plages sont représentées par les listes d'éléments qu'elles contiennent. Essayez-le en ligne!

Explication

L'idée est de diviser la liste en blocs et de transformer les blocs en plages, puis de vérifier qu'ils ne se chevauchent pas.

{~c⟨⌋⟦₂⌉⟩ᵐ.c≠∧}ᶠ  Input is a list.
{             }ᶠ  Compute all possible outputs for this predicate:
 ~c                Break the list into contiguous blocks.
   ⟨    ⟩ᵐ         For each block,
    ⌋  ⌉           take its minimum and maximum,
     ⟦₂            and create the range between them.
          .        This is the output.
           c       Also, if you concatenate the output,
            ≠      its elements are distinct.
             ∧     Prevent the interpreter from thinking this is also the output.

JavaScript (ES6), 166 164 octets

Edit: version mise à jour qui prend désormais en charge les doublons

Imprime les résultats directement sur la console au format [min, max] .

f=(a,r=[],l=0)=>a[l++]?f([...a],r,l,f(a,[...r,[Math.min(...x=a.splice(0,l)),Math.max(...x)]])):a[0]|r.some(([x,y],i)=>r.some(([z])=>i--&&z>=x&z<=y))||console.log(r)

Cas de test

f=(a,r=[],l=0)=>a[l++]?f([...a],r,l,f(a,[...r,[Math.min(...x=a.splice(0,l)),Math.max(...x)]])):a[0]|r.some(([x,y],i)=>r.some(([z])=>i--&&z>=x&z<=y))||console.log(r)

consoleLog = console.log;
console.log = s => consoleLog(JSON.stringify(s))

consoleLog('Test case: [3, 1, 2, 5, 4, 7, 6]')
f([3, 1, 2, 5, 4, 7, 6])
consoleLog('Test case: [2, 3, 2, 4]')
f([2, 3, 2, 4])

Python 2 , 179 octets

lambda l:[l for l in[[range(min(x),max(x)+1)for x in P]for P in p(l)]if len(sum(l,[]))==len(set(sum(l,[])))]
p=lambda l:[[l[:i]]+a for i in range(1,len(l))for a in p(l[i:])]+[[l]]

Essayez-le en ligne!

Affiche une liste de plages complètes.

Fortement inspiré par l'implémentation de référence.

Construit toutes les partitions, puis des plages de min / max pour chaque partition. Une liste de plages est valide si aucune valeur n'apparaît plus d'une fois dans la liste.

sum(l,[]) aplatit une liste de listes et me permet de vérifier les doublons:

l=[[1, 2], [2, 3]]
sum(l,[]) = [1,2,2,3]
len([1,2,2,3] == len(set([1,2,2,3]))  -> False (duplicates)

Pyth , 17 octets

f{IsTmm}hSkeSkd./

Essayez-le ici!

Maintenant, c'est beaucoup mieux. Sort toutes les plages. Voir l'historique des révisions de la version précédente (à 31 octets stupéfiants).

Comment ça fonctionne

f {IsTmm} hSkeSkd./ ~> Programme complet.

               ./ ~> Liste des partitions.
     m ~> Carte utilisant une variable d.
      md ~> Carte sur d à l'aide d'une variable k.
        hSk ~> Le minimum de k.
           eSk ~> Le maximum de k.
       } ~> Plage entière inclusive.
f ~> Filtrez ces ...
   sT ~> Qui, une fois aplati,
 {I ~> Sont invariables sur la déduplication.