Napraw zakresy


30

Biorąc pod uwagę listę dodatnich liczb całkowitych z niektórymi zamienionymi na 0, wypisz listę z brakującymi liczbami, które zostały zmienione na 0zamienione.

Charakterystyka listy danych wejściowych:

  • Lista zawsze będzie miała długość co najmniej 2.

  • Zdefiniujmy listę wejściową jako ai „oryginalną listę” (czyli listę przed zastąpieniem liczb 0s) jako b. Dla każdego n, a[n]jest albo b[n]albo 0.

  • Dla każdego n, b[n]jest albo b[n-1] + 1albo b[n-1] - 1. Oznacza to, że liczby bbędą zawsze zmieniały się 1przy każdym indeksie od poprzedniego. Pierwszy element jest oczywiście zwolniony z tej zasady.

  • Dla każdego przebiegu zer w a(to znaczy kolejne elementy zastąpione 0), z xco stanowi wskaźnik na początku cyklu, a y reprezentujących koniec, a[x-1]aby a[y+1]zawsze albo wyłącznie zwiększenia lub jedynie maleje. Dlatego będzie tylko jeden możliwy sposób wypełnienia zer.

    • Oznacza to również, że ani pierwszy, ani ostatni element tablicy nie może być zerami.

Mówiąc prościej, aby wypełnić ciąg zer, po prostu zastąp go zakresem od liczby poprzedzającej do liczby następującej po niej. Na przykład wejście

1 2 0 0 0 6 7

musi generować

1 2 3 4 5 6 7

Ponieważ jest to , wygra najkrótszy kod w bajtach.

Przypadki testowe:

In                      Out
-----------------------------------------------------
1 0 0 0 5 6 0 4 0 0 1 | 1 2 3 4 5 6 5 4 3 2 1
7 6 0 0 3 0 0 0 7 0 5 | 7 6 5 4 3 4 5 6 7 6 5
1 0 3 0 5 0 3 0 5 0 7 | 1 2 3 4 5 4 3 4 5 6 7
14 0 0 0 0 0 0 0 0 23 | 14 15 16 17 18 19 20 21 22 23

Zamiast tego 0nasz program może przyjąć inną wartość, na przykład null?
Downgoat

@Downgoat Nie, brakujące liczby należy podać jako 0.
Klamka

Odpowiedzi:


15

JavaScript (ES6), 72 66 64 54 53 bajty

Zaoszczędź 12 bajtów dzięki @Neil!

Zapisano 1 bajt dzięki @IsmaelMiguel

a=>a.map((l,i)=>l?b=l:b+=a.find((q,r)=>r>i&&q)>b||-1)

Całkiem dobrze jak na JavaScript.


Wypróbuj online (wszystkie przeglądarki działają)

Wyjaśnienie

a=>  // Function with arg `a`
  a.map((l,i)=>  // Loop through input
    l?             // If nonzero
      b=l          // Set `b` to current number
    :a.find((q,r)=>r>i&q) // Otherwise look for the next nonzero number
     >b?           // If it's increased since nonzero last number   
       ++b:--b)    // Increasing? increase `b` (the previous nonzero number)
                   // otherwise decrease `b`

1
Myślę, że a.find((q,r)=>r>i&&q)>b?++b:--bto to samo cob+=a.find((q,r)=>r>i&&q)>b||-1
Ismael Miguel

@IsmaelMiguel, który jest inteligentny, dzięki!
Downgoat

Nie ma za co. Cieszę się, że ci się udało.
Ismael Miguel

Myślę, że możesz zastąpić && just & (Właśnie zauważyłem, że masz jedno i wyjaśnienie, a dwa w odpowiedzi)
Charlie Wynn

7

MATL , 11 12 bajtów

fGXzGn:3$Yn

Działa z bieżącą wersją (13.0.0) języka / kompilatora.

Wypróbuj online!

f        % implicitly input array. Indices of nonzero elements (*)
GXz      % push input and get its nonzero elements (**)
Gn:      % vector [1,2,...,n], where n is input length (***)
3$Yn     % interpolate at positions (***) from data (**) defined at positions (*)

