Remplissez une séquence croissante avec autant de nombres que possible

29

Une liste de nombres est appelée croissante monotone (ou non décroissante) si chaque élément est supérieur ou égal à l'élément qui le précède.

Par exemple, 1, 1, 2, 4, 5, 5, 5, 8, 10, 11, 14, 14augmente de façon monotone.

Étant donné une liste monotoniquement croissante d'entiers positifs qui a un nombre arbitraire de taches vides désignées par ?, remplissez les taches vides avec des entiers positifs de telle sorte que le plus grand nombre possible d'entiers uniques soient présents dans la liste, mais cela reste monotone.

Il peut y avoir plusieurs façons d'y parvenir. Tout est valide.

Sortez la liste résultante.

Par exemple , si l'entrée est

?, 1, ?, 1, 2, ?, 4, 5, 5, 5, ?, ?, ?, ?, 8, 10, 11, ?, 14, 14, ?, ?

il est garanti que sans les espaces vides, la liste augmentera de façon monotone

1, 1, 2, 4, 5, 5, 5, 8, 10, 11, 14, 14

et votre tâche consiste à affecter des entiers positifs à chacun ?pour maximiser le nombre d'entiers distincts dans la liste tout en la gardant non décroissante.

Une affectation non valide est

1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 8, 10, 11, 14, 14, 14, 14, 14

car, bien qu'il ne soit pas décroissant, il n'a qu'un seul entier de plus que l'entrée, à savoir 3.

Dans cet exemple, il est possible d'insérer six entiers positifs uniques et de maintenir la liste non décroissante.
Deux façons possibles sont:

1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 8, 8, 10, 11, 12, 14, 14, 15, 16

1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 5, 6, 6, 7, 8, 10, 11, 13, 14, 14, 20, 200

