Calculer le surensemble

18

Votre tâche ici est simple:

Étant donné une liste d'ensembles entiers, recherchez l'union d'ensemble. En d'autres termes, recherchez la liste la plus courte des ensembles entiers qui contiennent tous les éléments de la liste d'origine des ensembles (mais pas d'autres éléments). Par exemple:

[1,5] and [3,9] becomes [1,9] as it contains all of the elements in both [1,5] and [3,9]
[1,3] and [5,9] stays as [1,3] and [5,9], because you don't want to include 4

Les ensembles sont notés en utilisant la notation de plage: [1,4]signifie les entiers 1,2,3,4. Les ensembles peuvent également être illimités: [3,]signifie tous les entiers >= 3et [,-1]signifie tous les entiers <= -1. Il est garanti que le premier élément de la plage ne sera pas supérieur au second.

Vous pouvez choisir de prendre des ensembles en notation de chaîne, ou vous pouvez utiliser des tuples à 2 éléments, en utilisant une constante non entière comme valeur "infinie". Vous pouvez utiliser deux constantes distinctes pour représenter la limite supérieure infinie et la limite inférieure infinie. Par exemple, en Javascript, vous pouvez utiliser[3,{}] pour noter tous les entiers >= 3, tant que vous l'utilisez de manière cohérente {}dans tous les cas de test.

Cas de test:

[1,3]                     => [1,3]
[1,]                      => [1,]
[,9]                      => [,9]
[,]                       => [,]
[1,3],[4,9]               => [1,9]
[1,5],[8,9]               => [1,5],[8,9]
[1,5],[1,5]               => [1,5]
[1,5],[3,7]               => [1,7]
[-10,7],[1,5]             => [-10,7]
[1,1],[2,2],[3,3]         => [1,3]
[3,7],[1,5]               => [1,7]
[1,4],[8,]                => [1,4],[8,]
[1,4],[-1,]               => [-1,]
[1,4],[,5]                => [,5]
[1,4],[,-10]              => [1,4],[,-10]
[1,4],[,]                 => [,]
[1,4],[3,7],[8,9],[11,20] => [1,9],[11,20]

Il s'agit de , alors répondez le plus brièvement possible!

Nathan Merrill
la source
En relation
Nathan Merrill
1
Puis-je utiliser à la Infinityplace {}?
Luis felipe De jesus Munoz
Pouvons-nous prendre l'entrée comme des valeurs flottantes, par exemple, [1.0, 3.0]au lieu de [1, 3]?
AdmBorkBork
Tant que vous les traitez comme des entiers, oui. En d'autres termes, cela [1.0, 3.0], [4.0, 5.0]devrait encore devenir[1.0, 5.0]
Nathan Merrill
Si votre langue ne peut pas prendre Infinityet -Infinitycomme entrée, est-elle autorisée à prendre -999999et 999999(ou même plus / moins) à la place?
Kevin Cruijssen du

Réponses:

7

R + intervals, 90 87 81 octets

function(...)t(reduce(Intervals(rbind(...),type="Z")))+c(1,-1)
library(intervals)

Essayez-le en ligne!

L'entrée est une liste d'intervalles. -Infet Infsont intégrés R pour moins / plus l'infini. La sortie est une matrice de colonnes d'intervalles.

Pas habituellement un fan de l'utilisation de bibliothèques non standard mais celle-ci était amusante. TIO n'a pas intervalsinstallé. Vous pouvez l'essayer sur votre propre installation ou sur https://rdrr.io/snippets/

Le intervalspackage prend en charge les type = "Z"intervalles réels et entiers ( ) et la reducefonction est intégrée à ce que le défi veut, mais la sortie semble avoir par défaut des intervalles ouverts, elle est donc nécessaire pour obtenir le résultat souhaité.close_intervals +c(1,-1)

L'ancienne version avait des exemples dans la liste des listes qui pourraient être pratiques, j'ai donc laissé le lien ici.

ngm
la source
Je pense que vous pouvez économiser quelques octets: function(...)close_intervals(reduce(Intervals(rbind(...),type="Z"))). Ou encore mieux, vous pouvez vérifier avec op s'ils autorisent une matrice en entrée.
JayCe
1
Je me tenais littéralement éveillé dans mon lit la nuit dernière en pensant "qu'il devait y avoir une meilleure façon de créer une matrice à partir des vecteurs d'entrée". Je pense que le défi est préférable de laisser l'apport tel quel. Mais c'était amusant d'avoir reduceet Reducelà-dedans.
ngm
J'adore le truc "double réduction"! tout simplement pas assez Golfy;) Qu'en est- il de modifier les intervalles ouverts comme celui - ci: f=function(...)t(reduce(Intervals(rbind(...),type="Z")))+c(1,-1)?
JayCe
6