7

Haskell, 68 61 58 bajtów

g(a:b:r)=[a..b-1]++[a,a-1..b+1]++g(b:r)
g x=x
g.filter(>0)

Przykład użycia: g.filter(>0) $ [7,6,0,0,3,0,0,0,7,0,5]-> [7,6,5,4,3,4,5,6,7,6,5].

Jak to działa: usuń z wejścia zera, a następnie zadzwoń g. Niech abędzie pierwszym, a bnastępnie drugim elementem pozostałej listy. Połącz listy od agóry do b-1i od adołu do b+1(jedna z nich będzie pusta), a połączenie rekurencyjne zostanie ausunięte.

Edycja: @Zgarb zapisał 3 bajty. Dzięki!


6

Mathematica, 59 bajtów

#//.{a___,x_,0..,y_,b___}:>{a,##&@@Range[x,y,Sign[y-x]],b}&

Przypadek testowy

%[{1,0,3,0,5,0,3,0,5,0,7}]
(* {1,2,3,4,5,4,3,4,5,6,7} *)

4

Perl, 47 45 44 39 37 bajtów

Obejmuje +1 dla -p

s%\S+%$p+=/\G(0 )+/?$'<=>$p:$&-$p%eg

Oczekuje listy na standardowe wejście. Przykład: echo 1 0 3 0 1 | perl -p file.pl


Widzę tu wklejanie kopii .. ;-) Ładnie wykonane btw.
Kenney,

3

Galaretka, 12 11 bajtów

ḢWW;ḟ0Ṫr¥\F

Wypróbuj online!

Alternatywna wersja, 8 bajtów (niekonkurująca)

Niestety, Jelly's popnie poddało się iteracji w najnowszej wersji, która poprzedza to wyzwanie. Zostało to naprawione, a następujące działania działają w bieżącej wersji.

ḟ0Ṫr¥\FḊ

Wypróbuj online!

Jak to działa

ḢWW;ḟ0Ṫr¥\F  Main link. Input: A (list)

Ḣ            Pop the first element of A. Let's call it a.
 WW          Yield [[a]].
   ;         Concatenate with the popped A.
             This wraps the first element of A in an array.
    ḟ0       Filter; remove all zeroes.
        ¥    Create a dyadic chain:
      Ṫ        Pop the last element of the left argument.
       r       Call range on the popped element and the right argument.
         \   Reduce the modified A by this chain.
          F  Flatten the resulting list of ranges.

W alternatywnej wersji ḢWW;staje się niepotrzebny. Ponieważ jednak pierwszy element jest rzutowany na iterowalny przed pojawieniem się, nie jest tak naprawdę modyfikowany. Finał usuwa duplikat pierwszego elementu.


3

Retina, 39 34 31 bajtów

3 bajty zapisane dzięki @Martin.