L'un ou l'autre (et bien d'autres) serait une sortie valide.

Tous les espaces vides doivent être remplis.

Il n'y a pas de limite supérieure sur les entiers qui peuvent être insérés. Ce n'est pas grave si de très grands nombres entiers sont imprimés en notation scientifique.

Zéro n'est pas un entier positif et ne doit jamais être inséré.

Au lieu de ?vous pouvez utiliser une valeur constante qui n'est pas un entier positif, comme 0, -1, null, Falseou "".

Le code le plus court en octets gagne.

Plus d'exemples

[input]
[one possible output] (a "*" means it is the only possible output)

2, 4, 10
2, 4, 10 *

1, ?, 3
1, 2, 3 *

1, ?, 4
1, 2, 4

{empty list}
{empty list} *

8
8 *

?
42

?, ?, ?
271, 828, 1729

?, 1
1, 1 *

?, 2
1, 2 *

?, 3
1, 3

45, ?
45, 314159265359

1, ?, ?, ?, 1
1, 1, 1, 1, 1 *

3, ?, ?, ?, ?, 30
3, 7, 10, 23, 29, 30 

1, ?, 2, ?, 3, ?, 4
1, 1, 2, 3, 3, 3, 4

1, ?, 3, ?, 5, ?, 7
1, 2, 3, 4, 5, 6, 7 *

1, ?, 3, ?, 5, ?, ?, 7
1, 2, 3, 4, 5, 6, 7, 7

1, ?, ?, ?, ?, 2, ?, ?, ?, ?, 4, ?, 4, ?, ?, 6
1, 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 5, 6, 6

98, ?, ?, ?, 102, ?, 104
98, 99, 100, 101, 102, 103, 104 *
Loisirs de Calvin
la source
Une meilleure façon de formuler le problème qui a une paire d'entrée / sortie stricte pour vérification serait probablement "Quel est le plus grand nombre possible de nombres distincts dans la séquence". De cette façon, toutes les réponses produiront le même nombre et rendra l'évaluation des cas de test beaucoup plus facile
Cruncher
@StewieGriffin Vous pouvez supposer que les valeurs de liste et la longueur sont inférieures aux maximums int comme d'habitude. Je voulais seulement dire que c'est correct d'insérer de très grands entiers à la fin si c'est ainsi que fonctionne votre algorithme.
Calvin's Hobbies

Réponses:

11

Haskell , 41 octets

fprend une liste et renvoie une liste, 0 représentant ?s.

f=scanr1 min.tail.scanl(#)0
m#0=m+1
_#n=n

Fondamentalement, la première liste de balayage à partir de la gauche, en remplaçant les 0 par un de plus que l'élément précédent (ou 0 au début); puis numérisez de droite en réduisant les éléments trop gros pour égaler celui de leur droite.

Essayez-le en ligne! (avec wrapper pour convertir ?s.)

Ørjan Johansen
la source
4

Mathematica, 84 octets

Rest[{0,##}&@@#//.{a___,b_,,c___}:>{a,b,b+1,c}//.{a___,b_,c_,d___}/;b>c:>{a,c,c,d}]&

Fonction pure prenant une liste en argument, où les espaces vides sont désignés par Null(comme dans{1, Null, Null, 2, Null} ) ou supprimés complètement (comme dans {1, , , 2, }), et renvoyant une liste appropriée (dans ce cas, {1, 2, 2, 2, 3}).

Il s'avère que j'utilise le même algorithme que dans la réponse Haskell d'Ørjan Johansen : remplacez d'abord chaque Nullpar un de plus que le nombre à sa gauche ( //.{a___,b_,,c___}:>{a,b,b+1,c}), puis remplacez tout nombre trop grand par le nombre à sa droite ( //.{a___,b_,c_,d___}/;b>c:>{a,c,c,d}). Pour traiter les éventuels Nulls au début de la liste, nous commençons par ajouter un 0({0,##}&@@# ), en faisant l'algorithme, puis en supprimant le initial 0( Rest).

Oui, j'ai choisi Nullau lieu de Xou quelque chose comme ça pour enregistrer littéralement un octet dans le code (celui qui serait autrement entre les virgules de b_,,c___).

Greg Martin
la source
Hm, préfixe 1 vous dites? J'ai utilisé un 0, à cause de choses comme ?, 2. Je soupçonne que vous produirez alors 2, 2au lieu de la bonne 1, 2.
Ørjan Johansen
Excellent point! Heureusement, la solution est simple.
Greg Martin
3

C 160

Cela ne gagnera jamais mais:

#define p(x)printf("%d ",x);
i=1,l=0,m=0,n;main(c,v)char**v;{for(;i<c;i++)if(*v[i]==63)m++;else{for(n=atoi(v[i]);m>0;m--)p(l<n?++l:n)p(l=n)}for(;m>0;m--)p(++l)}

Il prend la liste des arguments de ligne de commande.

Jerry Jeremiah
la source
137 octets
Plafond
3

05AB1E , 31 23 13 octets

10 octets enregistrés grâce à Grimy

ε®X:D>U].sR€ß

Essayez-le en ligne!

Explication

ε      ]       # apply to each number in input
 ®X:           # replace -1 with X (initially 1)
    D>U        # store current_number+1 in X
        .s     # get a list of suffixes
          R    # reverse
           ۧ  # take the minimum of each
Emigna
la source
Pourquoi cela n'imprime-t-il qu'une partie de la sortie? Dans votre exemple TIO, le premier 1 est manquant.
Fatalize
Je sais que cela fait un certain temps, et il peut probablement être joué un peu plus, mais -3 octets avec quelques golfs faciles: les deux }}peuvent être ]pour économiser 2 octets; et õ-)Rpeut consister )˜Rà enregistrer un octet supplémentaire.
Kevin Cruijssen
2
@KevinCruijssen: En effet, cela pourrait :)
Emigna
1
C'est toujours possible! 16 , 15 , 13 .
Grimmy
@Grimy: Wow, merci! Ce tour de suffixe était vraiment intelligent!
Emigna
2

Pip , 25 23 21 octets

Y{Y+a|y+1}MgW PMNyPOy

Prend l'entrée comme plusieurs arguments de ligne de commande séparés par des espaces. Sort la liste des résultats un numéro par ligne. Essayez-le en ligne! (J'ai truqué la chose avec plusieurs arguments de ligne de commande car ce serait difficile d'ajouter 25 arguments sur TIO, mais cela fonctionne aussi comme annoncé.)

Explication

Nous procédons en deux passes. Tout d'abord, nous remplaçons chaque série de ?s dans l'entrée par une séquence commençant par le numéro précédent de la liste et augmentant d'une fois à chaque fois:

