Kiedy liczby całkowite dołączą do kolejki

26

Wprowadzenie

Kolejka jest abstrakcyjne typy danych, gdzie elementy są dodawane do przodu (Kolejkuj) i usuwa się z tyłu (rozkolejkowania). Jest to również znane jako zasada FIFO (First In First Out) .

Najlepiej pokazano to na przykładzie:

wprowadź opis zdjęcia tutaj


Wyzwanie

Biorąc pod uwagę niepusty tablicę zawierającą dodatnie liczby całkowite i elementy, które wskazują na rozkolejkowania (usunięcie elementu), wyjście końcowe lista kolejki.

Powiedzmy, że Xw tym przykładzie oznacza to dequeue. Rzućmy okiem na następującą listę:

[45, X, X, 37, 20, X, 97, X, 85]

Można to przetłumaczyć na następujący pseudo-kod kolejki:

                   Queue
Enqueue 45    ->   45
Dequeue       ->   
Dequeue       ->              (dequeue on an empty queue is a no-op)
Enqueue 37    ->   37
Enqueue 20    ->   20 37
Dequeue       ->   20
Enqueue 97    ->   97 20
Dequeue       ->   97
Enqueue 85    ->   85 97

Widać na końcu, że wynikiem jest wynik [85, 97]tej sekwencji.


Przypadki testowe

Pamiętaj, że możesz wybrać dowolny inny symbol lub znak X, o ile nie jest to dodatnia liczba całkowita.

[1, X, 2, X, 3, X]      ->     []
[1, 2, X]               ->     [2]
[1, 2, 3]               ->     [3, 2, 1]
[1, 2, X, X, X, 3]      ->     [3]
[1, 2, X, 3, X, 4]      ->     [4, 3]

To jest , więc wygrywanie z najmniejszą ilością bajtów wygrywa!

Adnan
źródło
Czy może to być ciąg oddzielony spacjami zamiast tablicy?
Riley
@ Riley Pewnie, cokolwiek będzie dla ciebie najlepsze
Adnan
2
Czy możemy użyć liczby ujemnej dla x (Haskell nie obsługuje list heterogenicznych)
Ogólna nazwa wyświetlana
2
... lub inne nieujemne liczby całkowite, takie jak zero lub pół?
Jonathan Allan
@GenericDisplayName Hmm, dobry punkt. Pozwolę na to, o ile nie będzie to dodatnia liczba całkowita
Adnan

Odpowiedzi:

4

Galaretka , 8 bajtów

F;@Ṗṛ?¥/

Używa dowolnej wartości fałszowania ( 0 lub pusta iterowalna) do usuwania z kolejki.

Wypróbuj online!

Jak to działa

F;@Ṗṛ?¥/  Main link. Argument: A (array)

       /  Reduce A by the link to the left.
      ¥     Combine the two links to the left into a dyadic chain.
F             Flatten the left argument.
    ṛ?        If the right argument is truthy:
 ;@             Concatenate the right argument and the flattened left argument.
              Else:
   Ṗ            Pop; remove the last element of the flattened left argument.
                This is why flattening is required, as Ṗ doesn't handle integers
                as intended for this challenge.
Dennis
źródło
1
W rzeczywistości nie jest to zabronione. Zabronione są tylko dodatnie liczby całkowite, 0 jest neutralne.
Erik the Outgolfer
Nie powiedziałem tego, kiedy opublikowałem odpowiedź, ale dziękuję za zgłoszenie się.
Dennis
8

Python 2, 56 53 50 bajtów

q=[]
for i in input():q=[[i]+q,q[:i]][i<0]
print q

Wypróbuj online!

Dequeue jest -1. Ta sztuczka pozwala na łatwe Pythonowe krojenie kolejki.

ćpun matematyki
źródło
7

Mathematica, 102 bajty

Zdecydowanie nie jest to najkrótsze rozwiązanie, ale nie mogłem się oprzeć, ponieważ to rodzaj przewrotności.

