Utwórz zrównoważony BST z posortowanej listy liczb całkowitych

15

Biorąc pod uwagę unikalną, posortowaną listę liczb całkowitych, utwórz zrównoważone drzewo wyszukiwania binarnego reprezentowane jako tablica bez użycia rekurencji.

Na przykład:

func( [1,2,3,5,8,13,21] ) => [5,2,13,1,3,8,21]

Zanim zaczniemy, wskazówka: możemy uprościć ten problem tonę, abyśmy nie musieli myśleć o wejściowych liczbach całkowitych (ani o żadnym podobnym obiekcie!).

Jeśli wiemy, że lista wejściowa jest już posortowana, jej zawartość nie ma znaczenia. Możemy po prostu pomyśleć o tym w kategoriach wskaźników w oryginalnej tablicy.

Wewnętrzna reprezentacja tablicy wejściowej staje się następnie:

func( [0,1,2,3,4,5,6] ) => [3,1,5,0,2,4,6]

Oznacza to, że zamiast pisać coś, co ma do czynienia z porównywalnymi obiektami, naprawdę wystarczy napisać funkcję, która odwzorowuje zakres z zakresu [0, n) na wynikową tablicę. Po otrzymaniu nowego zamówienia możemy po prostu zastosować mapowanie z powrotem do wartości na wejściu, aby utworzyć tablicę zwrotną.

Prawidłowe rozwiązania muszą:

  • Zaakceptuj tablicę z zerowymi elementami i zwróć pustą tablicę.
  • Zaakceptuj tablicę liczb całkowitych o długości n i zwróć tablicę liczb całkowitych
    • O długości od n do następnej największej potęgi 2 minus 1. (np. Dla wielkości wejściowej 13 powróć gdziekolwiek między 13 a 15).
    • Tablica reprezentująca BST, w której węzeł główny znajduje się w pozycji 0, a wysokość jest równa log (n), gdzie 0 oznacza brakujący węzeł (lub nullpodobną wartość, jeśli pozwala na to Twój język). Puste węzły, jeśli są obecne, muszą istnieć tylko na końcu drzewa (np. [2,1,0])

Wejściowa tablica liczb całkowitych ma następujące gwarancje:

  • Wartości to 32-bitowe liczby całkowite ze znakiem większe od zera.
  • Wartości są unikalne.
  • Wartości są w porządku rosnącym od pozycji zero.
  • Wartości mogą być rzadkie (tj. Nie przylegać do siebie).

Wygrywa najbardziej zwięzły kod według liczby znaków ascii, ale interesują mnie również eleganckie rozwiązania dla każdego konkretnego języka.

Przypadki testowe

Wyjścia w prostych układach zawierających 1się nna różne n. Jak opisano powyżej, końcowe 0s są opcjonalne.

[]
[1]
[2,1,0]
[2,1,3]
[3,2,4,1,0,0,0]
[4,2,5,1,3,0,0]
[4,2,6,1,3,5,0]
[4,2,6,1,3,5,7]
[5,3,7,2,4,6,8,1,0,0,0,0,0,0,0]
[6,4,8,2,5,7,9,1,3,0,0,0,0,0,0]
[7,4,9,2,6,8,10,1,3,5,0,0,0,0,0]
[8,4,10,2,6,9,11,1,3,5,7,0,0,0,0]
[8,4,11,2,6,10,12,1,3,5,7,9,0,0,0]
[8,4,12,2,6,10,13,1,3,5,7,9,11,0,0]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,0]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]
Jake Wharton
źródło
Wszystkie pytania na tej stronie, czy to puzzle programistyczne, czy golf kodowy, powinny mieć obiektywne podstawowe kryterium wygranej, aby można było bezdyskusyjnie zdecydować, które zgłoszenie powinno wygrać.
Howard
@ Howard Thanks. Zaktualizowano o ostateczne kryteria dla zwycięzcy.
Jake Wharton
1
Przydałoby się mieć kilka przypadków testowych, które obejmują trudne przypadki, a nie (jak obecnie) tylko najłatwiejsze.
Peter Taylor
Czy istnieje jakiś powód, aby wykluczyć rekurencję? Nie dlatego, że szukam rozwiązania rekurencyjnego, ale wydaje się to zarówno sztuczne, jak i niepotrzebne.
dmckee --- były moderator kotek
1
Czy ktoś może wyjaśnić, w jaki sposób lista reprezentuje BST?
justinpc

