Wpisz ciąg rosnący, używając jak największej liczby liczb

29

Lista liczb nazywana jest monotonicznie rosnącym (lub nie malejącym), jeśli każdy element jest większy lub równy pierwiastkowi przed nim.

Na przykład 1, 1, 2, 4, 5, 5, 5, 8, 10, 11, 14, 14monotonicznie rośnie.

Biorąc pod uwagę monotonicznie rosnącą listę dodatnich liczb całkowitych, które mają dowolną liczbę pustych miejsc oznaczonych przez ?, wypełnij puste miejsca dodatnimi liczbami całkowitymi, tak aby na liście było jak najwięcej unikalnych liczb całkowitych, ale nadal monotonicznie rośnie.

Istnieje wiele sposobów osiągnięcia tego celu. Każda jest ważna.

Wyświetl wynikową listę.

Na przykład , jeśli dane wejściowe to

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

gwarantuje się, że bez pustych miejsc lista będzie monotonicznie powiększana

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

a Twoim zadaniem jest przypisanie dodatnich liczb całkowitych do każdej z nich, ?aby zmaksymalizować liczbę różnych liczb całkowitych na liście, jednocześnie nie zmniejszając jej.

Jedno niepoprawne zadanie to

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

ponieważ chociaż nie zmniejsza się, ma tylko jedną unikalną liczbę całkowitą niż wejście, mianowicie 3.

W tym przykładzie można wstawić sześć unikatowych liczb całkowitych dodatnich i nie zmniejszać listy.
Kilka możliwych sposobów to:

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

Każdy z nich (i wiele innych) byłby prawidłowym wyjściem.

Wszystkie puste miejsca muszą zostać wypełnione.

Nie ma górnego limitu liczb całkowitych, które można wstawić. Jest ok, jeśli w notacji naukowej drukowane są bardzo duże liczby całkowite.

Zero nie jest dodatnią liczbą całkowitą i nigdy nie powinno być wstawiane.

Zamiast ?was może wykorzystać dowolną stałą wartość, która nie jest liczbą całkowitą dodatnią, takich jak 0, -1, null, False, lub "".

Najkrótszy kod w bajtach wygrywa.

Więcej przykładów