JavaScript (ES6), 103 octets

1 octet enregistré grâce à @Shaggy
1 octet enregistré grâce à @KevinCruijssen

Attend +/-Infinitydes valeurs infinies.

a=>(a.sort(([p],[P])=>p-P).map(m=M=([p,q])=>p<M+2?M=q>M?q:M:(b.push([m,M]),m=p,M=q),b=[]),b[0]=[m,M],b)

Essayez-le en ligne!

Comment?

Nous trions d'abord les intervalles par leur borne inférieure, du plus bas au plus élevé. Les limites supérieures sont ignorées.

Nous itérons ensuite sur les intervalles triés [pn,qn] , tout en gardant une trace des limites inférieures et supérieures actuelles m et M , initialisées respectivement à p1 et q1 .

Pour chaque intervalle [pn,qn] :

  • Si pnM+1 : cet intervalle peut être fusionné avec les précédents. Mais nous pouvons avoir une nouvelle limite supérieure, nous mettons donc à jour M à max(M,qn) .
  • Sinon: il y a un écart entre les intervalles précédents et celui-ci. Nous créons un nouvel intervalle [m,M] et mettons à jour m et M pourpn etqn respectivement.

A la fin du processus, nous créons un dernier intervalle avec les bornes actuelles [m,M] .

Commenté

a => (                  // a[] = input array
  a.sort(([p], [P]) =>  // sort the intervals by their lower bound; we do not care about
    p - P)              // the upper bounds for now
  .map(m = M =          // initialize m and M to non-numeric values
    ([p, q]) =>         // for each interval [p, q] in a[]:
    p < M + 2 ?         //   if M is a number and p is less than or equal to M + 1:
      M = q > M ? q : M //     update the maximum M to max(M, q)
    : (                 //   else (we've found a gap, or this is the 1st iteration):
      b.push([m, M]),   //     push the interval [m, M] in b[]
      m = p,            //     update the minimum m to p
      M = q             //     update the maximum M to q
    ),                  //
    b = []              //   start with b[] = empty array
  ),                    // end of map()
  b[0] = [m, M], b      // overwrite the 1st entry of b[] with the last interval [m, M]
)                       // and return the final result
Arnauld
la source
p<=M+1peut être p<M+2?
Kevin Cruijssen
@KevinCruijssen J'ai complètement raté celle-là ... Merci!
Arnauld
4

Python 2 , 118 113 112 111 106 105 104 101 octets

x=input()
x.sort();a=[];b,c=x[0]
for l,r in x:
 if l>c+1:a+=(b,c),;b,c=l,r
 c=max(c,r)
print[(b,c)]+a

Enregistré un octet grâce à Mr.Xcoder, un grâce à Jonathan Frech et trois grâce à Dead Possum.
Essayez-le en ligne!


la source
(b,c),enregistre un octet.
M. Xcoder
Huh, je pensais que j'avais déjà essayé ça.
Cela ne gsignifie pas que votre fonction fn'est pas réutilisable et n'est donc pas valide?
Neil
@Neil Probablement, mais ce n'était qu'un reliquat d'une tentative antérieure.
1
Vous pouvez également faire le returndevientprint pour un autre octet.
Jonathan Frech
2

Rubis , 89 76 octets

->a{[*a.sort.reduce{|s,y|s+=y;y[0]-s[-3]<2&&s[-3,3]=s.max;s}.each_slice(2)]}

Essayez-le en ligne!

Triez le tableau, puis aplatissez en ajoutant toutes les plages à la première: si une plage chevauche la précédente, jetez 2 éléments des 3 derniers (en ne gardant que le maximum).

Aplatissez tout à la fin.

GB
la source
1

Pascal (FPC) , 367 362 357 octets

uses math;type r=record a,b:real end;procedure d(a:array of r);var i,j:word;t:r;begin for i:=0to length(a)-1do for j:=0to i do if a[i].a<a[j].a then begin t:=a[i];a[i]:=a[j];a[j]:=t;end;j:=0;for i:=1to length(a)-1do if a[j].b>=a[i].a-1then begin a[j].a:=min(a[i].a,a[j].a);a[j].b:=max(a[i].b,a[j].b)end else j:=j+1;for i:=0to j do writeln(a[i].a,a[i].b)end;