Odpowiedzi:

4

Ruby , 143

s=ARGV.size;r,q=[],[[0,s]];s.times{b,e=q.shift;k=Math::log2(e-b).to_i-1;m=(e-b+2)>(3<<k)?b+(2<<k)-1:e-(1<<k);r<<ARGV[m];q<<[b,m]<<[m+1,e]};p r

Jest to (luźno) skompresowana wersja następującego kodu, która zasadniczo wykonuje BFS na drzewie.

def l(n)
    k = Math::log2(n).to_i-1
    if n+2 > (3<<k) then
        (2<<k)-1
    else
        n-(1<<k) 
    end
end

def bfs(tab)
  result = []
  queue = [[0,tab.size]]
  until queue.empty? do
    b,e = queue.shift
    m = b+l(e-b)
    result << tab[m]
    queue << [b,m] if b < m
    queue << [m+1,e] if m+1 < e
  end
  result
end

p bfs(ARGV)

Poza tym, ponieważ jest to BFS, a nie DFS, wymóg nierekurencyjnego rozwiązania nie jest znaczący i stawia niektóre języki w niekorzystnej sytuacji.

Edycja: Naprawiono rozwiązanie, dzięki @PeterTaylor za komentarz!

dtldarek
źródło
@PeterTaylor Zamiarem było umieszczenie 3 po lewej stronie 4, ale nie ma żadnych pustych miejsc, więc jest źle. Dzięki za zwrócenie na to uwagi!
dtldarek
@PeterTaylor Naprawiono podczas lunchu, powinno już działać.
dtldarek
4

Java , 252

Ok, oto moja próba. Bawiłem się operacjami bitowymi i wymyśliłem ten bezpośredni sposób obliczania indeksu elementu w BST na podstawie indeksu w oryginalnej tablicy.

Wersja skompresowana

public int[]b(int[]a){int i,n=1,t;long x,I,s=a.length,p=s;int[]r=new int[(int)s];while((p>>=1)>0)n++;p=2*s-(1l<<n)+1;for(i=0;i<s;i++){x=(i<p)?(i+1):(p+2*(i-p)+1);t=1;while((x&1<<(t-1))==0)t++;I=(1<<(n-t));I|=((I-1)<<t&x)>>t;r[(int)I-1]=a[i];}return r;}

Długa wersja znajduje się poniżej.

