Policzmy...

Policz do 2 i wracaj do 1
Policz do 4 i wracaj do 1
Policz do 6 i wracaj do 1
... ok, rozumiesz ...

połącz je wszystkie, a otrzymasz następującą sekwencję

 {1,2,1,2,3,4,3,2,1,2,3,4,5,6,5,4,3,2,1,2,3,4,5,6,7,8,7,6,5,4,3,2,1,2,3...}

Wyzwanie
Biorąc pod uwagę liczbę całkowitą n>0dla 1-indeksowanego (lub n>=0dla 0-indeksowanego), wypisz n-ty składnik tej sekwencji

Przypadki testowe

Input->Output  

1->1  
68->6  
668->20  
6667->63  
10000->84

Zasady

Twój program musi być w stanie obliczyć rozwiązania do n = 10000 w niecałą minutę

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach!

JavaScript (ES7),  59 ... 44  43 bajty

Zaoszczędził 1 bajt dzięki Tytusowi

Oczekiwany wkład: 1-indeksowany.

n=>(n-=(r=(~-n/2)**.5|0)*r*2)<++r*2?n:r*4-n

Początkowo zainspirowany formułą dla A004738 , która jest podobną sekwencją. Ale ostatecznie przepisałem to całkowicie.

Przypadki testowe

let f=

n=>(n-=(r=(~-n/2)**.5|0)*r*2)<++r*2?n:r*4-n

console.log(f(1))     // -> 1
console.log(f(68))    // -> 6
console.log(f(668))   // -> 20
console.log(f(6667))  // -> 63
console.log(f(10000)) // -> 84

W jaki sposób?

Sekwencja może być ułożona w trójkąt, z lewą częścią w porządku rosnącym, a prawą w kolejności malejącej.

Poniżej znajdują się pierwsze 4 wiersze zawierające pierwsze 32 wyrażenia:

            1 | 2
        1 2 3 | 4 3 2
    1 2 3 4 5 | 6 5 4 3 2
1 2 3 4 5 6 7 | 8 7 6 5 4 3 2

Teraz wprowadzimy kilka zmiennych:

 row  | range   | ascending part              | descending part
 r    | x to y  | 1, 2, ..., i                | 4(r+1)-(i+1), 4(r+1)-(i+2), ...
------+---------+-----------------------------+-----------------------------------------
  0   |  1 -  2 |                           1 | 4-2
  1   |  3 -  8 |                   1   2   3 | 8-4  8-5  8-6
  2   |  9 - 18 |           1   2   3   4   5 | 12-6 12-7 12-8  12-9  12-10
  3   | 19 - 32 |   1   2   3   4   5   6   7 | 16-8 16-9 16-10 16-11 16-12 16-13 16-14

Zaczynamy od 2 elementów u góry i dodajemy 4 elementy w każdym nowym rzędzie. Dlatego liczbę elementów w rzędzie r indeksowanym przez 0 można wyrazić jako:

a(r) = 4r + 2

1-indeksowana pozycja początkowa x rzędu r jest sumą wszystkich poprzednich wyrażeń w tej serii arytmetycznej plus jeden, co prowadzi do:

x(r) = r * (2 + a(r - 1)) / 2 + 1
     = r * (2 + 4(r - 1) + 2) / 2 + 1
     = 2r² + 1

Odwrotnie, biorąc pod uwagę 1-indeksowaną pozycję n w sekwencji, odpowiedni wiersz można znaleźć za pomocą:

r(n) = floor(sqrt((n - 1) / 2))

lub jako kod JS:

r = (~-n / 2) ** 0.5 | 0

Kiedy znamy r (n) , odejmujemy pozycję początkową x (r) minus jeden od n :

n -= r * r * 2

Porównując n o o (R) / 2 + 1 = 2r + 2 dowiedzieć się, czy znajdują się w części wstępującej lub zstępującej części:

n < ++r * 2 ?

Jeśli to wyrażenie jest prawdziwe, zwracamy n . W przeciwnym razie zwracamy 4 (r + 1) - n . Ale ponieważ r zostało już zwiększone w ostatnim stwierdzeniu, jest to uproszczone jako:

n : r * 4 - n

Haskell , 37 bajtów

(!!)$do k<-[1,3..];[1..k]++[k+1,k..2]

Wypróbuj online!

Zero indeksowane. Generuje listę i indeksuje do niej. Dzięki Ørjan Johansen za oszczędność 2 bajtów!

Haskell , 38 bajtów

