Wyzwanie:

Rozważ funkcję, F(N) = 2^N + 1gdzie Ndodatnia liczba całkowita jest mniejsza niż 31. Sekwencja zdefiniowana przez tę funkcję to:

3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, 8193, 16385, 32769, 65537, 131073, 262145, 524289, 1048577, 2097153, 4194305, 8388609, 16777217, 33554433, 67108865, 134217729, 268435457, 536870913, 1073741825

Dane wejściowe zostaną wygenerowane w następujący sposób:

• Weź 5 ciągłych liczb całkowitych z powyższej sekwencji.
• Zastąp jedną z nich inną, dodatnią liczbą całkowitą (która może, ale nie musi, być częścią powyższej sekwencji).
• Opcjonalnie zmień kolejność 5 wynikowych liczb.

Biorąc pod uwagę taką listę 5 liczb całkowitych, znajdź tę, która została zamieniona i dlatego nie jest częścią oryginalnych 5 ciągłych liczb całkowitych.

Przykład:

• Oryginalny podlistę: 5, 9, 17, 33, 65.
• Wymienić jeden: 5, 7, 17, 33, 65.
• Zmiana kolejności: 33, 17, 5, 7, 65.

Oczekiwany wynik to 7.

5 wartości na wejściu będzie zawsze wyraźnych i zawsze będzie istniało unikalne rozwiązanie. (Na przykład, nie mają do czynienia z wejściami jak 3, 9, 17, 33, 129gdzie albo 3czy 129może zostały zamienione w.)

Przypadki testowe:

5,9,17,33,829
o/p: 829

9,5,17,829,33
o/p: 829

33, 17, 5, 7, 65
o/p: 7

5,9,177,33,65
o/p: 177

65,129,259,513,1025
o/p: 259

129,259,513,1025,65
o/p: 259

63,129,257,513,1025
o/p: 63

65,129,257,513,4097
o/p: 4097

5, 9, 2, 17, 33
o/p: 2

536870913, 67108865, 1073741825, 1, 268435457
o/p: 1

Galaretka, 15 bajtów

⁹R2*‘ṡ5ḟ@€µEÐfQ

TryItOnline
Wszystkie przypadki testowe również w TryItOnline

Zwraca listę zawierającą jedną listę zawierającą nieparzystą.

W jaki sposób?

⁹R2*‘ṡ5ḟ@€µEÐfQ - Main link, a (list)
⁹               - literal 256 (saving a byte over literal 30)
 R              - range, [1,2,3,...]
  2*            - 2 ** x, [2,4,8,...]
    ‘           - increment, [3,5,9,...]
     ṡ5         - all contiguous slices of length 5
       ḟ@€      - filter with reversed arguments for each
          µ     - monadic chain separation
            Ðf  - filter on condition:
           E    - all equal (those previously filtered lists with only one value)
              Q - unique (there can be two, but both will have the same odd-one-out)

JavaScript (ES6), 62 bajty

a=>a.find(n=>--n&--n|!n)||a.sort((a,b)=>a-b)[a[0]*16>a[3]?4:0]

Całkowicie nowy algorytm, ponieważ, jak wskazał @ edc65, poprzedni został uszkodzony. Objaśnienie: Najpierw zajmujemy się łatwym przypadkiem, szukając 2 lub liczby, która nie jest o jeden większa od potęgi 2. Jeśli nie znaleziono żadnej, to są dwa możliwe przypadki, w zależności od tego, czy dodatkowa wartość była poniżej czy powyżej oryginalny przebieg pięciu, więc sprawdzamy, czy najmniejsza i druga największa wartość należy do tego samego przebiegu pięciu, a jeśli tak, to winimy największą wartość, w przeciwnym razie najmniejszą wartość.

Python, 84 bajty

def f(a,i=0):s=set(a)-{2**j+1for j in range(i,i+5)};return len(s)<2and s or f(a,i+1)

Wszystkie przypadki testowe są w ideone

Dla poprawnych danych wejściowych zwraca zestaw zawierający tylko nieparzyste.
W przypadku nieprawidłowego wprowadzenia zostanie osiągnięty limit rekurencji i zostanie zgłoszony błąd.