public static int[] makeBst(int[] array) {
  long size = array.length;
  int[] bst = new int[array.length];

  int nbits = 0;
  for (int i=0; i<32; i++) 
    if ((size & 1<<i)!=0) nbits=i+1;

  long padding = 2*size - (1l<<nbits) + 1;

  for (int i=0; i<size; i++) {
    long index2n = (i<padding)?(i+1):(padding + 2*(i-padding) + 1);

    int tail=1;
    while ((index2n & 1<<(tail-1))==0) tail++;
    long bstIndex = (1<<(nbits-tail));
    bstIndex = bstIndex | ((bstIndex-1)<<tail & index2n)>>tail;

    bst[(int)(bstIndex-1)] = array[i];
  }
 return bst;
}
Mikail Sheikh
źródło
Potrzebujesz liczby postaci, a obecnie nie jest to gra w golfa.
dmckee --- były moderator kotek
@dmckee Zredagowałem post, aby uwzględnić wersję skompresowaną i liczbę znaków
mikail sheikh
Dobry występ. Założę się, że niektóre z tych miejsc są niepotrzebne. C int[] b(int[] a)jest równie dobrze wyrażone jak int[]b(int[]a).
dmckee --- były moderator kotek
Masz a.lengthprzydział tablicy. Zmień to na s. Pozbądź się miejsca for (wiele razy. Każda pętla for tworzy int i=0także int t=0. Twórz za pomocą n( int n=0,i,t;), a następnie tylko i=0w pętlach i t=1wewnątrz. Zadeklaruj wewnętrzny long xi za long Ipomocą si po prostu zainicjuj w pętli ( long s=a.length,I,x;i x=../ I=..). Nie powinieneś potrzebować spacji wokół pliku binarnego AND &.
Jake Wharton
Ponadto, I=I|..może być zapisanaI|=..
Jake Wharton
3
def fn(input):
    import math
    n = len(input)
    if n == 0:
        return []
    h = int(math.floor(math.log(n, 2)))
    out = []
    last = (2**h) - 2**(h+1) + n

    def num_children(level, sibling, lr):
        if level == 0:
            return 0
        half = 2**(level-1)
        ll_base = sibling * 2**level + lr * (half)
        ll_children = max(0, min(last, ll_base + half - 1) - ll_base + 1)
        return 2**(level-1) - 1 + ll_children

    for level in range(h, -1, -1):
        for sibling in range(0, 2**(h-level)):
            if level == 0 and sibling > last:
                break
            if sibling == 0:
                last_sibling_val = num_children(level, sibling, 0)
            else:
                last_sibling_val += 2 + num_children(level, sibling - 1, 1) \
                    + num_children(level, sibling, 0)
            out.append(input[last_sibling_val])
    return out
niesamowicie
źródło
2

Nie jestem pewien, czy pasuje to dokładnie do twoich wymagań dotyczących pustych węzłów znajdujących się na końcu drzewa i na pewno nie wygra żadnych nagród za zwięzłość, ale myślę, że jest poprawne i ma przypadki testowe :)

public class BstArray {
    public static final int[] EMPTY = new int[] { };
    public static final int[] L1 = new int[] { 1 };
    public static final int[] L2 = new int[] { 1, 2 };
    public static final int[] L3 = new int[] { 1, 2, 3 };
    public static final int[] L4 = new int[] { 1, 2, 3, 5 };
    public static final int[] L5 = new int[] { 1, 2, 3, 5, 8 };
    public static final int[] L6 = new int[] { 1, 2, 3, 5, 8, 13 };
    public static final int[] L7 = new int[] { 1, 2, 3, 5, 8, 13, 21 };
    public static final int[] L8 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35 };
    public static final int[] L9 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35, 56 };
    public static final int[] L10 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35, 56, 91 };

    public static void main(String[] args) {
        for (int[] list : Arrays.asList(EMPTY, L1, L2, L3, L4, L5, L6, L7, L8, L9, L10)) {
            System.out.println(Arrays.toString(list) + " => " + Arrays.toString(bstListFromList(list)));
        }
    }

    private static int[] bstListFromList(int[] orig) {
        int[] bst = new int[nextHighestPowerOfTwo(orig.length + 1) - 1];

        if (orig.length == 0) {
            return bst;
        }

        LinkedList<int[]> queue = new LinkedList<int[]>();
        queue.push(orig);

        int counter = 0;
        while (!queue.isEmpty()) {
            int[] list = queue.pop();
            int len = list.length;

            if (len == 1) {
                bst[counter] = list[0];
            } else if (len == 2) {
                bst[counter] = list[1];
                queue.add(getSubArray(list, 0, 1));
                queue.add(new int[] { 0 });
            } else if (len == 3) {
                bst[counter] = list[1];
                queue.add(getSubArray(list, 0, 1));
                queue.add(getSubArray(list, 2, 1));
            } else {
                int divide = len / 2;
                bst[counter] = list[divide];
                queue.add(getSubArray(list, 0, divide));
                queue.add(getSubArray(list, divide + 1, len - (divide + 1)));
            }
            counter++;
        }

        return bst;
    }

    private static int nextHighestPowerOfTwo(int n) {
        n--;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        n++;

        return n;
    }

    private static int[] getSubArray(int[] orig, int origStart, int length) {
        int[] list = new int[length];
        System.arraycopy(orig, origStart, list, 0, length);
        return list;
    }
}
Andrew Flynn
źródło
2

Golfscript ( 99 89)

