Definicja

Wektor zawierający n elementów mówi się majorize lub dominują wektor b z n elementów IFF dla wszystkich wartości k , tak że 1 ≤ k ≤ n suma pierwszego elementu w ^↓ przez k ty element o ^↓ jest większa lub równa sumie elementów od b do ^↓ od pierwszego do k , gdzie v ^↓ reprezentuje wektor v posortowany w porządku malejącym.

To jest,

                          a_1 >= b_1
                    a_1 + a_2 >= b_1 + b_2
              a_1 + a_2 + a_3 >= b_1 + b_2 + b_3
                              ...
      a_1 + a_2 + ... + a_n-1 >= b_1 + b_2 + ... + b_n-1
a_1 + a_2 + ... + a_n-1 + a_n >= b_1 + b_2 + ... + b_n-1 + b_n

gdzie i b są sortowane w kolejności malejącej.

Dla celów tego wyzwania, będziemy używać niewielki uogólnienie majorization: powiemy lista jest nieposortowane majorization innego jeśli wszystkie powyższe nierówności są prawdziwe bez sortowania i b . (Jest to oczywiście matematycznie bezużyteczne, ale sprawia, że ​​wyzwanie jest ciekawsze.)

Wyzwanie

Biorąc pod uwagę wprowadzenie dwóch odrębnych list a i b liczb całkowitych z zakresu od 0 do 255 (włącznie), obie listy o długości n ≥ 1, określają, czy pierwsza lista nieposortowana - główna druga ( a > b ), druga nieposortowana - majorizes pierwszy ( b > a ) lub żaden.

Opcjonalnie możesz wymagać podania długości dwóch list jako danych wejściowych. Dane wyjściowe zawsze muszą mieć jedną z trzech odrębnych wartości, ale same wartości mogą być dowolne (proszę określić, które wartości reprezentują a > b , b > a , i żadne z nich w odpowiedzi).

Przypadki testowe dla a > b :

[255] [254]
[3,2,1] [3,1,2]
[6,1,5,2,7] [2,5,4,3,7]

Przypadki testowe dla b > a :

[9,1] [10,0]
[6,5,4] [7,6,5]
[0,1,1,2,1,2] [0,1,2,1,2,1]

Przypadki testowe bez specjalizacji:

[200,100] [150,250]
[3,1,4] [2,3,3]
[9,9,9,9,9,0] [8,8,8,8,8,9]

Galaretka , 10 8 6 bajtów

2 bajty dzięki @orlp.

2 bajty dzięki @Dennis.

_+\ṠQS

Wypróbuj online!

1dla a>b, -1dla a<b, 0bez specjalizacji.

_+\ṠQS

_       Difference (vectorized)
 +\     Cumulative sum.
   Ṡ    Sign of every difference
    Q   Deduplicate
     S  Sum

Gdyby oba były obecne 1i -1obecne (niektóre skumulowane kwoty są większe, niektóre mniejsze), to przyniosłoby to ostatni krok 0.

ngn / apl, 11 bajtów

{+/∪×+\⍺-⍵}

Na podstawie metody zawartej w odpowiedzi @Leaky Nun .

Biorąc pod uwagę dwie listy A i B , znajdź różnicę pomiędzy każdym elementwise wartości, albo niech C = A - B . Następnie znajdź skumulowane sumy C i weź znak każdego z nich. Wynik będzie sumą unikalnych wartości znakowych. Jeśli A > B , wynik wynosi 1, jeśli A < B wynik wynosi -1, a jeśli nie ma większości, wynik wynosi 0.

Wypróbuj online.

Julia, 30 bajtów

a^b=sum(sign(cumsum(a-b))∪0)

Zaoszczędź 4 bajty dzięki @Dennis!

Python 3.5, 85 bajtów:

lambda*e:[all(sum(g[:k])>=sum(h[:k])for k in range(1,-~len(h)))for g,h in[e,e[::-1]]]

Anonimowa funkcja lambda. Zwraca [True,False]jeśli a>b, [False,True]jeśli b>alub [False,False]żadne z nich nie jest prawdziwe. Mam nadzieję, że to w porządku.

Wypróbuj online! (Ideone)

Cheddar , 118 114 bajtów

n->[n.map(i->i[0]-i[1]).map((j,k,l)->l.slice(0,k+1).sum).map(i->i>0?1:i<0?-1:0)].map(j->j has 1?j has-1?0:1:-1)[0]

Zasadniczo port mojej odpowiedzi Jelly .

Fakt, że funkcja wewnątrz zakresu jest zepsuta, powodując niemożność zdefiniowania zmiennej wewnątrz funkcji, oznacza, że ​​musiałbym to zrobić [xxx].map(i->yyy)[0]zamiast var a=xxx;yyy.

Pobiera transponowaną tablicę jako dane wejściowe.

n->[n
.map(i->i[0]-i[1])                     Difference (vectorized)
.map((j,k,l)->l.slice(0,k+1).sum)      Cumulative sum.
.map(i->i>0?1:i<0?-1:0)]               Sign of every difference
.map(j->j has 1?j has-1?0:1:-1)[0]     Deduplicate and Sum

Python 2, 73 bajty

a,=b,=r={0}
for x,y in zip(*input()):a+=x;b+=y;r|={cmp(a,b)}
print sum(r)

Przetestuj na Ideone .

Rubin, 72 59 bajtów

Zwraca 1za a>b, -1za a<b, 0za żadne.

-13 bajtów od przekreślenia sumy sztuczki @Dennis w odpowiedzi na Python

Wypróbuj online!

->a,b{x=y=0;a.zip(b).map{|i,j|(x+=i)<=>y+=j}.uniq.inject:+}

Python 2, 59 bajtów

t=r=0
for x,y in zip(*input()):t+=x-y;r|=cmp(t,0)%3
print r

Wyjścia:

• 1 dla a>b
• 2 dla b>a
• 3 za żadne

Iteruje po liście, śledząc bieżącą sumę tróżnic. Liczba sśledzi znaki, które były postrzegane jako liczba dwubitowa r: dodatnie w prawym bicie i ujemne w lewym bicie. Dzieje się tak przez cmp(t,0)%3, co daje

• t>0 → +1→ 1
• t==0→ 0 → 0
• t<0 → -1→ 2

Biorąc orto i bieżącą wartość raktualizacji, aktualizujemy 2 bity or, przy czym wartości zerowe nie mają wpływu.

JavaScript (przy użyciu zewnętrznej biblioteki-Enumerable) (123 bajty)

(a,b)=>(z=(c,d)=>_.Range(1,c.length).All(x=>_.From(c).Take(x).Sum()>=_.From(d).Take(x).Sum()))(a,b)==z(b,a)?0:(z(a,b)?1:-1)

Link do lib: https://github.com/mvegh1/Enumerable

Objaśnienie kodu: Przekaż wektor aib, utwórz funkcję globalną z. z rozpocznie się od utworzenia tablicy liczb całkowitych od 1, dla zliczenia długości a. Wszystkie sprawdzą, czy predykat jest prawdziwy dla każdego członka należącego do. Ten predykat mówi, aby załadować jako wyliczalny, policzyć ten wyliczalny ekwiwalent bieżącej wartości iteracji tego zakresu, który stworzyliśmy, i zsumować. Sprawdź, czy> = ta sama logika z tablicy „b”. Tak więc, wywołujemy z w kolejności (a, b) i porównujemy to z kolejnością (b, a) ... jeśli równa się, zwracamy 0, aby oznaczać, że nie ma znacznika. W przeciwnym razie zwracamy 1, jeśli (a, b) jest prawdą, w przeciwnym razie -1