r=Reverse@{##}&
a_~f~b___:=b
f[a_,b___,]:=b
ToExpression[{"r[","f["~Table~StringCount[#,"]"],#}<>"]"]&

Po niektórych funkcjach pomocniczych definiuje to czystą funkcję, która przyjmuje ciąg znaków jako dane wejściowe: w ciągu liczby są oddzielane przecinkami (białe znaki są opcjonalne); postacią znaków jest "]"; a lista nie ma ograniczników z przodu ani z tyłu. Na przykład pierwszy przykład w OP byłby wprowadzony jako ciąg "45,],],37,20,],97,],85". Wynikiem funkcji jest lista liczb.

Funkcja zlicza liczbę dequeues "]"w ciągu wejściowym, dołącza tyle kopii z "f["przodu ciągu, a następnie otacza całość "r[...]". W powyższym przykładzie powoduje to "r[f[f[f[f[45,],],37,20,],97,],85]"; zauważ, że wsporniki są wyważone.

Następnie ToExpressioninterpretuje powstały ciąg jako fragment kodu Mathematica i wykonuje go. Funkcja fjest dogodnie zdefiniowana, aby zachować wszystkie argumenty oprócz pierwszego (a także ignoruje końcowe przecinki; jest to i tak konieczne do obsługi usuwania kolejek z pustych kolejek) i rkonwertuje wynikową sekwencję liczb na listę liczb we właściwej kolejności.

Greg Martin
źródło
Czy przecinek w linii 3 b___,ma być tam? To działa , ale zwoje przecinek czerwony powodu. (także, jaka jest różnica między wierszami 2 i 3?)
numbermaniac 7.04.17
1
Dobre oko :) Linia 2 jest równoważna f[a_,b___]:=b(bez przecinkiem), podczas gdy linia 3 jest równoważna f[a_,b___,Null]:=b. W obu przypadkach b___odnosi się do dowolnej liczby argumentów (w tym żadnej). Wiersz 3 jest bardziej szczegółowy, dlatego w razie potrzeby jest zawsze używany przed wierszem 2. Zatem funkcja fignoruje swój pierwszy argument, a także ignoruje swój ostatni argument, jeśli jest to argument Null. Było to konieczne do obsługi usuwania z kolejki pustej kolejki. Zauważ, że typowe dane wejściowe dają wyrażenie typu r[f[f[f[5,3,],2,],],11], gdzie każdy przecinek przedtem ]oznacza a Null.
Greg Martin
1
Wow bardzo fajnie :). Nawiasem mówiąc, myślę, że to w rzeczywistości 102 bajty; na końcu mogłeś policzyć dodatkowy znak nowej linii.
numbermaniac
4

Siatkówka , 30 bajtów

1+`\d+,(.*?)X,?|^X,
$1
O^$`\d+

Wypróbuj online!

Wielokrotnie usuwa pierwszą liczbę, która (niekoniecznie natychmiast), po której następuje Xrazem z nią Xlub Xna początku łańcucha. Następnie cofa pozostałe liczby.

Martin Ender
źródło
4

JavaScript, 70 63 53 50 43 bajty

Dzięki @Neil za grę w golfa z 10 bajtów za pomocą x.map zamiast za wyrażenie pętlowe i trójskładnikowe

Dzięki @Arnauld za grę w golfa z 3 bajtów

Dzięki @ETHproductions za grę w golfa poza 7 bajtami

x=>(t=[],x.map(a=>+a?t=[a,...t]:t.pop()),t)

Wypróbuj online!

Dequeue może być dowolną wartością nienumeryczną inną niż true.

Fəˈnɛtɪk
źródło
Byłoby to krótsze, jeśli użyjesz trójki zamiast if instrukcji, i jeszcze krótsze, jeśli użyjesz mapzamiast pętli, a jeszcze krótsze, jeśli użyjesz wyrażenia zamiast bloku. Zobacz wskazówki .
Neil
Opublikowałem pierwszą wersję, w której działałem. Potem zjadłem obiad: P
fəˈnɛtɪk
Możesz zrobić, x=>(t=[],x.map(a=>a>0?t.unshift(a):t.pop()),t)aby zaoszczędzić sporo bajtów nareturn
ETHproductions
x=>x.map(a=>a>0?t.unshift(a):t.pop(),t=[])&&tjest jeszcze krótszy.
Neil,
(A może po prostu a?wystarczy?)
Neil
3

Mathematica, 46 45 bajtów

Dzięki ngenisis za oszczędność 1 bajtu.

Reverse[#//.{_Integer:0,a___,X,b___}:>{a,b}]&

Zasadniczo to samo, co moja odpowiedź Retina, przy użyciu dopasowania wzorca. Wielokrotnie dopasowujemy pierwszy Xi usuwamy go wraz z pierwszym numerem (jeśli taki istnieje). Po zakończeniu cofamy listę.

Martin Ender
źródło
3

Pure Bash, 72

Dane wejściowe podane jako parametry wiersza polecenia.

for a;{
[ ${a/X} ]&&q=(${a:n++,0} ${q[@]})||((n-=n>0))
}
echo ${q[@]::n}

Wypróbuj online .

Cyfrowa trauma
źródło
3

Haskell, 41 bajtów

x&y:z|y<1=init x&z|w<-y:x=w&z
x&y=x
([]&)
Michael Klein
źródło
Ninja'd :) wygląda na to, że mieliśmy ten sam pomysł
ogólna nazwa wyświetlana
(Chociaż potrzebujesz nawiasów wokół znaku y: zx&(y:z)
Ogólna nazwa wyświetlana
Działa w mojej REPL, która jest częścią uścisków. Nie jestem jednak pewien dokładnej wersji.
Michael Klein
3

MATL , 13 12 bajtów

vi"@?@wh}IL)

Dane wejściowe to tablica liczb z 0„dequeue”.

Dane wyjściowe to liczby oddzielone spacjami. Pusty wynik jest wyświetlany jako nic.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

v        % Concatenate stack contents: gives []. This will grow to represent the queue
i        % Input numeric array
"        % For each entry in the input array
  @?     %   If current entry is non-zero
    @wh  %     Prepend current entry to the queue
  }      %   Else
    IL)  %     Remove last element from the queue
         %   End (implicit)
         % End (implicit)
         % Display (implicit)
Luis Mendo
źródło
3

Haskell, 41 40 bajtów

l#a|a>0=a:l|l>[]=init l|1>0=l

Funkcja jest foldl(#)[](uwzględniona również w bajtach z bajtem separacji pomiędzy)

Wypróbuj online!

X jest dowolną liczbą całkowitą nie dodatnią

EDYCJA: -1 bajtów dzięki nim

Ogólna nazwa wyświetlana
źródło
Możesz przerzucić dwóch ostatnich strażników, aby uratować bajt:|l>[]=init l|1>0=l
nimi
3

Julia, 78 76 73 57 bajtów

f(a)=(q=[];[x<1?q=q[2:end]:push!(q,x)for x=a];reverse(q))

Podziękowania dla Harrison Grodin za wspaniałe sugestie Julii dotyczące gry w golfa. Zastąpiony if / else trójskładnikiem i for / end ze zrozumieniem listy dla oszczędności 16 bajtów.

f(a)=(q=[];for x in a if x<1 q=q[2:end]else q=[q...,x]end end;reverse(q))

Usunięto niepotrzebne spacje dla oszczędności 3 bajtów.

Zanim dozwolone były liczby ujemne lub zero:

f(a)=(q=[];for x in a if x==:X q=q[2:end] else q=[q...,x] end end;r everse(q))

Nie golfowany:

function dequeue(list)
    queue = []

    for x in list
        if x < 1
            queue = queue[2:end]
        else
            queue = [queue..., x]
        end
    end

    reverse(queue)
end

Jestem całkiem nowy dla Julii; może być lepszy sposób. Używa :XX, który jest symbolem w Julii. Zaktualizowano: Teraz, gdy 0 jest dozwolone, używa 0 (lub dowolnej liczby ujemnej) dla X, zapisując dwa znaki. Zaktualizowałem ponownie, aby usunąć spacje, o których nie wiedziałem, że nie są potrzebne.

David Conrad
źródło
2

05AB1E , 12 11 bajtów

Oszczędność bajtu dzięki Riley

)Evyai¨ëy¸ì

Wypróbuj online!

Wyjaśnienie

Dequeues są oznaczone dowolną literą .

)             # wrap stack in a list (pushes empty list)
 Ev           # for each y in evaluated input
   yai        # if y is a letter
      ¨       # remove the first element of the list
       ëy¸ì   # else, prepend y to the list