Mathematica, 65 bajtów

f[a___,x_,b___]/;NestList[2#-1&,a~Min~b/. 2->0,4]~SubsetQ~{a,b}=x

Definiuje funkcję, fktóra powinna zostać wywołana z 5 argumentami, np

f[5, 9, 17, 33, 829]

Zasadniczo funkcję można wywołać z dowolną (niezerową) liczbą argumentów, ale możesz uzyskać nieoczekiwane wyniki ...

Myślę, że po raz pierwszy udało mi się postawić całe rozwiązanie nietrywialnego wyzwania po lewej stronie =.

Wyjaśnienie

To rozwiązanie naprawdę działa dla nas w zakresie możliwości dopasowywania wzorców Mathematica. Podstawową funkcją, której używamy, jest to, że Mathematica nie może po prostu zdefiniować prostych funkcji, takich jak, f[x_] := (* some expression in x *)ale możemy użyć dowolnie złożonych wzorców po lewej stronie, np. f[{a_, b_}, x_?OddQ] := ...Dodałby definicję, fktóra jest używana tylko wtedy, gdy jest wywoływana za pomocą dwuelementu lista i nieparzysta liczba całkowita. Dogodnie możemy już nadawać nazwy elementom dowolnie daleko w dół wyrażenia po lewej stronie (np. W ostatnim przykładzie moglibyśmy od razu odnieść się do dwóch elementów listy jako ai b).

Wzór, którego używamy w tym wyzwaniu jest f[a___,x_,b___]. Tu a___i b___są sekwencje zero lub więcej argumentów i xjest pojedynczym argumentem. Ponieważ po prawej stronie definicji jest po prostu x, potrzebujemy trochę magii, która zapewni, że xzostanie użyta dla szukanego przez nas wejścia a___ib___ są po prostu symbolami wieloznacznymi obejmującymi pozostałe elementy.

Odbywa się to poprzez dołączenie warunku do wzorca za pomocą /;. Prawa strona /;(wszystko do =) musi wrócić, Trueaby ten wzór pasował. Piękno polega na tym, że dopasowujący wzór Mathematica spróbuje każdego zadania a, xib aby wejść do nas, więc poszukiwanie właściwego elementu odbywa się za nami. Jest to zasadniczo deklaratywne rozwiązanie problemu.

Jeśli chodzi o sam warunek:

NestList[2#-1&,a~Min~b/. 2->0,4]~SubsetQ~{a,b}

Zauważ, że to wcale nie zależy x. Zamiast tego warunek ten zależy tylko od pozostałych czterech elementów. Jest to kolejna wygodna funkcja rozwiązania dopasowywania wzorców: ze względu na wzorce sekwencji ai brazem zawierają wszystkie inne dane wejściowe.

Zatem ten warunek musi sprawdzić, czy pozostałe cztery elementy są ciągłymi elementami z naszej sekwencji z co najwyżej jedną przerwą. Podstawowym pomysłem na sprawdzenie tego jest to, że generujemy kolejne cztery elementy z minimum (via ) i sprawdzamy, czy te cztery elementy są podzbiorem tego. Jedynymi danymi wejściowymi, które mogą powodować problemy, są te, które zawierająxi+1 = 2xi - 12 , ponieważ generuje to również prawidłowe elementy sekwencji, więc musimy sobie z tym poradzić osobno.

Ostatnia część: przejdźmy do samego wyrażenia, ponieważ jest tu trochę zabawniejszego cukru syntaktycznego.

...a~Min~b...

Ta notacja infix jest skrótem od Min[a,b]. Pamiętajmy jednak, że ai bto sekwencje, więc to rzeczywiście rozwija się do czterech elementów Min[i1, i2, i3, i4]i daje nam najmniejszy pozostały element w wejściu.

.../. 2->0

Jeśli wynikiem jest 2, zamieniamy ją na 0 (co wygeneruje wartości, które nie są w sekwencji). Przestrzeń jest niezbędna, ponieważ w przeciwnym razie Mathematica analizuje literał pływaka .2.

NestList[...&,...,4]

Do tej wartości 4 razy stosujemy nienazwaną funkcję i zbieramy wyniki na liście.

2#-1&

To po prostu zwielokrotnia jego wkład przez 2 i zmniejsza go.

...~SubsetQ~{a,b}

Na koniec sprawdzamy, czy lista zawierająca wszystkie elementy z ai bstanowi jej podzbiór.

Rakieta 198 bajtów

(λ(m)(let((l(for/list((i(range 1 31)))(+ 1(expt 2 i))))(r 1)(n(length m)))(for((i(-(length l)n)))(let
((o(for/list((j m)#:unless(member j(take(drop l i)n)))j)))(when(eq?(length o)1)(set! r o))))r))

Wersja bez golfa:

(define f
  (λ(m)
    (let ((l (for/list ((i (range 1 31))) 
               (+ 1 (expt 2 i))))
          (res 1)
          (n (length m)))
      (for ((i (- (length l) n)))
        (let ((o (for/list ((j m) 
                             #:unless (member j 
                                             (take (drop l i) n))) 
                    j)))
          (when (eq? (length o) 1)
            (set! res o))))
      res)))

Testowanie:

(f '(5 9 17 33 829))
(f '(9 5 17 829 33))
(f '(5 9 177 33 65))
(f '(65 129 259 513 1025))
(f '(129 259 513 1025 65))
(f '(63 129 257 513 1025))
(f '(65 129 257 513 4097))

Wynik:

'(829)
'(829)
'(177)
'(259)
'(259)
'(63)
'(4097)

05AB1E , 32 30 26 24 20 bajtów

30Lo>Œ5ùv¹yvyK}Dgi`q

Wyjaśnienie

30Lo>    # list containing the sequence [3 .. 1073741825]
Œ5ù      # all sequence sublists of length 5
v        # for each such list
 ¹yvyK}  # remove it's elements from input
 Dgi     # if the remaining list has length 1
    `q   # end the program and print the final list flattened

Wypróbuj online!

R, 97 bajtów

Okazało się to trudniejsze niż myślałem. Jestem pewien, że można to znacznie pograć w golfa.

m=match(x<-sort(scan()),2^(1:31)+1);l=diff(m);ifelse(NA%in%m,x[is.na(m)],x[ifelse(l[4]>1,5,l>1)])

Nie golfił i wyjaśnił

x<-sort(scan())                  # read input from stdin and sort, store as vector
m=match(x, 2^(1:31)+1)           # generate a vector of indices for which input matches the sequence
l=diff(m)                        # vector of the difference of indices (will only contain 4 elements)
ifelse(NA%in%m,                  # if m contains NA do:
       x[is.na(m)],              # return x where no match has been found, else:
       x[ifelse(l[4]>1,5,l>1)])  # return x by index where diff>1 unless it's the last object, then return x[5]

match()Funkcja powróci NA, jeśli każdy element wektora wejściowego nie jest w sekwencji, a co za tym idzie możemy tylko znaleźć indeks, gdzie NAistnieje w wejście i powrót w ten sposób:x[is.na(m)]

To staje się nieco bardziej skomplikowane, jeśli dane wejściowe są częścią sekwencji, ale są niewłaściwie umieszczone. Ponieważ dane wejściowe zostały posortowane, odległość między każdą parą wskaźników powinna wynosić 1. Możemy zatem znaleźć źle umieszczony element, badając 1stróżnicę dopasowanych indeksów l=diff(m)i wybierając indeks, dla którego l>1. To by wystarczyło, gdyby nie fakt, że tak jestl zawiera 4elementy, a nie 5. Jest to problem tylko wtedy, gdy ostatni element w posortowanym wejściu jest elementem sekwencji, ALE nie jest częścią podsekwencji (jak w ostatecznym przypadku testowym). W konsekwencji, jeśli 4thelement >1pobierze 5thwpis w posortowanym wejściu, poszukaj indeksu w 4wektorze -length:x[ifelse(l[4]>1,5,l>1)]

Haskell, 66 64 bajtów

g x=[s|n<-[1..],[s]<-[filter(`notElem`[2^m+1|m<-[n..n+4]])x]]!!0

Przykład użycia: g [65,129,257,513,4097]-> 4097.

Pętle przez wszystkie ciągłe podlisty o długości 5 z F(N) , zachowują elementy, których nie ma na liście danych wejściowych, xa wzorzec odpowiada elementom o długości 1 (-> [s]).

Edycja: @xnor zapisał dwa bajty, usuwając górną granicę zewnętrznej pętli. Ponieważ istnieje gwarancja, że ​​istnieje rozwiązanie, lenistwo Haskella zatrzymuje się na pierwszym znalezionym numerze.

Perl, 64 59 bajtów

Obejmuje +2 za -an

Podaj listę danych wejściowych w STDIN:

perl -M5.010 oddout.pl <<< "5 9 2 17 33"

oddout.pl:

#!/usr/bin/perl -an
@a=grep$_,@a{@F,map{2**$_+++1}($.++)x5}=@F while$#a;say@a

Jeśli nie przeszkadza ci zmienna ilość miejsca wokół wyniku, 58-bajtowy verson działa:

#!/usr/bin/perl -ap
$_=join$",@a{@F,map{2**$_+++1}($.++)x5}=@F while/\b +\b/

Obie wersje zapętlają się na zawsze, jeśli dane wejściowe nie mają rozwiązania.

To bardzo chory kod, ale nie mogę wymyślić nic eleganckiego ...

Sposób, w jaki używam (ab) %ato nowa sztuczka perlgolfa, o ile mi wiadomo.

Python 2, 73 bajty

s=set(input());i,=d={1}
while~-len(s-d):i*=2;d=d-{i/32+1}|{i+1}
print s-d

Iteruje przez zestawy d pięciu kolejnych elementów sekwencji, aż znajdzie taki, który zawiera wszystkie oprócz jednego elementu wejściowego, a następnie wypisuje różnicę, która jest wynikiem w zestawie singletonów.

Zestawy dpięciu kolejnych elementów są budowane z niczego przez wielokrotne dodawanie nowego elementu i+1i usuwanie każdego starego elementu, i/32+1który pojawia się przed bieżącym oknem 5. Oto, jak wygląda jego postęp.

{1}
{3}
{3, 5}
{3, 5, 9}
{3, 5, 9, 17}
{3, 5, 9, 17, 33}
{5, 9, 17, 33, 65}
{9, 17, 33, 65, 129}
{17, 33, 65, 129, 257}
{33, 65, 129, 257, 513}

Na początku od inicjalizacji występuje zbłąkany 1, ale jest nieszkodliwy, ponieważ jest natychmiast usuwany. Mniejsze zestawy składające się z 5 elementów są również nieszkodliwe.

PHP, 87 76 75 bajtów

for(;count($b=array_diff($argv,$a?:[]))-2;)$a[$n%5]=1<<++$n|1;echo end($b);

Biegnij z php -r '<code>' <value1> <value2> <value3> <value4> <value5>

C #, 69 bajtów

int M(int[]a)=>a.Except(new int[30].Select((_,i)=>(1<<i+1)+1)).Sum();

Java 7,85 bajtów

int f(int[]a,int l){int i=1;for(;i<l;)if(a[i++-1]*2-1!=a[i])return a[i];return a[0];}

Nie golfił

int f(int[]a,int l){
    int i=1;
    for(;i<l;)
    if(a[i++-1]*2-1!=a[i])
    return a[i];
   return a[0];

}

PHP, 76 bajtów

zaimplementowano pomysł Titusa w modzie 5

<?for(;count($x=array_diff($_GET[a],$r))-1;$r[++$i%5]=2**$i+1);echo end($x);

126 bajtów wcześniej

<?for(;$x=array_diff($_GET[a],array_map(function($z){return 2**$z+1;},range(++$i,$i+4)));)if(count($x)<2){echo end($x);break;}

Pyth, 18 bajtów

hhlD-LQ.:mh^2dSCd5

Utwórz sekwencję, weź podlisty o długości 5, usuń każdą podlistę z Q, weź najkrótszy wynik, wyprowadzaj jej jedyny element.

Kotlin, 55 bajtów

fun f(a:IntArray)=a.find{it-1 !in(1..30).map{1 shl it}}