+`1(1*) (?= +((1)\1)?)
$0$1$3$3

Pobiera dane wejściowe i podaje dane wyjściowe jako jednoargumentowy.

Kod iteracyjnie wypełnia każde puste miejsce (0) previous_number - 1 + 2 * if_next_nonzero_number_bigger. previous_number - 1jest $1i if_next_nonzero_number_biggerjest $3.

W przypadku dziesiętnych operacji we / wy kod ma 51 bajtów, co widać w tłumaczeniu online ze wszystkimi przypadkami testowymi .


Możesz zapisać kolejny bajt, pomijając pierwszy 1w Lookahead.
Martin Ender

@ MartinBüttner Right, zredagowane.
randomra

2

GNU Sed (z execrozszerzeniem za pomocą bash), 61

Wynik obejmuje +1 za -ropcję sed.

:
s/( 0)+ /../
s/\w+..\w+/{&}/
s/.*/bash -c 'echo &'/e
/ 0/b
  • Znajdź serie 0s i zamień je..
  • Umieść nawiasy klamrowe wokół numerów punktów końcowych, aby utworzyć rozwinięcie nawiasu klamrowego, tak jak {1..4}dla lokalnych punktów końcowych. Piękno ekspansji nawiasów klamrowych polega na tym, że wygenerowana sekwencja zawsze będzie przebiegać we właściwym kierunku, niezależnie od tego, czy początek czy koniec jest większy.
  • Użyj eopcji spolecenia, aby wywołać bash, aby ocenić to rozwinięcie nawiasu
  • Jeśli 0znaleziono więcej s, wróć do początku.

Ideone.


2

Python 2, 195 111 bajtów (dzięki Alex !)

t=input()
z=0
for i,e in enumerate(t):
 if e:
  while z:t[i-z]=e+z if l>e else e-z;z-=1
  l=e
 else:z+=1
print t

Dane wejściowe: musi być a [list]ints Dane
wyjściowe: [list]ints


Przepraszam za to! Naprawiony. Dzięki za heads-upy.
vageli

Bez obaw. Niezłe rozwiązanie. :) Za pomocą tego możesz sprowadzić go do 112 bajtów , co jest twoim podejściem, tylko trochę bardziej golfowym. Mamy również zbiór wskazówek dla golfa w Pythonie tutaj .
Alex A.

1

Perl, 85 82 bajtów

zawiera +1 dla -p

s/(\d+)(( 0)+) (\d+)/$s=$1;$e=$4;$_=$2;$c=$s;s!0!$c+=$e<=>$s!eg;"$s$_ $e"/e&&redo

Oczekuje listy na standardowe wejście. Przykład: echo 1 0 3 0 1 | perl -p file.pl.

Używa zagnieżdżonego wyrażenia regularnego. Nieco czytelne:

s/(\d+)(( 0)+) (\d+)                  # match number, sequence of 0, number
 /
    $s=$1;                            # start number
    $e=$4;                            # end number
    $_=$2;                            # sequence of ' 0'
    $c=$s;                            # initialize counter with start number
    s!0! $c += $s <=> $e !eg          # replace all 0 with (in|de)cremented counter
    "$s$_ $e"                         # return replacement
 /e
&& redo                               # repeat until no more changes.

1

Python 2, 92 88 bajtów

(Usunięto zmienną pośrednią)

t=filter(bool,input())
print sum([range(o,p,cmp(p,o))for o,p in zip(t,t[1:])],[])+t[-1:]

1

Pyth, 17 bajtów

u+G+treGHHfTtQ[hQ

Jak to działa:

u                 reduce
              [hQ     seed: the first element of input, in a list
                      iterable:
          tQ              all except the first element of input
        fT                remove if 0
                      lambda: G is the list to be returned, H is the current item
 +G                       append to return list
    reGH                  a range from the last element of the return list and the current item
   +                      concatenated with
        H                 the last item (this step forms a bidirectional inclusive list)

Innymi słowy: wszystkie zera są usuwane z danych wejściowych, następnie wyłączny zakres jest wstawiany między każdy element. Ten zakres wynosi zero dla elementów tylko jednego od siebie.



1

Vim: 231 kluczowych poleceń

Zauważ, że każde ^ poprzedzające znak oznacza, że ​​powinieneś zachować kontrolę podczas pisania tego znaku

mbomayiwo^V^R"^V^V^V^X ^V^["sy0dd`a@f ^["bc0yiwo^V^V^V^X^V^R"^V^[0l@sa^V^V^V^A-^V^[0f-"ayhdd`a@i ^["dc0mbyiwo^V^R"Exe@b^V^[0fel"ty2ldd`b@t ^["ec0wmbyiwo@f @d^V^[@z ^["fc0"xyiwwmbyiwocw^V^V^V^Rx^V^V^V^[@a@i @e^V^[@z ^["ic0IB0 B^V^R" ^V^OWB0 ^V^OA B0^V^[0*w"tyiWdd`b@t ^["zd0dd`bAe^[0@e 

Kroki, abyś mógł to uruchomić!

  1. Skopiuj linię do Vima
  2. Wpisz :s/\^V/<Ctrl-V><Ctrl-V>/gi naciśnij enter (dwa s powinny dać ci niebieskie ^ V)
  3. Wpisz :s/\^R/<Ctrl-V><Ctrl-R>/gi naciśnij klawisz Enter (teraz powinieneś zobaczyć niebieski ^ Rs)
  4. Wpisz :s/\^X/<Ctrl-V><Ctrl-X>/gi naciśnij klawisz Enter (teraz powinieneś zobaczyć niebieski ^ Xs)
  5. Wpisz :s/\^O/<Ctrl-V><Ctrl-O>/gi naciśnij enter
  6. Wpisz :s/\^A/<Ctrl-V><Ctrl-A>/gi naciśnij enter
  7. Wpisz :s/\^\[/<Ctrl-V><Ctrl-[>/gi naciśnij klawisz Enter (to polecenie jest nieco inne, ponieważ musiałem uciec przed [)
  8. Wpisz 0"yy$. Polecenie jest teraz przechowywane w rejestrze y
  9. Skonfiguruj dane wejściowe w linii i uruchom z @y

Jeśli ktoś zna lepszy sposób udostępniania polecenia, daj mi znać. Wiem, że to jest długie, ale najlepsze, co mogłem wymyślić.

Wejście wyjście

Łańcuch wejściowy powinien być sam w dowolnym wierszu pliku. 1 0 0 4 3 0 0 0 7

Dane wyjściowe po prostu nadpisują ciąg wejściowy 1 2 3 4 3 4 5 6 7

Wyjaśnienie

Algorytm

  1. Zacznij od niezerowej liczby, upewnij się, że nie jest to ostatni numer
  2. Znajdź następny niezerowy numer
  3. Weź ich różnicę. Jeśli odpowiedź jest przecząca, należy zmniejszyć wartość, aby naprawić zakres, w przeciwnym razie należy zwiększyć wartość, aby naprawić zakres.
  4. Wróć do pierwszego znaku i zamień każde zero, zwiększając / zmniejszając poprzedni numer.
  5. Powtarzaj, aż dojdziesz do ostatniej postaci

Makra używane

@e - Sprawdź koniec. Do ostatniego numeru zostanie dołączony e. Jeśli liczba pod kursorem ma na końcu e, usuń e i zatrzymaj wykonywanie. W przeciwnym razie rozpocznij cykl interpolacji za pomocą @b.

mbyiwo^R"Exe@b^[0fel"ty2ldd`b@t

@b - Rozpocznij cykl interpolacji. Zapisz liczbę pod kursorem dla operacji odejmowania (@s), a następnie znajdź następny niezerowy termin (@f)

mayiwo^R"^V^X ^["sy0dd`a@f

@s - Przechowuje polecenie odejmowania do użycia w @d. To jest po prostu (val)^Xgdzie (val)jest liczba na początku kroku interpolacji. Ustawia się to za pomocą polecenia @b.

@f - Znajdź następny niezerowy termin. Zapisz bieżącą wartość do rejestru bez nazwy, następnie napisz @f @dw następnym wierszu, a następnie uruchom @z. Powtórzy to polecenie, jeśli liczba jest zerem, i wykona @d, jeśli nie jest.

wmbyiwo@f @d^[@z

@z - warunkowe wykonanie, jeśli rejestr bez nazwy ma wartość 0. To polecenie oczekuje dwóch poleceń w nowym wierszu w formacie command1 command2. Jeśli rejestr bez nazwy ma wartość 0, command1jest wykonywany, w przeciwnym razie command2jest wykonywany. Zauważ, że żadne polecenie nie może zawierać spacji.

 IB0 B^R" ^OWB0 ^OA B0^[0*w"tyiWdd`b@t`

@t - Tymczasowy rejestr poleceń. Przechowuje różne polecenia przez krótki czas przed ich wykonaniem. Używany głównie w instrukcjach if.

@d - Określ kierunek interpolacji. Odejmuje pierwszą liczbę w sekwencji od liczby pod kursorem (używając @s). Jeśli wynik jest ujemny, interpolacja musi zostać zmniejszona, aby ^ X zostało zapisane w @a. W przeciwnym razie powinniśmy zwiększyć, aby ^ A zostało zapisane w @a. Po zapisaniu, wróć na początek tego cyklu interpolacji i uruchom @i, aby faktycznie interpolować

yiwo^V^X^R"^[0l@sa^V^A-^[0f-"ayhdd`a@i

@a - Zapisanie albo ^Alub ^Xzwiększać lub zmniejszać w czasie etapu interpolacji. Ustawia się to za pomocą polecenia @d.

@i - Interpoluj. Skopiuj numer z bieżącej lokalizacji do @x i przejdź do następnego numeru. Jeśli liczba ta wynosi zero, zamień ją na @x i uruchom @a, aby poprawnie ją zmienić w górę lub w dół, a następnie powtórz to polecenie. Jeśli liczba nie jest zerem, osiągnęliśmy koniec tego cyklu interpolacji. Nowy należy rozpocząć od tego numeru na początku, więc uruchom @e, aby sprawdzić koniec i uruchom ponownie.

"xyiwwmbyiwocw^V^Rx^V^[@a@i @e^[@z

@x - Rejestr tymczasowego przechowywania. Używany w poleceniu interpolacji (@i)

Rozbijanie naciśnięć klawiszy

mbo :Set b mark to current position and open a new line below to write macros
mayiwo^V^R"^V^V^V^X ^V^["sy0dd`a@f ^["bc0 :Write to @b and reset line

yiwo^V^V^V^X^V^R"^V^[0l@sa^V^V^V^A-^V^[0f-"ayhdd`a@i ^["dc0 :Write to @d and reset line

mbyiwo^V^R"Exe@b^V^[0fel"ty2ldd`b@t ^["ec0 :Write to @e and reset line

wmbyiwo@f @d^V^[@z ^["fc0 :Write to @f and reset line

"xyiwwmbyiwocw^V^V^V^Rx^V^V^V^[@a@i @e^V^[@z ^["ic0 :Write to @i and reset line

IB0 B^V^R" ^V^OWB0 ^V^OA B0^V^[0*w"tyiWdd`b@t ^["zd0 :Write to @z and reset line

dd`b :Delete this line and move cursor back to original line

Ae^[ :Append an e to the last number

0@e  :Move to the beginning of the line and run

0

Python 3.5, 159 bajtów

rozwiązanie rekurencyjne

def f(s):
 h=s[0]
 g=lambda s,h,v:h*(h[-1]==s[0])if len(s)==1else(g(s[1:],h+[h[-1]-v],-v)+g(s[1:],h+[h[-1]+v],+v))*(s[0]==0 or h[-1]==s[0])
 return g(s,[h],1)

Bez golfa

def f(s):
    h=s[0]
    def g(s,h,v):
        if len(s)==1:
            if h[-1]!=s[0]:
                r=[]
            else:
                r=h
        else:
            if s[0]==0:
                r=g(s[1:],h+[h[-1]+v],v)
            elif h[-1]!=s[0]:
                r=[]
            else:
                r=g(s[1:],h+[h[-1]-v],-v)+g(s[1:],h+[h[-1]+v],+v)
        return r
return g(s,[h],1)

W rozwiązaniu golfowym zastępuję warunki, wykorzystując fakt, że h*True=hih*False=[]

Wynik

>>> f([7, 6, 0, 0, 3, 0, 0, 0, 7, 0, 5])
[7, 6, 5, 4, 3, 4, 5, 6, 7, 6, 5]


0

MATLAB, 39 38 37 bajtów

@(a)interp1(find(a),a(a>0),find(a/0))

Anonimowa funkcja interpolująca liniowo między punktami w a. find(a)to tablica wskaźników elementów niezerowych w ai a(a>0)są wartościami dodatnimi. Zapisane 1 bajt dzięki sugestii kolegi z >zamiast ~=.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.