Emigna
źródło
2

GNU Sed, 43

Wynik obejmuje +2 za użycie flag -ri -n.

G
s/X\n( *|(.*)\b\S+ *)$/\2/
s/\n/ /
h
$p

Wypróbuj online .

Wyjaśnienie

                            # Implicitly read the next line
G                           # append a newline, then the contents of the hold space
s/X\n( *|(.*)\b\S+ *)$/\2/  # If the input was an X, remove it, the newline, and any element at the end
s/\n/ /                     # Otherwise if the input was not an X, it is simply enqueued by removing the newline between it and the rest of the line
h                           # save a copy of the queue to the hold space
$p                          # since we're using -n to suppress output at the end of processing each input line, then this explicit print is required in the last line
Cyfrowa trauma
źródło
2

PHP, 85 bajtów

<?$r=[];foreach($_GET as$v)is_int($v)?array_unshift($r,$v):array_pop($r);print_r($r);

-8 Bajtów $vzamiast, is_int($v)jeśli każda wartość usuwana z kolejki należy do fałszu

Jörg Hülsermann
źródło
2

Python 3 , 95 94 bajtów

def f(x):q=[];[*map(lambda s:exec(("q.pop(0)"if q else"","q+=[s]")[s!="X"]),x)];print(q[::-1])