Essayez-le en ligne!

Une procédure qui prend un tableau dynamique d'enregistrements composé de 2 limites de plage, modifie le tableau en place, puis l'écrit sur la sortie standard, une plage par ligne. (Désolé pour cette phrase tordue.) Utilise 1/0pour le haut et le -1/0bas sans limite .

Version lisible

Ce serait bien de renvoyer simplement le tableau avec le nombre corrigé d'éléments, mais le tableau dynamique transmis à la fonction / procédure n'est plus un tableau dynamique ... D'abord j'ai trouvé cela , puis il y a ceci excellente explication époustouflante .

C'est la meilleure structure de données que j'ai pu trouver pour raccourcir le code. Si vous avez de meilleures options, n'hésitez pas à faire une suggestion.

AlexRacer
la source
1

Wolfram Language (Mathematica) , 57 octets

List@@(#-{0,1}&/@IntervalUnion@@(Interval[#+{0,1}]&/@#))&

Essayez-le en ligne!

Prend l'entrée comme une liste de listes {a,b}représentant l'intervalle [a,b], où apeut être -Infinityet bpeut être Infinity.

Utilise le intégré IntervalUnion, mais bien sûr, nous devons d'abord masser les intervalles en forme. Pour prétendre que les intervalles sont des entiers, on ajoute 1 à la borne supérieure (en s'assurant que l'union de [1,3]et [4,9]est [1,9]). À la fin, nous annulons cette opération et transformons le résultat en une liste de listes.

Il y a aussi une approche complètement différente, qui affiche 73 octets :

NumericalSort@#//.{x___,{a_,b_},{c_,d_},y___}/;b+1>=c:>{x,{a,b~Max~d},y}&

Ici, après avoir trié les intervalles, nous remplaçons simplement deux intervalles consécutifs par leur union chaque fois que ce serait un seul intervalle, et répétons jusqu'à ce qu'il n'y ait plus aucune opération à faire.

Misha Lavrov
la source
1

05AB1E (hérité) , 88 79 78 octets

g≠i˜AKïDW<UZ>VIøεAXY‚Nè:}ïø{©˜¦2ôíÆ1›.œʒíεćsO_*}P}н€g®£εø©θàDYQiA}V®нßDXQiA}Y‚

L'infini est saisi sous forme d'alphabet minuscule ( 'abcdefghijklmnopqrstuvwxyz').

Essayez-le en ligne ou vérifiez tous les cas de test .

Remarque importante: s'il y avait un réel Infinityet -Infinity, il aurait plutôt été de 43 à 42 octets . Si un peu plus de 50% environ 30% est comme solution de contournement pour le manque de Infinity..

{©Dg≠i˜¦2ôíÆ1›.œʒíεćsO_*}P}н€g®£εø©θàV®нßY‚

Essayez-le en ligne (avec Infinityremplacé par 9999999999et -Infinityremplacé par-9999999999 ).

Peut certainement être joué beaucoup. En fin de compte, il s'est avéré très, très laid, plein de solutions de contournement. Mais pour l'instant, je suis juste content que ça marche.

Explication:

Dgi          # If the length of the implicit input is NOT 1:
              #   i.e. [[1,3]] → length 1 → 0 (falsey)
              #   i.e. [[1,4],["a..z",-5],[3,7],[38,40],[8,9],[11,20],[25,"a..z"],[15,23]]
              #    → length 8 → 1 (truthy)
    ˜         #  Take the input implicit again, and flatten it
              #   i.e. [[1,4],["a..z",-5],[3,7],[38,40],[8,9],[11,20],[25,"a..z"],[15,23]]
              #    → [1,4,"a..z",-5,3,7,38,40,8,9,11,20,25,"a..z",15,23]
     AK       #  Remove the alphabet
              #   i.e. [1,4,"a..z",-5,3,7,38,40,8,9,11,20,25,"a..z",15,23]
              #    → ['1','4','-5','3','7','38','40','8','9','11','20','25','15','23']
       ï      #  Cast everything to an integer, because `K` turns them into strings..
              #   i.e. ['1','4','-5','3','7','38','40','8','9','11','20','25','15','23']
              #    → [1,4,-5,3,7,38,40,8,9,11,20,25,15,23]
        D     #  Duplicate it
         W<   #  Determine the min - 1
              #   i.e. [1,4,-5,3,7,38,40,8,9,11,20,25,15,23] → -5
           U  #  Pop and store it in variable `X`
         Z>   #  Determine the max + 1
              #   i.e. [1,4,-5,3,7,38,40,8,9,11,20,25,15,23] → 40
           V  #  Pop and store it in variable `Y`