~]:b[]:^;{b}{{:|.,.2base,(2\?:&[-)&2/]{}$0=&(2/+:o[=]^\+:^;|o<.!{;}*|o)>.!{;}*}%:b}while^p

Zasadniczo prosty port mojego rozwiązania w języku Python działa prawie w ten sam sposób.

Prawdopodobnie można go nieco ulepszyć dzięki większej liczbie „golfizmów”, poprawionych już o 10 znaków z wkładem @ petertaylor :)

Joachim Isaksson
źródło
Myślę, że powinno to być możliwe w nie więcej niż 70, chociaż nadal nie do końca ukończyłem odpowiedź na GolfScript. Istnieje jednak kilka łatwych ulepszeń. !{;}{}ifmoże być po prostu !{;}*dlatego, że !gwarancje zwrotu 0lub 1. Możesz używać tokenów niealfabetycznych dla zmiennych, więc jeśli użyjesz ^zamiast r, |zamiast x, &zamiast y, możesz wyeliminować całą białą spację.
Peter Taylor
@PeterTaylor Dzięki, nie wiedziałem o zmiennych niealfanumerycznych, wciąż bardzo nowy w golfscript :)
Joachim Isaksson
2

Java 192

Mapuje indeks na wejściu do indeksu na wyjściu

int[]b(int[]o){int s=o.length,p=0,u=s,i=0,y,r[]=new int[s],c[]=new int[s];while((u>>=1)>0)p++;for(int x:o){y=p;u=i;while(u%2>0){y--;u/=2;}r[(1<<y)-1+c[y]++]=x;i+=i>2*s-(1<<p+1)?2:1;}return r;}

Długa wersja:

static int[] bfs(int[] o) {
  int rowCount = 32 - Integer.numberOfLeadingZeros(o.length); // log2
  int slotCount = (1<<rowCount) - 1; // pow(2,rowCount) - 1

  // number of empty slots at the end
  int emptySlots = slotCount - o.length;
  // where we start to be affected by these empty slots
  int startSkippingAbove = slotCount - 2 * emptySlots; // = 2 * o.length - slotCount

  int[] result = new int[o.length];
  int[] rowCounters = new int[rowCount]; // for each row, how many slots in that row are taken
  int i = 0; // index of where we would be if this was a complete tree (no trailing empty slots)
  for (int x : o) {
    // the row (depth) a slot is in is determined by the number of trailing 1s
    int rowIndex = rowCount - Integer.numberOfTrailingZeros(~i) - 1;
    int colIndex = rowCounters[rowIndex]++; // count where we are
    int rowStartIndex = (1 << rowIndex) - 1; // where this row starts in the result array

    result[rowStartIndex + colIndex] = x;

    i++;
    // next one has to jump into a slot that came available by not having slotCount values
    if (i > startSkippingAbove) i++;
  }

  return result;
}
Wouter Coekaerts
źródło
2

Wolfram Mathematica 11, 175 bajtów

g[l_]:=(x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2);Join@@Table[Cases[l//.{{}->{},b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b])},_Integer,{m}],{m,x[l]}])

Funkcja g[l]przyjmuje jako dane wejściowe a List(np. l={1,2,3,4,...}) I zwraca a Listżądanej postaci. Działa w następujący sposób:

  • x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2) pobiera listę i znajduje katalog główny skojarzonego BST.
    • i=Length[a]+1 skrót do długości listy
    • 2^Ceiling@Log2[i]/2 górna granica wartości korzenia
    • Min[i-#/2,#]&@(...)Minimum dwa argumenty, gdzie #oznacza to, co jest w środku(...)
  • l//.{...} Zastosuj wielokrotnie następujące zasady zastępowania l
  • {}->{} Nic do zrobienia (jest to przypadek na krawędzi, aby uniknąć nieskończonej pętli)
  • b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b])Podziel Listna{{lesser}, root, {greater}}
  • Cases[...,_Integer,{m}] Weź wszystkie liczby całkowite na poziomie (głębokość) m
  • Table[...,{m,1,x[l]}]Dla wszystkich mdo x[l](co w rzeczywistości jest więcej niż to konieczne).