(!!)[min(k-r)r|k<-[0,4..],r<-[1..k-2]]

Wypróbuj online!

Zero indeksowane. Generuje listę i indeksuje do niej.

Haskell , 39 bajtów

n%k|n<k=1+min(k-n)n|j<-k+4=(n-k)%j
(%2)

Wypróbuj online!

Zero indeksowane. Metoda rekurencyjna.

Python , 46 bajtów

f=lambda n,k=2:-~min(n,k-n)*(n<k)or f(n-k,k+4)

Wypróbuj online!

Zero indeksowane.

Łuska , 8 bajtów

!…ṁoe1DN

1-indeksowany. Wypróbuj online!

Wyjaśnienie

!…ṁoe1DN  Implicit input (an integer).
       N  Positive integers: [1,2,3,4,...
  ṁo      Map and concatenate
      D   double: [2,4,6,8,...
    e1    then pair with 1: [1,2,1,4,1,6,1,8,...
 …        Fill gaps with ranges: [1,2,1,2,3,4,3,2,1,2,3,4,5,6,...
!         Index with input.

Perl 6 , 29 bajtów

{({|(1...$+=2...2)}...*)[$_]}

Wypróbuj online

W oparciu o 0

Rozszerzony:

{  # bare block lambda with implicit parameter ｢$_｣

  (
    # generate an outer sequence

    {           # bare block lambda

      |(        # flatten into outer sequence

        # generate an inner sequence

        1       # start at 1

        ...     # go (upward) towards:

        $       # an anonymous state variable (new one for each outer sequence)
          += 2  # increment by 2

        ...     # go (downward) towards:

        2       # stop at 2 (1 will come from the next inner sequence)

      )
    }

    ...         # keep generating the outer sequence until:
    *           # never stop

  )[ $_ ]       # index into outer sequence
}

Wewnętrzna sekwencja 1...$+=2...2tworzy

(1, 2).Seq
(1, 2, 3, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 5, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2).Seq
...

Aby był oparty na 1, dodaj 0,przed drugim {lub dodaj -1po$_

R, 64 bajty

function(n)unlist(sapply(seq(2,n,2),function(x)c(2:x-1,x:2)))[n]

Funkcja, która przyjmuje argument n. Tworzy wektor 2:nz przyrostem 2. Dla każdego z nich, wektor 1:(x-1)i x:2jest tworzony. To w sumie będzie dłuższe niż n. My unlist, aby uzyskać wektor i wziąć n-ty wpis.

Python 2 , 56 bajtów

def f(x):n=int((x/2)**.5);print 2*n-abs(2*n*n+2*n+1-x)+2

Wypróbuj online!

To jest indeksowane na 0.

-1 bajt dzięki @JustinMariner

Jak to działa

Zauważmy, że 1-indeksowana n-ta grupa ( 1, 2, ... 2n ..., 2, 1) występuje z elementów o numerze 0-indeksowanych 2(n-1)^2do 2n^2.

Aby znaleźć element w indeksie x, możemy znaleźć numer grupy, nktóry xjest w nim. Na podstawie tego obliczamy odległość od środka grupy, która xjest. (Ta odległość wynosi abs(2*n**2+2*n+2-x)).

Ponieważ jednak elementy zmniejszają się dalej od środka grupy, odejmujemy odległość od maksymalnej wartości grupy.

05AB1E , 8 bajtów

Kod:

ÅÈ€1Ÿ¦¹è

Wykorzystuje kodowanie 05AB1E . Wypróbuj online!

Wyjaśnienie:

ÅÈ           # Get all even numbers until input (0, 2, ..., input)
  €1         # Insert 1 after each element
    Ÿ        # Inclusive range (e.g. [1, 4, 1] -> [1, 2, 3, 4, 3, 2, 1])
     ¦       # Remove the first element
      ¹è     # Retrieve the element at the input index

JavaScript, 39 bajtów

f=(n,t=2)=>n>t?f(n-t,t+4):n>t/2?t-n+2:n

Galaretka , 10 , 9 bajtów

ḤŒḄṖµ€Fị@

Wypróbuj online!

Również 1 zindeksowany i kończy się dość szybko.

Jeden bajt zapisany dzięki @ErikTheOutgolfer!

Wyjaśnienie:

Hipotetycznie powiedzmy, że input ( a) to 3.

    µ€      # (Implicit) On each number in range(a):
            #
Ḥ           # Double
            #   [2, 4, 6]
            #
 ŒḄ         # Convert to a range, and Bounce
            #   [[1, 2, 1], [1, 2, 3, 4, 3, 2, 1], [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]]
            #
   Ṗ        # Pop
            #   [[1, 2], [1, 2, 3, 4, 3, 2], [1, 2, 3, 4, 5, 6, 5, 4, 3, 2]]
            #
     F      # Flatten
            #   [1, 2, 1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2]
            #
      ị@    # Grab the item[a]
            #   1
            #

MATL , 15 bajtów

li:"@EZv4L)]vG)

Na podstawie 1.

Wypróbuj online!

Przekroczono limit czasu dla największych przypadków testowych w TIO, ale kończy się z czasem na moim komputerze stacjonarnym (kompilator działający na MATLAB R2017a). Aby wyświetlić czas, który upłynął, dodaj Z`na końcu kodu.

>> matl 'li:"@EZv4L)]vG)Z`'
> 10000
84
15.8235379852476

Wyjaśnienie

Kod generuje o wiele więcej terminów niż to konieczne. W szczególności oblicza n„kawałki” sekwencji, w których każdy kawałek jest zliczaniem w górę i z powrotem do 1.

l       % Push 1
i       % Push input, n
:       % Range [1 2 ...n]
"       % For each k in that range
  @E    %   Push 2*k
  Zv    %   Symmetric range: [1 2 ... 2*k-1 2*k 2*k-1 ... 2 1]
  4L)   %   Remove last entry: [1 2 ... 2*k-1 2*k 2*k-1 ... 2]
]       % End
v       % Concatenate all stack contents into a column vector
G)      % Get n-th entry. Implicitly display

Łuska , 12 10 bajtów

!ṁ§¤+hḣṫİ0

Wypróbuj online!

1-indeksowany, działa dość szybko

Wyjaśnienie

!ṁ§¤+hḣṫİ0
 ṁ      İ0    Map the following function over the even numbers and concatenate the results together
  §   ḣṫ      Get the ranges 1-n and n-1, then... 
   ¤+h         remove the last element from both of them and concatenate them together
!             Return the element of the resulting list at the given index

Mathematica, 90 bajtów

Flatten[{1}~Join~Table[Join[Rest[p=Range@i],Reverse@Most@p],{i,2,Round[2Sqrt@#],2}]][[#]]&

Wypróbuj online!

Siatkówka , 62 bajty

.+
$*
^((^.|\2..)*)\1.
6$*1$2$2;1
(?=.+;(.+))\1(.+).*;\2.*
$.2

Wypróbuj online! Link zawiera przypadki testowe. Dane wejściowe są indeksowane 1. Pierwszy etap to konwersja dziesiętna na jednostkową. W drugim etapie najwyższa liczba kwadratowa znajduje się sdokładnie poniżej połowy n; $1jest s², podczas gdy $2jest 2s-1. Oblicza dwie wartości, po pierwsze liczbę liczb w bieżącym przebiegu w górę / w dół, która jest 4(s+1) = 4s+4 = 2$2+6, a po drugie pozycję w tym przebiegu, która n-2s² = n-(2$1+1)+1 = n-$&+1wymaga tylko 1uzupełnienia 1zastosowanego w celu wymuszenia ścisłej nierówności. Ostatni etap jest następnie liczony od tej pozycji do początku i końca przebiegu, a następnie przyjmuje niższy wynik i konwertuje go na liczbę dziesiętną.

Mathematica, 67 bajtów

(t=z=1;While[(x=3-4t+2t^2)<#,t++;z=x];If[#-z>2t-2,4t-5+z-#,#-z+1])&

Wypróbuj online!

Perl 5 , 43 + 1 (-p) = 44 bajty

$_=($n=2*int sqrt$_/2)+2-abs$n/2*$n+$n+1-$_

Wypróbuj online!

Pracowałem nad formułą do bezpośredniego obliczenia n-tego elementu. Potem zobaczyłem, że @ fireflame241 wykonał tę pracę i grałem w golfa w Perlu.

# Perl 5 , 50 + 1 (-n) = 51 bajtów

push@r,1..++$",reverse 2..++$"while@r<$_;say$r[$_]

Wypróbuj online!

Wyniki są indeksowane 0.

Haskell , 115 81 bajtów

y%x=snd(span(<x)$scanl(+)y[y+1,y+3..])!!0
g 1=1
g x|1%x>2%x=1+g(x-1)|1>0=g(x-1)-1

Wypróbuj online!

Tutaj dzieje się trochę magii. Prawdopodobnie może być krótszy, gdybym użył normalnego podejścia.

Wyjaśnienie

Najpierw zdefiniujemy %. %jest funkcją, która przyjmuje dwie zmienne xoraz y. Tworzy listę scanl(+)y[y+1,y+3..]i stwierdza, że ​​pierwszy element tej listy jest większy niż x. scanl(+)po prostu wykonuje sumy iteracyjne, aby uzyskać liczby trójkątne, które moglibyśmy zrobić scanl(+)0[1..], aby uzyskać liczby kwadratowe, które zrobilibyśmyscanl(+)0[1,3..] . Dwie listy, które będziemy konstruować, są scanl(+)2[3,5..]i scanl(+)1[2,4..]są to punkty przegięcia wzoru.

Teraz definiujemy główną funkcję, gktóra zajmuje x. Jeśli xjest jeden, to zwracamy, 1ponieważ jest to pierwsza wartość. W przeciwnym razie sprawdzamy dwa kolejne punkty przegięcia, jeśli przegięcie w dół jest większe1%x>2x zwracamy następcę, w g$x-1przeciwnym razie zwracamy poprzednika g$x-1.

Ok, ale dlaczego to działa?

Przede wszystkim „Co ze sposobem, w jaki znajdujemy wierzchołki?”. Ważne jest, aby zwrócić uwagę na odległość między kolejnymi wierzchołkami tego samego typu. Zauważysz, że różnice rosną za każdym razem o 2. Ma to sens, ponieważ podstawy trójkątów stają się za każdym razem szersze o 2. Możemy zrobić stałą różnicę listy, używając literału listy tak [2,4..]i używamyscanl(+) do przekształcania tych list w nasze listy wierzchołków, w zależności od położenia pierwszego wierzchołka i pierwszej różnicy.

Teraz, gdy mamy już sposób na znalezienie wierzchołków w górę i w dół, możemy wykorzystać te informacje do uzyskania wartości. Mówimy, że pierwszą wartością jest1 inaczej, musimy wziąć następcę lub poprzednika. Jeśli następny wierzchołek jest skierowany w górę, chcemy wziąć poprzednika, w przeciwnym razie weźmiemy następcę.

Haskell , 56 51 46 bajtów

Oto moje lepsze rozwiązanie z mniejszą matematyką i mniejszą liczbą bajtów.

d x|e<-[1..x-1]=e++map(x+1-)e
(([1..]>>=d)!!0)

Wypróbuj online!

Pyke , 14 bajtów

SF}SDtO_+)sQt@

Wypróbuj tutaj!

S              -    range(1, input)
 F}SDtO_+)     -   for i in ^:
  }            -      ^ * 2
   S           -     range(1, ^)
        +      -    ^ + v
     tO_       -     ^[1:-1:-1]
          s    -  sum(^)
           Qt@ - ^[input-1]

C # (.NET Core) , 120 bajtów

Objaśnienie: całkiem proste, pierwsza zagnieżdżona pętla wspina się na maksimum, druga schodzi z powrotem do 2. Powtórzenie dla każdej wielokrotności 2.

x=>{var a=0;for(int i=2,j=0;j<x;i+=2){for(var b=1;b<=i&j<x;b++,j++){a=b;}for(var c=i-1;c>1&j<x;c--,j++){a=c;}}return a;}

Wypróbuj online!

Rubinowy , 78 75 bajtów

Oszczędność 1 bajtu dzięki Stepowi Henowi

Zaoszczędzony 1 bajt dzięki Mr. Xcoder

->n{a=0;b=2;c=1;n.times{if a==b then c=0;b+=2;end;c=1if a<2;a+=c<1?-1:1};a}

Wypróbuj online!

Mam nadzieję, że uda mi się uzyskać wskazówki dotyczące dalszego zmniejszania liczby bajtów. Próbowałem zastosować proste podejście.

Java (OpenJDK 8) , 53 bajty

n->{int i=2;for(;n>i;i+=4)n-=i;return n>i/2?i-n+2:n;}

Wypróbuj online!

-2 bajty dzięki Nevay.

1-indeksowany.

TL; DR Podzieliliśmy sekwencję na wygodne fragmenty, znajdź kawałek n, a następnie znajdź nthpozycję w kawałku.

Tutaj możemy podzielić sekwencję jak [[1,2],[1,2,3,4,3,2],[1,2,3,4,5,6,5,4,3,2],...], co daje nam wielkość porcji 4i-2. Począwszy od i=2, odejmujemy iod nzasadniczo ruchu w górę kawałek na raz. Gdy spełnimy n<=i, wiemy, że njest to pozycja prawidłowej wartości w bieżącej porcji.

Następnie otrzymujemy wartość, porównując ndo iwielkości porcji. Punkt środkowy każdej części jest równy i/2+1; jeśli njest mniejszy, po prostu wracamy n. Jeśli njest większy, wracamy i-n+2.

Przykład

n = 16, i = 2

Is n > i? Yes, n = n - 2 = 14, i = i + 4 = 6
Is n > i? Yes, n = n - 6 = 8, i = i + 4 = 10
Is n > i? No, stop looping.
10 / 2 + 1 = 6
Is n > 6? Yes, return i - n + 2 = 8 - 6 + 2 = 4

Python 2 , 5! bajtów (120 bajtów: P)

r=range
a=[]
for i in r(2,998,2): 
	for j in r(1,i+1): a.append(j)
	for j in r(i-1,1,-1): a.append(j)
print a[input()-1]

Wypróbuj online!

Prosto, tworzy listę, a następnie przyjmuje element wejściowy

Python 3 , 184 156 bajtów

l,n,r=list,next,range
h=lambda x:l(r(1,x))+l(r(x-2,1,-1))
def g():
	x=3
	while True:yield from h(x);x+=2
def f(i):
	x=g()
	for _ in r(i-1):n(x)
	return n(x)

Wypróbuj online!

gra w golfa z generatorem Pythona do „leniwej” oceny

QBIC , 47 bajtów

g=q{p=p+1~p=:|_Xg\g=g+q~g=1or g>=r|r=r+1┘q=q*-1

Wyjaśnienie

g=q         var g is the current value of the sequence; set to 1 at the start
{           DO infinitely
p=p+1       raise the step counter (var p)
~p=:|_Xg    IF p equals the input term a (read from cmd line) THEN QUIT, printing g
\           ELSE
g=g+q       raise (or decrement) g by q (q is 1 at the start of QBIC)
~g=1        IF g is at the lower bound of a subsequence
    or g>=r OR g is at the upper bound (r start as 2 in QBIC)
|r=r+1      THEN increment r (this happens once on lower bound, and once on upper, 
            total of 2 raise per subsequence)
┘q=q*-1     and switch q from 1 to -1

Röda , 54 bajty

f n{seq 1,n|{|i|seq 1,2*i;seq 2*i-1,2}_|head n+2|tail}

Wypróbuj online!

Zadzwoń z: try f(n)

Ta funkcja szybko zwraca odpowiedź, ale potem wykonuje kilka niepotrzebnych obliczeń i ostatecznie kończy się pamięć.

Ponieważ funkcja zwraca rzeczywistą odpowiedź wkrótce po jej wywołaniu (wyraźnie poniżej minuty), myślę, że ta odpowiedź jest poprawna.

(W Röda funkcje mogą zwracać wartości, zanim wyjdą z powodu równoległości).

C # (.NET Core) , 99 95 86 bajtów

n=>{int i=1,t=2,d=0;for(;n>1;){i+=1-2*d;if(i==t){d++;t+=2;}if(i==1)d--;n--;}return i;}

Wypróbuj online!

Funkcja Lambda, która przyjmuje i zwraca liczbę całkowitą. Pojedyncza pętla, która obsługuje zliczanie w górę i w dół.

PHP, 65 + 1 bajtów

for($x=$d=$z=1;--$argn;)$d=($x+=$d)>1?$x>$z?-1:$d:!!$z+=2;echo$x;

Uruchom jako potok z -Rlub wypróbuj go online (lub odkomentuj jedną z pozostałych wersji).

Port rekursywnego JavaScript tsh zajmuje 66 bajtów:

function f($n,$t=2){return$t<2*$n?$t<$n?f($n-$t,$t+4):$t-$n+2:$n;}

Port rozwiązania Arnaulda zajmuje 62 + 1:

$n=$argn;echo($n-=($r=(~-$n/2)**.5|0)*$r*2)<++$r*2?$n:$r*4-$n;

Golfowy port Javy Xanderhall ma jak najkrótszy kod (55 + 1 bajtów):

for($n=$argn;$n+2>$i+=4;)$n-=$i-2;echo$n*2>$i?$i-$n:$n;

Pyth ,  19  18 bajtów

-yhKs@/Q2 2a*yKhKt

Wypróbuj tutaj!