Iø            #  Take the input again, and transpose/zip it (swapping rows and columns)
              #   i.e. [[1,4],["a..z",-5],[3,7],[38,40],[8,9],[11,20],[25,"a..z"],[15,23]]
              #    → [[1,'a..z',3,38,8,11,25,15],[4,-5,7,40,9,20,'a..z',23]]
  ε       }   #  Map both to:
   A          #   Push the lowercase alphabet
    XY       #   Push variables `X` and `Y`, and pair them into a list
       Nè     #   Index into this list, based on the index of the mapping
         :    #   Replace every alphabet with this min-1 or max+1
              #   i.e. [[1,'a..z',3,38,8,11,25,15],[4,-5,7,40,9,20,'a..z',23]]
              #    → [['1','-6','3','38','8','11','25','15'],['4','-5','7','40','9','20','41','23']]
ï             #  Cast everything to integers again, because `:` turns them into strings..
              #   i.e. [['1','-6','3','38','8','11','25','15'],['4','-5','7','40','9','20','41','23']]
              #    → [[1,-6,3,38,8,11,25,15],[4,-5,7,40,9,20,41,23]]
 ø            #  Now zip/transpose back again
              #   i.e. [[1,-6,3,38,8,11,25,15],[4,-5,7,40,9,20,41,23]]
              #    → [[1,4],[-6,-5],[3,7],[38,40],[8,9],[11,20],[25,41],[15,23]]
  {           #  Sort the pairs based on their lower range (the first number)
              #   i.e. [[1,4],[-6,-5],[3,7],[38,40],[8,9],[11,20],[25,41],[15,23]]
              #    → [[-6,-5],[1,4],[3,7],[8,9],[11,20],[15,23],[25,41],[38,40]]
   ©          #  Store it in the register (without popping)
˜             #  Flatten the list
              #   i.e. [[-6,-5],[1,4],[3,7],[8,9],[11,20],[15,23],[25,41],[38,40]]
              #    → [-6,-5,1,4,3,7,8,9,11,20,15,23,25,41,38,40]
 ¦            #  And remove the first item
              #   i.e. [-6,-5,1,4,3,7,8,9,11,20,15,23,25,41,38,40]
              #    → [-5,1,4,3,7,8,9,11,20,15,23,25,41,38,40]
  2ô          #  Then pair every two elements together
              #   i.e. [-5,1,4,3,7,8,9,11,20,15,23,25,41,38,40]
              #    → [[-5,1],[4,3],[7,8],[9,11],[20,15],[23,25],[41,38],[40]]
    í         #  Reverse each pair
              #   i.e. [[-5,1],[4,3],[7,8],[9,11],[20,15],[23,25],[41,38],[40]]
              #    → [[1,-5],[3,4],[8,7],[11,9],[15,20],[25,23],[38,41],[40]]
     Æ        #  Take the difference of each pair (by subtracting)
              #   i.e. [[1,-5],[3,4],[8,7],[11,9],[15,20],[25,23],[38,41],[40]]
              #    → [6,-1,1,2,-5,2,-3,40]
      1      #  Determine for each if they're larger than 1
              #   i.e. [6,-1,1,2,-5,2,-3,40] → [1,0,0,1,0,1,0,1]
            #  Create every possible partition of these values
              #   i.e. [1,0,0,1,0,1,0,1] → [[[1],[0],[0],[1],[0],[1],[0],[1]],
              #                             [[1],[0],[0],[1],[0],[1],[0,1]],
              #                             ...,
              #                             [[1,0,0,1,0,1,0],[1]],
              #                             [[1,0,0,1,0,1,0,1]]]
  ʒ         } #  Filter the partitions by:
   í          #   Reverse each inner partition
              #    i.e. [[1],[0,0,1],[0,1],[0,1]] → [[1],[1,0,0],[1,0],[1,0]]
    ε     }   #   Map each partition to:
     ć        #    Head extracted
              #     i.e. [1,0,0] → [0,0] and 1
              #     i.e. [1] → [] and 1
              #     i.e. [1,0,1] → [1,0] and 1
      s       #    Swap so the rest of the list is at the top of the stack again
       O      #    Take its sum
              #     i.e. [0,0] → 0
              #     i.e. [] → 0
              #     i.e. [1,0] → 1
        _     #    And check if it's exactly 0
              #     i.e. 0 → 1 (truthy)
              #     i.e. 1 → 0 (falsey)
         *    #    And multiply it with the extracted head
              #    (is only 1 when the partition has a single trailing 1 and everything else a 0)
              #     i.e. 1 and 1 → 1 (truthy)
              #     i.e. 1 and 0 → 0 (falsey)
           P  #   And check if all mapped partitions are 1
