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, 14
augmente 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
, False
ou ""
.
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 *
la source
Réponses:
Haskell , 41 octets
f
prend une liste et renvoie une liste, 0 représentant?
s.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.)la source
Mathematica, 84 octets
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
Null
par 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 éventuelsNull
s au début de la liste, nous commençons par ajouter un0
({0,##}&@@#
), en faisant l'algorithme, puis en supprimant le initial0
(Rest
).Oui, j'ai choisi
Null
au lieu deX
ou quelque chose comme ça pour enregistrer littéralement un octet dans le code (celui qui serait autrement entre les virgules deb_,,c___
).la source
?, 2
. Je soupçonne que vous produirez alors2, 2
au lieu de la bonne1, 2
.C 160
Cela ne gagnera jamais mais:
Il prend la liste des arguments de ligne de commande.
la source
05AB1E ,
312313 octets10 octets enregistrés grâce à Grimy
Essayez-le en ligne!
Explication
la source
}}
peuvent être]
pour économiser 2 octets; etõ-)R
peut consister)˜R
à enregistrer un octet supplémentaire.Pip ,
252321 octetsPrend 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: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.
la source
Python 2 avec NumPy, 163 octets
8 octets enregistrés grâce à @wythagoras
Zéros utilisés pour marquer les espaces vides
Plus lisible avec des commentaires:
la source
if l[a]>l[b]:l[a]=l[b]
peut êtrel[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 lewhile
. Et je pensel=input()
etl=[1]+l
peut êtrel=[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 ) )len(z)-i:f(z[i-1],z[i]);i+=1
en commençant avec i = 1.PHP,
9577716968 octetsprend l'entrée des arguments de la ligne de commande, imprime la liste séparée par des espaces. Courez avec
-nr
.panne
$n
est vrai pour n'importe quelle chaîne, mais la chaîne vide et"0"
.$n>0
est vrai pour les nombres positifs - et les chaînes les contenant.la source
Perl 6 , 97 octets
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:
la source
$"
au lieu de' '
raser un octet. Est-ce que ça marche ici?$!
. ($/
existe mais est utilisé pour$1
→$/[1]
et$<a>
→$/{ qw< a > }
)JavaScript (ES6), 65 octets
Parce que je voulais utiliser
reduceRight
. Explication: lemap
remplace chaque valeur de falsification par une de plus que la valeur précédente, puisreduceRight
revient à la fin en veillant à ce qu'aucune valeur ne dépasse la valeur suivante.la source
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 .
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.
la source
TI-Basic (TI-84 Plus CE), 81 octets
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:
la source
Java 8,
199164 octetsModifie le tableau d'entrée au lieu d'en renvoyer un nouveau pour économiser des octets.
Utilise
0
au lieu de?
.Essayez-le en ligne.
Explication:
la source
Python 2 ,
144124119 119 octetsEssayez-le en ligne!
Utilise
0
au lieu de?
la source
b=filter(abs,l[n:])
égal àb=l[n:]
?JavaScript (ES6), 59
Une fonction avec un tableau d'entiers en entrée. Les espaces vides sont marqués avec
0
Tester
la source
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.
Essayez-le en ligne!
la source
Perl 5
-p
, 99 octetsEssayez-le en ligne!
la source