[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 *
Hobby Calvina
źródło
Prawdopodobnie lepszym sposobem sformułowania problemu, który ma ścisłe dane wejściowe i wyjściowe do weryfikacji, byłoby „Jaka jest najwyższa możliwa liczba różnych liczb w sekwencji”. W ten sposób wszystkie odpowiedzi wygenerują tę samą liczbę i znacznie ułatwią ocenę przypadków testowych
Cruncher
@StewieGriffin Możesz założyć, że wartości na liście i długość są poniżej maksymalnych wartości int. Chodziło mi tylko o to, że można wstawiać na końcu bardzo duże liczby całkowite, jeśli tak działa algorytm.
Calvin's Hobbies

Odpowiedzi:

11

Haskell , 41 bajtów

fpobiera listę i zwraca listę, gdzie 0 oznacza ?s.

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

Zasadniczo, pierwsza lista skanowania od lewej, zastępując zera o jeden więcej niż poprzedni element (lub 0 na początku); następnie skanuj od prawej, zmniejszając zbyt duże elementy, aby zrównać się z tymi po prawej.

Wypróbuj online! (z otoki do konwersji ?s.)

Ørjan Johansen
źródło
4

Mathematica, 84 bajty

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

Czysta funkcja przyjmująca listę jako argument, w której puste miejsca są oznaczane przez Null(jak w {1, Null, Null, 2, Null}) lub usuwane całkowicie (jak w {1, , , 2, }), i zwraca odpowiednią listę (w tym przypadku {1, 2, 2, 2, 3}).

Okazuje się, że używam tego samego algorytmu, co w odpowiedzi Haskella Ørjana Johansena : najpierw zamień każdy Nullo jeden więcej niż liczba po lewej ( //.{a___,b_,,c___}:>{a,b,b+1,c}), a następnie dowolną zbyt dużą liczbę na liczbę po prawej ( //.{a___,b_,c_,d___}/;b>c:>{a,c,c,d}). Aby poradzić sobie z możliwymi Nullliterami s na początku listy, zaczynamy od przygotowania 0( {0,##}&@@#), wykonania algorytmu, a następnie usunięcia początkowej 0( Rest).

Tak, wybrałem Nullzamiast Xlub coś w tym rodzaju, aby zapisać dosłownie jeden bajt w kodzie (ten, który w innym przypadku znajdowałby się między przecinkami b_,,c___).

Greg Martin
źródło
Hm, przygotowując 1 mówisz? Użyłem 0, z powodu takich rzeczy ?, 2. Podejrzewam, że wtedy produkowałbyś 2, 2zamiast właściwego 1, 2.
Ørjan Johansen
Doskonały punkt! Na szczęście naprawa jest łatwa.
Greg Martin
3

C 160

To nigdy nie wygra, ale:

#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)}

Pobiera listę z argumentów wiersza poleceń.

Jerry Jeremiasz
źródło
137 bajtów
ceilingcat
3

05AB1E , 31 23 13 bajtów

Oszczędność 10 bajtów dzięki Grimy

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

Wypróbuj online!

Wyjaśnienie

ε      ]       # 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
źródło
Dlaczego drukuje to tylko część wyniku? W twoim przykładzie TIO brakuje pierwszego 1.
Fatalize
Wiem, że minęło trochę czasu i prawdopodobnie można jeszcze trochę zagrać w golfa, ale -3 bajty z kilkoma łatwymi golfami: Oba }}mogą ]zaoszczędzić 2 bajty; i õ-)Rmoże być )˜Rzapisanie dodatkowego bajtu.
Kevin Cruijssen
2
@KevinCruijssen: Rzeczywiście może :)
Emigna
1
Nadal może! 16 , 15 , 13 .
Grimmy
@Grimy: Wow, dzięki! Ta sztuczka z przyrostkiem była naprawdę sprytna!
Emigna
2

Pip , 25 23 21 bajtów

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

Pobiera dane wejściowe jako wiele oddzielonych spacjami argumentów wiersza polecenia. Wysyła listę wyników o jeden numer w wierszu. Wypróbuj online! (Sfałszowałem wiele argumentów wiersza poleceń, ponieważ dodanie 25 argumentów do TIO byłoby utrudnione, ale działa również tak, jak reklamowano).

Wyjaśnienie

Wykonujemy dwa przejścia. Najpierw zamieniamy każdy ?ciąg s na wejściu na sekwencję rozpoczynającą się od poprzedniego numeru na liście i zwiększającą się o jeden za każdym razem:

? 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

Potem znów się zapętlamy; dla każdego numeru drukujemy jego minimum i wszystkie liczby po jego prawej stronie. To obniża zbyt wysokie liczby, aby utrzymać monotoniczność.

                      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
źródło
2

Python 2 z NumPy, 163 bajty

Zaoszczędzono 8 bajtów dzięki @wythagoras

Zero używane do oznaczania pustych miejsc

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:]

Bardziej czytelne z komentarzami:

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
Dead Possum
źródło
1
Kilka ulepszeń: if l[a]>l[b]:l[a]=l[b]może być, l[a]=min(l[a],l[b])a potem może być na linii wcześniej. Oznacza to również, że całą linię można umieścić po while. I myślę l=input()i l=[1]+lmoże być l=[1]+input()(Ogólnie: jeśli używasz dwóch poziomów wcięcia, możesz użyć spacji i tabulacji zamiast spacji i dwóch spacji w Pythonie 2 (patrz codegolf.stackexchange.com/a/58 ) )
wythagoras
1
Ponadto, obok ostatniego wiersza może znajdować się podczas len(z)-i:f(z[i-1],z[i]);i+=1rozpoczynania od i = 1.
wythagoras
@wythagoras Dziękuję, dobre porady. Dodałem to do kodu
Dead Possum
Fajnie, ale to tylko 163 bajty.
wythagoras
@wythagoras Oh, zapomniałem zaktualizować liczbę bajtów
Dead Possum
1