н             #  Take the head (there should only be one valid partition left)
              #   i.e. [[[1],[0,0,1],[0,1],[0,1]]] → [[1],[0,0,1],[0,1],[0,1]]
 g           #  Take the length of each inner list
              #   i.e. [[1],[0,0,1],[0,1],[0,1]] → [1,3,2,2]
   ®          #  Push the sorted pairs we've saved in the register earlier
    £         #  Split the pairs into sizes equal to the partition-lengths
              #   i.e. [1,3,2,2] and [[-6,-5],[1,4],[3,7],[8,9],[11,20],[15,23],[25,41],[38,40]]
              #    → [[[-6,-5]],[[1,4],[3,7],[8,9]],[[11,20],[15,23]],[[25,41],[38,40]]]
ε             #  Map each list of pairs to:
 ø            #   Zip/transpose (swapping rows and columns)
              #    i.e. [[1,4],[3,7],[8,9]] → [[1,3,8],[4,7,9]]
              #    i.e. [[25,41],[38,40]] → [[25,38],[41,40]]
  ©           #   Store it in the register
   θ          #   Take the last list (the ending ranges)
              #    i.e. [[25,38],[41,40]] → [41,40]
    à         #   And determine the max
              #    i.e. [41,40] → 41
     DYQi }   #   If this max is equal to variable `Y`
              #     i.e. 41 (`Y` = 41) → 1 (truthy)
         A    #    Replace it back to the lowercase alphabet
           V  #   Store this max in variable `Y`
  ®           #   Take the zipped list from the register again
   н          #   This time take the first list (the starting ranges)
              #    i.e. [[25,38],[41,40]] → [25,38]
    ß         #   And determine the min
              #    i.e. [25,38] → 25
     DXQi }   #   If this min is equal to variable `X`
              #     i.e. 25 (`X` = -6) → 0 (falsey)
         A    #    Replace it back to the lowercase alphabet
           Y #   And pair it up with variable `Y` (the max) to complete the mapping
              #    i.e. 25 and 'a..z' → [25,'a..z']
              #  Implicitly close the mapping (and output the result)
              #   i.e. [[[-6,-5]],[[1,4],[3,7],[8,9]],[[11,20],[15,23]],[[25,41],[38,40]]]
              #    → [['a..z',-5],[1,9],[11,23],[25,'a..z']]
              # Implicit else (only one pair in the input):
              #  Output the (implicit) input as is
              #   i.e. [[1,3]]
Kevin Cruijssen
la source
1

C (clang) , 346 342 octets

Drapeaux du compilateur -DP=printf("(%d,%d)\n", -DB=a[i+1]et-DA=a[i]

typedef struct{int a,b;}t;s(t**x,t**y){if((*x)->a>(*y)->a)return 1;else if((*x)->a<(*y)->a)return -1;}i;f(t**a){for(i=0;A;)i++;qsort(a,i,sizeof(t*),s);for(i=0;B;i++){if(B->a<=A->b+1){A->b=B->b;if(B->a<A->a)A->a=B->a;else B->a=A->a;}}for(i=0;A;i++){if(!B)break;if(A->a!=B->a)P,A->a,A->b);}P,A->a,A->b);}

Essayez-le en ligne!

Logern
la source
Je pense que vous comptez sur ila valeur globale de.
Jonathan Frech
@JonathanFrech signifie que cela while(A)i++;devrait être for(i=0;A;)i++;défini explicitement i=0avant de l'utiliser dans la boucle while, au lieu d'utiliser sa 0valeur par défaut au niveau global. Je ne sais plus pourquoi, mais c'est requis selon les méta-règles. Principalement parce que les méthodes doivent être autonomes / réutilisables, sans avoir à réinitialiser les valeurs globales entre les appels de méthode, IIRC.
Kevin Cruijssen
Correction de la dépendance à la ivaleur globale
Logern
246 octets
plafond du
1

Stax , 46 39 octets

ÿδ7│ⁿ╚╪║»ÿ1Wç♥├óπ◙+╣╝[á╬p£ß₧ΓÑ°♥ºië«4T╗

Exécuter et déboguer

Ce programme prend l'entrée dans la notation de chaîne spécifiée à l'origine.

récursif
la source