Można to przetestować, uruchamiając

Table[g[Range[a]], {a, 0, 15}]//MatrixForm

Ta implementacja nie zawiera końcowych zer.

MannyC
źródło
1

Python ( 175 171)

Dość skondensowane, wciąż dość czytelne;

def f(a):
 b=[a]
 while b:
  c,t=((s,2**(len(bin(len(s)))-3))for s in b if s),[]
  for x,y in c:
   o=min(len(x)-y+1,y/2)+(y-1)/2
   yield x[o]
   t+=[x[:o],x[o+1:]]
  b=t

Zwraca wynik, więc można go nad nim zapętlić lub (do celów wyświetlania) wydrukować jako listę;

>>> for i in range(1,17): print i-1,list(f(range(1,i)))
 0 []
 1 [1]
 2 [2, 1]
 3 [2, 1, 3]
 4 [3, 2, 4, 1]
 5 [4, 2, 5, 1, 3]
 6 [4, 2, 6, 1, 3, 5]
 7 [4, 2, 6, 1, 3, 5, 7]
 8 [5, 3, 7, 2, 4, 6, 8, 1]
 9 [6, 4, 8, 2, 5, 7, 9, 1, 3]
10 [7, 4, 9, 2, 6, 8, 10, 1, 3, 5]
11 [8, 4, 10, 2, 6, 9, 11, 1, 3, 5, 7]
12 [8, 4, 11, 2, 6, 10, 12, 1, 3, 5, 7, 9]
13 [8, 4, 12, 2, 6, 10, 13, 1, 3, 5, 7, 9, 11]
14 [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13]
15 [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]
Joachim Isaksson
źródło
@dtldarek Jego komentarz wydaje się być usunięty, ale wydaje się, że teraz zdaje egzaminy.
Joachim Isaksson
Usunąłem swój komentarz, aby ludzie nie powstrzymali się od upvotowania odpowiedzi @ dtldarek z powodu komentarza stwierdzającego, że jest błędny.
Peter Taylor
@PeterTaylor Cóż, dziękuję za uwagę ;-)
dtldarek
1

Jawa

Jest to bezpośrednie rozwiązanie obliczeniowe. Myślę, że to działa, ale ma jeden pragmatycznie niewinny efekt uboczny. Tablica, którą tworzy, może być uszkodzona, ale nie może to w żaden sposób wpływać na wyszukiwanie. Zamiast produkować 0 (zerowych) węzłów, utworzy nieosiągalne węzły, to znaczy węzły zostały już wcześniej znalezione w drzewie podczas wyszukiwania. Działa poprzez mapowanie tablicy indeksów o regularnej sile 2-wymiarowej tablicy drzewa wyszukiwania binarnego na nieregularną tablicę drzewa wyszukiwania binarnego. Przynajmniej myślę, że to działa.

import java.util.Arrays;

public class SortedArrayToBalanceBinarySearchTreeArray
{
    public static void main(String... args)
    {
        System.out.println(Arrays.toString(binarySearchTree(19)));
    }

    public static int[] binarySearchTree(int m)
    {
        int n = powerOf2Ceiling(m + 1);
        int[] array = new int[n - 1];

        for (int k = 1, index = 1; k < n; k *= 2)
        {
            for (int i = 0; i < k; ++i)
            {
                array[index - 1] = (int) (.5 + ((float) (m)) / (n - 1)
                        * (n / (2 * k) * (1 + 2 * index) - n));
                ++index;
            }
        }

        return array;
    }

    public static int powerOf2Ceiling(int n)
    {
        n--;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        n++;

        return n;
    }

}

Oto bardziej skrócona wersja (tylko sparowana funkcja i nazwy). Wciąż jest biała przestrzeń, ale nie martwię się o wygraną. Również ta wersja faktycznie zajmuje tablicę. Drugi wziął int dla najwyższego indeksu w tablicy.