PHP, 95 77 71 69 68 bajtów

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

pobiera dane z argumentów wiersza poleceń, drukuje listę rozdzieloną spacjami. Uruchom z -nr.

awaria

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

$njest prawdą dla każdego łańcucha oprócz pustego łańcucha i "0".
$n>0jest prawdziwe dla liczb dodatnich - i ciągów je zawierających.

Tytus
źródło
1

Perl 6 , 97 bajtów

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

Dane wejściowe to albo lista wartości, albo ciąg oddzielony spacjami, gdzie ?służy do zastąpienia wartości do zamiany.

Dane wyjściowe to ciąg rozdzielany spacjami z końcową spacją.

Spróbuj

Rozszerzony:

{                       # 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
źródło
Nie znam Perla 6, ale w Perlu 5 możesz użyć $"zamiast ' 'golić bajt. Czy to działa tutaj?
msh210
@ msh210 Prawie wszystkie zmienne zniknęły lub mają dłuższe nazwy. O jedynej, która wciąż istnieje i ma ten sam cel, jest $!. ( $/istnieje, ale jest używany do $1$/[1]i $<a>$/{ qw< a > })
Brad Gilbert b2gills
1

JavaScript (ES6), 65 bajtów

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

Ponieważ chciałem użyć reduceRight. Objaśnienie: mapZastępuje każdą wartość fałsz jedną o więcej niż poprzednią, a następnie reduceRightwraca od końca, upewniając się, że żadna wartość nie przekracza następującej wartości.

Neil
źródło
1

Q, 63 bajty

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

Zasadniczo ten sam algorytm, co odpowiedź Haskella Ørjana Johansena .

  • Zakłada się? = 0
  • Wstawia 0 na początku tablicy w przypadku? na starcie.
  • Skanuje tablicę, zastępując 0 1 + poprzednim elementem.
  • Odwraca tablicę i skanuje ponownie, zastępując elementy większe niż poprzedni element poprzednim elementem.
  • Odwraca i wycina pierwszy element (dodane 0 od początku).

Wykorzystano min vs last, aby zapisać jeden bajt, ponieważ można założyć, że ostatnim elementem będzie element min, biorąc pod uwagę malejący rodzaj tablicy.

Daniel Plainview
źródło
Fajna odpowiedź, witamy na stronie! :)
DJMcMayhem
1

TI-Basic (TI-84 Plus CE), 81 bajtów

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

Prosty port odpowiedzi Haskell firmy Ørjan Johansen na TI-Basic. Używa 0 jako wartości zerowej. Pobiera dane z L 1 .

Wyjaśnienie:

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
pizzapanty184
źródło
1

Java 8, 199 164 bajtów

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

Zmienia tablicę wejściową zamiast zwracać nową, aby zapisać bajty.
Używa 0zamiast ?.

Wypróbuj online.

Wyjaśnienie:

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
źródło
0

Python 2 , 144 124 119 bajtów

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

Wypróbuj online!


Używa 0zamiast?

ovs
źródło
Nie b=filter(abs,l[n:])równa się b=l[n:] ?
Dead Possum,
@DeadPossum filter (abs ... odfiltrowuje wszystkie zera
OV
Och, to usuwa zera, rozumiem
Dead Possum
0

JavaScript (ES6), 59

Funkcja z tablicą liczb całkowitych jako wejściem. Puste miejsca są oznaczone symbolem0

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

Test

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
źródło
0

C # (.NET Core) , 182 bajty

Stosując tę ​​samą strategię jak Ørjan Johansen.

Używa 0 na liście danych wejściowych do oznaczenia nieznanego var.

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+" ");};

Wypróbuj online!

Destroigo
źródło
0

Perl 5 -p , 99 bajtów

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

Wypróbuj online!

Xcali
źródło