? 1 ? 1 2 ? 4 5 5 5 ? ? ? ? 8 10 11 ?  14 14 ?  ?
1 1 2 1 2 3 4 5 5 5 6 7 8 9 8 10 11 12 14 14 15 16

Ensuite, nous bouclons à nouveau; pour chaque numéro, nous imprimons le minimum et tous les numéros à sa droite. Cela fait baisser les nombres trop élevés pour conserver la monotonie.

                      y is initially "", which is 0 in numeric contexts
                      Stage 1:
 {       }Mg           Map this function to list of cmdline args g:
   +a                  Convert item to number: 0 (falsey) if ?, else nonzero (truthy)
     |                 Logical OR
      y+1              Previous number +1
  Y                    Yank that value into y (it is also returned for the map operation)
Y                      After the map operation, yank the whole result list into y
                      Stage 2:
            W          While loop, with the condition:
               MNy      min(y)
              P         printed (when y is empty, MN returns nil, which produces no output)
                  POy  Inside the loop, pop the leftmost item from y
DLosc
la source
2

Python 2 avec NumPy, 163 octets

8 octets enregistrés grâce à @wythagoras

Zéros utilisés pour marquer les espaces vides

import numpy
l=[1]+input()
z=numpy.nonzero(l)[0]
def f(a,b):
 while b-a-1:a+=1;l[a]=l[a-1]+1;l[a]=min(l[a],l[b])
i=1
while len(z)-i:f(z[i-1],z[i]);i+=1
print l[1:]

Plus lisible avec des commentaires:

import numpy
l=[1]+input()           # add 1 to the begining of list to handle leading zeros
z=numpy.nonzero(l)[0]   # get indices of all non-zero values
def f(a,b):             # function to fill gap, between indices a and b
    while b-a-1:
        a+=1
        l[a]=l[a-1]+1   # set each element value 1 larger than previous element
        l[a]=min(l[a],l[b])   # caps it by value at index b
i=1
while len(z)-i:       
    f(z[i-1],z[i])      # call function for every gap
    i+=1
print l[1:]             # print result, excluding first element, added at the begining
Possum mort
la source
1
Quelques améliorations: if l[a]>l[b]:l[a]=l[b]peut être l[a]=min(l[a],l[b])et puis il peut être à la ligne avant cela. Cela signifie également que toute la ligne peut être placée après le while. Et je pense l=input()et l=[1]+lpeut être l=[1]+input()(aussi, en général: si vous utilisez deux niveaux d'indentation, vous pouvez utiliser un espace et un onglet au lieu d'un espace et de deux espaces en Python 2 (voir codegolf.stackexchange.com/a/58 ) )
wythagoras
1
De plus, l'avant-dernière ligne peut être tout len(z)-i:f(z[i-1],z[i]);i+=1en commençant avec i = 1.
wythagoras
@wythagoras Merci, bons conseils. Je l'ai ajouté au code
Dead Possum
Bien, mais il ne fait que 163 octets.
wythagoras
@wythagoras Oh, j'ai oublié de mettre à jour le nombre d'octets
Dead Possum
1

PHP, 95 77 71 69 68 octets

for($p=1;$n=$argv[++$i];)echo$p=$n>0?$n:++$p-in_array($p,$argv)," ";

prend l'entrée des arguments de la ligne de commande, imprime la liste séparée par des espaces. Courez avec -nr.

panne

for($p=1;$n=$argv[++$i];)   # loop through arguments
    echo$p=                     # print and copy to $p:
    $n>0                            # if positive number
        ?$n                             # then argument
        :++$p                           # else $p+1 ...
            -in_array($p,$argv)         # ... -1 if $p+1 is in input values
    ," ";                       # print space

$nest vrai pour n'importe quelle chaîne, mais la chaîne vide et "0".
$n>0est vrai pour les nombres positifs - et les chaînes les contenant.

Titus
la source
1

Perl 6 , 97 octets

{my $p;~S:g/(\d+' ')?<(('?')+%%' ')>(\d*)/{flat(+($0||$p)^..(+$2||*),(+$2 xx*,($p=$2)))[^+@1]} /}

L'entrée est soit une liste de valeurs, soit une chaîne séparée par des espaces, où ? est utilisée pour remplacer les valeurs à remplacer.

La sortie est une chaîne séparée par des espaces avec un espace de fin.