public static int[] b(int m[])
{
    int n = m.length;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;

    int[] a = new int[n - 1];

    for (int k = 1, j = 1, i; k < n; k *= 2)
    {
        for (i = 0; i < k; ++i)
        {
            a[j - 1] = m[(int) (.5 + ((float) m.length) / (n - 1)
                    * (n / (2 * k) * (1 + 2 * j) - n)) - 1];
            ++j;
        }
    }

    return a;
}
metafizować
źródło
Ponieważ jest to gra w golfa , skróć swoje metody / nazwy / itp. Do możliwie najkrótszych; usuń wszystkie białe znaki (i niepotrzebne metody / materiały) i wstaw liczbę znaków. W przeciwnym razie świetnie sobie radzisz.
Justin
@Jake Wharton. Naprawdę chciałbym zobaczyć twoje bezpośrednie rozwiązanie do mapowania. Nie jestem w 100% pewien, że moja kopalnia działa na bardzo dużych tablicach, ponieważ opiera się na ciągłym odwzorowaniu matematycznym, którego wartości są zaokrąglane. Z pewnością wydaje się, że działa, ale nie jestem pewien, jak to udowodnić.
metafizować
1

GolfScript ( 79 77 70 znaków)

Ponieważ przykład w pytaniu używa funkcji, uczyniłem ją funkcją. Usunięcie w {}:f;celu pozostawienia wyrażenia, które pobiera dane wejściowe ze stosu i pozostawia BST na stosie, pozwoliłoby zaoszczędzić 5 znaków.

{[.;][{{.!!{[.,.)[1]*{(\(@++}@(*1=/()\@~]}*}%.{0=}%\{1>~}%.}do][]*}:f;

Demo online (uwaga: aplikacja może trochę się rozgrzać: przekroczyła limit czasu dwa razy przed uruchomieniem za 3 sekundy).

Z białymi znakami, aby pokazać strukturę:

{
    # Input is an array: wrap it in an array for the working set
    [.;]
    [{
        # Stack: emitted-values working-set
        # where the working-set is essentially an array of subtrees
        # For each subtree in working-set...
        {
            # ...if it's not the empty array...
            .!!{
                # ...gather into an array...
                [
                    # Get the size of the subtree
                    .,
                    # OEIS A006165, offset by 1
                    .)[1]*{(\(@++}@(*1=
                    # Split into [left-subtree-plus-root right-subtree]
                    /
                    # Rearrange to root left-subtree right-subtree
                    # where left-subtree might be [] and right-subtree might not exist at all
                    ()\@~
                ]
            }*
        }%
        # Extract the leading element of each processed subtree: these will join the emitted-values
        .{0=}%
        # Create a new working-set of the 1, or 2 subtrees of each processed subtree
        \{1>~}%
        # Loop while the working-set is non-empty
        .
    }do]
    # Stack: [[emitted values at level 0][emitted values at level 1]...]
    # Flatten by joining with the empty array
    []*
}:f;
Peter Taylor
źródło
1

J , 52 bajty

t=:/:(#/:@{.(+:,>:@+:@i.@>:@#)^:(<.@(2&^.)@>:@#`1:))

funkcja pobiera posortowaną listę i zwraca w kolejności drzewa binarnego

zauważ, że drzewa mają identyczny kształt, ale dolny poziom jest skrócony

  • `1: zacznij od 1
  • <.@(2&^.)@>:@# iteruj według podłogi log2 (długość + 1)
  • +: , >:@+:@i.@>:@# pętla: dołącza podwójny ostatni wektor o liczbach nieparzystych 1,3 .. 2 * długość + 1
  • # /:@{. weź tylko wymaganą liczbę przedmiotów i uzyskaj ich indeksy sortowania
  • /: zastosuj te wskaźniki sortowania do podanych danych wejściowych

TIO

jayprich
źródło
0

Python 2 , 107 bajtów

Golf odpowiedzi Joachima Isakssona: Input jest singletonem zawierającym listę.

def f(a):
 for x in a:
	if x:w=len(x);y=1<<len(bin(w))-3;o=min(w-y+1,y/2)+~-y/2;yield x[o];a+=x[:o],x[o+1:]

Wypróbuj online!

ovs
źródło