Wypróbuj online!

Również 94 bajty:

def f(x):q=[];[*map(lambda s:exec((("","q.pop(0)")[q>[]],"q+=[s]")[s!="X"]),x)];print(q[::-1])
Trelzevir
źródło
2

Perl 5 , 28 + 1 = 29 bajtów

28 bajtów kodu + -pflaga.

/\d/?$\=$_.$\:$\=~s/.*
$//}{

Wypróbuj online!

Używa łańcucha ( $\) jako kolejki: gdy wejście zawiera liczbę całkowitą ( /\d/?, dodajemy go na początku $\( $\=$_.$\), a w przeciwnym razie usuwamy ostatnią za pomocą s/.*\n$//. Na końcu $\jest domyślnie drukowany dzięki -pflagie (i te niezrównane }{).


Inne podejścia:

  • 33 bajty , używając tablicy jako kolejki (myślę, że jest to najbardziej naturalny sposób w Perlu, ale nie najkrótszy):

    /X/?pop@F:unshift@F,$_}{$_="@F"

    Wypróbuj online!

  • 52 bajty , używając wyrażenia regularnego i reverse(zdarza się, że jest to dokładnie to samo, co odpowiedź Retiny Martina Endera - dzięki czemu zapisałem na nim 2 bajty). Odwrócenie listy wymaga jednak wielu znaków, ponieważ aby zachować liczby całkowite, muszę przekonwertować ciąg na tablicę, aby go odwrócić, a następnie z powrotem na ciąg, aby go wydrukować. ( say forzamiast $_=join$",może zaoszczędzić 2 bajty, ale wymaga -Elub -M5.010nie jest aż tak interesujące).

    s/\d+ (.*?)X ?|^X/$1/&&redo;$_=join$",reverse split

    Wypróbuj online!

Dada
źródło
1

Python 3, 107 bajtów

def f(x):
 r = []
 for i in x:exec("try:r.pop(0)\nexcept:8;r+=i,".split(";")[type(i)==int])
 return r[::-1]

Dequeuer może być dowolną wartością nienumeryczną.

Wypróbuj online

Cairney Coheringaahing
źródło
1

Partia, 160 bajtów

@set s=.
@for %%n in (%*)do @if %%n==X (call set s=%%s:* =%%)else call set s=%%s:~,-1%%%%n .
@set t=
@for %%n in (%s:~,-1%)do @call set t= %%n%%t%%
@echo%t%

To było trudniejsze niż trzeba.

  • Chociaż Batch może wyliczyć wynik podziału łańcucha, nie może łatwo usunąć elementu z wyliczenia.
  • Może usunąć pierwszy element, ale tylko jeśli jest co najmniej jeden element. W przeciwnym razie dostaniesz śmieci.

Oznacza to, że a) muszę mieć znacznik końca kolejki, którego nie można usunąć, oraz b) manipulować kolejką od przodu do przodu, aby nowe elementy wstawiane były tuż przed znacznikiem końca, aby stare elementy mogły zostać usunięte z przodu, co oznacza, że ​​I c) muszę odwrócić kolejkę przed wydrukowaniem.

Neil
źródło
1

PHP, 70 bajtów

foreach($argv as$v)+$v?$r[]=$v:array_shift($r);krsort($r);print_r($r);
użytkownik63956
źródło
1

C #, 115 bajtów + 33 bajtów do użycia

l=>{var r=new List<int>();foreach(var n in l)if(n<0)try{r.RemoveAt(0);}catch{}else r.Add(n);r.Reverse();return r;};