Essayez-le

Étendu:

{                       # bare block lambda with implicit parameter 「$_」

    my $p;              # holds the previous value of 「$2」 in cases where
                        # a number is sandwiched between two replacements

    ~                   # stringify (may not be necessary)
    S                   # replace
    :global
    /
        ( \d+ ' ' )?    # a number followed by a space optionally ($0)

        <(              # start of replacement

          ( '?' )+      # a list of question marks
          %%            # separated by (with optional trailing)
          ' '           # a space

        )>              # end of replacement

        (\d*)           # an optional number ($2)

    /{                  # replace with the result of:

        flat(

          +( $0 || $p ) # previous value or 0
          ^..           # a range that excludes the first value
          ( +$2 || * ), # the next value, or a Whatever star

          (
            +$2 xx *,   # the next value repeated endlessly

            ( $p = $2 ) # store the next value in 「$p」
          )

        )[ ^ +@1 ]      # get as many values as there are replacement chars
    } /                 # add a space afterwards
}
Brad Gilbert b2gills
la source
Je ne connais pas Perl 6, mais en Perl 5 vous pouvez utiliser $"au lieu de ' 'raser un octet. Est-ce que ça marche ici?
msh210
@ msh210 Presque toutes ces variables ont disparu ou ont des noms plus longs. Le seul qui existe toujours et qui a le même objectif est $!. ( $/existe mais est utilisé pour $1$/[1]et $<a>$/{ qw< a > })
Brad Gilbert b2gills
1

JavaScript (ES6), 65 octets

a=>a.map(e=>a=e||-~a).reduceRight((r,l)=>[r[0]<l?r[0]:l,...r],[])

Parce que je voulais utiliser reduceRight. Explication: le mapremplace chaque valeur de falsification par une de plus que la valeur précédente, puis reduceRightrevient à la fin en veillant à ce qu'aucune valeur ne dépasse la valeur suivante.

Neil
la source
1

Q, 63 octets