Anonimowa metoda, która zwraca listę liczb całkowitych po wykonaniu operacji kolejkowania i usuwania z kolejki. Do usuwania elementów z kolejki używane są ujemne liczby całkowite.

Pełny program z nieprzylepioną metodą i przypadkami testowymi:

using System;
using System.Collections.Generic;

public class Program
{
    static void PrintList(List<int> list)
    {
        var s = "{";
        foreach (int element in list)
            s += element + ", ";
        if (s.Length > 1)
            s += "\b\b";
        s += "}";
        Console.WriteLine(s);
    }

    public static void Main()
    {
        Func<List<int>, List<int>> f =
        l =>
        {
            var r = new List<int>();
            foreach (var n in l)
                if (n < 0)
                    try
                    {
                        r.RemoveAt(0);
                    }
                    catch
                    { }
                else
                    r.Add(n);
            r.Reverse();
            return r;
        };

        // test cases:
        var list = new List<int>(new[]{1, -1, 2, -1, 3, -1});   // {}
        PrintList(f(list));

        list = new List<int>(new[]{1, 2, -1});  // {2}
        PrintList(f(list));

        list = new List<int>(new[]{1, 2, 3});   // {3, 2, 1}
        PrintList(f(list));

        list = new List<int>(new[]{1, 2, -1, -1, -1, 3});   // {3}
        PrintList(f(list));

        list = new List<int>(new[]{1, 2, -1, 3, -1, 4});    // {4, 3}
        PrintList(f(list));
    }
}
adrianmp
źródło
1

Scala, 97 bajtów

type S=Seq[_];def f(a:S,b:S):S=a match{case h::t=>f(t,if(h==0)b dropRight 1 else h+:b);case _=>b}

Jako dane wejściowe fpobiera listę z 0elementem „dequeue”. Wykorzystuje rekurencję ogona z drugim parametrem ( b), działając jak akumulator. Początkowo bjest pusty Seq( Nil).

Objaśnienia:

type S=Seq[_]                               // defines a type alias (save 1 byte since Seq[_] is used 3 times)
def f(a: S, b: S): S = {                    // a is the initial list, b is an accumulator
    a match {                           
        case h::t =>                        // if a is non-empty
            f(t,                            // recursive call to f with 1st parameter as the tail
                if (h==0) b dropRight 1     // if h == 0 (dequeue) then remove last element of b,
                else h+:b                   // otherwise, just add h at the beginning of b in recursive call
            )
        case _ => b                         // when the list is empty, return b (final result)
    }
}

Uwaga: b dropRight 1 jest stosowany zamiast b.taildo wyjątku unikać: tail of empty list.

Przypadki testowe :

f(Seq(45, 0, 0, 37, 20, 0, 97, 0, 85), Nil)     // List(85, 97)
f(Seq(1, 0, 2, 0, 3, 0), Nil)                   // List()
f(Seq(1, 2, 0), Nil)                            // List(2)
f(Seq(1, 2, 3), Nil)                            // List(3, 2, 1)
f(Seq(1, 2, 0, 0, 0, 3), Nil)                   // List(3)
f(Seq(1, 2, 0, 3, 0, 4), Nil)                   // List(4, 3)

fmoże także współpracować z innymi typami ( String, char, ..., nawet niejednorodny wykaz tych typów!):

f(Seq(false, '!', "world", 0, "Hello"), Nil)    // List(Hello, world, !)
norbjd
źródło
1

REXX, 115 bajtów

arg n
do while n>''
  parse var n m n
  if m=X then pull
  else queue m
  end
o=
do while queued()>0
  pull a
  o=a o
  end
say o

Pobiera ciąg rozdzielony spacjami, drukuje ciąg rozdzielony spacjami

idrougge
źródło
1

C ++, 122 119 bajtów

#import<list>
void f(std::list<int>o,std::list<int>&q){for(int i:o)if(i)q.push_front(i);else if(q.size())q.pop_back();}

0 oznacza dequeue.

Wypróbuj online!

Steadybox
źródło
1

Swift 3, 70 bajtów

Zakładając, że mamy szereg Ints jak let x = [1, 2,-1,3,-1,4]

print(x.reduce([].prefix(0)){(a,i)in return i>0 ?[i]+a:a.dropLast(1)})

Zauważ, że [].prefix(0)jest to podstępny sposób na uzyskanie pustej ArraySlice

Matt
źródło