{1_(|){if[y>min x;y-:1];x,y}/[(|){if[y=0;y:1+-1#x];x,y}/[0,x]]}

Essentiellement le même algorithme que la réponse Haskell de Ørjan Johansen .

  • Suppose? = 0.
  • Insère un 0 au début du tableau en cas de? au début.
  • Analyse le tableau en remplaçant 0 par 1 + l'élément précédent.
  • Inverse le tableau et analyse à nouveau, en remplaçant les éléments supérieurs à l'élément précédent par l'élément précédent.
  • Inverse et coupe le premier élément (le 0 ajouté depuis le début).

L'utilisation de min vs last a été utilisée pour enregistrer un octet, car peut supposer que le dernier élément sera l'élément min compte tenu du tri décroissant du tableau.

Daniel Plainview
la source
Cool réponse, bienvenue sur le site! :)
DJMcMayhem
1

TI-Basic (TI-84 Plus CE), 81 octets

not(L1(1))+L1(1→L1(1
For(X,2,dim(L1
If not(L1(X
1+L1(X-1→L1(X
End
For(X,dim(L1)-1,1,-1
If L1(X)>L1(X+1
L1(X+1→L1(X
End
L1

Un simple portage de la réponse Haskell d' Ørjan Johansen à TI-Basic. Utilise 0 comme valeur nulle. Prend l'entrée de L 1 .

Explication:

not(L1(1))+L1(1→L1(1 # if it starts with 0, change it to a 1
For(X,2,dim(L1     # starting at element 2:
If not(L1(X              # if the element is zero
1+L1(X-1→L1(X            # change the element to one plus the previous element
End
For(X,dim(L1)-1,1,-1 # starting at the second-last element and working backwards
If L1(X)>L1(X+1           # if the element is greater than the next
L1(X+1→L1(X               # set it equal to the next
End
L1                   # implicitly return
pizzapants184
la source
1

Java 8, 199 164 octets

a->{for(int l=a.length,n,j,x,i=0;i<l;)if(a[i++]<1){for(n=j=i;j<l;j++)if(a[j]>0){n=j;j=l;}for(j=i-3;++j<n-1;)if(j<l)a[j+1]=j<0?1:a[j]+(l==n||a[n]>a[j]|a[n]<1?1:0);}}

Modifie le tableau d'entrée au lieu d'en renvoyer un nouveau pour économiser des octets.
Utilise 0au lieu de ?.

Essayez-le en ligne.

Explication:

a->{                      // Method with integer-array parameter and no return-type
  for(int l=a.length,     //  Length of the input-array
      n,j,x,              //  Temp integers
      i=0;i<l;)           //  Loop `i` over the input-array, in the range [0, length):
    if(a[i++]<1){         //   If the `i`'th number of the array is 0:
                          //   (And increase `i` to the next cell with `i++`)
      for(n=j=i;          //    Set both `n` and `j` to (the new) `i`
          j<l;j++)        //    Loop `j` in the range [`i`, length):
        if(a[j]>0){       //     If the `j`'th number of the array is not 0:
          n=j;            //      Set `n` to `j`
          j=l;}           //      And set `j` to the length to stop the loop
                          //    (`n` is now set to the index of the first non-0 number 
                          //     after the `i-1`'th number 0)
      for(j=i-3;++j<n-1;) //    Loop `j` in the range (`i`-3, `n-1`):
        if(j<l)           //     If `j` is still within bounds (smaller than the length)
          a[j+1]=         //      Set the `j+1`'th position to:
            j<0?          //       If `j` is a 'position' before the first number
             1            //        Set the first cell of the array to 1
            :             //       Else:
             a[j]+        //        Set it to the `j`'th number, plus:
              (l==n       //        If `n` is out of bounds bounds (length or larger)
               ||a[n]>a[j]//        Or the `n`'th number is larger than the `j`'th number
               |a[n]<1?   //        Or the `n`'th number is a 0
                1         //         Add 1
               :          //        Else:
                0);}}     //         Leave it unchanged by adding 0
Kevin Cruijssen
la source
0

Python 2 , 144 124 119 119 octets

l=input()
for n in range(len(l)):a=max(l[:n]+[0]);b=filter(abs,l[n:]);b=len(b)and b[0]or-~a;l[n]=l[n]or a+(b>a)
print l

Essayez-le en ligne!


Utilise 0au lieu de?

ovs
la source
N'est-ce pas b=filter(abs,l[n:])égal à b=l[n:] ?
Dead Possum
@DeadPossum filter (abs ... filtre tous les 0
ovs
Oh, cela supprime les zéros, je comprends
Dead Possum
0

JavaScript (ES6), 59

Une fonction avec un tableau d'entiers en entrée. Les espaces vides sont marqués avec0

a=>a.map((v,i)=>v?w=v:(a.slice(i).find(x=>x)<=w?w:++w),w=0)

Tester

var F=
a=>a.map((v,i)=>v?w=v:(a.slice(i).find(x=>x)<=w?w:++w),w=0)

;[[2, 4, 10]
,[1, 0, 3]
,[1, 0, 4]
,[]
,[8]
,[0]
,[0, 0, 0]
,[0, 1]
,[0, 2]
,[0, 3]
,[45, 0]
,[1, 0, 0, 0, 1]
,[3, 0, 0, 0, 0, 30]
,[1, 0, 2, 0, 3, 0, 4]
,[1, 0, 3, 0, 5, 0, 7]
,[1, 0, 3, 0, 5, 0, 0, 7]
,[1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 4, 0, 4, 0, 0, 6]
,[98, 0, 0, 0, 102, 0, 104]]
.forEach(a=>{
  console.log(a+'\n'+F(a))
})

edc65
la source
0

C # (.NET Core) , 182 octets

En utilisant la même stratégie que Ørjan Johansen.

Utilise 0 dans la liste d'entrée pour marquer la variable inconnue.

l=>{if(l[0]<1)l[0]=1;int j;for(j=0;j<l.Length;j++)l[j]=l[j]==0?l[j-1]+1:l[j];for(j=l.Length-2;j>=0;j--)l[j]=l[j]>l[j+1]?l[j+1]:l[j];foreach(var m in l) System.Console.Write(m+" ");};

Essayez-le en ligne!

Destroigo
la source
0

Perl 5 -p , 99 octets

s,(\d+ )?\K((\? )+)(?=(\d+)),$d=$1;$l=$4;$2=~s/\?/$d<$l?++$d:$l/rge,ge;($d)=/.*( \d+)/;s/\?/++$d/ge

Essayez-le en ligne!

Xcali
la source